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.
12 Dezembro 2017, 11:00 • Paulo Alexandre Carreira Mateus
The set Aomega. Proof that Aomega is a PSPACE complete language.
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.
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.
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.