Calculabilité et complexité

La version que vous consultez n'est pas définitive. Cette fiche d’activité peut encore faire l'objet de modifications. La version finale sera disponible le 1er juin.

5.00 crédits

30.0 h + 30.0 h

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

Thèmes abordés

Définition et modélisation de problèmes au moyen de la théorie des langages

Automates à états finis : définitions, opérations,
Grammaires : définition, expressivité, hiérarchie de Chomsky, ...

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

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
Ensembles énumérables
Calculabilité: résultats fondamentaux
Modèles de calculabilité
Logique des propositions
Introduction à la complexité algorithmique
Classes de complexité

Méthodes d'enseignement

Ce cours peut être donné selon différentes modalités présentielles et distancielles. Ceux-ci pourront notamment contenir des cours magistraux, des lectures, des préparations, des séances d'exercices ainsi que du travail individuel ou en groupe.

Modes d'évaluation
des acquis des étudiants

Différents modes d'évaluations pourront être organisés : évaluation continue, travaux notés, participation, examen. L'examen sera écrit, mais en cas de doute de l'enseignant sur la note à attribuer à un étudiant, celui-ci pourra être interrogé complémentairement en oral. En fonction du nombre d'étudiants, l'examen de septembre pourrait être 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

Approfondissement en sciences mathématiques

APPMATH

Filière en Informatique

FILINFO

Bachelier en sciences mathématiques

MATH1BA

Bachelier en sciences informatiques

SINF1BA

Mineure Polytechnique

MINPOLY

Master [120] en enseignement section 4 : mathématiques

MATH2M4

Mineure en enseignement des mathémathiques

APPENSMAT