Información del curso

Facultad de Ciencias, Universidad Nacional Autónoma de México

Autómatas y Lenguajes Formales, semestre 2020-2, Grupo 7036

Ver el curso en los horarios de la facultad, click aquí

Profesor: Noé Salomón Hernández S.

Horario: lunes y miércoles de 17 - 18:30 hrs.

Aula: P210

Ayudante: Aide Itzel García Hernández

Horario: martes y jueves de 16 - 17 hrs.

Aula: P210

El curso de Autómatas y Lenguajes Formales es fundamental en la licenciatura en Ciencias de la Computación, en él se pretende definir de manera formal la idea de computabilidad. Para ello necesitamos algunas definiciones tales como estado, transición, no-determinismo, reducción y derivación. La formalidad que buscamos se encuentra en los conceptos matemáticos que serán estudiados: autómatas, expresiones regulares, gramáticas y máquinas de Turing. Estos formalismos tienen un valor incalculable para la ciencia de la computación, sugieren propiedades para el hardware y software; además, a través de ellos podemos determinar qué puede y qué no puede resolver una computadora.

Algunos filósofos de principios del siglo veinte quisieron reducir toda la matemática a la manipulación formal de símbolos, de modo que los problemas estudiados en este curso serán expresados generalmente como problemas de pertenencia de una cadena a un lenguaje particular.

Los temas tratados en este curso tienen un impacto en otras áreas tales como: lenguajes de programación, compiladores, complejidad computacional, analizadores sintácticos y reconocedor de expresiones regulares (tales como grep).


Temario

  1. Introducción
  2. Autómatas finitos deterministas y no deterministas.
  3. Expresiones regulares.
  4. Gramáticas libres del contexto.
  5. Autómatas de pila.
  6. Jerarquía de Chomsky.
  7. Máquinas de Turing.
  8. Introducción a la complejidad y decidibilidad.

Todos los pormenores del temario y plan de estudio para esta asignatura puede ser consultados dando click aquí.


Evaluación

La evaluación consiste en exámenes, tareas y prácticas. Los resultados obtenidos se mostrarán en la pestaña de Calificaciones.

En caso de detectarse copia, los alumnos involucrados tendrán cero en el trabajo en cuestión. Si se reitera en la copia una segunda vez, entonces el alumno estará automáticamente reprobado.

El NP es para aquellas personas que no presenten ninguna evaluación. Si llegaran a presentar algún trabajo, entonces deberán solicitar el NP a más tardar el jueves 14 de mayo a la dirección de correo nohernan@turing.iimas.unam.mx y también tendrán que dejar de presentar exámenes, tareas y prácticas a partir de esa fecha. En resumen, para obtener NP no deben presentarse, o si entregan algún trabajo, deben de abandonar el curso y avisarme el 14 de mayo.

Adicionalmente, el profesor y los ayudantes solemos otorgar puntos extra por ejercicios hechos en clase. Tales puntos extra ayudan a la calificación del examen parcial, tareas o prácticas más próximo.

Los porcentajes correspondientes a cada uno de los rubros de la evaluación se dan a continuación.


  • Exámenes. Tienen un peso del 60%. Los exámenes se diseñan para que el alumno pueda obtener 11 como máximo de calificación.

Se apliacarán cuatro exámenes durante el semestre en las siguientes fechas:

El viernes 25 de junio se tiene la posibilidad de presentar una reposición, o si prefieren, un examen final que sustituirá únicamente la calificación de exámenes.

  • Tareas. Se les asigna un porcentaje de 20%. Algunas tareas tienen un puntaje máximo de 11.

Las tareas son cortas por lo que se dejarán ocho. Los días de publicación de las tareas y de entrega son:

Las tareas se realizan por equipos de dos y aparecerán el día de la publicación en la pestaña de Archivos, que se encuentra en el menú de la izquierda.

  • Prácticas. Tienen un valor de 20%.

Los lineamientos, el contenido y el calendario de prácticas pueden ser consultados en la pestaña de Laboratorio.


Curva

Las calificaciones finales de exámenes, tareas y prácticas estarán sujetas a la siguiente fórmula

Calif_final = Calif_inicial * X

donde Calif_inicial es el promedio individual del alumno para el rubro en cuestión, y X es una constante que toma en cuenta el promedio del grupo (Prom) para dicho rubro. La constante X se define a continuación.

Si Prom<5 o Prom>= 7.5, entonces X = 1.

Si 6.3<= Prom <7.5, entonces X = 1.065.

Si 5<= Prom <6.3, entonces X=1.05.

Por ejemplo, un alumno obtiene las siguientes calificaciones al final del semestre Calif_inicial_exámenes = 5.05, Calif_inicial_tareas = 6.98 y Calif_inicial_laboratorio = 6.5. En su grupo los promedios para exámenes, tareas y laboratorio son Prom_exámenes = 6.61, Prom_Tareas = 7.32 y Prom_laboratorio = 5.73. Así,

Calif_final_exámenes = 5.05 * 1.065 = 5.37825

Calif_final_tareas = 6.98 * 1.065 = 7.4337

Calif_final_laboratorio = 6.5 * 1.05 = 6.825‬

Por lo tanto, la calificación final del alumno es (5.37825*0.6) + (7.4337*0.2) + (6.825‬*0.2) = 6.07869‬.


Google classroom

Los anuncios y actualizaciones sobre clases, tareas, exámenes y prácticas se comunicarán a través del google classroom. Accedan a https://classroom.google.com/ e introduzcan el código de clase que se proporcionará los primeros días del semestre.