Teoría de la Computación CC3102 (2017/02)

Propósito: Conocer qué problemas puede resolver un computador a través de diversos modelos de computación. Conocer diferencias en cuanto a la eficiencia de computación de distintos problemas.

Profesor: Alejandro Hevia (email: ahevia ARROBA dcc PUNTO uchile PUNTO cl).

Aspectos administrativos:

Cátedra: Martes y Jueves 12pm-1:30pm, [B213]
Auxiliar: Miércoles 4:15pm-5:45pm, [B213]
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: CC3001 Algoritmos y Estructuras de Datos, CC3101 Matemáticas Discretas para la Computación
Carácter del curso: obligatorio Cs. de la Computación

Libro del Curso

El libro de referencia del curso es el libro de Michael Sipser, “Introduction to the Theory of Computation, Third Edition”. También se usará el apunte del profesor Navarro para ciertos capitulos, lo cual se indicará explícitamente. Ver referencia al final. Se espera que el estudiante lea y estudie en forma independiente el o los capílos correspondientes a la materia vista en clases.

Novedades

  • Importante: leer Reglas del Juego con respecto a las evaluaciones (controles y tareas).
  • Fechas Controles:
    1. Control 1: Por Anunciar
    2. Control 2: Por Anunciar
    3. Control 3: Por Anunciar

Tareas

Para algunas de las tareas, el estudiante deberá estar familiarizado con el software JFLAP.

Detalles del Curso

Objetivo: Al finalizar el curso el alumno será capaz de conocer qué problemas puede resolver un computador a través de diversos modelos simples de computación. Algunos de estos modelos son usados en diversas áreas como la construcción de compiladores (análisis léxico y sintáctico), sistemas de entrada y salida de datos discretos, editores de texto, búsqueda de patrones, etc. Además, el alumno será capaz de conocer y clasificar problemas en términos de límites conjeturados en eficiencia teórica en su computación.

Temario

  1. Cadenas y Lenguajes:
    • Conceptos básicos de alfabeto, cadena y operaciones asociadas. Lenguajes. Representación finita de lenguajes.
  2. Lenguajes regulares y autómatas finitos:
    • Expresiones regulares. Lenguajes regulares. Modelo simple de un computador. Autómata finito. Propiedades. Determinismo y no determinismo. Equivalencia entre ambos modelos. Equivalencia entre autólmatas y lenguajes regulares. Lema del Bombeo. Igualdad entre lenguajes regulares. Minimización de Autómatas.
  3. Lenguajes libres del contexto y autómatas de pila:
    • Gramáticas libres del contexto. Derivación de palabras. Lenguajes libres del contexto. Autómatas de pila. Propiedades. Determinismo y no determinismo. Lema del Bombeo. Equivalencia entre autómatas de pila y lenguajes libres del contexto.
  4. Máquinas de Turing y Computabilidad:
    • Modelo general de un computador. Máquina de Turing. Variaciones del modelo. No determinismo. Decidibilidad. Problema de la parada (Halting Problem). Modelos alternativos. Tesis de Church.
  5. Introducción a la Complejidad Computacional:
    • Medidas de eficiencia y notación de orden O(). Las clases P y NP. NP-completitud. Teorema de Cook, NP-completitud de SAT. Reducción de problemas.

Metodología

Dos clases de cátedra semanales, más una clase auxiliar para resolver ejercicios y profundizar los conceptos teóricos.

Evaluación y Reglas del Juego

General: La evaluación se basa en tres controles (con apuntes limitados) y un exámen (apuntes limitados, eximible) más varias (de 4 a 5) tareas. Cualquier deshonestidad académica es causal inmediata de reprobación del curso y de sumario académico.

Controles y Examen: Habrá tres controles los cuales cubrirán toda la materia. Se eximiriá del exámen con nota igual o superior a 5.5. Tiene derecho a examen recuperativo si la nota está entre 3.7 y 3.9. Se podrán reclamar los controles y, si el tiempo lo permite, el examen. No se permite el uso (hablar ni tipear) de celulares o dispositivos móviles durante controles o el exámen. Inasistencia a un control significa un 1.0 a menos que exista justificación médica oficial, en cuyo caso la nota del exámen remplazará el control perdido.

Tareas: Habrá 4 o 5 tareas, de las cuales casi todas ellas serán de tipo teórico (resolución de problemas) y a lo más 1 de tipo implementación (programación). La proporción de tareas teóricas versus tareas de programación podrá variar año a año. Tanto las tareas teóricas como las de programación son individuales.

Discusión de Tareas vs. Copia: De ser necesario, la tarea se puede discutir en grupos de a lo más dos personas. Esto es opcional, Ud. no está obligado a discutirla con otra persona. Discutir significa: conversar respecto al problema SIN tomar apuntes, discutiendo, por ejemplo, en qué consiste el problema, qué se necesita saber para resolverlo e incluso ideas generales de cómo resolverlo, pero NUNCA COMPARTIR ni RE-USAR soluciones. Cada persona debe hacer su propia solución, escrita y redactada en forma individual, y entregar su solución separadamente. La solución de cada estudiante debe indicar el nombre del otro estudiante con el cual se discutió la tarea (si es que existe). El no cumplimiento de cualquiera de estas condiciones se considerará copia.

Nota: Si Ud. sigue estas instrucciones no se preocupe, es casi siempre obvio cuando una solución es copia. En caso de sospecha, el autor de la solución debe estar preparado para explicar su tarea en detalle en forma personal al profesor. La tarea de implementación (de existir) podría tener coeficiente 2.

La nota de tareas será el promedio de las notas de tareas, donde este promedio será calculado usando ponderación doble para la tarea de implementación. Se descontará 1 punto por día de atraso (si hubiera una pregunta bonus esta NO se corregirá y por ende no se otorgará a las tareas atrasadas.)

Situación Final: Los 3 controles se promedian para obtener la nota de controles. La nota NC se obtiene como el promedio ponderado de la nota de controles (60%) y el examen (40%). Las tareas se promedian para obtener la NT, donde el promedio se calcula según la fórmula especificada más abajo (tareas de implementación tienen coeficiente doble). Se elimina la nota de la peor tarea (excepto si es la menor nota es una tarea de coeficiente doble, en cuyo caso dicha nota tendrá sólo coeficiente simple). La nota NC y la nota NT deben aprobarse por separado y se promedian como 2/3 NC + 1/3 NT. La nota final (NF) es 2/3 de la nota NC más 1/3 de la nota de tareas. Ambas se deben aprobar separadamente (mayor o igual a 4.0). En caso de obtener una nota de tareas inferior a 4.0 pero superior a 3.5 se dará una tarea recuperativa significamente más difícil que las anteriores; la tarea recuperativa se deberá realizar individualmente y presentar personalmente al profesor. En caso de aprobar, la nota I se reemplazar por nota 4.0 independiente de la nota de controles (NC).

Bibliografía:

  1. Michael Sipser, “Introduction to the Theory of Computation, Third Edition”, 2013. Cengage Learning Press. Referencia.
  2. Gonzalo Navarro, “Teoría de la Computación (Lenguajes Formales, Computabilidad y Complejidad), Apuntes y Ejercicios”, Universidad de Chile, 2017. Disponible desde la página del Prof. Gonzalo Navarro.
  3. J. Hopcroft, R. Motwani, y J. Ullman. Introduction to Automata Theory, Languages and Computation. 3er edition, Addison-Wesley, 2007.
  4. H. Lewis y C. Papadimitrou. Elements of the Theory of Computation. Prentice-Hall, 1981.

Última modificación: 1 de Agosto 2017.