Sumários

T22: Basic on Kolmogorov complexity

15 Dezembro 2017, 10:00 Paulo Alexandre Carreira Mateus

Basic concepts from Kolmogorov complexity.  Undecidability. The invariance theorem. Plan of the presentations to be given by the students for evaluation.


T21: PSPACE completeness

12 Dezembro 2017, 11:00 Paulo Alexandre Carreira Mateus

The set Aomega. Proof that Aomega is a PSPACE complete language. 


T20: Information Theory and Statistics

5 Dezembro 2017, 11:00 Paulo Alexandre Carreira Mateus

Method of types, law of large numbers, large deviations, and Sanov's theorem. Lecturer: Mario Figueiredo.

 

 


T19: Channel Capacity and Channel Coding

28 Novembro 2017, 11:00 Paulo Alexandre Carreira Mateus

Channel capacity for memoryless channels and its main properties. Simple examples: binary symmetric channel, noisy typewriter. The channel coding theorem (with a recent simple proof). Lecturer: Mario Figueiredo.

 


T18: Optimal Coding and Arithmetic Coding. Differential Entropy.

24 Novembro 2017, 10:00 Paulo Alexandre Carreira Mateus

Optimal coding: Huffman codes and their optimality. Shannon-Fano-Elias coding and its efficient implementation: arithmetic coding.

 Information theoretic quantities for continuous random variables: differerential entropy (marginal, conditional, and joint). Kullback-Leibler divergence, the information inequality and its corollaries. Lecturer: Mario Figueiredo.