TITRE : Théorie de l'information (Information theory)
DUREE : 8 semaines (évaluation comprise)
RESPONSABLE : Andrei Romashchenko
QUALITE/CV : CR2 CNRS
RESUME/ABSTRACT :
The term "Information theory" is applied to a bunch of fairly different mathematical and engineering disciplines, including coding theory, Shannon's entropy theory, theory of algorithmic randomness, etc. In this course we study several basic ideas of mathematical theory of information: What is information? How to measure of quantity of information ? Where and how is the notion of information applied ?
The aim of the course is to see how the notions of information, entropy and randomness work is different applications. This course is much more theoretic than practical, and the students are expected to have a taste for mathematical arguments.
OBJECTIFS/OBJECTIVES :
Introduction to the mathematical framework of information theory; sketching a road map for different branches of information theory. Usage of mathematical technique from information theory in computer science problems.
CONTENU/CONTENTS :
A measure of information in a finite object: combinatorial approach.
a) Hartley's information.
b) Searching problems and information.
c) Secret sharing.
Probabilistic approach to the measure of information.
a) Shannon entropy: definition and basic properties.
b) Kraft's inequality, the Shannon-Fanno code.
c) Shannon's noiseless coding theorem.
d) Shannon's entropy and reliable cryptography.
e) Communication protocols and communication complexity.
Transmission of the information in noisy channels.
a) Channels with bounded number of errors. Simple upper and lower bounds for capacity of a channel.
b) Correcting one single error: Hamming's codes.
c) Reed-Solomon codes.
d) Shannon's noisy channel coding theorem.
Algorithmic definition of the measure of information.
a) Kolmogorov complexity of a finite word.
b) The Kolmogorov--Levin theorem about symmetry of the mutual
information.
c) Connections between Kolmogorov complexity and Shannon's entropy.
d) Random infinite sequence. Martingales and random bits in a casino:
randomness deficiency means profit.
e) Entropy in learning theory. Minimum Description Length principle.
BIBLIOGRAPHIE/BIBLIOGRAPHY :
1. M. Li and P. Vitanyi. An introduction to Kolmogorov complexity and its applications. Second Edition. Springer Verlag, 1997.
2. T. M. Cover and J. A. Thomas. Elements of information theory. Wiley, 2004.
SUPPORT de COURS :
|
|
Site Web du Cours |
Polycopié du cours |
Copie des transparents |
|
Support de cours |
|
|
|
MODE D’EVALUATION :
Quelque soit la langue du cours, c'est l'étudiant qui choisi la langue dans laquelle il sera évalué. La rédaction du sujet est dans la langue du cours (un cours en français aura un sujet en français, un cours en anglais aura un sujet en anglais).
|
|
Présentation Orale |
Ecrit en temps limtié |
Livraison sur Site Web |
|
Production Logicielle |
|
|
|
|
Rédaction d’un mémoire |
|
|
|
|
Examen |
|
X |
|
Mettre une croix dans le mode d'évaluation choisi
AUTRES INFORMATIONS :
Si nous devions illustrer ces enseignements avec des visites d’entreprises locales, quelles seraient-elles ? :
Pour les quatre parcours suivants, quel est, selon vous, l’intérêt de votre module ?
|
Sans intérêt |
Peu d’intérêt |
Beaucoup d’intérêt |
Indispensable |
|
|
SSR : Système, Sécurité et Réseaux |
|
x |
|
|
|
CID : Connaissance, Information, Décision |
|
|
x |
|
|
IAM : Informatique Ambiante et Mobile |
|
x |
|
|
|
VIM : Vision, Image et Multimédiax |
|
x |
|
|
|
|
x |
|
|
|
|
|
x |
|
|
|
|
Système d’information |
|
x |
|
|
|
Intéraction homme-machines |
|
x |
|
|
Les quatre premiers parcours correspondent à des spécialités habilitées, les quatres suivant correspondent à un affichage interne et à une possibilité de suivre cet ensemble de cours.
Y-a-t’il Club d’étudiants pour prolonger l’activité de ce module dans les activités extra-scolaires ? Si oui lequel ?
Y-a-t’il une compétition ouverte aux étudiants à laquelle prépare ce module ?