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.
- 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
le mode de fonctionnement de l'UE est présenté au début des enseignements
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
l'ensemble des références bibliographiques est communiqué au début des enseignements
Responsable de l'unité d'enseignement
Anca Muscholl
Enseignants
la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements