Calculabilité (L3 ENS Paris-Saclay)

Cours 1 : Introduction, Machines de Turing

TD 1 : Problème de l’arrêt, Fonctions calculables, Castors affairés

Énoncé (pas les mêmes numéros d’exercices)

TD2 : Ensembles récursifs/récursivement énumérables

Énoncé (pas les mêmes numéros d’exercices)

TD 3 : Argument diagonal, Réductions

Énoncé (pas les mêmes numéros d’exercices)

Course 2 : Beavers, Multi-Tapes Machines, I/O Machines, Recursive/Recursively enumerable languages

Cours 3 : Machine Universelle, Problème de l’arrêt, Théorème de Rice, Réduction

Cours 4 : Indécidabilité : Problème de correspondance de Post, Pavages

Cours 5 : Fonctions récursives/récursives primitives/récursives partielles, Hiérarchie de Grzegorczyk, Fonction d’Ackermann

Cours 6 : Complexité : Introduction

Introduction

DM1 : Virus

Calculabilité DM 1 : Virus

TD4 : Théorème de Rice, Réductions, Machines de Minsky

EX 1

TD6 : Fonctions récursives

EX 1

TD7 : Complexité : Accélération linéaire, Réductions LOGSPACE et Machines alternantes

Version PDF

TD8 : Complexité :

EX 1

TD10 : Complexité : CTL

EX 1

Cours 7 : Complexité : Classe NLOGSPACE, Théorème d’Immerman-Szelepscenyi, Langage d’un automate non déterministe

Classe NLOGSPACE = NL

Cours 8 : Complexité : SPACE Hierarchy Theorem

SPACE Hierarchy Theorem

Cours 9 : Rappels, récapitulatif

2-SAT

DM Complexité : 1_3_SAT, VECSUBSETSUM, WEIGHTEDPATH

DM de Complexité