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