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:
- Control 1: 23 de Abril 2008
- 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
- 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.
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:
- 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: 8 de Abril 2008.
|