Algorithmique avancée

Bloc 5 du DIU « Enseignement de l’informatique au lycée »

Cette page regroupe des documents pour le Bloc 5 « Algorithmique avancée » du diplôme inter-universitaire « Enseignement de l’informatique au lycée », proposé par l’Université de Montpellier pour le compte de l’académie de Montpellier. Les stagiaires inscrits sont invités à consulter également la page du DIU sur Moodle.

Cours

Poly de cours : couvre environ le programme du Bloc 5

Slides de cours :

1. Algorithmes classiques sur les arbres binaires et les graphes
2. Programmation dynamique
3. Recherche textuelle (de naïf à Boyer-Moore)
4. Calculabilité et complexité
5. Compléments (aperçu d’un algorithme d’intelligence artificielle et d’un algorithme probabiliste)

TD/TP, DM

• TD1 : Programmation dynamique
• TD2 : Algorithmes classiques
• TD3 : Recherche textuelle [chr18.tar.gz]
• TD4 : Calculabilité et complexité
• DM : un peu des quatre TD

Bibliographie commentée

Les ouvrages suivants couvrent ce qui est présenté dans le poly, et permettent surtout d’aller (beaucoup) plus loin.

Parties 1 et 2 du poly

• Th. Cormen, Ch. Leiserson, R. Rivest, C. Stein. Introduction à l’algorithmique, Dunod, 2004 (traduit de l’américain).

La fameuse bible d’algorithmique. Ce n’est pas l’ouvrage que je préfère, mais il faut reconnaître que son exhaustivité est impressionnante.

• J. Erickson. Algorithms, auto-publié, 2018.

Mon bouquin préféré d’algorithmique. Très complet, avec de nombreux exercices. Disponible en ligne.

• S. Dasgupta, Ch. Papadimitriou, U. Vazirani. Algorithms, McGraw-Hill, 2006.

Super bouquin très concis, efficace (l’anti-thèse du « Cormen »). Disponible très facilement en ligne.

• D. Beauquier, J. Berstel, Ph. Chrétienne. Éléments d’algorithmique, Masson, 1992.

Ouvrage épuisé mais disponible en ligne.

Partie 3 du poly

• E. Asarin. Calculabilité, support de cours et de TD, 2003.

Mon introduction préférée à la calculabilité ! En 44 pages, l’essentiel est présenté. En ligne.

• S. Perifel. Complexité algorithmique, Ellipses, 2014.

Très bon bouquin sur la théorie de la complexité, avec une approche assez scolaire. Disponible en ligne.

• B. Barak. Introduction to Theoretical Computer Science, en cours d’écriture.

Ce bouquin ambitieux, toujours en cours d’écriture (mais qui compte déjà 600 pages), explore de manière assez complète la théorie du calcul, de la calculabilité historique à la complexité la plus moderne. Beaucoup de références à d’autres très bons ouvrages anglophones. En ligne.

Dernière modification : 7 mars 2023