Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires

Azar y Autómatas
Segundo Cuatrimestre 2022






Profesora : Verónica Becher
Carga horaria total: 40 hs
Puntaje: 2 puntos para Licenciatura en Ciencias de la Computación; 2 puntos doctorado en Ciencias de la Computación .
Correlativas: Algoritmos III
Día: Miércoles de 10 a 13hs
Fecha de inicio: Miércoles 31 de Agosto 2022
Fecha de fin: Miércoles 23 Noviembre 2022
Lugar: Cero más Infinito Aula 1114


Objetivo
Estudiar el concepto de aleatoriedad y relacionarlo con la teoría de autómatas, la teoría de la computabilidad. Estos temas no están cubiertos en las materias obligatorias de la carrera en Ciencias de la Computación.

Resumen
A principios de 1900 Émile Borel dio una definición matemática de azar para los números reales (y para las secuencias infinitas). A partir de esta vemos al azar como equiprobabilidad de todas las posibilidades e impredicibilidad. ¿ Impredecibilidad para qué habilidades? Los distintos modelos de cómputo, tales como las máquinas de Turing --con y sin oráculos--, los autómatas de pila y los autómatas finitos, tienen distintas capacidades predictivas y, por lo tanto, dan origen a distintas formas del azar.

Programa
  1. La noción más elemental de azar: normalidad. Definiciones equivalentes de normalidad. Ejemplos de secuencias normales mediante combinatoria de palabras (Champernowne, de Bruijn, etc). Normalidad en una base y en multiples bases.
  2. Normalidad y autómatas finitos. La secuencias normales son exactamente las incompresibles mediante autómatas finitos Hay secuencias normales compresibles mediante autómatas de pila no-deterministicos Selección de subsecuencias mediante autómatas finitos preserva normalidad
  3. La noción más pura de azar: aleatoriedad algorítmica. Complejidad de Kolmogorov. Definiciones equivalentes de aleatoriedad algoritmica. Teorema: La secuencias algorítmicamente aleatorias son exactaemente las incompresibles mediante Máquinas de Turing.
  4. Aleatoriedad y máquinas de Turing. Ejemplos de secuencias aleatorias (definibles pero no-exhibibles). Aleatoriedad algorítmica implica normalidad, e implica no computabilidad.
  5. Aleatoriedad junto con otras propiedades, tales como nivel en la jerarquía aritmética, aproximaciones Diofánticas, representación por fracciones continuas, velocidad de convergencia a aleatoriedad.
Diapositivas
  1. Clase 1 Introducción a los contenidos de la materia.
  2. Clase 2 Definición de normalidad. Equivalencia entre tres formulaciones equivalentes.
  3. Clase 3 Lema de Piatetski-Schapiro (también conocido como Hot Spot lemma). Tres construcciones de palabras normales: Champernowne, de Bruijn infinitas, y una palabra autosimilar.
  4. Clase 4 Construcción de números absolutamente normales. Definición de normalidad como d.u. módulo 1.
  5. Clase 5 Construcción eficiente de números absolutamente normales (algoritmo polinomial.
  6. Clase 6 Las secuencias normales son exactamente las secuencias incompresibles mediante autómatas finitos.
  7. Clase 7 Selección mediante autómatas finitos. Independencia.
  8. Clase 8 Aleatoriedad pura (respecto de máquinas de Turing). Complejidad de Chaitin-Kolmogorov.
  9. Clase 9 Aleatoriedad de Martin-Löf. Distribución uniforme. Un test lindo
  10. Clase 10 Baterías de tests de aleatoriedad para secuencias finitas
Bibliografía

V. Becher and O. Carton, Chapter "Normal numbers and Computer Science" En "Sequences, Groups, and Number Theory", Valérie Berthéand Michel Rigó editors. Trends in Mathematics Series, Birkhauser/Springer, 2018. .pdf

Y. Bugeaud. Distribution Modulo One and Diophantine Approximation. Number 193 in Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 2012. .pdf

H. Niederreiter and A. Winterhof Applied Number Theory
Springer (2015). .pdf

Kuipers, L., Niederreiter, H.: Uniform distribution of sequences. Dover (2006). .pdf

US National Institute of Standards and Technology (NIST), Special Publication 800-22rev1a, April 2010, A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications, that describes the test suite. link

NIST Statistical Test Suite. July 9, 2014, link

R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010.

A. Nies, Computability and Randomness, Oxford University Press, 2009.

Recursos
US National Institute of Standards and Technology (NIST) link

Random.org link

--> Ejercicios
ejercicios.tex ejercicios.pdf