Theory of information coding computing and complexity

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: 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

Cours ayant celui-ci comme co-requis

• 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

Contacts

• Nicolas CERF (Nicolas.Cerf@ulb.be)
• Jérémie ROLAND (Jeremie.Roland@ulb.be)

Campus

Solbosch

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 )