Objectifs

L'objectif du cours d'algorithmique de 3ème année de licence d'informatique est principalement d'étudier des algorithmes fondamentaux qui sont universellement utilisés aujourd'hui, que ce soit dans le secteur industriel ou dans le secteur académique. Certains sont utilisés comme briques élémentaires pour le développement d'autres algorithmes. Nous abordons la logique de Hoare pour introduire une démarche systématique et plus rigoureuse de certaines preuves de la validité des algorithmes. La complexité reste une préoccupation majeure de ce cours. Un objectif secondaire est de préparer les étudiants à la théorie de la complexité qui sera abordée en master.

On aborde les thèmes classiques de l'algorithmique à travers l'étude de quelques algorithmes fon­da­men­taux. Les algorithmes sont présentés dans un pseudo langage de programmation dont les spé­ci­fi­ca­tions sont suffisamment floues pour pouvoir utiliser des boites noires quand cela est nécessaire. L'objectif est de se concentrer sur la nature des algorithmes que l'on étudie et de ne pas se disperser sur des difficultés techniques accessoires. C'est pour la même raison qu'en aucun cas nous ne faisons de programmation en cours ou en travaux dirigés. La rigidité et les spécificités des langages de programmation ne font que compliquer la compréhension des algorithmes, la programmation reste donc cantonnée aux travaux pratiques. Nous ferons un exception quand la nature même d'un lan­ga­ge de programmation et que les structures de données qu'il propose changent la conception de l'al­go­ri­thme.

Le lecteur est invité à lire ou relire le cours d'algorithmique de 2ème année où ont été introduits la machine ram, un pseudo-langage algorithmique, les fonctions de complexité et les notations asymptotiques.

Contrôle des connaissances

Le contrôle des connaissances se fait à l'aide de :

1. deux contrôles continus d'une durée de 45 minutes au premier et deuxième tiers du cours. Il s'agit de quelques questions de cours et d'exercices élémentaires corrigés dans la foulée ;
2. une épreuve écrite terminale de 3 heures ;
3. une épreuve pratique de 3 heures.

Annales des contrôles terminaux

Chapitres du cours

Le cours est en refonte complète. Les liens absents devaient être rétablis durant l'année universitaire 2016-2017 mais j'ai eu d'autres cours à préparer, ce sera donc pour l'année 2017-2018 si aucun con­tre­temps ne m'en empêche. Merci pour votre patience…

1. ✍ Logique de Hoare
2. ⚙ Crible d'Eratosthène
3. ⚙ L'algorithme d'Euclide
4. ✍ Modèle et structures de données avancés (relations, graphes, arbres)
5. ✍ La récursivité
6. ⚙ Le problème des 8 reines
7. ⚙ Le problème du cavalier
8. ⚙ Le problème du Sudoku
9. ⚙ Tri par arbre binaire
10. ⚙ Arbres équilibrés
11. ⚙ Plus longues sous-séquences communes
12. ⚙ Arbre lexicographique
13. ✍ Fonctions et tables de hachage
14. ⚙ Sérialisation de tâches (tri topologique)
15. ⚙ Parallélisation de tâches (tri parallèle)
16. ⚙ Parcours en largeur : plus court chemin (Dijkstra)
17. ⚙ Arbre couvrant minimal (Kruskal / Prim)
18. ⚙ Composantes fortement connexes (Tarjan / Kosaraju)
19. ⚙ Compression entropique (Shannon-Fano / Huffman)
20. ⚙ Multiplication rapide (Karatsuba / Fourier)