Fundamentos de Ciencias de la Computación CC30B (2009/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, B203
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

  • 13 de Abril: Ejemplo de archivo JFLAP actualizado, es más claro al representarlo gráficamente .
  • 9 de Abril, 2pm: Se agregaron links y actualizó el enunciado de la tarea 2.
  • 9 de Abril: La tarea 2 está disponible.
  • La tarea 1 está disponible.
  • 12 de Marzo: Ver lecturas recomendadas para cada semana.
  • 12 de Marzo: Aparecieron las fechas de controles (ver abajo).
  • Importante: leer Reglas del Juego con respecto a las evaluaciones (tareas).
  • Fechas Controles:
    1. Control 1: 29 de Abril 2009
    2. Control 2: 10 de Junio 2009

Tareas

  • Tarea 1: pdf. Fecha entrega: 2 de Abril 2009, 23:59hrs. vía ucursos.
  • Tarea 2: pdf (actualizado a las 2pm, 9 de Abril 2009).

    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.

    Lecturas Recomendadas para cada semana

    • Para la semana del 14 de Abril de 2009:
      • Sipser: Cap. 2.1, 2.2
      • Navarro: Cap. 3.1-3.5
    • Para la semana del 7 de Abril de 2009:
      • Sipser: Cap. 1.3, 1.4
      • Navarro: Cap. 2.4,2.6,2.8
    • Para la semana del 31 de Marzo de 2009:
      • Sipser: Cap. 1.2 desde "Closure..." (pag.58),1.3
      • Navarro: Cap. 2.7,2.1,2.4,2.6
    • Para la semana del 24 de Marzo de 2009:
      • Sipser: Cap. 1.2 hasta "Closure..." (pag.58)
      • Navarro: Cap. 2.3,2.5
    • Para la semana del 17 de Marzo de 2009:
      • Sipser: Cap. 0,1.1,1.2
      • Navarro: Cap. 1,2.2,2.3,2.4

    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.

    Habrá dos controles los cuales pueden no cubrir toda la materia; por lo mismo, no hay eximición. Sin embargo, a los alumnos con promedio de controles igual o superior a 5.5 se les dará la opción de no responder las preguntas del exámen correspondientes a materias cubiertas en los controles. 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.

    Habrá 6 o 7 tareas, de las cuales 5 o 6 serán de tipo teórico (resolución de problemas) y a lo más 1 de ellas será 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). La tarea de implementación tendrá 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 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.)

    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 independiente de la nota de controles (NC).

    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: 13 de Abril 2009.