Calculabilité

lingi1123  2017-2018  Louvain-la-Neuve

Calculabilité
5 crédits
30.0 h + 30.0 h
Q2
Enseignants
Deville Yves;
Langue
d'enseignement
Français
Préalables
Au sein du programme SINF1BA : LSINF1101
Au sein du programme FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401

Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.
Thèmes abordés
  • Théorie de la calculabilité : problèmes et algorithmes, fonctions calculables et non calculables, réduction, classes de problèmes indécidables (théorème de Rice) , théorème du point fixe, thèse de Church-Turing,
  • Principaux modèles de calculabilité : machine de Turing, fonctions récursives, lambda-calcul, automates,
  • Théorie de la complexité : classes de complexité, NP-complétude, théorème de Cook, résolution de problèmes NP-complets.
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

1

Eu égard au référentiel AA du programme « Bachelier ingénieur civil », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

  • AA1.1, AA1.2
  • AA2.4

Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

  • S1.I3, S1.G1
  • S2.2

Les étudiants ayant suivi avec fruit ce cours seront capables de

  • reconnaître, expliquer et identifier les limites du traitement de l'information par un ordinateur;
  • expliquer et exploiter à bon escient les principaux modèles de calculabilité en explicitant  leurs fondements, leurs différences et leurs similitudes;
  • reconnaître, identifier et appréhender les problèmes non calculables ainsi que les problèmes intrinsèquement complexes.

Les étudiants auront développé des compétences méthodologiques et opérationnelles.  En particulier, ils auront développé leur capacité à

  • avoir un regard critique sur les performances et la capacité des systèmes informatiques
 

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
Contenu
  • Introduction
  • Concepts : demonstration et raisonnement, ensembes, diagonalisation de Cantor
  • Calculabilité: résultats fondamentaux
  • Modèles de calculabilité
  • Analyse de la thèse de Church-Turing
  • Introduction à la complexité algorithmique
  • Classes de complexité
Méthodes d'enseignement
  • cours magistraux
  • exercices encadré par un assistant
Modes d'évaluation
des acquis des étudiants
  • Examen écrit (Septembre, examen oral)
Autres infos
Préalables:
  • Algorithmique et structures de données (p.e. SINF1121)
Ressources
en ligne
http://icampus.uclouvain.be/claroline/course/index.php?cid=INGI1123
Bibliographie
Transparents en ligne
Livres de référence
  • O. Ridoux, G. Lesventes.  Calculateurs, calculs, calculabilité. Dunod  Collection Sciences Sup, 224 pages, 2008.
  • P. Wolper Introduction à la calculabilité 2nd Edition, Dunod, 2001.
  • Sipser M. Introduction to the Theory of Computation PWS Publishing Company, 1997
Faculté ou entité
en charge
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Master [120] : ingénieur civil en mathématiques appliquées
MAP2M
5
Bachelier en sciences informatiques
SINF1BA
5
LSINF1101 ET LSINF1102 ET LSINF1103 ET LSINF1250
Mineure en sciences de l'ingénieur : informatique
LSINF100I
5
Mineure en sciences informatiques
LINFO100I
5
LSINF1101
Approfondissement en sciences mathématiques
LMATH100P
5
Approfondissement en sciences mathématiques
TMATH100P
5