Algorithmique et programmation : année 2008-2009

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 TPs proposent la mise en œuvre des connaissances abordées en cours en langage C et en salle machine.

Le projet de programmation aura pour but la programmation d'un algorithme plus complexe que ceux étudier dans les TPs de la première partie du cours. Sondage: Doodle et les projets. Le projet théorique aura pour but l'étude d'un article.

Planning prévisionnel

Cours d'algorithmique
Lundi 15h15-18h15, salle Amphi Galois (NIR)
(Jacques Stern)
TP d'algorithmique
Mercredi 8h45-10h45, salle Info 3
(P.-A. Fouque et D. Vergnaud)
29 septembre 2008
Algorithmes: conception et évaluation
cours de base: terminaison, complexité, stratégies de programmation,
cours avancé: bin packing, allocation dynamique de mémoire.
1 octobre 2008 [DV]
Apprentissage à la programmation en C
[sujet]
Première partie : algorithmique des structures de données
6 octobre 2008
Tri et hachage
cours de base: exemples de tris, hachage, collisions, hachage ouvert,
cours avancé: tri Shell.
8 octobre 2008 [DV]
TP Tri et hachage
[sujet]
13 octobre 2008
Recherche de motifs
cours de base: Rabin-Karp, Knuth-Morris-Pratt,
cours avancé: algorithmes de bio-informatique.
15 octobre 2008 [PAF]
TP Recherche de motifs et Arbres
[sujet]
20 octobre 2008
Arbres
cours de base: arbres de recherche, exemples,
cours avancé: tas fusionnables (tas binomiaux, tas de Fibonacci).
22 octobre 2008 [PAF]
TP Arbres
[sujet]
27 octobre 2008
Graphes
cours de base: Fermeture transitive, composantes connexes, plus courts chemins,
cours avancé: valeurs propres et graphe d'expansion.
29 octobre 2008 [PAF]
TP Graphes
[sujet]
3 novembre 2008
Flots
cours de base: Ford-Fulkerson, Edmonds-Karp,
cours avancé: Flots unitaires, Dinic, couplages maximaux.
5 novembre 2008 [DV]
TP Flots
[sujet]
Seconde partie : algorithmique numérique
17 novembre 2008
Entiers
cours de base: multiplication, exponentiation,
cours avancé: tests de primalité.
19 novembre 2008 [DV]
TD Entiers
[sujet]
24 novembre 2008
Transformation de Fourier rapide
cours de base: FFT, complexité,
cours avancé: multiplication rapide.
26 novembre 2008 [DV-PAF]
Soutenance Projet programmation
2 décembre 2008
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.
4 décembre 2008 [PAF-DV]
TP Transformation de Fourier rapide
[sujet]
8 décembre 2008
[Examen : algorithmique des structures de données]
10 décembre 2008 [PAF]
TP Algèbre linéaire
[sujet]
15 décembre 2008
Programmation linéaire
cours de base: simplexe, complexité,
cours avancé: méthode de l'ellipsoïde.
17 décembre 2008 [DV]
TP Programmation linéaire
[sujet]
5 janvier 2008
Factorisation des polynômes
cours de base: polynômes à coefficients entiers, pgcd, polynômes binaires,
cours avancé: algorithme de Berlekamp, Cantor-Zassenhaus.
7 janvier 2008 [DV]
TP Polynômes
[sujet]
12 janvier 2008
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
14 janvier 2008 [PAF]
TP Systèmes d'équations polynomiales
[sujet]
19 janvier 2008
[Examen : algorithmique numérique]
21 janvier 2008
Soutenance article
26 janvier 2008
Soutenance article
28 janvier 2008
Soutenance article