Complexité algorithmique (CA) - KAIN7M04

Objectif(s)

1) Savoir modéliser un problème réel comme un problème de graphes (application à des problèmes de transports, d'ordonnancement, de jeux, d'affectation...)
2) Savoir résoudre un problème de graphes avec des algorithmes classiques (dont on maîtrisera la complexité) et justifier de l'optimalité de solution proposée.
3) Savoir raisonner sur des structures discrètes, en particulier la rédaction de démonstration, la justification propre d'un algorithme et surtout la récurrence.
4) Savoir calculer la complexité d'un algorithme élaboré (récursif, ou boucles à longueur variable, ou utilisant une structure de données avancée comme le Union-Find)
4) Savoir identifier les problèmes NP-complets, prouver qu'ils sont dans NP et conduire proprement une réduction polynomiale

Contenu(s)

0) Rappels sur les graphes : vocabulaire de base et représentation des graphes
1) Rappels de complexité algorithmique : notation O(...), complexité d'un algorithme récursif, complexité d'une double-boucle imbriquée à longueur variable, complexité linéaire en le nombre d'arêtes sur un graphe
2) Notion de connexité, de parcours, de graphes eulériens
3) Arbres non-enracinés et arbres couvrants de poids minimum; algorithme de Kruskal avec Union-Find implémentée sous forme de forêt : quel gain sur la complexité ?
4) Coloration et quelques classes particulières : graphes bipartis, graphes planaires (théorème des 4 couleurs), graphes d'intervalles
5) Couplage et transversaux; théorème de König dans le cas biparti
6) Flots et coupes; algorithme de Ford-Fulkerson; théorème flot max / coupe min
7) Classes de complexité P et NP
- vocabulaire de base de la complexité : instance; problème de décision versus d'optimisation ; complexité d'un problème versus complexité d'un algorithme ; brève mention de la machine de Turing pour la définition d'algorithme
- réduction de NP-difficulté; théorème de Cook-Levin
- problèmes NP-complets, principalement issus de la théorie des graphes ou de la satisfiabilité booléenne (SAT) : Clique, Stable, Vertex Cover, Coloration, Voyageur de Commerce, Cycle Hamiltonien, 3-SAT et quelques-unes de ses variantes, Subset Sum, Sac-à-Dos

Algorithmique de base ; notions sur les graphes; techniques d'analyses d'algorithme : complexité temporelle, invariants

Contrôle des connaissances

50% contrôle continu
50% examen terminal :

• 1 épreuve écrite - 2h
• Document autorisé : une feuille A4 recto-verso manuscrite autorisée
• En cas de tiers-temps : 1/3 de temps supplémentaire
  En cas de non validation d’une UE, le jury peut autoriser l’élève ingénieur à passer des épreuves complémentaires pour la valider.

Calendrier

Le cours est programmé dans ces filières :

• Formations d'ingénieur - INFO - Semestre 7

Informations complémentaires

Code de l'enseignement : KAIN7M04
Langue(s) d'enseignement :

Vous pouvez retrouver ce cours dans la liste de tous les cours.