Cours MPI

Attention

Ce section est en cours de construction. Merci de me signaler les erreurs éventuelles.

Résumés des chapitres

Les résumés numériques suivants vous permettent de revoir le cours. Ils ne sont en aucun cas exhaustifs et ne dispensent certainement pas d'une écoute et d'une prise de notes actives en cours.

1. Induction et récurrence
2. Langages réguliers, expressions régulières
3. Parcours de graphes et algorithme A
   • Parcours : illustrations
4. Automates finis
5. Arbres couvrants de poids minimal
6. Théorème de Kleene
7. Logique propositionnelle, logique des prédicats, déduction naturelle
8. Apprentissage supervisé
   • Algorithme ID3 : le choixpeau magique
   • Arbres k-dimensionnels : illustrations
9. Décidabilité et complexité
10. Grammaires algébriques
11. Composantes fortement connexes
12. Programmation concurrente
13. Apprentissage non supervisé
14. Algorithmes probabilistes
15. Couplages dans les graphes
    • Chemin augmentants, graphe résiduel : exemple
16. Jeux d'accessibilité

Notions de MP2I

Je mets également ici des documents liés concernant les notions de MP2I. Il est toujours utile de les réviser car elles peuvent évidemment tomber aux concours.

• Bases de données et SQL
• Complexité amortie
• Programmation dynamique (en Python)

Compléments (hors-programme)

Les documents suivants permettent, à celles et ceux qui le veulent, d'aller un peu plus loin sur les notions vues en cours. Leur lecture est vivement conseillée à celles et ceux qui préparent les concours les plus sélectifs.

• Théorème de Myhill-Nerode et applications
• Langages réguliers et reconnaissance par monoïde
• Lemme d'Arden et applications
• Algorithme de McNaughton et Yamada
• Machines de Turing
• Algorithme CYK
• Analyseurs syntaxiques LL(1)