Information Theory (2008/2009)

Learning outcomes

Course objective is to present fundamentals of information and communication theory, and in particular, encoding, compression, entropy, transmission, transduction, security, and algorithmic complexity.

1. Encoding
---------------
1.1. Introduction.
1.2. Information, information measures, and entropy.
1.3. Types of codes and main characteristics.
1.4. Information sources and optimal codes..

2. Compression
-------------------
2.1. Kraft Norm and McMillan Theorem.
2.2. Huffman, LZ, Arithmetic, Shannon-Fano, Burrow-Weeler.
2.3. First Shannon Theorem.

3. Entropy
-----------------------
3.1. Types of entropy and their relationships.
3.2. Information Distance and Mutual Information.
3.2. Stocastic and e marcoviane sources.

4. Tipicality
---------------------
4.1. Typical Sequences and AEP (Asintotic Equipartition Propety).

5. Transmission
---------------------
5.1. Trasmission Codes, channel capacity and transmission rate.
5.2. Second Shannon Theorem.
5.3. Hamming Codes.

6. Transduction
-------------------------
6.1. Continuous entropic concepts.
6.2. Sampling Theorem.
6.3. Maxwell Theorem
6.4. Third Shannon Theorem.

7. Security
------------------
7.1. Private Key Criptografy. Historical Developments and the key distribution problem.
7.2. Diffie-Hellman Protocol.
7.3. Public Key Criptografy.
7.4. Autenticazione, signature and certificate schemata.
Bennet-Brassard Protocol.

7. Complessity
------------------
8.1. Kolmogorov-Chaitin algorithmic complexity.
8.2. Random strings and elegant programs.
8.3. Chaitin Elegance Theorem.

Oral Examination