Teoría de la Computación CC3102 (2010/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 2:30pm-4pm, B205
Auxiliar: Lunes 2:30pm-4pm, [Sala por anunciar]
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
Novedades
- 13 de Marzo: Ver lecturas recomendadas para cada semana.
- 8 de Marzo: Aparecieron las fechas de controles (ver abajo).
- Importante: leer Reglas del Juego con respecto
a las evaluaciones (tareas).
- Fechas Controles:
- Control 1: 10 de Mayo 2010
- Control 2: 14 de Junio 2010
- Control 3: 5 de Julio 2010
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 13 de Abril de 2010:
- Sipser: Cap. 1.2 desde "Closure..." (pag.58),1.3
- Navarro: Cap. 2.7,2.1,2.4,2.6
- Para la semana del 6 de Abril de 2010:
- Sipser: Cap. 1.2 hasta "Closure..." (pag.58)
- Navarro: Cap. 2.3,2.5
- Para la semana del 30 de Marzo de 2010:
- 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 tres controles (con apuntes limitados) y un
exámen (sin apuntes, eximible) más varias (de 5 a 6)
tareas.
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 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á tres controles los cuales cubrirán toda la materia.
Se eximiriá del exán 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.
Habrá 5 o 6 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á
de tipo implementación (programación).
Las tareas teóricas son individuales.
De ser necesario, la tarea se puede discutir en grupos de a lo
más dos personas.
Discutir significa:
conversar respecto al problema, en qué consiste,
qué se necesita saber para resolverlo e incluso ideas generales
de cómo resolverlo, pero NO significa 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 o adaptación de otra.
En caso de sospecha, el autor de la solución debe estar preparado
para explicarla en detalle en forma personal.
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 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 2010.
|