Calculabilité, logique et complexité

lsinc1123  2020-2021  Charleroi

Calculabilité, logique et complexité
En raison de la crise du COVID-19, les informations ci-dessous sont susceptibles d’être modifiées, notamment celles qui concernent le mode d’enseignement (en présentiel, en distanciel ou sous un format comodal ou hybride).
5 crédits
30.0 h + 30.0 h
Q2

  Cette unité d'enseignement n'est pas dispensée en 2020-2021

Langue
d'enseignement
Français
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.
 
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

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

  • cours magistraux
  • exercices encadré par un assistant
Modes d'évaluation
des acquis des étudiants

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

Examen écrit en juin, oral en septembre.
Faculté ou entité
en charge
EPL


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

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Bachelier en sciences informatiques
SINC1BA
5