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