AIDE | QUITTER
   

Année académique 2017-2018
16/12/2017
Image transparente
Dernière modification : le 17/05/2017 par CERF, Nicolas

Langue/Language


Information, Coding, Computing and Complexity Theory
INFO - H422

I. Informations générales
Intitulé de l'unité d'enseignement * Information, Coding, Computing and Complexity Theory
Langue d'enseignement * Enseigné en anglais
Niveau du cadre de certification * Niveau 7 (2e cycle-MA/MC/MA60)
Discipline * Informatique
Titulaire(s) * [y inclus le coordonnateur] Nicolas CERF (coordonnateur), Jérémie ROLAND, Stijn VANSUMMEREN
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 * Théorie des probabilités
Programme(s) d'études comprenant l'unité d'enseignement - CEPULB - Conseil de l'Éducation Permanente de l'Université Libre de Bruxelles (5 crédits, obligatoire)
- M-IRIFS - Master en ingénieur civil en informatique, à finalité spécialisée (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) *

Objectifs: Développer une compréhension des théories de l'information, du codage, de la calculabilité et de la complexité.

A l’issue de ce cours, l'étudiant sera capable:

- de définir rigoureusement les notions étudiées (y compris les outils et modèles mathématiques connexes)
- d’illustrer ces notions au moyen d’exemples et/ou de preuves formelles
- d’expliquer l’utilité et le domaine d’application de ces notions
- de résoudre des problèmes fondamentaux de théorie de l’information comme le calcul de la capacité d’un canal et de construire certains codes source / correcteurs d’erreurs

Contenu de l'unité d'enseignement *

Théorie de l’information et du codage
- Entropies de Shannon
- équipartition asymptotique (séquences typiques)
- codage de source (p. ex. codes de Huffman)
- capacité de canal
- codage de canal et codes correcteurs d’erreurs (p. ex. codes de Hamming)


Théorie de la calculabilité
- modèles de calcul
- notions d’algorithme et de langage
- problèmes décidables, semi-décidables et indécidables
- notion de réduction entre problèmes


Théorie de la complexité
- Classes P et NP
- réduction polynomiale
- NP-complétude et heuristiques
- Notions alternatives de complexité : complexité en espace ou complexité de circuits

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

- Cours théorique (toutes les parties)
- Séances d’exercices (uniquement théorie de l’information et du codage)

Support(s) de cours indispensable(s) *
Autres supports de cours
Références, bibliographie et lectures recommandées *

T.M. Cover and J.A. Thomas, Elements of information theory, (John Wiley and Sons, New York, 2006)

M. Sipser, Introduction to the theory of computation, (Cengage Learning, 2013)

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

Examen oral

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

100% évaluation lors de l’examen final.

 

Chacune des deux parties du cours est notée sur 20.

 
Si les deux notes sont supérieures ou égales à 7/20, la note globale est la moyenne pondérée de ces deux notes (la partie "Théorie de l'information et du codage" intervient pour 60%, tandis que la partie "Théorie de la calculabilité et de la complexité" intervient pour 40%).
 
Si l'une des deux notes est inférieure à 7/20, la note globale est le minimum de ces deux notes.
 
Langue d'évaluation *

anglais

V. Organisation pratique
Institution organisatrice * ULB
Faculté gestionnaire * Ecole polytechnique Bruxelles
Quadrimestre * Deuxième quadrimestre (NRE : 40028)
Horaire * Deuxième quadrimestre
Volume horaire

- 24 cours théoriques de 2h
- 6 séances d’exercices de 2h

VI. Coordination pédagogique
Contact *

- Nicolas CERF (ncerf@ulb.ac.be)
- Jérémie ROLAND (jroland@ulb.ac.be)
- Stijn VANSUMMEREN (stijn.vansummeren@ulb.ac.be)

Lieu d’enseignement *

Solbosch

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