Problemas, Lenguajes y Algoritmos
Marta Sagastume, Gabriel Baum e Guillermo Martínes (Colaboración)
La primera edición de este libro fue escrita para la primera Escuela Brasilero-Argentina de Informática como texto del curso “Teoría de la Computación”. Esta segunda edición ampliada recoge experiencias en el dictado de diversos cursos de Lenguajes Formales y Autómatas y de Computabilidad y Complejidad en universidades argentinas. El material presentado aquí esta dirigido a alumnos de los últimos años de carreras de Ciencias de la Computación o a graduados que deseen introducirse en el tema. En el Capítulo I se presentan los autómatas finitos, a pila, las máquinas de Turing y la correspondiente jerarquía de Chomsky de gramáticas. Se estudian las formas normales de Chomsky y de Greibach para las libres de contexto. Se prueba la equivalencia de los autómatas finitos con los lenguajes regulares y se demuestra el teorema que define, si existe, el autómata finito mínimo. Se introducen finalmente las redes de Petri que modelizan procesos concurrentes. El objetivo del Capítulo II es mostrar las limitaciones de la calculabilidad efectiva. Se presentan los resultados clásicos principales de esta teoría y la idea básica del teorema de incompletitud de Gödel. Se demuestra el llamado “pumping lemma” para los lenguajes de tipo 2 y 3. Se analizan cuatro problemas de decisión relacionados con lenguajes. Se da al final un ejemplo de problema indecidible relativo a redes de Petri. En el Capítulo III se presentan las funciones recursivas parciales y los algoritmos de Markov como modelos de calculabilidad alternativas a la máquina de Turing. Se hace uso de un subconjunto de un lenguaje de programación de tipo PASCAL como herramienta para facilitar los razonamientos. Se dan pruebas informales de la equivalencia entre los tres modelos. La idea básica del Capítulo IV es introducir la noción de complejidad de un algoritmo y presentar la clase de problemas NP-completos. Los dos primeros Capítulos fueron escritos por M. Sagastume y los dos últimos por G. Baum. A eso se debe la diferencia de estilos entre la primera y segunda parte del texto. Se incluyen también tres apéndices de Guillermo Martínez, el primero de los cuales es el resumen de un cursillo que dictó en la UNS (Bahía Blanca, Argentina) sobre computabilidad, complejidad y teoremas de Gödel, que profundiza nociones y resultados básicos de este libro. El segundo y el tercero son comentarios de libros aparecidas en diarios de Bs. As.: El último teorema de Fermat, de Simon Singh, y el de la última edición de Leyendo a Euclides, de Bepo Levi.
Volume 37 – 2003
Disponível para download em: https://www.cle.unicamp.br/ebooks/index.php/publicacoes/catalog/book/68
