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

Azar y Autómatas
Segundo Cuatrimestre 2017






Profesora : Verónica Becher
Carga horaria total: 16 hs (son 8 clases de 2 horas)
Puntaje: 1 punto para Licenciatura en Ciencias de la Computación; doctorado en trámite.
Correlativas: Algoritmos III
Evaluación: Un examen final
Día: Viernes de 10 a 12hs
Fecha de inicio: Viernes 25 de Agosto 2017
Lugar: Aula 12 del Pabellón I


Objetivo
El curso tiene por objetivo estudiar el concepto de aleatoriedad y relacionarlo con la teoría de autómatas, la teoría de la computabilidad y los generadores pseudo-aleaotrios. 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 un ser humano, para un dispositivo mecánico, o para una computadora universal? 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. Generadores de números pseudo aleatorios. Métodos de congruencia lineal. Baterías de test de US National Institute of Standards and Technology (NIST).
  6. 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 (25 de agosto): Introducción a los contenidos de la materia.
  2. Clase 2 (1 septiembre): Definición de normalidad. Equivalencia entre tres formulaciones equivalentes.
  3. Clase 3 (8 septiembre): 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 (15 septiembre): Las secuencias normales son exactamente las secuencias incompresibles mediante autómatas finitos.
  5. Clase 5 (22 septiembre): Selección mediante autómatas finitos. Independencia.
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. Draft Julio, 2017. .pdf

Y. Bugeaud. Distribution Modulo One and Diophantine Approximation. Number 193 in Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 2012 .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