• Liste des parcours dans lesquels apparaît l'EC

• Mention / Parcours / Parcours type	ECTS	Points
  Informatique / Informatique / IA	3	30

• Équipe pédagogique

• • Responsables

  • MIGNOT Pascal (Responsable)

    Département : Mathématiques (UFR SEN)

• Volume horaire

• Nature	CM	TD	Total
  Durée	20h	10h	30h

• Modalités de contrôle des connaissances (MCC)

• Epreuves	Nature	DST	EET	Total
  	Durée	2h	2h
  Cas général	1ère session	100		100%
  	2nd session		100	100%
  Dispense contrôle continu	1ère session	100		100%
  	2nd session		100	100%

• Modalités de contrôle des connaissances (MCC)

• Cas général

• Nature	Durée	1ère session	2ème session
  	DST	2h	100%	0%
  EET	2h	0%	100%

• Dispense contrôle continu

• Nature	Durée	1ère session	2ème session
  	DST	2h	100%	0%
  EET	2h	0%	100%

• Objectifs

• ? Modèles théoriques de traitement informatique? Notions de décidabilité et de calculabilité? Notions de complexité temporelle et spatiale? Notions de complétude et problèmes NP et NL complets? Problème NP-complets

• Compétences spécifiques visées

• ? Comprendre les limites théoriques de l'informatique? Distinguer les problèmes que l?on peut résoudre en informatique et, parmi eux, ceux que l?on sait pouvoir résoudre efficacement ou pas

• Compétences générales visées

• ? Informatique théorique

• Connaissances requises

• ? Langages et compilation

• Programme

• ? Introduction, définitions et motivations de l?étude sur la décidabilité? Machine de Turing? Décidabilité, Indécidabilité? Introduction, définitions et motivations de la théorie de la complexité? Calculabilité? Complexité temporelle : classes P, NP et NP-complétude? Complexité spatiale : classes L, NL, et NL-complétude? Présentation de problèmes NP-complets, et introduction à leurs méthodes de résolution