Semaine du lundi 14 octobre 2024
Tout ce qui précède est susceptible de tomber. Concernant le chapitre de graphes, seul l'algorithme A* a été traité depuis suffisamment longtemps pour être considéré comme faisant partie du programme de colles. A ce sujet, il faut :
- connaître son fonctionnement, et notamment expliquer ce qui le sépare de l'algorithme de Dijkstra (recherche de plus courte distance vers UN sommet, et non pas vers tous ; et présence d'une heuristique)
- connaître les résultats de terminaison, correction, et complexité, et les hypothèses qu'ils requièrent sur l'heuristique (terminaison toujours garantie ; correct si heuristique admissible ; complexité comme Dijkstra si heuristique monotone)
- être capable de le ré-implémenter si on dispose d'une implémentation correcte de files de priorité.
On peut cependant s'attendre à toute une panoplie d'exercices autour des graphes qui sont sans lien direct avec les algorithmes vus dans le chapitre 4 ; par exemple, des exercices qui ressortent des notions de première année autour des graphes, ou qui explorent d'autres notions après les avoir définies. Les chapitres de langages et automates sont également suffisamment vastes et permettent de fournir également des exercices intéressants pour cette semaine.
