Résolution de problèmes

Cette UE couvre les principales méthodes de résolution de problèmes difficiles en Intelligence Artificielle et en Recherche Opérationnelle. Le cours abordera ainsi les algorithmes de résolution exacte, mais également les algorithmes approchés (recherche heuristique dans les espaces d'états, les méthodes de recherche locale, les méta-heuristiques, etc.), et notamment ceux avec garantie de performance. Les étudiants auront aussi l'occasion de mettre en pratique les méthodes algorithmiques étudiées en développant et en comparant certains algorithmes de résolution pour des problèmes concrets.

On abordera la résolution de problèmes dans les graphes d'états et en particulier l'algorithme A*. On abordera ensuite la résolution de problèmes de satisfaction de contraintes, puis la résolution de problèmes par méta-heuristiques (méthodes évolutionniste, recherche locale...). Ces méthodes de résolution seront illustrées en travaux dirigées et appliquées à la résolution de problèmes divers tels que la planification d'itinéraires, la résolution de jeux ou de puzzles, …

On abordera également les algorithmes gloutons, les algorithmes basés sur la méthode du primal-dual, la méthode de l’arrondi, la randomisation, le recherche locale etc… Ces techniques algorithmiques seront illustrées en travaux dirigés et appliquées à la résolution de problèmes tels que les problèmes de flots, de « clustering », de localisation de services, d’ordonnancement, les réseaux de Hopfield, ...

Documents

• Algorithmique, Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Dunod, 2010.
• Algorithm Design, Jon Kleinberg, Eva Tards, Addison Wesley, 2006.
• Artificial Intelligence: A Modern Approach, Stuart Russel and Peter Norvig, Prentice Hall series, 2003.
• Combinatorial Optimization: Algorithms and Complexity, Christos Papadimitriou and Kenneth Steiglitz, Prentice-Hall, 1982.
• Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, Bernhard Korte and Jens Vygen, Springer, Berlin Heidelberg New York, 2006.
• Constraint Processing, Rina Dechter, 2003.
• Problem-solving methods in artificial intelligence, Nils J. Nilsson, McGraw-Hill, 1971
• Résolution de problèmes par l'homme et la machine, Jean-Louis Laurière, 2ème édition, 1987, Eyrolles.