Teoría de la Computación CC3102 (2012/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).
Aspectos administrativos: Cátedra: Martes, Jueves 10:15am-11:45am, B203 Libro del CursoEl libro de referencia del curso es el libro de Michael Sipser, “Introduction to the Theory of Computation, Second Edition”. 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 varias 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 semana
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 5 a 6) 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 3 o 4 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). 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 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 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 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. En caso de aprobar, la nota I se reemplazar por nota 4.0 independiente de la nota de controles (NC). Bibliografía:
Última modificación: 7 de Agosto 2012. |