Fundamentos de Ciencias de la Computación CC30B (2008/01)

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, Jueves 12pm-1:30pm, B213
Auxiliar: Miércoles 4:15pm-6:45pm, [Sala por anunciar]
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: MA26B o Autorización
Carácter del curso: obligatorio Cs. de la Computación

Novedades

  • La tarea 3 está disponible.
  • La tarea 2 está disponible.
  • La tarea 1 está disponible.
  • Importante: leer Reglas del Juego con respecto a las evaluaciones (tareas).
  • Fechas Controles:
    1. Control 1: 23 de Abril 2008
    2. Control 2: 28 de Mayo 2008

Tareas

  • Tarea 1: pdf. Fecha entrega: 1 de Abril 2008, 23:59hrs. vía ucursos.
  • Tarea 2: pdf. Fecha entrega: 15 de Abril 2008, 23:59hrs. vía ucursos.
  • Tarea 3: pdf. Fecha entrega: 23 de Abril 2008, 11:59hrs. vía ucursos.

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

La evaluación se basa en dos controles (con apuntes limitados) y un exámen (sin apuntes) más varias (de 6 a 7) tareas.

La nota del examen elimina la peor nota de control. Las notas de controles, y el examen se promedian para obtener la NC. 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 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.

Los dos controles cubrirán (preferiblemente) toda la materia. Se exime con 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.

Habrá 6 o 7 tareas, de las cuales 4 o 5 serán de tipo teórico (resolución de problemas) y a lo más 2 de ellas serán de tipo implementación (programación). Las tareas teóricas se podrán hacer en grupos de a lo más dos (2) alumnos, siempre que la redacción de la tarea entregada por el alumno la realice dicho alumno en forma individual (cada alumno debe sin embargo mencionar el nombre del alumno con el cual resolvió la tarea). Las tareas de implementación tendrán coeficiente 2 y podrán hacerse en grupos de hasta 2 personas. La nota de tareas será el promedio de las notas de tareas, donde este promedio será calculado usando ponderación doble para las tareas 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.

La nota final (NF) es 2/3 de la nota de controles (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 se dará una tarea recuperativa significamente más difícil que las anteriores; la tarea recuperativa se deberá realizar individualmente. En caso de aprobar, la nota I se reemplazar por nota 4.0.

Bibliografía:

  1. Michael Sipser, “Introduction to the Theory of Computation, Second Edition”, ISBN 13: 978-0-534-95097-2 (2006), ISBN 10: 0-534-95097-3, 15 de Febrero, 2005. Publicado por Course Technology. Referencia.
  2. Gonzalo Navarro, “Fundamentos de Ciencia de la Computación (Lenguajes Formales, Computabilidad y Complejidad), Apuntes y Ejercicios”, Universidad de Chile, 2007. Disponible desde la página del Prof. Gonzalo Navarro.
  3. H. Lewis y C. Papadimitrou. Elements of the Theory of Computation. Prentice-Hall, 1981.
  4. J. Hopcroft y J. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

Última modificación: 8 de Abril 2008.