Complexité et Résolution de Problèmes

Algorithmique et structures de données 1 et 2

L’étude de la complexité des problèmes permet de savoir si un problème peut être résolu par un algorithme et combien de ressources (en termes de temps et d’espace) faudra-t-il pour résoudre ce problème par un algorithme.

La résolution des problèmes peut être effectuée selon différentes méthodes. Certaines stratégies vont résoudre un problème plus efficacement que d’autres. L’objectif de ce module serait donc de mettre le point sur plusieurs aspects :

– Acquérir les notions de complexités algorithmiques.

– Comprendre les différentes notions permettant de classer les problèmes.

– Reconnaitre les problèmes qui ne peuvent pas être résolus.et ceux pour lesquels il est difficile de concevoir une solution efficace.

– Introduire la démarche de résolution et de construction de solution.

– Présenter plusieurs méthodes pour la résolution des problèmes.

Ces notions seront présentées à travers des problèmes provenant de différents domaines de l’informatique.

Chapitre 1 : Complexité des algorithmes

1. Introduction
2. Notion de Complexité des algorithmes
3. Notations de landau
4. Types d’analyse (pire cas, cas moyen),
5. Equations de récurrence et techniques de résolution

Chapitre 2 : Complexité des problèmes

1. Introduction
2. Classes P et NP
3. Réductions polynomiales
4. NP-Complétude

Chapitre 3 : L’Intelligence Artificielle pour la résolution des problèmes

1. Introduction
2. Démarche de représentation et résolution de problèmes

Chapitre 4 : Méthodes de résolution dans des espaces d’états

1. Stratégies de recherche aveugles
   Recherche en largeur
   Recherche en profondeur

Recherche en profondeur limitée

etc.

2. Stratégies de recherche heuristiques
Notions d’heuristiques
Algorithmes gloutons

Chapitre 5 : Méthodes de résolution par décomposition de problème

1. Représentation par arbre ET/OU
2. Stratégies de résolution de problèmes décomposables

Consultez les ressources disponibles concernant ce module sur le moteur de recherche de la bibliothèque, ou accédez directement au cours de vos enseignants via la plateforme de téléenseignement de l’école « e-learn ».