Algorithmique et programmation : année 2005-2006

Le cours présente les bases sur les structures de données et les principes de conception des algorithmes ainsi qu'un certain nombre de développements plus avancés. On attend des étudiants un minimum de connaissances algorithmiques. Chaque séance est organisée en deux parties, la première consacrée aux connaissances de base et la seconde à un résultat plus avancé (ou exceptionnellement plusieurs).

Les TD proposent la mise en œuvre des connaissances abordées en cours. Les TP ont un rythme indépendant et sont une initiation à la programmation en C.

Planning prévisionnel

Cours d'algorithmique
Lundi 15h15-18h15, salle Henri Cartan
(Jacques Stern)
TD d'algorithmique
Mardi 8h45-10h45, salle U ou V
(L. Granboulan et P.-A. Fouque)
TP de programmation
Mardi 16h-18h, salle T
(L. Granboulan et P.-A. Fouque)
3 octobre 2005
Algorithmes: conception et évaluation
cours de base: terminaison, complexité, stratégies de programmation,
cours avancé: bin packing, allocation dynamique de mémoire.
4 octobre 2005 [LG]
TD Algorithmes: conception et évaluation
Fibonacci, Huffman, recouvrement de sommets, TSP.
[sujet]
10 octobre 2005
Entiers
cours de base: multiplication, exponentiation,
cours avancé: tests de primalité.
11 octobre 2005 [LG]
TD Entiers
chaînes d'addition-soustraction, fractions continues, racines carrées, génération de premier, reconstruction de rationnel.
[sujet]
17 octobre 2005
Transformation de Fourier rapide
cours de base: FFT, complexité,
cours avancé: multiplication rapide.
18 octobre 2005 [LG]
TD Transformation de Fourier rapide
Flottants. Multiplication d'entiers. Division flottante.
[sujet]
24 octobre 2005
Tri et hachage
cours de base: exemples de tris, hachage, collisions, hachage ouvert,
cours avancé: tri Shell.
25 octobre 2005 [LG]
TD Tri et hachage
Manipulation d'ensembles. Minimum, médiane, tri optimum.
[sujet]
25 octobre 2005 [LG]
Introduction à la programmation en langage C. Édition, compilation, débugguage.
[slides] [sujet]
31 octobre 2005
Pont accordé par l'ENS
1er novembre 2005
Jour férié
7 novembre 2005
Recherche de motifs
cours de base: Rabin-Karp, Knuth-Morris-Pratt,
cours avancé: algorithmes de bio-informatique.
8 novembre 2005 [PAF]
TD Recherche de motifs
Boyer-Moore, Aho-Corasick.
[sujet]
8 novembre 2005 [PAF]
Entrées / sorties. Fonctions.
[sujet]
14 novembre 2005
Arbres
cours de base: arbres de recherche, exemples,
cours avancé: tas fusionnables (tas binomiaux, tas de Fibonacci).
15 novembre 2005 [LG]
TD Arbres
Frontière, B-Arbres, rotations AVL.
[sujet]
15 novembre 2005 [PAF]
Allocation dynamique. Calculatrice à pile. Le préprocesseur et les macros.
[sujet]
21 novembre 2005
Graphes
cours de base: Fermeture transitive, composantes connexes, plus courts chemins,
cours avancé: valeurs propres et graphe d'expansion.
22 novembre 2005 [PAF]
TD Graphes
graphe bipartite, circuits eulériens, composantes biconnexes, arborescences.
[sujet]
22 novembre 2005 [LG]
Tableaux et arithmétique des pointeurs.
[sujet]
28 novembre 2005
Flots
cours de base: Ford-Fulkerson, Edmonds-Karp,
cours avancé: Flots unitaires, Dinic, couplages maximaux.
29 novembre 2005 [PAF]
TD Flots
Hall, connectivité, survie.
[sujet]
[corrige]
29 novembre 2005 [LG]
make, configure, RCS, CVS, etc.
[sujet]
5 décembre 2005
[Partiel]
6 décembre 2005
Rien cette semaine
Projet de programmation
[sujet]
12 décembre 2005
Algèbre linéaire et géométrie des nombres
cours de base: décomposition LUP, moindres carrés,
cours avancé: réseaux à coordonnées entières; algorithme LLL.
13 décembre 2005 [PAF]
TD Algèbre linéaire et géométrie des nombres
Wiedemann.
9 janvier 2006
Programmation linéaire
cours de base: simplexe, complexité,
cours avancé: méthode de l'ellipsoïde.
10 janvier 2006 [PAF]
TD Programmation linéaire
plus court chemin, flot maximal, sac à dos, en nombre entiers.
16 janvier 2006
Factorisation des polynômes
cours de base: polynômes à coefficients entiers, pgcd, polynômes binaires,
cours avancé: algorithme de Berlekamp, Cantor-Zassenhaus.
17 janvier 2006 [LG]
TD Systèmes d'équations polynomiales
Séparation de zéros, polynômes de Cauchy.
[sujet]
23 janvier 2006
Systèmes d'équations polynomiales
cours de base: Ordres sur les monômes, bases standard (de Gröbner), algorithme de Buchberger,
cours avancé: théorème de Mayr et Meyer
24 janvier 2006 [PAF]
TD Factorisation des polynômes
Hensel, Mignotte, LLL.
30 janvier 2006
[Examen]