ENS, année scolaire 2011-2012
Algorithmique et Programmation

Enseignant Principal:
Jacques Stern (stern AT di.ens.fr, Lun 14:00-15:00, S5)

Chargés de TD:

Cours Lundi 15:15-18:15, Salle U ou V (ancien immeuble rateau, passage rouge)
TDs Mercredi 08:45-10:45, Info 4 (NIR)

Annonces
Résumé du cours
Planning des cours
Projet de Programmation
Cours Avancé (ce sont des notes de cours téléchargeables)
Planning des TDs
Partiels des années précédentes
Autres Notes de Cours

Annonces

Examens:
  1. 5 Décembre 2011 : Examen Algorithmique des Structures de données
  2. 23 Jan. 2012 : Examen Algorithmique numérique
Projets:
  1. 31 Oct. 2011 : Choix des Projet de Programmation
  2. 9 Décembre 2011 : Envoi des Projets de Programmation
  3. 14 Décembre. 2011 : Soutenances des Projet de Programmation [Planning des soutenances. Les soutenances ont lieu en salle S16, Ancien immeuble rataud, niveau -1]

Résumé du cours


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 présente un résultat plus avancé (ou exceptionnellement plusieurs). Détails.

Projets de programmation

Vous aurez le choix entre plusieurs sujets de programmation. Cette liste est susceptible d'évoluer jusqu'au 31 octobre à minuit. Vous devez indiquer aux chargés de TD (ou bien à td-algo@di.ens.fr) quel sujet vous choisissez le 1er novembre au plus tard.

Vous devrez implémenter l'algorithme que vous avez choisi en C. L'intérêt de la chose est que vous vous coltiniez ce langage au moins une fois dans votre vie, vu que c'est un des plus (sinon le plus) utilisé. Vous devrez également préparer une brève soutenance durant laquelle vous nous raconterez un peu le fonctionnement de l'algorithme, votre implémentation, ses performances, les problèmes que vous avez rencontrés, les idées d'améliorations que vous avez eues, etc.

Avis aux connaisseurs (et/ou aux petits malins) : l'usage du C++ est interdit. Plus précisément, l'usage d'objets (new, class...) et de la STL est interdit. Vous pouvez éventuellement utiliser les template si ça vous chante, mais il n'est pas certain que ce soit utile. Si vous voulez vraiment pouvoir déclarer des variables dans les expressions for(int i=0; ....), vous pouvez utiliser l'option -c99 de gcc.

Voici la liste des sujets, avec la liste des étudiants qui les ont choisi(s). Plusieurs personnes peuvent prendre le même sujet bien sûr.

Liste des Cours



Date Sujet
1 3 Oct Algorithmes: conception et évaluation
2 10 Oct Tri et hachage
3 17 Oct Recherche de motifs
4 24 Oct Arbres
31 Oct Pas de cours
5 7 Nov Graphes
6 14 Nov Flots
7 21 Nov Entiers
8 28 Nov Transformation de Fourier rapide
5 Déc Examen Algorithmique des Structures de données (1-6)
9 12 Déc Algébre linéaire et géométrie des nombres
10 9 Jan Programmation linéaire
11 16 Jan Factorisation des polynômes
12 23 Jan Systémes d'équations polynomiales
30 Jan Examen Algorithmique numérique (7-12)

Liste et sujets des TDs

Date Prof Sujet
1 5 Oct CB TD Conception et evaluation
2 12 Oct DV TD Tri et hachage
3 19 Oct CB TD Morphismes du monoïde libre
4 26 Oct DV TD Arbres
5 2 Nov CB TD Splay trees (et Horn-Sat)
6 9 Nov DV TD Graphes
7 16 Nov CB TD Flots
8 23 Nov DV TD Entiers
9 30 Nov CB TD Transformation de Fourier rapide
7 Déc Pas de TD - Finir les projets
14 Déc Soutenances projet
10 4 Jan DV TD Algèbre linéaire et géométrie des nombres
11 11 Jan CB TD Programmation linéaire
12 18 Jan DV TD Factorisation des polynômes
13 25 Jan CB TD Systèmes d'équations polynomiales

Autres Notes de Cours

  1. Jean Berstel
  2. Jeff Erickson (chaudement recommandé)

Partiel Années Précédentes

  1. Partiel 2006
  2. Partiel 2007
  3. Partiel 2008
  4. Partiel 2009 (lost ?)
  5. Partiel 2010
  6. Partiel 2011

Examen Années Précédentes

  1. Examen 2008
  2. Examen 2009
  3. Examen 2010
  4. Examen 2011