Bases d’algorithmique (2011–2012)
Xavier Caruso &
Lionel Fourquaux
La page du cours 2012–2013 est
ici.
Liste des cours
- Recherche dichotomique, complexité, tri par sélection, tri par insertion,
tri par fusion (LF, 8 septembre 2011)
— illustration
- Tri rapide, sélection rapide, arbres binaires de recherche, arbres
rouge-noir (LF, 15 septembre 2011)
- Arbres rouge-noir (suite), représentation des graphes, parcours en largeur,
parcours en profondeur (LF, 22 septembre 2011)
- Tri topologique, composantes fortement connexes,
recherche du plus court chemin, maximisation de flot
(XC, 29 septembre 2011)
- Représentation des nombres entiers, changement de base, exponentiation rapide,
virgule flottante (LF, 6 octobre 2011)
- Virgule flottante, approximation des fonctions usuelles (LF, 20 octobre 2011)
- Interpolation polynomiale, FFT, multiplication rapide
(XC, 7 novembre 2011)
- Multiplication rapide, division multiprécision, méthode de Newton
(LF, 10 novembre 2011)
- Arithmétique sur les polynômes : division euclidienne,
algorithme d’Euclide, Euclide étendu, lemme chinois (XC, 17 novembre 2011)
- 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)
- 1er décembre 2011 (XC)
- 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
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.
Cours des années précédentes