Computabilidad y Complejidad
Este curso reune temas fundamentales de la informática teórica, que son parte indispensable de la formación de un ingeniero de sistemas.
El curso comienza con un contexto motivador que describe el origen de computación y su relación estrecha con la lógica matemática. El curso cubre tres modelos fundamentales de computación y sus correspondientes lenguajes formales: Máquinas de estado finito y lenguajes regulares, máquinas de pila y lenguajes incontextuales, máquinas de Turing y lenguajes recursivos. Se estudiará la expresividad de estos modelos y sus limitaciones absolutas: En particular, se mostrará formalmente que hay problemas que no pueden ser solucionados (decididos) por ninguna máquina de Turing (el más expresivos de todos los modelos computacionales), lo cual implica que no pueden ser solucionados por ningún algoritmo de acuerdo a la tesis fundamental de Turing (también estudiada en el curso).
Por otro lado también se estudiarán y clasificarán, de acuerdo a su complejidad espacial y temporal inherente, problemas fundamentales que sí pueden ser decididos por una máquina de Turing. Este estudio cubre el análisis de complejidad de algoritmos y estructuras de datos, como también clases fundamentales de problemas que pueden ser solucionadas en tiempo polinomial de una manera determinista (P), no determinista (NP), en tiempo exponencial de manera determinista (EXP), y con espacio polinomial de manera determinista (EXP).
En conclusión, este curso agrupa temas teóricos fundamentales, que enriquecerán la visión del estudiante acerca de las ciencias de la computación y lo llevarán a aplicar esta ciencia en el desempeño de una ingeniería de calidad.
Al finalizar el curso los participantes podrán:
Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
---|---|---|---|---|---|
1-2 | 3 | 2 | Presentación del curso y nociones básicas de conjuntos y cadenas. | Uso | [1, Introducción] |
Total de Horas: 5.
Sesión | Horas de trabajo independiente | Temas | Bibliografía |
---|---|---|---|
1-2 | 4 | Tareas semanales, resolución de problemas en temas vistos | [1, Introducción] |
Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
---|---|---|---|---|---|
3-8 | 9 | 6 | Autómatas deterministas de estados finitos y lenguajes regulares. Autómatas de estado finito no deterministas y construcción de conjunto potencia. Expresiones regulares y patrones de secuencia. Limitaciones de Autómatas finitos (lema del bombeo) | Evaluación | [1, cap. 1] |
Total de Horas: 15.
Sesión | Horas de trabajo independiente | Temas | Bibliografía |
---|---|---|---|
3-8 | 12 | Tareas semanales, resolución de problemas en temas vistos | [1, cap. 1] |
Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
---|---|---|---|---|---|
9-14 | 9 | 6 | Lenguajes Incontextuales y Formas Normales. Lema de Bombeo para Lenguages Incontextuales. Autómatas de Pila. Sintaxis abstracta y concreta, parsing. | Evaluación | [1, cap. 2] |
Total de Horas: 15.
Sesión | Horas de trabajo independiente | Temas | Bibliografía |
---|---|---|---|
9-14 | 12 | Tareas semanales, resolución de problemas en temas vistos | [1, cap. 2] |
Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
---|---|---|---|---|---|
15-20 | 9 | 6 | Máquinas de Turing y Tesis de Church y Turing. Lenguajes Recursivos y Jerarquía de Chomsky. Modelos Equivalentes. Máquinas de Turing Universales y programas que toman otros programas como entrada. Problemas no computables (Indecidibilidad) y Reducibilidad: Problema de la parada. | Evaluación | [1, cap. 3] |
Total de Horas: 15.
Sesión | Horas de trabajo independiente | Temas | Bibliografía |
---|---|---|---|
15-20 | 12 | Tareas semanales, resolución de problemas en temas vistos | [1, cap. 3] |
Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
---|---|---|---|---|---|
21-32 | 18 | 12 | Cota superior asintótica (notaciones O, Omega y Theta), ecuaciones de recurrencia y teorema maestro. Análisis espacial y temporal de algoritmos y estructura de datos. Clases de Complejidad. Clases P, NP, EXP y P-Space. Reducción y Completitud. P vs NP y Algunos Problemas de decisión NP-completos: SAT y Knapsack. | Evaluación | [2, cap. 1, 7, 8] |
Total de Horas: 30.
Sesión | Horas de trabajo independiente | Temas | Bibliografía |
---|---|---|---|
21-32 | 24 | Tareas semanales, resolución de problemas en temas vistos | [2, cap. 1, 7, 8] |
(A) La habilidad para aplicar conocimientos de matemáticas, ciencias e ingeniería.
(B) La habilidad para analizar un problema e identificar los requerimientos necesarios para su definición y solución.
(C) La habilidad para diseñar, implementar y evaluar procesos y sistemas computacionales.
(D) La habilidad para funcionar en equipos de trabajo.
(E) El entendimiento de la responsabilidad profesional y ética.
(F) La habilidad para comunicarse efectivamente.
(G) La habilidad para analizar los impactos de la computación y la ingeniería en las personas, organizaciones y la sociedad.
(H) El reconocimiento de la necesidad de, y la habilidad para, continuar con el desarrollo profesional.
(I) La habilidad para usar las técnicas, destrezas y herramientas modernas para la práctica de la computación.
(J) La habilidad para aplicar los fundamentos y principios de las matemáticas y de la computación en el modelamiento y diseño de sistemas computacionales de manera que se demuestre comprensión de las ventajas y desventajas en las decisiones de diseño.
(K) La habilidad para aplicar los principios de diseño y desarrollo de software en la construcción de sistemas de diferente complejidad.
Resultados de Programa | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | e | f | g | h | i | j | k | |
Relevancia | 4 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 4 | 0 |
1: baja relevancia - 5 alta relevancia
El curso es presencial y con participación y trabajo en clase. Se asignarán trabajos, ejercicios y lecturas. Durante la sesión se expondrán los conceptos acompañados de ejemplos, se fomentará la participación de los estudiantes. Se realiza un taller semanal en el que se aplican los fundamentos teóricos.
Resultados del Programa | Indicadores de Desempeño | Objetivos/Contenido del Curso | Actividades de aprendizaje | Instrumentos de medición |
---|---|---|---|---|
(A) Aplicación de Conocimientos | (A1) Identificar los fundamentos científicos y los principios de ingeniería que rigen un proceso o sistema. (Conocimiento) (A2) Resolver problemas relacionados con la disciplina y otras áreas por medio de la utilización de conocimientos, modelos y formalismos de las ciencias de la computación, las matemáticas y la ingeniería. (Aplicación) (A4) Interpretar modelos matemáticos para estimar su precisión y confiabilidad. (Comprensión) | Todos | Exposiciones del profesor, talleres, tareas y lecturas | Exámenes, Talleres, proyecto |
(F) Comunicación efectiva | (F2) Comunicarse de manera efectiva de acuerdo al público objetivo haciendo uso correcto del lenguaje, estilo, tiempo y expresión corporal. (Aplicación). (F4) Defender ideas con precisión y claridad. (Evaluación). | Todos | Ejercicios de demostración, presentación oral y escrita de talleres | Exámenes y proyecto |
(J) Modelamiento y diseño de sistemas computacionales | (J1) Reconocer la importancia del modelamiento cuando se resuelve un problema. (Compresión). (J2) Relacionar conceptos y principios teóricos para la resolución efectiva de un problema. (Síntesis). (J4) Evaluar decisiones de diseño basándose en principios matemáticos y de computación. (Evaluación). | Todos | Exposiciones del profesor, talleres, tareas y proyectos | Exámenes, Talleres, proyecto |
La tabla muestra que aspectos de las competencias de Comunicación Escrita, Lectura Crítica y Razonamiento Cuantitativo son evaluados a través de los factores ABET correspondientes. Por otra parte, la competencias de Inglés se favorece gracias a la metodología del curso y también, gracias al factor ABET correspondientes.
Resultados de Programa | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
A | B | C | D | E | F | G | H | I | J | K | |
Comunicación escrita | E | ||||||||||
Lectura crítica | E | ||||||||||
Inglés | U | ||||||||||
Razonamiento cuantitativo | E | E |
E- Se evalúa. U - Se usa
La Carrera de Ingeniería de Sistemas y Computación plantea los siguientes objetivos educacionales, El estudiante graduado de la carrera será capaz de:
Resultados de Programa | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
A | B | C | D | E | F | G | H | I | J | K | |
Objetivo 1 | X | X | |||||||||
Objetivo 2 | X | X | |||||||||
Objetivo 3 | X | ||||||||||
Objetivo 4 | X | X | |||||||||
Objetivo 5 | X | X |
Instrumento | Porcentaje | A | B | C | D | E | F | G | H | I | J | K |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Parcial I | 20% | 70% | 20% | 10% | ||||||||
Parcial II | 20% | 50% | 20% | 30% | ||||||||
Parcial III | 20% | 20% | 10% | 70% | ||||||||
Proyecto I | 20% | 50% | 10% | 40% | ||||||||
Talleres | 20% | 30% | 70% |
Se permite uso de cualquier material impreso. No se permite uso de ningún dispositivo electrónico.
Obligatoria.
Salón de clase con computador y proyector (Sala Linux, PL-3.2). Laboratorio de Ingeniería de Sistemas y Computación.
Se distribuye material después de cada clase por medio de lista de correos asignada al curso.