CURSO:TEORIA DE LA COMPUTACION TRADUCCION:THEORY OF COMPUTATION SIGLA:IIC2214 CREDITOS:10 MODULOS:03 CARACTER:MINIMO TIPO:CATEDRA CALIFICACION:ESTANDAR PALABRAS CLAVE:LOGICA,COMPLEJIDAD COMPUTACIONAL,MAQUINAS DE TURING. NIVEL FORMATIVO:PREGRADO I.DESCRIPCIÓN DEL CURSO En este curso los estudiantes analizaran las principales herramientas para abstraer y estudiar procesos computacionales. Los estudiantes se veran familiarizados con las ramas de la logica necesarias para trabajar en computacion, y aprenderan a usar logica para modelar procesos computacionales. Asi mismo, comprenderan los postulados teoricos detras del estudio de la complejidad de algoritmos, y podran aplicarlos en escenarios realistas. A modo de contexto, la teoria de la computacion descansa en la logica como lenguaje para modelar y entender practicamente todos los procesos, algoritmos y paradigmas de la computacion, y por lo mismo, la logica ha sido llamada el calculo de la computacion. II.RESULTADOS DE APRENDIZAJE 1.Crear maquinas de Turing que resuelvan procesos computacionales sencillos analizando las implicaciones practicas de las distintas arquitecturas posibles para estas maquinas. 2.Aplicar el concepto de reduccion para demostrar la existencia de problemas indecidibles. 3.Contrastar el concepto de no-determinismo y la simulacion de algoritmos no-deterministas mediante la busqueda exhaustiva y la diferencia entre resolver un problema versus verificar la solucion a un problema. 4.Utilizar herramientas basicas de logica proposicional en el modelamiento de problemas de computacion y la demostracion de propiedades sobre estos modelos. 5.Distinguir algoritmos eficientes de otros que no lo son, a traves de la definicion formal de la clase NP y los conceptos de hardness, completitud y reducciones. 6.Usar logica de primer orden para modelar procesos computacionales contrastando las diferencias entre la logica proposicional y la logica de primer orden. III.CONTENIDOS 1.Computabilidad y Maquinas de Turing 1.1.Problemas de decision 1.2.Maquinas de Turing como modelo de computacion 1.3.Existencia de problemas indecidibles 1.4.Reducciones de Turing 1.5.No-determinismo 2.Logica Proposicional 2.1.Sintaxis y lectura unica 2.2.Semantica 2.3.Consecuencia logica y monotonia 2.4.Resolucion proposicional 2.5.El problema de evaluacion 2.6.Aplicaciones en computacion, el problema de satisfacibilidad (SAT) 3.Introduccion a la Complejidad Computacional 3.1.Clases de complejidad 3.2.NP y SAT 3.3.Hardness, completitud y reducciones 3.4.Otras clases de complejidad 4.Logica de Primer orden sobre relaciones y aplicaciones en computacion 4.1.Sintaxis y semantica 4.2.Consultas Conjuntivas 4.3.Teorias, Incompletitud IV.ESTRATEGIAS METODOLOGICAS ?Clases expositivas. ?Talleres de trabajo. ?Ayudantias. ?Tareas. V.ESTRATEGIAS EVALUATIVAS -Tareas: 70% -Examen final escrito: 30% VI.BIBLIOGRAFIA Minima Michael Sipser. Introduccion a la teoria de la computacion. Cengage Learning; 3ra Edicion, 2012 Complementaria Leopoldo Bertossi. Logica para Ciencia de la Computacion. Ediciones UC,1996 Michael Huth, Mark Ryan. Logic in Computer Science, Cambridge University Press,2004 Herbert B. Enderton. A mathematical introduction to Logic. Academic Press New York,2001 PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE ESCUELA DE INGENIERIA / OCTUBRE 2022