L'option informatique poursuit le travail de première année en s'appuyant toujours sur le langage OCaml. On y traite des sujets classiques d'algorithmique, arbres binaires de recherche, tas, graphes, on introduit la logique propositionnelle ainsi que les langages rationnels et les automates.
Les devoirs proposés sont chargeables depuis cette page. Ils sont le plus souvent corrigés.
Les sujets de travaux pratiques, avec leurs corrigés, sont décrits ici.
Retour
Chapitres du cours
- Un court chapitre présente les fonctionnelles (map, iter, fold).
- Le premier (vrai) chapitre définit la structure d'arbres binaires de recherche. En plus des exercices, il propose deux problèmes, le Plus Proche Ancêtre Commun et les B-arbres.
- Le deuxième chapitre définit la structure de Tas et l'applique pour définir une file de priorité et le tri par tas. Il contient aussi deux problèmes sur les tableaux fonctionnels et la structure d'arbre gauchiste.
- Le troisième chapitre expose l'initiation à la logique présente dans le programme. À la fin sont proposés sont proposés, sous forme de problèmes, deux solveurs de satisfiabilité, l'un par brute force, l'autre utilisant le connecteur IfThenElse. Ils sont suivis de 5 puzzles logiques.
- Le chapitre 4 introduit les définitions et définit les algorithmes de parcours des graphes (non valués).
- Dans le chapitre 5, nous généralisons les graphes en donnant un poids aux arêtes. Le programme ne contient que la recherche des chemins de poids minimal, d'autres algorithmes seront vus en TP.
- Le chapitre 6 débute le bloc de cours concernant les langages rationnels. On y définit les langages rationnels, leur caractérisation par des expressions régulières et on finit par les langages locaux et linéaires en vue du théorème de Berry-Sathi. Les exercices contiennent, entre autres, l'étude des mots de Lyndon ainsi que celle des langages dérivés avec la finitude des dérivés des langages rationnels.
- Le chapitre 7 présente les automates. On y voit que les langages reconnus par un automates sont les mêmes pour toutes les définitions possibles puis on prouver que tout langage rationnel est reconnaissable par un automate.