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 (P.-A. Fouque et A. Miné) |
TP de programmation
Mardi 16h-18h, salle T (P.-A. Fouque et A. Miné) |
|---|---|---|
| 2 octobre 2006
Algorithmes: conception et évaluation cours de base: terminaison, complexité, stratégies de programmation, cours avancé: bin packing, allocation dynamique de mémoire. |
3 octobre 2006 [PAF]
TD Algorithmes: conception et évaluation Fibonacci, Huffman, recouvrement de sommets, TSP. [sujet] |
|
| 9 octobre 2006
Introduction à la programmation impérative principes ; bases du langage C |
10 octobre 2006 [AM]
Introduction à la programmation en langage C. Édition, compilation, débugguage. [slides] [sujet] | |
| Première partie : algorithmique des structures de données | ||
| 16 octobre 2006
Tri et hachage cours de base: exemples de tris, hachage, collisions, hachage ouvert, cours avancé: tri Shell. |
17 octobre 2006 [PAF]
TD Tri et hachage Manipulation d'ensembles. Minimum, médiane, tri optimum. [sujet] |
17 octobre 2006 [AM]
Entrées / sorties. Fonctions. [sujet] |
| 23 octobre 2006
Recherche de motifs cours de base: Rabin-Karp, Knuth-Morris-Pratt, cours avancé: algorithmes de bio-informatique. |
24 octobre 2006 [AM]
TD Recherche de motifs Boyer-Moore, Aho-Corasick. [sujet] |
24 octobre 2006 [AM]
Allocation dynamique. Calculatrice à pile. Le préprocesseur et les macros. [sujet] |
| 30 octobre 2006
Arbres cours de base: arbres de recherche, exemples, cours avancé: tas fusionnables (tas binomiaux, tas de Fibonacci). |
31 octobre 2006 [PAF]
TD Arbres Frontière, B-Arbres, rotations AVL. [sujet] |
31 octobre 2006 [AM]
Tableaux et arithmétique des pointeurs. [sujet] |
| 6 novembre 2006
Graphes cours de base: Fermeture transitive, composantes connexes, plus courts chemins, cours avancé: valeurs propres et graphe d'expansion. |
7 novembre 2006 [PAF]
TD Graphes graphe bipartite, circuits eulériens, composantes biconnexes, arborescences. [sujet] |
7 novembre 2006 [AM]
make, configure, RCS, CVS, etc. [sujet] |
| 13 novembre 2006
Flots cours de base: Ford-Fulkerson, Edmonds-Karp, cours avancé: Flots unitaires, Dinic, couplages maximaux. |
14 novembre 2006 [PAF]
TD Flots Hall, connectivité, survie. [sujet] |
Projet de programmation
[sujet] |
| Seconde partie : algorithmique numérique | ||
| 20 novembre 2006
Entiers cours de base: multiplication, exponentiation, cours avancé: tests de primalité. |
21 novembre 2006 [PAF]
TD Entiers chaînes d'addition-soustraction, fractions continues, racines carrées, génération de premier, reconstruction de rationnel. [sujet] |
|
| 27 novembre 2006
Transformation de Fourier rapide cours de base: FFT, complexité, cours avancé: multiplication rapide. |
28 novembre 2006 [PAF]
TD Transformation de Fourier rapide Flottants. Multiplication d'entiers. Division flottante. [sujet] |
|
| 4 décembre 2006
[Examen : algorithmique des structures de données] | 5 décembre 2006
Rien cette semaine |
|
| 11 décembre 2006
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. |
12 décembre 2006 [PAF]
TD Algèbre linéaire e [sujet] |
|
| 18 décembre 2006
Programmation linéaire cours de base: simplexe, complexité, cours avancé: méthode de l'ellipsoïde. |
19 décembre 20066 [AM]
TD Programmation linéaire Algorithme du Simplexe. [sujet] |
|
| 8 janvier 2007
Factorisation des polynômes cours de base: polynômes à coefficients entiers, pgcd, polynômes binaires, cours avancé: algorithme de Berlekamp, Cantor-Zassenhaus. |
9 janvier 2007 [AM]
TD Factorisation des polynômes [sujet] |
|
| 15 janvier 2007
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 |
16 janvier 2007 [AM]
TD Systèmes d'équations polynomiales Séparation de zéros, polynômes de Cauchy. [sujet] |
|
| 22 ou 29 janvier 2007
[Examen : algorithmique numérique] |
||