Algorithmique et complexité

Conception et analyse d’algorithmes efficaces.

• Algorithmes randomisés.
• Complexité des algorithmes, classes P et NP.
• Algorithmes d’approximation.

Prérequis

Bases de l’algorithmique et des probabilités.

Acquis d’apprentissage

• Méthode de construction d’algorithmes: Diviser pour Régner, Algorithmes Gloutons, Programmation Dynamique.
• Algorithmes probabilistes: type Monte-Carlo, Las Vegas, temps attendu.
• Classes P et NP : définitions, conséquences algorithmiques de P = NP, NP-complétude, réduction polynomiale.
• Algorithmes d’approximation: rapport d’approximation, qualité d’un algorithme d’approximation.

Compétences visées

• Concevoir des algorithmes et évaluer leur complexité.
• Modéliser des problèmes complexes.
• Proposer des solutions informatiques à des problèmes complexes.