Travail de rédaction
L'évaluation du cours se fait par un examen et par un travail de
rédaction. Le rattrapage est fait par un examen oral.
L'idée de ce travail de rédaction est d'obtenir quelques pages (entre 5
et 10) qui pourraient être intégrées au support de cours. Une liste non
exhaustive de thèmes pouvant donner lieu à la rédaction d'un rapport est
donnée ci-dessous.
- 1er novembre
- Choix du sujet
- 18 décembre
- Rendu des rapports
- 6, 13 et 20 janvier
- Soutenances
- Langages rationnels
- transformations expression rationnelle en automate
- Mots de Sturm (J. Berstel)
- algorithme d'Hopcroft
(référence [chapitre 9])
- langages testables par morceaux
- équivalence entre logique monadique du second ordre et automates
- rationnels du monoïde commutatif libre
- transductions rationnelles
- théorie des codes
- théorème de Cobham
- suites automatiques
- séries N et Z-rationnelles
- motifs inévitables
- conjecture de Černý
- automates sur les mots infinis
(référence [chapitre 1])
- automates sur les mots transfinis
- déterminisation d'automates (max,plus)
- automates (max,plus) et empilements de pièces
- Langages algébriques
- forme normale de Greibach
(référence)
- le hardest langage
- automates à pile déterministes
- groupe de Hotz
- automates à plusieurs piles (P. Habermehl)
- grammaires booléennes
- Calculabilité
- machines à compteurs
- λ-calcul
- pavages et indécidabilité
- algorithmes de Markov
- équivalence MT et RAM (sans DEC)
- théorème de Rice pour les ensembles récursivement énumérable ([HU74]
pages 188-192)
- Théorème de Cardinalité (Article de M. Kummer)
- calculabilité distribuée (Article de Angluin and Co)
- Complexité
- complexité de Kolmogorov ([Sip97])
- modèle de Blum-Shub-Smale
- complexité de Valiant
- complexité de décision et de recherche (Article de
Bellare et Goldwasser)
- classes de complexité randomisées et BPP ⊆ Σ2
([Pap95] chapitre 11 et pages 429-431)
- limites de la méthode de diagonalisation ([Sip97] section 9.2 ou
[Pap95] section 14.3 ou [Rey04] annexe C)
- IP = PSPACE ([MR95] section 7.7)
- simulation d'une MT à k bandes en O(T(n)) par une MT à deux bandes en
O(T(n)/log n) ([HU74] pages 292-299 ou [Rey04] pages 134-138)
- théorème de Gap de Borodin ([HU74] section 12.6 ou [Rey04] annexe C)
- théorème d'accéleration de Blum ([HU74] section 12.6 ou [Rey04]
annexe C)
- problème sur les expressions régulières avec exponentiation en
espace au moins exponentiel ([HU74] section 13.6)
- procédure de décision pour les réels avec addition et borne
inférieure (même chose avec Presburger) ([HU74] pages 354-362)
- Zero-knowledge proofs
- hiérarchie polynomiale - Théorème de Karp,Lipton,Sipser ([Pap95]
chapitre 17)
- théorème de Ladner ([Pap95] ou référence)
Il est impératif de rédiger ce rapport en utilisant LaTeX. Pour de la
documentation et en particulier des introductions à ce traitement de textes
mathématiques, une bonne adresse est le LaTeX navigator.
Voici un exemple de fichier squelette.tex en LaTeX avec un fichier
associé squelette.bib de bibliographie
BibTeX.
- Horaires
- Règles du jeu
- L'objectif de la présentation orale est de donner envie à l'auditoire
de lire le rapport.
- La présentation orale de doit pas dépasser 20mn. Tout exposé
plus long sera interrompu.
- La forme de l'exposé est libre. Il peut être fait à la craie au
tableau, avec des transparents ou à l'aide d'un vidéo-projecteur
(cf. ci-dessous).
- Les élèves désirant utiliser le vidéo-projecteur sont priés d'envoyer
à P.-A. Fouque au moins la veille leur fichier au format Pdf.
- L'exposé est suivi de 5mn de questions
- Les exposés son publics et il est même recommandé de venir
écouter (tous) les exposés dans la mesure du possible.
Il est vivement conseillé à ceux désirant utiliser un vidéo-projecteur
de préférer LaTeX et le package beamer à tout autre
logiciel (commercial). Voici un exemple de fichier expose.tex en LaTeX avec le résultat
obtenu en Pdf.