Formation à l’enseignement de la spécialité ISN

On présente des algorithmes « avancés », au sens où ils vont au delà des algorithmes de base sur les structures de données et les ordres, pour résoudre des problèmes précis. C’est l’occasion de revisiter les concepts et méthodes de l’algorithmique : complexité, preuves de correction (notamment avec la notion d’invariant), choix des types abstraits de données pour la spécification du problème et de l’algorithme, etc.

On pourra par exemple aborder :

• la recherche de plus court chemin dans un graphe avec le parcours de Dijkstra ;
• le calcul de l’enveloppe convexe avec l’algorithme de Graham ;
• le tracé d’un segment dans le plan discret avec la méthode de Bresenham.