Descriptif
INF563 — Introduction à la Théorie de l'Information
Responsable : Thomas Debris-Alazard (thomas.debris@inria.fr)
Objectifs :
La théorie de l'information consiste à trouver les limites fondamentales de la compression d'un signal, du stockage des données ou de la communication des informations de manière fiable sur un canal bruyant par exemple. Il s'avère que toutes ces limites peuvent être exprimées en termes d'une seule quantité, qui est l'entropie. Les fondements de ce domaine ont été posé par Shannon qui a quantifié de manière très élégantes ces limites.
Nous aborderons pendant ce cours ses résultats principaux et nous donnerons également une réponse moderne à ce type d'enjeu qui fournissent des schémas très efficaces pour compresser ou protéger les données contre les bruits. Ajourd'hui cette théorie a aussi trouvé des applications dans de nombreux autres secteurs tels que la cryptographie, la biologie, l'informatique quantique, la linguistique, la détection de plagiat ou la reconnaissance des formes. Nous aborderons certains de ces auters applications pendant le cours.
Lecture suggérée : T. Cover, J. Thomas, "Elements of Information Theory". Wiley Series in Telecommunications, 1991.
Langue : Le support de cours est en anglais. Les cours peuvent être donnés en frnaçais ou en anglais, à la convenance des étudiants.
Evaluation : Le cours se valide par un examen oral.
Prérequis :
-
Des connaissances de base en statistiques ou en théorie des probabilités est recommandée mais pas obligatoire.
-
En informatique : des connaissance en algorithmique et en programmation comme INF411 ou INF421.
Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- MScT-Cybersecurity
- Non Diplomant
- Titre d’Ingénieur diplômé de l’École polytechnique
- M1 MPRI - Fondements de l'Informatique
Parcours de rattachement
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Prérequis :
- Des connaissances de base en statistiques ou en théorie des probabilités est recommandée mais pas obligatoire.
- En informatique : des connaissance en algorithmique et en programmation comme INF411 ou INF421.
Pour les étudiants du diplôme M1 MPRI - Fondements de l'Informatique
Prérequis :
- Des connaissances de base en statistiques ou en théorie des probabilités est recommandée mais pas obligatoire.
- En informatique : des connaissance en algorithmique et en programmation comme INF411 ou INF421.
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme M1 MPRI - Fondements de l'Informatique
Vos modalités d'acquisition :
Evaluation : Le cours se valide par un examen oral (de 30min) et écrit (de 3h).
Rattrapâge : Un potentiel rattrapage consistera en 30 mlinutes de discussions autour du cours ainsi que des exercices traités lors des séances de TD
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Vos modalités d'acquisition :
Evaluation : Le cours se valide par un examen oral (de 30min) et écrit (de 3h).
Rattrapâge : Un potentiel rattrapage consistera en 30 mlinutes de discussions autour du cours ainsi que des exercices traités lors des séances de TD
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme MScT-Cybersecurity
Vos modalités d'acquisition :
Evaluation : Le cours se valide par un examen oral (de 30min) et écrit (de 3h).
Rattrapâge : Un potentiel rattrapage consistera en 30 mlinutes de discussions autour du cours ainsi que des exercices traités lors des séances de TD
Le rattrapage est autorisé (Note de rattrapage conservée)Pour les étudiants du diplôme Programmes d'échange internationaux
Vos modalités d'acquisition :
Evaluation : Le cours se valide par un examen oral (de 30min) et écrit (de 3h).
Rattrapâge : Un potentiel rattrapage consistera en 30 mlinutes de discussions autour du cours ainsi que des exercices traités lors des séances de TD
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Non Diplomant
Vos modalités d'acquisition :
Evaluation : Le cours se valide par un examen oral (de 30min) et écrit (de 3h).
Rattrapâge : Un potentiel rattrapage consistera en 30 mlinutes de discussions autour du cours ainsi que des exercices traités lors des séances de TD
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
Programme détaillé
Ce cours est divisé en huit cours magistraux, huit cours d'exercices et un examen. Ces cours portent sur les principaux concepts algorithmiques et mathématiques de la théorie de l'information.
- Entropie, séquences typiques
- Source de codage sans mémoire
- Source de codage sans mémoire, codage de Huffman, codage de Shannon-Fano-Elias, codage de Shannon et codage arithmétique
- Source stationnaire, séquences typiques, propriété d'équipartition asymptotique
- Codage canal, capacité, théorème de Shannon
- Codes linéaires, codes de Hamming et de Reed-Solomon, codage concatené
- Applications de la Théorie de l'Information aux autres domaines comme la cryptographie
