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
Cette unité d'enseignement n'est pas dispensée en 2019-2020
Langue
d'enseignement
d'enseignement
Français
Préalables
Ce cours suppose acquises les compétences en programmation,
algorithmique et langage de programmation visées dans le cours LEPL1402 et en mathématiques discrètes telles que vues dans les cours LINFO1114 ou LEPL1108
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.
algorithmique et langage de programmation visées dans le cours LEPL1402 et en mathématiques discrètes telles que vues dans les cours LINFO1114 ou LEPL1108
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
- Logique : logique des propositions et logique des prédicats (syntaxe, sémantique, preuve, quantificateurs, model checking, résolution)
- Modèles de calculabilité : machine de Turing
- 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 :
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 :
|
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 : démonstration et raisonnement, ensembles, 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é
' Concepts : démonstration et raisonnement, ensembles, 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
' exercices encadré par un assistant
Modes d'évaluation
des acquis des étudiants
des acquis des étudiants
Examen écrit (Septembre, examen oral)
Faculté ou entité
en charge
en charge
INFO
