Aller au sommaire principal

ULB - Université libre de Bruxelles

 

AIDE | QUITTER

   

Année académique 2017-2018
24/05/2019
Image transparente
Dernière modification : le 19/12/2014 par CARDINAL, Jean

Langue/Language


Computability and complexity
INFO - F408

I. Informations générales
Intitulé de l'unité d'enseignement * Computability and complexity
Langue d'enseignement * Enseigné en anglais
Niveau du cadre de certification * Niveau 7 (2e cycle-MA/MS/MA60)
Discipline * Informatique
Titulaire(s) * [y inclus le coordonnateur] Jean CARDINAL (coordonnateur), Jean-François RASKIN
II. Place de l'enseignement
Unité(s) d'enseignement co-requise(s) *
Unité(s) d'enseignement pré-requise(s) *
Connaissances et compétences pré-requises *
Programme(s) d'études comprenant l'unité d'enseignement - M-INFOS - Master en sciences informatiques (5 crédits, obligatoire)
III. Objectifs et méthodologies
Contribution de l'unité d'enseignement au profil d'enseignement *
Objectifs de l'unité d'enseignement (et/ou acquis d'apprentissages spécifiques) *

Le cours vise à familiariser les étudiants avec certains concepts fondamentaux de l'informatique, à savoir les théories de la décidabilité et la complexité.

A l'issue du cours, les étudiants devront être à même de définir rigoureusement ces notions (ainsi que l'outillage mathématique nécessaire pour arriver à ces définitions: machine de Turing, notion de réduction, etc), de les illustrer par des cas concrets, d'en expliquer la portée, et d'expliquer leur mise en pratique. Par exemple, on attendra des étudiants qu'ils puissent comprendre et expliquer une preuve de complexité qui n'a pas été vue au cours, mais on ne demandera pas aux étudiants de trouver une preuve qui n'aurait pas été étudiée.

Contenu de l'unité d'enseignement *

Récursivité. Ensembles récursivement énumérables. Récursivité relative. Degrés d'indécidabilité. Théorèmes de Rice et de Rice-Shapiro. Mesures de complexité. Etude de nombreux problèmes NP-complets.

Méthodes d'enseignement et activités d'apprentissages *

Cours ex cathedra, complétés par des exercices faits en classe.

Support(s) de cours indispensable(s) * Non
Autres supports de cours

L'ouvrage de Sipser est la référence principale.

 

Références, bibliographie et lectures recommandées *

M. Sipser, Introduction to the theory of computation, PWS Publisher, 053494728X

 

IV. Evaluation
Méthode(s) d'évaluation *

Examen oral avec préparation écrite portant sur la théorie et les exercices.

Construction de la note (en ce compris, la pondération des notes partielles) *
Langue d'évaluation *

Français ou Anglais

V. Organisation pratique
Institution organisatrice * ULB
Faculté gestionnaire * Sciences
Quadrimestre * Premier quadrimestre (NRE : 18358)
Horaire * Premier quadrimestre
Volume horaire
VI. Coordination pédagogique
Contact *

Jean Cardinal 

Lieu d’enseignement *

Plaine

VII. Autres informations relatives à l’unité d’enseignement
Remarques

Retour aux détails du cursus
Image transparente
Passer directement au début de la page
Version: 8.1.1.17