Bases d’algorithmique (2011–2012)

Liste des cours

1. Recherche dichotomique, complexité, tri par sélection, tri par insertion, tri par fusion (LF, 8 septembre 2011) — illustration
2. Tri rapide, sélection rapide, arbres binaires de recherche, arbres rouge-noir (LF, 15 septembre 2011)
3. Arbres rouge-noir (suite), représentation des graphes, parcours en largeur, parcours en profondeur (LF, 22 septembre 2011)
4. Tri topologique, composantes fortement connexes, recherche du plus court chemin, maximisation de flot (XC, 29 septembre 2011)
5. Représentation des nombres entiers, changement de base, exponentiation rapide, virgule flottante (LF, 6 octobre 2011)
6. Virgule flottante, approximation des fonctions usuelles (LF, 20 octobre 2011)
7. Interpolation polynomiale, FFT, multiplication rapide (XC, 7 novembre 2011)
8. Multiplication rapide, division multiprécision, méthode de Newton (LF, 10 novembre 2011)
9. Arithmétique sur les polynômes : division euclidienne, algorithme d’Euclide, Euclide étendu, lemme chinois (XC, 17 novembre 2011)
10. Arithmétique sur ℤ : division euclidienne, pgcd, Euclide et Euclide étendu, théorème de Bézout, congruences, anneaux ℤ/nℤ, lemme chinois, fonction indicatrice d’Euler, multiplication de Montgomery (XC, 24 novembre 2011)
11. 1^er décembre 2011 (XC)
12. lundi 5 décembre 2011, 14h (XC)

Bibliographie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein, Introduction to Algorithms
• Donald E. Knuth, The Art of Computer Programming
• Henri Cohen, A Course in Computational Algebraic Number Theory
• Jean-Pierre Demailly, Analyse numérique et équations différentielles
• David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, ACM Computing Surveys, 23(1), mars 1991, doi:10.1145/103162.103163
• David Monniaux, The pitfalls of verifying floating-point computations, TOPLAS, 30(3):12, mai 2008, doi:10.1145/1353445.1353446
• Peter L. Montgomery, Modular Multiplication Without Trial Division, Mathematics of Computation, Vol. 44, No. 170, avril 1985, pages 519–521, doi:10.1090/S0025-5718-1985-0777282-X
• Christoph Burnikel & Joachim Ziegler, Fast Recursive Division, Max-Planck-Institut für Informatik Research Report MPI-I-98-1-022

Travaux dirigés et travaux pratiques

Les TDs et TPs sont dirigés par Sandrine Caruso.

Voici un corrigé pour l’exercice 1 de la feuille de TD n°2.

Contrôle continu

Il n’y a pas d’examen terminal pour ce cours. La note attribuée est la note de contrôle continu.

• Interrogation 1 (17 octobre 2011)
• Interrogation 2 (24 novembre 2011)
• Interrogation 3 (28 novembre 2011)
• Interrogation 4 : jeudi 1^er décembre 2011

Cours des années précédentes

• 2010–2011 : cours de Marie-Françoise Roy et Antoine Chambert-Loir (page de la seconde partie du cours)
• 2009–2010 : sujets d’examen première session, seconde session