Colle 3 : Graphes et classes de complexité

Voici la liste des compétences et connaissances à avoir en colle ainsi que le DS 3.

Révisions sur les graphes : Tout le cours.

Arbres couvrants : Tout le cours.

Composantes fortement connexes et Kosaraju : Tout le cours.

Couplages et graphes bipartis : Tout le cours.

Plus courts chemins et A* : Tout le cours.

Décidabilité : Tout le cours.

Classes de complexité : Tout le cours.

Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).

Algorithmes d'approximation et Branch and Bound : Tout le cours.

Algorithmes probabilistes : Tout le cours.