Teoría de la Computación CC3102 (2019/02)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). Profesores Auxiliares: Ivana Buchmann, Rodrigo Fuentes, Vicente Rojas. Aspectos administrativos:Cátedra: Martes y Jueves 12pm-1:30pm, [sala por definir] Libro del CursoEl libro de referencia del curso es el libro de Michael Sipser, “Introduction to the Theory of Computation, Third Edition”. También se usará el apunte del profesor Navarro para ciertos capitulos, lo cual se indicará explícitamente. Ver referencia al final. Se espera que el estudiante lea y estudie en forma independiente el o los capílos correspondientes a la materia vista en clases.Novedades
TareasPara algunas de las tareas, el estudiante deberá estar familiarizado con el software JFLAP.Detalles del CursoObjetivo: 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
Lecturas Recomendadas para cada semanaSe publicarán en el blog de ucursos.MetodologíaDos clases de cátedra semanales, más una clase auxiliar para resolver ejercicios y profundizar los conceptos teóricos.Evaluación y Reglas del JuegoGeneral: La evaluación se basa en tres controles (con apuntes limitados) y un exámen (apuntes limitados, eximible) más varias (de 4 a 5) tareas. Cualquier deshonestidad académica es causal inmediata de reprobación del curso y de sumario académico. Controles y Examen: Habrá tres controles los cuales cubrirán toda la materia. Se eximiriá del exámen 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. Tareas: Habrá 4 o 5 tareas, de las cuales casi todas ellas serán de tipo teórico (resolución de problemas) y a lo más 1 de tipo implementación (programación). Las tareas de tipo implementación, de existir, tendr´n coeficiente 2. La proporción de tareas teóricas versus tareas de programación podrá variar año a año. Tanto las tareas teóricas como las de programación son todas individuales. Discusión de Tareas vs. Copia: Ver documento de políticas de colaboración en ucursos.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.) Situación Final: 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 tarea de coeficiente doble, en cuyo caso no se eliminará pero, a cambio, 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. 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 pero superior a 3.5 se dará una tarea recuperativa significamente más difícil que las anteriores; la tarea recuperativa se deberá realizar individualmente y presentar personalmente al profesor. En caso de aprobar, la nota I se reemplazar por nota 4.0 independiente de la nota de controles (NC).Bibliografía:
|