INF431: Algorithmique et programmation
2011-2012
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 théorique à 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.
Plan du cours
Voici un plan prévisionnel:
-
bloc 01 (01/02/2012):
introduction à l'algorithmique:
le problème des mariages stables.
-
bloc 02 (08/02/2012):
introduction à la programmation orientée objet:
classes, interfaces, héritage, encapsulation.
-
bloc 03 (15/02/2012):
structures persistantes et récursivité:
tas binaires et files de priorité.
-
bloc 04 (29/02/2012):
diviser pour régner.
-
bloc 05 (07/03/2012):
structures modifiables:
listes, tas, et autres collections.
-
bloc 06 (14/03/2012):
graphes:
représentation et parcours.
-
bloc 07 (21/03/2012):
algorithmes gloutons (1):
plus courts chemins dans un graphe, codage de Huffman.
-
bloc 08 (28/03/2012):
algorithmes gloutons (2):
arbres couvrants minimaux.
-
bloc 09 (04/04/2012):
programmation dynamique.
-
bloc 10 (11/04/2012):
test:
spécification, test, debugging.
-
18/04/2012:
contrôle classant (1).
-
bloc 11 (02/05/2012:
preuve de programmes:
spécification, vérification.
-
bloc 12 (09/05/2012):
exploration:
non-déterminisme, rebroussement, stratégie, élagage.
-
bloc 13 (23/05/2012):
interprétation:
évaluation d'une expression arithmétique ou d'un programme.
-
bloc 14 (30/05/2012):
analyse syntaxique (1):
grammaires, analyse descendante non déterministe.
-
bloc 15 (06/06/2012):
analyse syntaxique (2):
analyse descendante déterministe, analyse tabulaire.
-
bloc 16 (13/06/2012):
concurrence (1):
threads, mémoire partagée, synchronisation.
-
bloc 17 (20/06/2012):
concurrence (2).
-
bloc 18 (27/06/2012):
concurrence (3).
-
04/07/2012:
contrôle classant (2).
Enseignants
Students who would prefer English-speaking PC and TD teachers are invited
to enroll in group 4 or 8.
Ressources pédagogiques
Les pages de suivi
Annales
Les sujets et corrigés des pales précédentes sont
disponibles ici. Toutefois, rappelons que le contenu du cours a en partie
évolué depuis.