Théorie de la complexité

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 48 heures
  • Temps de travail personnel : 132 heures

Objectifs et compétences

Objectifs :
Un cours renforcé sur la théorie de la complexité ainsi que les bases de la calculabilité. Il introduit la classe NP et les problèmes NP-complets, la classe IP et les preuves interactives, le théorème de Shamir IP=PSPACE, les fonctions à sens unique et les générateurs pseudo-aléatoires. Enfin, il aborde les problématiques classiques de décidabilité et d'indécidabilité en abordant au moins le Théorème de Rice et l'argument diagonal sur une machine de Turing.

Compétences :
  • Connaître le ou les champs professionnel(s) associé(s) à la discipline.

  • Comprendre et mettre en oeuvre l'intérêt et les principes de la démarche de recherche fondamentale et/ou appliquée
  • Construire et développer une argumentation.

  • Être capable de traduire un problème simple en langage mathématique.

  • Évaluer une solution informatique

Organisation pédagogique

- Non défini -

Contrôle des connaissances

1ère session :

Contrôle continu - coef. 1/3

Examen écrit terminal (3h) - coef. 2/3

Note 1ère session = 1/3*Contrôle continu + 2/3*Examen écrit terminal

2ème session :

Examen écrit terminal (3h) - coef. 2/3

Note 2nde session = 2/3*Examen écrit terminal session 2 + 1/3*note

max(contrôle continu de session 1; examen écrit terminal session 2)

Lectures recommandées

- Non défini -

Responsable de l'unité d'enseignement

Anca Muscholl

Enseignants

- Non défini -