Algorithmique

Concevoir une stratégie algorithmique pour la solution d’un problème.
Passer de la description abstraite d’un algorithme à sa mise en œuvre.
Choisir les structures des données adaptées en utilisant notamment les librairies d’un langage programmation.
Analyser la correction et l’efficacité de la mise en œuvre.

Cet enseignement suppose acquis le programme Informatique pour tous des CPGE scientifiques, les cours de « Programmation » et de « Méthodes Numériques » du semestre 5 et des notions élémentaires de mathématiques.
Cet enseignement participe avec les autres cours de la spécialité en semestre 6 (« Programmation objets », « Systèmes et Réseaux ») à la constitution d’un socle de culture Informatique d’un niveau intermédiaire.

Structures de données : tas, arbres binaires de recherche, tables de hachage, graphes et graphe pondérés.
Méthodes de conception : diviser pour régner, randomisation, algorithmes glouton, programmation dynamique, premiers exemples de dualité.
Techniques d’analyse : solution de relations de récurrence élémentaires, analyse de complexité dans le pire des cas et en moyenne. Notion de complexité amortie.