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:
- Control 1: 29 de Abril 2009
- 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
- Cadenas y Lenguajes:
- Conceptos básicos de alfabeto, cadena y operaciones
asociadas. Lenguajes. Representación finita de lenguajes.
- 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.
- 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.
- 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.
- 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:
- 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.
- 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.
- H. Lewis y C. Papadimitrou. Elements of the Theory of Computation. Prentice-Hall, 1981.
- J. Hopcroft y J. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
Última modificación: 13 de Abril 2009.
|