Cours d'introduction à l'Informatique Théorique pour des non-informaticiens suivant le Master M2 "Modélisation des systèmes complexes". Ce cours est l'occasion de présenter les notions de calculabilité, de complexité algorithmique, ainsi que des bases en mathématiques discrètes, par exemple en théorie des graphes.
10 séances de 2h de cours + 5 séances de 2h de TD + un examen de 2h.
| Semaine | Cours | TD |
|---|---|---|
| 1 | Petit historique. Slides incomplets : odp, pdf | |
| 2 | Structures mathématiques discrètes : les ensembles, les entiers, les mots. Définitions de bases. Notion de codage (p.ex. les entiers par des mots). Notion de cardinal (dénombrable, non dénombrable, preuve que NXN est dénombrable, preuve que R n'est pas dénombrable par argument diagonal). | Petits exercices sur les entiers (p.ex. codages redondants des entiers), les mots (p.ex. transformation/réécriture de mots, ou exemples de compression), les cardinaux (p.ex. quizz dénombrable/non dénombrable). |
| 3 | Structures mathématiques discrètes : les graphes. Définitions de bases (chemins, cycles, cliques, indépendants, connexité, arbres, ...). | Petits exercices sur les graphes (sans algorithmique). |
| 4 | Premiers modèles de calculs : automates finis / transducteurs, puis machines de Turing. Définitions. Formalisation du calcul de fonction ou du cas particulier des problèmes de décision, par ces machines et via les langages. Des exemples. Notion de robustesse de ces modèles de calcul : pouvoir de reconnaissance robuste face à certaines modifications du langage (complémentaire, union, ...), face à certaines modifications de la machine (conditions d'arrêt, multiplication des rubans, ...). Animations / vidéos du fonctionnement (exemple). | Notion d'expression rationnelle pour les automates finis (mini-exemples, citer l'équivalence avec expression rationnelle = reconnaissable par automate fini, mais faire juste des petits bouts de preuve). Lemme de l'étoile pour prouver la non-reconnaissance par automate fini (preuve et exemples d'utilisation). Construire une machine de Turing pour un exemple facile. |
| 5 | Les limites du calcul : indécidabilité. Existence de langages indécidables par machine de Turing : par simple argument de cardinalité, ou en précisant des langages indécidables comme le problème de l'arrêt. Machine de Turing universelle. Thèse de Church. Début de présentation d'un autre modèle de calcul : fonctions récursives. | Quizz décidable/indécidable. Fonctions récursives amusantes : McCarthy 91. Morceaux choisis de l'équivalence entre Machines de Turing et Fonctions récursives. |
| 6 | Modèles de calcul exotiques : automates cellulaires. Définition. Exemples en 1D,2D,3D. Discussion et morceaux de preuve que les automates cellulaires ont le même pouvoir de calcul que les machines de Turing. Animations / vidéos du fonctionnement.. | |
| 7 | Complexité algorithmique. Notions de complexité algorithmique selon différentes ressources : temps, espace, communications ... Modèle RAM et pseudo-code à la C. Petits exemples concrets : recherche, tri, multiplication de matrices, puissances dans un monoide. | |
| 8 | Zoologie en complexité. Classes P et NP. Trouver vs Vérifier. Notion de NP-difficile et NP-complétude. Théorème de Cook. Tableau P vs NP, listant des problèmes classiques et leur appartenance à P ou NP-complet (déf sur les graphes introduites en cours 3). | |
| 9 | Algorithmique des graphes. Structures de données classiques (matrices d'adjacence, listes d'adjacence). Parcours de graphes (en largeur, en profondeur). Application à la connexité (non orienté). Plus court chemins depuis une source en orienté pondéré. Arbre couvrant de poids min en non-orienté pondéré. | Applications des parcours (p.ex. sortir d'un labyrinthe, calculer l'accessibilité, le diamètre ...). Plus courts chemins entre toutes les couples de sommets via la multiplication de matrices et les puissances dans un monoide. |
| 10 | Grands problèmes ouverts en informatique théorique. Donner une liste en commentant (piocher par exemple dans le document Challenges for computer science). Commenter des grandes découvertes récentes. |
Beaucoup d'interactions avec les étudiants car beaucoup de surprises, sachant que culture en informatique théorique très faible en général (par contre niveau en programmation hétérogène avec peut être des bons programmeurs ou technophiles dans le lot). Risque de prendre facilement du retard (mais pas forcément grave). En 2009, trop de temps passé sur les automates finis (trop d'efforts p.ex. pour montrer complètement l'équivalence expression rationnelle = reconnaissable par automate fini) avec pour conséquence les cours suivants très tronqués dans leur contenu. Modèle de calcul exotique présenté en 2009 : machines quantiques (mais difficile à faire passer en fin de compte car requiert des notions de quantique). Mixer slides et tableau noir aurait été l'idéal pour aller plus vite et clairement à l'essentiel, mais non réalisé finalement. Certains énoncés de TD peuvent être récupérés sur la page de Jonathan Grattage. Livres/ressources utilisées : livre de Pierre Wolper (cf biblio en dessous) et Wikipedia !