Enseignant : Laurent Jouhet
Documents référencés
Pour voir les documents d’une ressource écrits par d’autres enseignants, cliquez sur son titre, ou bien sur son icône ou .
Thèmes : Complexité, Algorithmique –
Cursus : ENS-Lyon - M1 Irénée Briquel , Laurent Jouhet - algo de Markov
- PRIMES, simulation efficace par une machine de Turing universelle, machine oblivious
- Ladner, simulation efficace par une machine de Turing non déterministe universelle
- fonctions constructibles en temps, langages unaires, langages creux
- reprend le TD4 et rajoute des exercices sur la constructibilité en temps et en espace
- le jeu de GO est PSPACE-complet
- machines alternantes
- des circuits et des cailloux
- Partiel
- des circuits et des cailloux, suite
- P/poly
- Rapport "Grands Stades Euro 2016"
- problèmes P-complets et P-SEL
- pièces biaisées, BPL, RL, réductions randomisés, th de réduction des erreurs pour RP
- TD 13
- TD 14
- un correction de AM[k] = AM