Informatique

Le but de l'algorithmique peut être résumé en " trouver un "bon" algorithme " pour un problème donné. Cela soulève de nombreuses questions:

• Existe-t-il un algorithme pour résoudre le problème? ( calculabilité, indécidabilité)
• Le problème est-il un "classique"? (modélisation, reformulation, connaissances)
• Comment concevoir un algorithme? (algorithmes corrects par construction, paradigmes)
• L'algorithme apporte-t-il bien la réponse au problème donné? ( correction des algorithmes)
• Que dire des ressources utilisées par l'algorithme? (analyse d'algorithmes)
• L'algorithme est-il "raisonnablement" efficace? Pourrait-on faire mieux? Que dire des ressources minima nécessaires pour résoudre le problème? Peut-on espérer avoir un algorithme "rapide" exact? Le problème est-il "dur"? (complexité des problèmes)
• Que faire face à un problème dur?

L'objectif du cours est de préparer à répondre à ces questions difficiles, d'entraîner au "computational thinking", donc de développer les compétences suivantes :

• analyser un problème - modélisation, reformulation, réduction, complexité
• concevoir une solution algorithmique appropriée, exacte ou approchée, en utilisant à bon escient les structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive ou/et les méthodes heuristiques, ...
• analyser cette solution - correction, garantie, complexité

• Paradigmes classiques de conception d'algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, ...) (resp. S. Tison)
• Complexité de problèmes: classes P, NP et EXPTime; réductions polynomiales; problèmes NP-durs. (resp/ M.-E. Voge)
• Algorithmique avancée: Quelques méthodes pour résoudre de manière exacte ou approchée des problèmes NP-durs (Branch-and-Bound, algorithmes probabilistes, heuristiques, méta-heuristiques, ...) (resp. B. Derbel).
Le cours sera éventuellement complété par une séance sur éthique et algorithmes.

• maîtriser plusieurs notions de complexité des algorithmes,
• connaître des paradigmes classiques d'algorithmes et savoir les mettre en oeuvre,
• comprendre la notion de la complexité d’un problème et les principales classes de complexité,<
• concevoir des réductions polynomiales entre problèmes,
• trouver des bornes inférieures et supérieures pour la complexité des problèmes,
• mettre en oeuvre des heuristiques pour résoudre des problèmes difficiles.