Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires - Optativa 3 puntos Licenciatura, 3 puntos Doctorado

Información y Azar

Segundo Cuatrimestre 2012

Profesora Verónica Becher
Miércoles de 13 a 17hs. Aula E24, Pabellón I.

Nos dedicamos a estas preguntas
- ¿Cómo se define "azar"?
- ¿Puede la computadora generar azar?
- ¿Cómo podemos distinguir, precisamente, el azar del no-azar?
- ¿Podemos hacer distinciones sutiles entre grados de azar?
- ¿Cómo se relaciona el azar con la información?
- ¿Podemos dar ejemplos de números aleatorios?

Este segundo cuatrimestre de 2012 daré una edición especial de la materia en vistas del próximo Semestre en Computabilidad, Complejidad y Aleatoriedad que organizamos en el Departamento de Computación, de Enero a Julio de 2013. El Semestre contará con más de veinte investigadores invitados de distintas universidades el exterior. Se dictarán dos seminarios semanales y un curso de 3 puntos para Licenciatura y Doctorado en Ciencias de la Computación.

Prácticas 1,2,3 .pdf   .tex
Prácticas 4,5,6,7 .pdf   .tex

Apuntes
Las computadoras con dominio libre de prefijos computan lo mismo que las otras" (computadoras-libres-de-prefijos.pdf).
Los números reales sin sietes no son aleatorios (sin7.pdf).
Martingala para secuencias con má ceros que unos (martinceros.pdf).
Sobre martingalas (martingalas.pdf).

Programa
1. Repaso de definiciones básicas de la teoría de la computabilidad.
2. Complejidad de largo de programa. Máquinas de Turing autodelimitantes.
3. La desigualdad de Kraft. La relación entre complejidad de largo de programa y probabilidAd algorítmica.
4. La teoría de largo de programa es una medida de entropía de información.
5. ¿Qué es aleatoriedad? Definición de Chaitin.
6. El número aleatorio de Chaitin: Omega. Propiedades.
7. Definición de Definición de Martin Löf. Casi todos los números reales son aleatorios.
Equivalencia entre las definiciones de Martin Löf y Chaitin.
8. Números reales aleatorios computablemente enumerables. Omega es computablemente enumerable.
La clase de los números Omega coincide con la clase de los reales aleatorios compatiblemente enumerables.
9. Jerarquía de aleatoriedad. Otros ejemplos de números aleatorios, más aleatorios que Omega.
10. Propiedad de normalidad (Borel) par números reales. Aleatorio implica normal.
11. Caracterización de secuencias normales por incompresibilidad de autómatas finitos.
12. Ejemplos de secuencias normales: Champernowne, Secuencias de Bruijn extendidas

Bibliografía

Libros sobre Aleatoriedad
Rod Downey, Denis Hirschfeldt. Algorithmic Randomness and Complexity, Springer, 2010
Andre Nies. Computability and Randomness, Oxford University Press, 2009
Gregory Chaitin, Algorithmic Information Theory, Cambridge University Press, fourth printing 2003.
Ming Li, Paul Vitanyi, Kolmogorov Complexity and Applications, Springer-Verlag, 1997.

El trabajo que da origen a la definición matemática de computadora
Alan Turing, "On Computable numbers with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2nd Series Vol 42, pp. 230-265, 1936.

Artículo fundamental de la complejidad de largo de programa
Gregory Chaitin, "A theory of program size formally identical to information theory", Journal of the ACM 22, pp. 329-340, 1975

Libros sobre teoría clásica de funciones recursivas
Hartley Rogers Jr. Theory of Recursive Functions and Effective Computability., Cambridge MIT Press, 1967
Piergiorgio Odifreddi, Classical Recursion Theory volume I, volume II", North Holland, Amsterdam, 1992, 1999.