Algorithmique avancée

4 ECTS, 39h d'enseignement, 2 contrôles sans document, pas de seconde session.
Ce module est commun au M1 informatique et au M1 mathématiques :

pour les M1 informatique, ce module fait partie de l'UE "Développement logiciel avancé", avec le module "Développement web serveur" (2 ECTS) et "Systèmes multiagents" (2 ECTS) ;
pour les M1 mathématiques, ce module est une UE autonome.

L'objectif de ce module est de préciser les limites de l'informatique.

Pierre Wolper est l'auteur de l'ouvrage Introduction à la calculabilité (empruntable à la BU, publié chez Dunod) sur lequel ce cours est basé.
Les transparents utilisés pour ce cours ont été rédigés par Jean-François Raskin.
Tous les documents nécessaires à la réussite de cette UE sont disponibles à partir de cette page.

Plan

Chapitre 0 - Cardinalité (1/42)

dénombrabilité, technique de la diagonale de Cantor
exemples d'ensembles infinis dénombrables et non-dénombrables

exercices cardinalité

Chapitre 1 - Machines de Turing (45/92)

définitions des MTD et MTND, exemples
1. exemple 1 (format SVG)
2. exemple 2 (format PNG) et exemple 2 (format jff pour JFLAP)
3. exemple 3 (format SVG)
langage accepté, langage décidé
la thèse de Church-Turing
extensions des MT et simulation des extensions
machines de Turing universelles :
- une MTD universelle : jff, svg
- un exemple de MTD à simuler : jff, png, son encodage avec le mot aaa en entrée

exercices MT et JFLAP

Chapitre 2 - Décidabilité et indécidabilité (138/144 - 162/166)

définitions : problème de décision, problème décidable, problème indécidable, technique de réduction (David Pichardie)
indécidabilité du problème de l'arrêt (1936), une courte preuve : version originale, version perso
les classes R et RE, R ⊆ RE
énumération des mots acceptés par une MT
optionnel : indécidabilité de la logique du premier ordre et classes décidables (Salvatore Ruggieri)
optionnel : théorème de Rice, transparent p. 167

Contrôle continu (CC), correction

Chapitre 3 - Une introduction à la théorie de la complexité (168/204/212/215/231)

rappels concernant l'analyse de la complexité des algorithmes
définition de la classe P, justification de la robustesse de P
définition des problèmes TS et HC, transformation polynomiale, HC α TS
définition NP, NP-complet et NP-dur
P ⊆ NP, statut de P = NP
preuve du théorème : si un langage de NPC est dans P alors P = NP
définition de SAT, théorème de Cook (1971), schéma de sa preuve
définition 3SAT, VC, tous deux dans NPC
optionnel :
- d'autres classes de complexité
- un programme en Prolog résolvant naïvement HC, VC et SAT (version en ligne ici)
- deux définitions équivalentes de NP
- la complexité descriptive, une définition purement logique des classes de complexité

Contrôle terminal (CT), correction

Evaluation

En contrôle continu : deux tests écrits (CC et CT) d'environ une heure chacun sans document ni appareil électronique.
Note finale = max((CC+CT)/2,CT).
Revoir tous les exercices corrigés en cours et en TD. Apprendre toutes les définitions et questions de cours listées ci-dessus.
NB : pas de seconde session.

Annales

Ressources

quelques scientifiques de renom et leurs apports à l'informatique PDF
JFLAP : Java Formal Languages and Automata Package, copie locale version 7.1 et 6
un simulateur de machines de Turing non-déterministe (François Schwarzentruber)
un autre simulateur de machines de Turing (Anthony Morphett)
pour une approche formelle, consulter par exemple : Verified Programming of Turing Machines in Coq, Forster Y., Kunze F., and Wuttke M., 2020. PDF, YouTube, GitHub

Fred Mesnard