Dans ce cours nous allons étudier des structures permettant de
modéliser et résoudre des problèmes informatiques, et apprendre à
raisonner sur ces structures.
Le cours mélange des aspects mathématiques et algorithmiques, et
vise à la fois à vous faire découvrir des structures de données
et algorithmes fondamentaux en informatique et à affûter vos
capacités de raisonnement.
Programme
Notes de cours : version en construction (29 avril).
- 17/01. Logique propositionnelle et principes de raisonnement. TP 1
- 24/01. Logique du premier ordre et ensembles. TP 2
- 31/01. Graphes, premières définitions. TD 1 [énoncé]
- 07/02. Chemins dans un graphe et connexité. TD 2 [énoncé]
- 14/02. Arbres et relations d'équivalence. TD 3 [énoncé]
- 21/02. Parcours de graphes et recherche de chemins. TP 3
- 28/02. Arbres binaires de recherche. TD 4 [énoncé]
- 07/03. Vacances.
- ??/03. Partiel.
- 21/03. Définitions par clôture et récurrence généralisée. TD 5 [énoncé corrigé]
- 28/03. Mots et termes structurés. TD 6 [énoncé corrigé]
- 04/04. Relations d'ordre et problèmes de terminaison d'algorithmes. TP 4 (noté)
- 11/04. Treillis et points fixes. TD 7 [énoncé corrigé]
- 18/04. Relâche.
- 25/04. SAT : algorithmes de résolution de contraintes. TD 8 [énoncé corrigé]
- ??/05. Révisions.
- 16/05. Examen.
Documents
Archives des examens
Organisation
Cours. Jeudi 8h30-10h00, amphi H4.
TD/TP. Jeudi 10h30-12h30.