Informatique théorique - 8INF713

Documents

Plan de cours

Exercices

Devoir 1 (solution)

Solution examen 1

Devoir 2 (solution)

Devoir 3

Planning

18 décembre

Discussion sur l'informatique quantique

11 décembre

Examen 3

Noms de A à H: Local P1-7090

Noms de I à Z: Local P1-7130

4 décembre

Classe de complexité P (cf. Sipser sections 7.1 et 7.2)

Classe de complexité NP et NP-complétude (cf. Sipser sections 7.3 à 7.5)

27 novembre

Langages décidables (cf. Sipser sections 4.1)

Langages indécidables (cf. Sipser sections 4.2)

20 novembre

Machines de Turing (cf. Sipser sections 3.1 et 3.3)

Thèse de Church-Turing

13 novembre

Examen 2

Local P1-6340

6 novembre

Lemme d'itération pour les langages algébriques (cf. Sipser section 2.3)

Langages algébriques déterministes (cf. Sipser section 2.4)

30 octobre

Automates à pile (cf. Sipser section 2.2)

Équivalence des grammaires algébriques et des automates à pile (cf. Sipser section 2.2)

23 octobre

Design de grammaires (cf. Sipser section 2.1)

Ambiguïté (cf. Sipser section 2.1)

Forme normale de Chomsky (cf. Sipser section 2.1)

16 octobre

Langages algébriques (cf. Sipser section 2.1)

9 octobre

Semaine de relâche (pas de cours)

2 octobre

Examen 1

Noms de A à H: Local P1-7090

Noms de I à Z: Local P1-7070

25 septembre

Lemme d'itération (cf. Sipser section 1.4)

18 septembre

Expressions rationnelles (cf. Sipser section 1.3)

Théorème de Kleene (cf. Sipser section 1.3)

11 septembre

Non-déterminisme (cf. Sipser section 1.2)

Propriétés de fermeture (cf. Sipser section 1.2)

4 septembre

Pas de cours (fête du travail)

28 août

Présentation du cours

Révision

Langages reconnaissables (cf. Sipser section 1.1)