Sumários
Prefix-free Kolmogorov complexity
15 dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Motivation for prefix-free Kolmogorov complexity. Definition of prefix-free Kolmogorov complexity and its properties. Prefix-free Kolmogorov complexity and probability distributions. Three different approaches and the the Coding theorem. Application to Information theory.
Lecturer: Andre Souto.
Symmetry of Information
10 dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Considerations about mutual information a la Kolmogorov complexity. Proof that symmetry of information cannot hold up to constant terms. Statement and proof of symmetry of information with logarithmic terms. Digression to application on security.
There were no classes
3 dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
There were no classes.
Incompressibility results
1 dezembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Revision of the topics of previous letter as a motivation for proving that if x=ywz is not compressible then neither of the 3 is compressible by log terms.
Proof of C(<x,y>) <= C(x) + C(y) +O(log min{C(x),c(y)} and its refinements.
Discussion on Language compression theorem.
Statement and initial consideration about symmetry of information. Its connection to information theory.
The Kolmogorov-Solomonoff theorem of invariance
26 novembro 2015, 14:00 • Paulo Alexandre Carreira Mateus
The Kolmogorov-Solomonoff theorem of invariance. Examples of application.Upper bounds on Kolmogorov complexity. The incomputability theorem. Incompressibility theorem.