-
Partager cette page
Theory of information coding computing and complexity
Titulaire(s) du cours
Nicolas CERF (Coordonnateur) et Jérémie ROLANDCrédits ECTS
5
Langue(s) d'enseignement
anglais
Contenu du cours
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
Objectifs (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
Pré-requis et Co-requis
Cours ayant celui-ci comme co-requis
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)
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)
Support(s) de cours
- Podcast
- Université virtuelle
Autres renseignements
Contacts
- Nicolas CERF (Nicolas.Cerf@ulb.be)
- Jérémie ROLAND (Jeremie.Roland@ulb.be)
Campus
Solbosch
Evaluation
Méthode(s) d'évaluation
- Examen oral
Examen oral
Examen oral à cahier ouvert.
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.
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%), arrondie au demi-entier le plus proche.
En cas de non-acquisition des crédits lors d'une session d'examen, toute note partielle (pour l'une des deux parties du cours) supérieure ou égale à 10/20 sera automatiquement reportée à la session suivante. Les notes strictement inférieures à 10/20 ne seront en aucun cas reportées.
Langue(s) d'évaluation
- anglais
- (éventuellement français )