Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 30.0 h
Q2
Enseignants
Deville Yves;
Langue
d'enseignement
d'enseignement
Français
Préalables
Au sein du programme SINF1BA : LSINF1101
Au sein du programme FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
Au sein du programme FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
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
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 :
|
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é et NP complétude
Méthodes d'enseignement
- cours magistraux
- exercices encadré par un assistant
Modes d'évaluation
des acquis des étudiants
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
en ligne
Bibliographie
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
Support de cours
- Transparents en ligne
- Syllabus collaboratif
Faculté ou entité
en charge
en charge
INFO
Programmes / formations proposant cette unité d'enseignement (UE)
Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
d'apprentissage
Master [120] : ingénieur civil en mathématiques appliquées
Master [60] en sciences informatiques
Master [120] en sciences informatiques
Approfondissement en sciences mathématiques
Mineure en sciences de l'ingénieur : informatique (accessible uniquement pour réinscription)