Calculabilité et 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 : 102 heures

Objectifs et compétences

Objectifs :
Le premier objectif de cet enseignement est de montrer que tout problème n'est pas résoluble de façon algorithmique. Il existe des problèmes dits indécidables, pour lesquels aucun algorithme existe. En outre, nous montrons que toute propriété non-triviale de programmes est indécidable : étant donné un programme quelconque, il n'existe pas d'algorithme qui détermine si le programme satisfait la propriété (théorème de Rice).

Dans la seconde partie de l'UE, nous étudions des ressources d'algorithmes, tels que le temps de calcul et la mémoire. Ceci permet de classifier les problèmes selon les ressources requises par les algorithmes leur correspondant. Parmi ces problèmes décidables, nous étudions en particulier la classe des problèmes NP-complets et la question "P =? NP".

Compétences :
  • 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.
  • Savoir se remettre en question, faire preuve d'esprit critique

  • Identifier les limites de l'informatique en termes de calculabilité et de complexité
  • Connaître les principaux paradigmes de programmation et sélectionner un langage adapté à une situation donnée
  • Modéliser une situation concrète en un énoncé formel au moyen d'outils (e.g., automates, langages, grammaires, graphes)
  • Connaître et mettre en application les principaux modèles mathématiques intervenant dans les différentes disciplines connexes du domaine Sciences et Technologies mais aussi des autres domaines
  • Maîtriser les bases de la logique et organiser un raisonnement mathématique.
  • Utiliser les bibliothèques et outils logiciels usuels de son domaine de spécialisation

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

Session 1:

Contrôle continu, coefficient 0.5

Examen final (3h), coefficient 0.5

Session 2:

CC, report de la session 1, coefficient 0.5

Examen écrit (2h), coefficient 0.5

Note finale session 2: max(NoteEx2, 0.5*NoteEx2 + 0.5*NoteCC)

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