Algorithmique et complexité

L2 Informatique, Université de Montpellier, 2018-2020

Le cours et les sujets de TD et TP sont en grande partie repris du cours HLIN508 de l’excellent Stéphane Bessy.

Cours

Les diapositives et notes de cours suivantes contiennent probablement des typos et des erreurs plus graves… À utiliser à vos risques et périls (et n’hésitez pas à me signaler les problèmes !).

Notes de cours : le contenu du cours, en très compact !
Diapositives :

Vidéos de cours

Dans le cadre du confinement dû à l’épidémie de Covid-19, j’ai enregistré des vidéos très basiques pour accompagner les diapositives. Elles commencent à la moitié du chapitre 4.

Diviser pour régner
- Multiplication d’entiers par l’algorithme de Karatsuba
- Calcul de rang (médiane, …)
Programmation dynamique

Sujets de TD

Les exercices qui suivent sont exceptionnellement originaux, c’est-à-dire qu’ils ne sont originaux qu’exceptionnellement (même cette phrase n’est pas de moi !).

2019-2020 +-
- TD1 – Introduction et rappels : Notations de Landau, analyse d'algorithmes
- TD2 – Structures de données arborescentes : Arbres binaires, arbres binaires de recherche, tas
- TD3 – Algorithmes gloutons : Exemples (choix d'activités, sac-à-dos fractionnaire, Set-cover, ...)
- TD4 – Diviser pour régner : Master theorem, exemples (sur des tableaux, algo. de Strassen, ...)
- TD5 – Programmation dynamique : Exemples (coefficients binomiaux, sac-à-dos, ...)
2018-2019 +-
- TD1 – Introduction et rappels : Notations de Landau, analyse d'algorithmes
- TD2 – Structures de données arborescentes : Arbres binaires, arbres binaires de recherche, tas
- TD3 – Algorithmes gloutons : Exemples (choix d'activités, sac-à-dos fractionnaire, Set-cover, ...)
- TD4 – Diviser pour régner : Master theorem, exemples (sur des tableaux, algo. de Strassen, ...)
- TD5 – Programmation dynamique : Exemples (coefficients binomiaux, sac-à-dos, ...)

Sujets de TP

2019-2020 +-
- TP1 – Arbres binaires de recherche : Opérations de base sur les ABR [TP1.tar.gz]
- TP2 – Tas : Opérations de base sur les tas et tri par tas [TP2.tar.gz]
- TP3 – Algorithmes gloutons : Set Cover dans le plan [TP3.tar.gz]
- TP4 – Diviser pour régner : Tri fusion, calcul de rang, tri rapide [TP4.tar.gz]
- TP5 – Programmation dynamique 1 : Distance d'édition (inclus : identification de l'origine du Covid-19 !) [TP5.tar.gz]
- TP6 – Programmation dynamique 2 : Voyageur de commerce [TP6.tar.gz]
2018-2019 +-
- TP1 – Arbres binaires de recherche : Opérations de base sur les ABR [TP1.tar.gz]
- TP2 – Tas : Opérations de base sur les tas, tri par tas et files de priorité [TP2.tar.gz]
- TP3 – Algorithmes gloutons : Choix optimal de cours, Set Cover [TP3.tar.gz]
- TP4 – Diviser pour régner : Tri fusion, calcul de rang, algorithme de Karatsuba en bonus [TP4.tar.gz]
- TP5 – Programmation dynamique : Distance d'édition, voyageur de commerce [TP5.tar.gz]

Bibliographie

J. Erickson. Algorithms. Self-published, 2019.
Mon ouvrage préféré d’algorithmique. Consulter ces autres notes de cours, passionnantes également ! Quelques unes de mes illustrations sont issues ou inspirées de cet ouvrage.
Disponible gratuitement en ligne.
S. Dasgupta, C.H. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill Higher Education, 2006.
Mon autre ouvrage préféré d’algorithmique ! Concis et efficace.
Disponible à la BIU
T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 3rd ed., 2009.
La bible de l’algorithmique, disponible en traduction française. Même si je n’adore pas le style de cet ouvrage, il faut bien reconnaître qu’il y a toute l’algorithmique classique dedans, et bien plus !
Disponible à la BIU, en français ou en anglais.

Dernière modification : 2 janvier 2023