INF431: Algorithmique et programmation
2013-2014
Présentation du cours
L'informatique est d'une part une discipline scientifique à part
entière, d'autre part un puissant outil, exploité par toutes les
disciplines, y compris l'informatique elle-même.
Ce cours constitue une introduction approfondie aux notions
fondamentales de l'informatique, aussi bien scientifiques que techniques.
Il s'adresse à ceux qui s'intéressent à l'informatique pour elle-même
comme à ceux qui s'y intéressent en tant qu'outil.
Ce cours enseigne d'abord l'algorithmique, c'est-à-dire la science de la
résolution systématique des problèmes et de l'organisation efficace des
données. L'accent est mis sur la conception des algorithmes et sur
l'analyse de leur efficacité. Un petit nombre de concepts et de techniques
fondamentaux, qui sont exploités dans de nombreuses situations, sont
présentés.
De plus, ce cours est conçu comme un approfondissement de la pratique de
la programmation. Le langage Java est utilisé tout au long du cours, pour
les travaux dirigés sur machine et pour un projet de programmation réalisé
en binôme. Ceci se double d'une réflexion à propos de la programmation: on
propose une introduction au test et à la preuve de programmes ainsi qu'une
introduction à la programmation concurrente.
La description officielle du cours se trouve dans le catalogue des
cours, en français
et en anglais.
Pale
Le corrigé de la pale CC2 est disponible plus
bas.
Projets
La page
des projets, avec les sujets, est en ligne.
Poly
Voici la version courante du poly
complet.
Plan du cours
- bloc 01 (29/01/2014): introduction à l'algorithmique:
le problème des mariages stables. (PC).
Transparents pour projection
et impression.
Capture vidéo
de l'amphi.
Matériel bibliographique: Mariages
Stables de Donald Knuth. L'article
original de 1962.
- bloc 02 (05/02/2014): Structures mutables:
Union-Find. (TD).
Transparents pour projection
et impression.
Capture vidéo
de l'amphi.
- bloc 03 (12/02/2014): Récursivité. (PC).
Transparents.
Capture vidéo
de l'amphi.
- bloc 04 (19/02/2014): Diviser pour régner.
Transparents.
Capture vidéo
de l'amphi.
- bloc 05 (05/03/2014): Algorithmes gloutons (Prim, Kruskal).
Transparents.
Transparents
sur quelques bibliothèques Java.
- bloc 06 (12/03/2014): Graphes : utilisations du parcours en
profondeur d'abord (DFS).
Regardez les vidéos suivantes avant l'amphi.
- bloc 07 (19/03/2014): Gloutons 2 : Huffman.
Transparents version
courte (imprimée) et version
longue (avec animations).
- bloc 08 (26/03/2014): Programmation Dynamique.
Vidéos à regarder :
Transparents
du matin (pdf).
- bloc 09 (02/04/2014) : Exploration Récursive.
Transparents
(pour animation). Le code
du solveur.
Pour aborder le sujet en douceur (exploration for dummies) :
une vidéo
(mp4, 200 Mo) presentant le problème des huit reines (code
Java).
-
bloc 10 (09/04/2014):
introduction aux algorithmes randomisés.
(PC.)
Transparents pour
projection et
impression.
Vidéo.
-
lundi 28 avril, de 9h à 11h, salle T5:
contrôle classant (1).
Le contenu des séances 1 à 9 est au programme.
-
bloc 11 (30/04/2014):
spécification et preuve de programmes.
(PC en salles info.)
Transparents pour
projection et
impression.
Code Java.
-
bloc 12 (07/05/2014):
arbres, récursivité, calcul symbolique:
interprétation d'un petit langage de programmation;
différentiation symbolique. (TD).
Transparents pour
projection et
impression.
-
bloc 13 (14/05/2014):
analyse syntaxique (1):
grammaires, analyse tabulaire.
(PC.)
Transparents pour
projection et
impression.
-
bloc 14 (21/05/2014):
analyse syntaxique (2):
analyse descendante.
(TD).
Transparents pour
projection et
impression.
Code Java pour CalculiX.
-
bloc 15 (28/05/2014):
concurrence (1):
processus et threads. (TD).
Transparents pour
projection et
impression.
-
bloc 16 (04/06/2014):
concurrence (2):
objets partagés, exclusion mutuelle, synchronisation à l'aide de verrous.
(PC).
Transparents pour
projection et
impression.
Démos Java.
-
bloc 17 (11/06/2014):
concurrence (3):
synchronisation entre producteurs et consommateurs à l'aide d'une file d'attente,
variables de condition.
(TD).
Transparents pour
projection et
impression.
Code Java.
-
bloc 18 (18/06/2014):
structure d'une interface graphique (GUI):
application de la programmation orientée objets et des threads.
(TD).
Transparents pour
projection et
impression.
Code Java.
-
mercredi 25 juin 2014 de 9h à 12h:
contrôle classant (2).
Devoirs à la maison (DM)
Voici le sujet du
DM01 à propos du problème des mariages stables.
Enseignants
- Amphis: Benjamin
Werner et François
Pottier;
- Groupes 1 et 6: Jean-Pierre
Tillich, Philippe
Chassignet (TDchef), Tie
Cheng (TDvac);
- Groupes 2 et 7: Bruno Salvy
(PC), Stéphane
Lengrand (TDchef), Ali
Assaf (TDvac);
- Groupes 3 et 8: Gilles
Schaeffer (PC), Éric
Fusy (TDchef), Quentin
Heath (TDvac);
- Groupes 4 et 9: Frédéric
Magniez (PC), Stéphane
Redon (TDchef), Antoine
Delignat-Lavaud (TDvac);
- Groupes 5 et 10: Benjamin
Doerr (PC), Karthikeyan
Bhargavan (TDchef), Nicolás
Bordenabe (TDvac);
- Responsable du projet informatique (PI): Benjamin Doerr.
Ressources pédagogiques
Les pages de suivi
Les sujets et corrigés des pales précédentes sont disponibles ici.