|
Objetivo
En este curso se revisa las ideas principales de los autómatas, finitos en sus estados pero potencialmente infinitos en sus memorias, y sus correspondencias con los lenguajes formales. El curso comprende muchas prácticas de programación. Cada estudiante está en libertad de escoger el ambiente de programación que considere más adecuado para la realización de sus tareas. En clase se ilustrará algunos procedimientos mediante el calculador simbólico xMaxima.
Temario
-
Contenido
1) Introducción
a) Autómatas, Computación y Complejidad
b) Nociones Matemáticas y Terminologías
c) Conjuntos
d) Funciones, relaciones
e) Pruebas, tipos de pruebas
-
Fundamentos de arquitecturas de computadoras.
a) Clases de computadoras
b) Taxonomía de Flynn
c) Definición de una Arquitectura de Computadora
d) Tendencias tecnológicas
-
Diseño de instrucciones
a) Tipos de instrucciones
b) Modos de direccionamiento de memoria
c) Control de flujo
d) Pipeline
e) Predicciones de salto
f) Paralelismo a nivel de instrucciones
g) Casos de estudio
-
Diseño de jerarquía de memoria.
a) Optimizaciones del rendimiento de memoria
b) Tecnología de memoria y optimización
c) Protección: Memoria virtual y máquinas virtuales
d) Casos de estudio
-
Arquitectura multicore
a) Paralelismo a nivel hilo
b) Arquitecturas de memoria centralizada compartida
c) Memoria compartida distribuida y coherencia
d) Arquitectura de cache
-
Procesamiento vectorial y arquitectura de GPU
a) Arquitectura vectorial
b) Conjunto de instrucciones SIMD para multimedia
c) Unidades de procesamiento gráfico
d) Arquitectura many-core heterogéneas (asimétricas)
e) Detección y mejora de paralelismo a nivel ciclo
Bibliografía básica (Libros recientes de texto)
-
Keith Cooper, Linda Torczon, Engineering a Compiler, 2nd Edition, Morgan Kaufmann, 2011.
-
Jim Hefferon, Theory of Computation, 2019.
-
Peter Linz, An Introduction to Formal Languages and Automata 6th Edition, Jones & Bartlett Learning; 6th edition, 2016.
-
A.M. Padma Reddy, Finite Automata And Formal Languages: A Simple Approach, Cengage, 2019.
-
Jean-Éric Pin, Mathematical Foundations of Automata Theory, Lecture notes LIAFA, Université Paris, 2010.
-
Dana Richards, Henry Hamburger, Logic And Language Models For Computer Science, 3rd Edition, WSPC, 2017.
-
Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012. El autor ofrece su curso aquí, con temario y láminas.
-
Guillermo Morales: Principios de autómatas finitos, México, 2000.
Bibliografía de texto clásicos
-
Aho, Ullman: Foundations of computer science, W. H. Freeman & Co., 1992.
-
Arbib: The algebraic theory of machines, languages and semigrups, Academic Press, 1968.
-
Arbib, Kfoury, Moll: A basis for theoretical computer science, Springer-Verlag, 1981.
-
Conway: Regular algebra and finite machines, Chapman & Hall, 1971.
-
Denning, Dennis, Qualitz: Machines, languages and computation, Prentice-Hall, 1978.
-
Eilenberg: Automata, languages, and machines, Volume A, Academic Press, 1974.
-
Ginzburg: Algebraic theory of automata, Academic Press, 1968.
-
Harrison: Introduction to switching and automata theory, McGraw-Hill Book company, 1965.
-
Harrison: Introduction to formal languages theory, Addison Wesley, 1978 Hopcroft, Ullman: Introduction to automata theory, languages and computation, Addison-Wesley, 1979.
-
Kfoury, Moll, Arbib: A programming approach to computability, Springer-Verlag, 1982.
-
Kohavi: Switching and finite automata theory, McGraw-Hill, 1979.
-
Kuich, Salomaa: Semirings, automata, languages, Springer-Verlag, 1985.
-
Lewis, Papadimitiou: Elements of the theory of computation, Prentice Hall, 1981.
-
Rytter: 100 execises in the theory of automata and formal languages, Research report 99, Dept. Comp. Sci., University of Warwick, 1987.
-
Rogers: Theory of recursive functions and effective computability, McGraw-Hill, 1967.
-
Salomaa: Automata theory, Pergamon Press, 1969 Salomaa: Formal languages, Academic Press, 1973.
|
|
