<- Archives UCL - Programme d'études ->



Calculabilité [ LINGI1123A ]


5.0 crédits ECTS  30.0 h + 30.0 h   2q 

Enseignant(s) Deville Yves ;
Langue
d'enseignement:
Français
Lieu de l'activité Louvain-la-Neuve
Ressources
en ligne

> https://www.icampus.ucl.ac.be/claroline/course/index.php?cid=INGI1123

Préalables
  • Algorithmique et structures de données avancées (p.e. SINF1121)
  • Raisonnement en mathématiques discrètes (p.e. INGI1101)
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

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

 

Modes d'évaluation
des acquis des étudiants
  • Examen écrit (Septembre, examen oral)
  • 2 évaluations formatives (qui n'interviennent pas dans la note finale) durant le quadrimestre
Méthodes d'enseignement
  • cours magistraux
  • exercices encadré par un assistant
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é
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
Cycle et année
d'étude
> Bachelier en sciences informatiques
Faculté ou entité
en charge
> INFO


<<< Page précédente