ALGO1 : Introduction à l'algorithmique

Licence 3 d'informatique (parcours recherche) et magistère de Mathématiques de Rennes - ENS Rennes - Année 2023/2024

Intervenants

Cours : François Schwarzentruber
Travaux dirigés : Kilian Barrère et Theo Losekoot
Poly du cours

Plan du cours

Séance 1 : Problème des mariages stables

Cours introductif. Invariant. Variant. Problème des mariages stables. Algorithme de haut niveau. Types abstraits et structures de données.

Séance 2 : Transformation de Fourier rapide

Transformée de Fourier. Démonstration avec du son. Démonstration avec un tracé. Diviser pour régner. Circuit.

Séance 3 : Table de hachage

Table de hachage par chaînage. Hypothèse de hachage uniforme. Hachage universel. Hachage parfait. Table de hachage Table de hachage

Séance 4 : Flots

Réseau de flots. Graphe résiduel. Algorithme de Ford-Fulkerson. Théorème de dualité max flow/min cut. Flots

Séance 5 : Réduction vers les flots

matching, clustering d'images, et MAPF (flotte de robots anonymes).

Séance 6 : Programmation linéaire réelle

Programmation linéaire réelle dans P (admis). Programme canonique. Programme équationnel. Tableau. Solution basique. Variables dans la base et hors base. Algorithme du simplexe.

Séance 7 : Terminaison

Terminaison avec règle de Bland. Prétraitement pour obtenir un tableau avec solution basique.

Séance 8 : Matroïdes et gloutons

Algorithme de Kruskal. Définition des matroïdes. Enoncé de la correspondance entre glouton et matroïdes.

Séance 9 : Apprentissage supervisé

généralité et k plus proches voisins, kd-trees

Séance 10 : Apprentissage supervisé (suite)

arbre de décision, algorithme de backpropagation dans un réseau de neurones

Séance 11 : P et NP

Problème de recherche. Classe NP. Certificat. Vérificateur. Algorithme non déterministe.

Séance 12 : NP-difficulté

Réductions en temps polynomial. NP-difficulté. Théorème de Cook. 3-coloration est NP-complet. Catalogue de réductions

Backtracking pour couverture exacte

Rappel sur le backtracking. Liens dansants.

Examens des années précédentes

Références

Introduction à l’algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod. (une référence, couvre beaucoup de choses, un peu lourd et quelques erreurs)
Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. (couvre l'essentiel, une approche intéressante et concise)
Algorithms, R. Sedgewick, Addison-Wesley.
Éléments d’algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson. (merci aux auteurs de donner le livre sur Internet)
Types de données et algorithmes, C. Froidevaux, M.-C. Gaudel, M. Soria, McGraw-Hill-InterEditions. (intéressant pour les structures de données)
Algorithmics, The Spirit of Computing. David Harel. (une façon originale de présenter le paysage des algorithmes : "les limites", "relâcher les règles (parallélisme, proba)", "algorithme dans la création de logiciels")
Algorithm design, Jon Kleinberg et Eva Tardos. (ouvrage riche en bons exemples) http://www.aw-bc.com/info/kleinberg/index.html