¡Esta es una revisión vieja del documento!


Nombre del curso

Computabilidad y Complejidad

Información Básica

  • Créditos: 3
  • Horas de Clase: 5 / semana (3 horas de clase, 2 de taller)
  • Horas de trabajo independiente: 4 / semana
  • Prerequisitos: Matemáticas Discretas para la Computación (300MAG031), Lógica en Ciencias de la Computación (300CIG002).
  • Tipo de curso: Núcleo de Formación Fundamental.

Descripción del Curso

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 temas para el análisis de complejidad especial 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.

Objetivos

Al finalizar el curso los participantes podrán:

  1. Definir e interpretar modelos computacionales de variado poder expresivo.
    1. Definir qué es un lenguaje regular y representar dicho lenguaje mediante autómatas de estados finitos deterministas, no deterministas o expresiones regulares.
    2. Demostrar que los autómatas deterministas, los no deterministas y las expresiones regulares son modelos equivalentes.
    3. A partir de la descripción de una situación del mundo real o de un sistema, definir un autómata de estados finitos que lo modela.
    4. Definir qué es un lenguaje incontextual.
    5. Calcular la derivación de una cadena en una gramática incontextual.
    6. Dado un lenguaje formal, definir una gramática incontextual que lo genera y dada una gramática incontextual, describir en forma verbal el lenguaje que genera.
    7. Convertir una gramática incontextual a la forma normal de Chomsky.
    8. Dado un lenguaje incontextual, definir un autómata de pila que lo reconoce y dado un autómata de pila, describir verbalmente cuál es el lenguaje que reconoce.
    9. Demostrar que autómatas de pila no deterministas y gramáticas incontextuales son modelos equivalentes.
    10. Definir qué es una máquina de Turing.
    11. Definir una máquina de Turing que reconoce un lenguaje formal dado y describir verbalmente el lenguaje que reconoce una máquina de Turing dada.
    12. Demostrar que la máquina de Turing no determinista tiene el mismo poder expresivo que la determinista.
    13. Definir una máquina de Turing que compute una función dada.
  2. Enunciar y argumentar la veracidad de los conceptos principales de la teoría de la computación.
    1. Enunciar la tesis de Church y Turing y argumentar su importancia.
    2. Definir qué es un lenguaje decidible y uno reconocible.
    3. Demostrar que un lenguaje dado es decidible y/o reconocible.
    4. Enunciar el problema de la parada y demostrar que es indecidible.
    5. Definir qué es una reducción entre lenguajes.
    6. Definir el lenguaje asociado a un problema de decisión.
    7. Definir la clase de Lenguajes P, NP, NP-Completo y PSPACE y demostrar la pertenencia de un lenguaje a alguna de estas categorías.
    8. Construir una jerarquía entre las clases de lenguajes estudiadas y argumentar las equivalencias o contenencias entre diferentes clases de lenguajes.
  3. Analizar la complejidad de una máquina de Turing y de un algoritmo.
    1. Utilizar la definición de las notaciones O, Omega y Theta para mostrar que una función matemática dada está o no acotada por otra mediante cada una de ellas.
    2. Aplicar las reglas de sumas y productos para calcular una cota superior de complejidad temporal a partir del pseudocódigo de un algoritmo.
    3. Estar en capacidad de evaluar la complejidad temporal y espacial de algoritmos que tienen como estructura de datos principal arreglos, árboles o grafos.

Se desarrollan competencias en

  1. Specification, simulation and testing in the JFLAP tool (básico) [3].

Contenido

Capítulo 1: Introducció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]

Capítulo 2: Lenguajes Regulares y Automatas Finitos

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]

Capítulo 3: Lenguajes Incontextuales y Autómatas de Pila

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]

Capítulo 4: Lenguajes Recursivos y Máquinas de Turing

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]

Capítulo 5: Complejidad Computacional

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]

Integración Curricular

Resultados de Programa (ABET)

(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.

Relevancia del curso con los resultados de programa

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

Integración de objetivos, contenido y metodología del curso

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

Contribución al Desarrollo de Competencias (CNA)

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

Contribución a los objetivos educacionales

La Carrera de Ingeniería de Sistemas y Computación plantea los siguientes objetivos educacionales, El estudiante graduado de la carrera será capaz de:

  1. Ejercitar la práctica de la Ingeniería de Sistemas y Computación profesionalmente.
  2. Diseñar y operar sistemas de computación que contribuyen a la solución de problemas relacionados a la disciplina, otra área de la ciencia y la ingeniería u otras disciplinas.
  3. Contribuir al bienestar de las comunidades desde posiciones prominentes en la industria, academia, sector público o como un emprendedor.
  4. Ser distinguido por su bases sólidas en computación, su sentido de ciudadanía responsable, su profesionalismo y liderazgo.
  5. Continuar su desarrollo profesional o involucrarse en estudios de posgrado.
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 4X X
Objetivo 5 X X

Recomendaciones del Director del Programa

Reglas del curso

Calificación y Balance del Curso

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%

Uso de material en exámenes

Se permite uso de cualquier material impreso. No se permite uso de ningún dispositivo electrónico.

Asistencia

Obligatoria.

Bibliografía

  1. Kozen, Dexter. Automata and Computability. ISBN 978-1-4612-7309-7. Springer, 1997.
  2. Papadimitriou, Christos. Computational Complexity. ISBN 0-201-53082-1. Addison Wesley, 1994.

Instalaciones

Salón de clase con computador y proyector (Sala Linux, PL-3.2). Laboratorio de Ingeniería de Sistemas y Computación.

Material de este semestre

Se distribuye material después de cada clase por medio de lista de correos asignada al curso.

 
materias/computabilidadcomplejidad.1473765208.txt.gz · Última modificación: 2016/09/13 06:13 por frank.valencia
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki