tc-presentación enero 2014
TRANSCRIPT
Enfoque estándar:
Autómatas Lenguajes Gramáticas Máquinas de Turing Decibilidad Redicibilidad
TC
Contenido Computabilidad
Enfoque clásico (A. Church, A.Turing, S.C. Kleene, E. Post, A.A. Markov)
Contenido Computabilidad
Nuevos enfoques
Tarea ….
Antecedentes Conceptos básicos de matemáticas:
conjuntos, funciones y relaciones. Métodos de demostración.
Directa Reducción al absurdo Inducción matemática
Lógica de primer orden. Consistencia Decidibilidad Completitud
Elementos básicos de lenguajes formales.
Fundamentos de las Ciencias de la Computación
MATEMÁTICAS CIENCIAS
INGENIERIA
Final Report of the ACM Task Force on the Core of Computer Science, in cooperation with the IEEE Computer Society.Computer, Feb. 1989.
I. Teoría de la Programación Estudiar los lenguajes para
implementar los cómputos.
¿Qué es la Teoría de la Computación?
Teoría de la
ComputaciónII. Teoría del Cómputo
- Entender la naturaleza del cómputo, sus posibilidades y limitaciones.
Presentación del Área de Teoría de la Computación en la UNAM
Sergio Rajsbaum, Instituto de Matemáticas, UNAM, Enero 29, 2004
I. Teoría de la ProgramaciónModelos de cómputoLenguajes de programaciónSemántica de lenguajesEstilos de programación- Lógica, funcional…ConcurrenciaEspecificación y verificaciónLógica y computaciónRepresentación del conocimiento, bases de
datos
II. TEORÍA DEL CÓMPUTOEl estudio de las propiedades generales
del cómputo, ya sea natural, artificial, o imaginario
Modelos teóricos clásicos:
- Funciones recursivas
- Máquinas de Turing
- λ-Calculus
- Máquinas de Post
- Autómatas
- Máquinas ABACUS
- …
II. Teoría del CómputoEl estudio de las propiedades generales del
cómputo, ya sea natural, artificial, o imaginario
Modelos teóricos no clásicos:
- Computación cuántica- Computación bioinspirada
- Neuronal- Genética- …
- Computación interactiva- Hypercomputación- …
Preguntas
• ¿Qué se computa (calcula)?• ¿Cómo se lleva a cabo el
cómputo? • ¿Qué se puede calcular
(computar)?• ¿Qué no se puede calcular o
computar? (limitaciones)
El conocimiento está en los textos
El conocimiento está en los artículos
Licenciatura VS Maestría
Problemas estándar Nuevos problemas
Para los problemas hay soluciones estándar
Se usan los manuales
Para los problemas no hay soluciones estándar
Se investigan los alcances de las soluciones.
Nueva actitud de estudio
Desarrollo de habilidades.
Un nuevo reto cotidiano: enfrentar problemas no resueltos.
Aprender a leer artículos donde aparece el conocimiento formalizado.
Aprovechar la experiencias de los profesores y de los compañeros.
Ser responsable del proceso de aprendizaje y dirigirlo.
Nueva actitud de estudio
Argumentar y desarrollar ideas propias.
Evaluación
70%
2 Exámenesescritos20%
Material de autoestudio10%
Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing Company.
Cohen, Daniel I.A. Introduction to Computer Theory. Ed. Wie Wiley.
Davis, Martín D., Weyuker, Elaine. Computability, Complexity and Languages Fundamentales of Theoretical Computer Science. Academic Press.
Brookshear. Teoría de la Computación, Lenguajes Formales, Autómatas y Complejidad. Addison Wesley.
Boolos, G. and Jeffrey, R. Computability and Logic
Bibliografía
Artículos originales de los autores principales.
Material de la Web Notas de clase Presentaciones Videos …
Bibliografía
Church, A. “A Note on the Entscheidungsproblem.” Am. J. of Mathematics 58 (1936), 345‐363.
Kurt Godel, 1992. On Formally Undecidable Propositions Of Principia Mathematica And Related Systems, tr. B. Meltzer, with a comprehensive introduction by Richard Braithwaite. Dover reprint of the 1962 Basic Books edition.
Post, E. Finite Combinatory Processes - Formulation 1. J. Symbolic Logic 1 (1936), 103-105.
Turing, A. "On Computable Numbers, With an Application to the Entscheidungsproblem." Proc. of the London Mathematical Society, series 2, 42 (1937), 230-265.
A. Church, Review of Turing 1936, J. Symbolic Logic 2(1) (1937), 42-43.
Bibliografía
Bibliografía
S. C. Kleene, The theory of recursive functions, approaching its centennial, Bull. A.M.S. (n.s.) 5, (1981), 43-61.
¿Preguntas?
