Calculabilité, logique et complexité

5 crédits

30.0 h + 30.0 h

Cette unité d'enseignement n'est pas dispensée en 2018-2019

Langue
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.

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

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

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;
convertir des affirmations du langage courant en expressions logiques en utilisant la syntaxe et la sémantique de la logique des propositions ou des prédicats
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 : 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

Modes d'évaluation
des acquis des étudiants

Examen écrit (Septembre, examen oral)

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

Bachelier en sciences informatiques

SINF1BA

LEPL1402 ET LINFO1114

Bachelier en sciences de l'ingénieur, orientation ingénieur civil

FSA1BA

LEPL1402