INTRODUCCION A LA COMPUTACION

Se trata, como su nombre indica, de un curso introductorio en la materia. Se ha dividido en cuatro apartados básicos, como ha venido siendo tradicional en algunos textos semejantes de quizá más envergadura, como son unos rudimentos de Lógica, un estudio esencialmente funcional de los Autómatas Finitos (pero no por ello menos descriptivo), más adecuado, en nuestra opinión, a una carrera no esencialmente técnica pero fuertemente teórica, para pasar a continuación al autómata más potente, la Máquina de Turing, con sus temas asociados de Computabilidad, Recursividad y unas ideas generales de Complejidad, y terminar con un tema sobre Lenguajes y Gramáticas, cuyo objetivo es fundamentalmente taxonómico. Se han obviado en casi todos los casos demostraciones de teoremas básicos, en algunos por su facilidad, pero en otros, porque su dificultad se sale, en principio, de la intención de que sea un curso introductorio destinado a dar una visión de conjunto más que a profundizar específicamente en los temas. De todos modos, quienes estén interesados en esa profundización pueden acudir a los textos citados en la bibliografía que son todos ellos magníficos en nuestra opinión. Se ha añadido un Apéndice, con problemas resueltos de la primera parte. Respecto a la segunda parte creemos que son suficientes los contenidos prácticos que hay en sus correspondientes capítulos. El texto está diseñado, en muchos aspectos, de manera informal, de forma que guarde cierto parecido con apuntes esquemáticos reducidos al establecimiento de axiomáticas, a listados de definiciones congruentes dentro del tema a tratar, y al enunciado de teoremas, con los que, en su caso se ponen en conexión ejemplos y/o ejercicios de aplicación práctica. Asimismo se repiten, cuando se ha considerado conveniente las definiciones de algunos conceptos o se dan otras definiciones equivalentes de ellos, con objeto de ampliar la visión de conjunto o de repasar.