Lenguajes Formales y Autómatas

Semestre 2018-I

Ingeniería en Computación, FI/UNAM

Lenguajes Formales y Autómatas

Semestre 2018-I

Ingeniería en Computación, FI/UNAM

para ingenieros

Información

Salón Clase

DS01 1670

Horario

Mártes y jueves de 7:00 a 9:15

Número de cláses

32

Página curso

http://turing.iimas.unam.mx/~ivanvladimir/page/curso_lfya

​

Objetivo

​

Estudiar:

• las propiedades fundamentales de las máquinas computacionales desde un punto de vista teórico

​

• entender la unificación del concepto de computación

Introducción

¿Qué es computación?

​

¿Qué es una máquina computacional?

​

¿Qué relaciones hay entre los tipos de máquinas?

​

¿Relación entre máquina, el conjunto de entradas que recibe y una descripción formal de estos conjuntos?

Antecedentes

No está serializada, pero es necesario:

• Teoría de conjuntos
• Algoritmos y estructuras de datos
• Matemáticas discretas

Otras habilidades

​

• Sentido común
• Abstracción
• Lógica
• Imaginación

Consecuente

Serializada con

• Compiladores

Pero importante además en:

• Lenguajes de programación
• Vida profesional: expresiones regulares
• Conceptualización de problemas computacionales

Por ejemplo

Temario

​

1. Introducción

​

• Gramáticas regulares y autómatas de estado finito

http://www.ingenieria.unam.mx/programas_academicos/licenciatura/Computacion/06/lenguajes_formales_y_automatas.pdf

Temario

3. Gramáticas de contexto libre y autómatas tipo push-down

​

• Gramáticas de contexto sensitivo y autómatas tipo push-down doble y autómatas lineales con frontera

http://www.ingenieria.unam.mx/programas_academicos/licenciatura/Computacion/06/lenguajes_formales_y_automatas.pdf

Temario

​

• Gramáticas de estructura de frase y máquina de Turing

​

• Indecibilidad

http://www.ingenieria.unam.mx/programas_academicos/licenciatura/Computacion/06/lenguajes_formales_y_automatas.pdf

Calendario

​

​

Revisar aquí

​

​

​

​

Bibliografía

​

​

Revisar aquí

​

Metodología

• Tres bloques
• Sesiones de teoría (jueves)
• Sesiones de ejercicios (martes)

​

• Al final de cada bloque
• Una sesión de revisión
• Una serie por bloque
• Una sesión de presentaciones por alumnos

Asistencia

Para evitar final 70% de asistencia.

7:00

​

Habrá un receso de 10 minutos a las 8:10

• Quienes tengan duda usen el receso para platicar conmigo

​

Calificación

• Libreta de ejercicios: 25%

​

• Series: 50%

​

• Presentación de una solución: 25%

​

​

​

Libreta de ejercicios

• Actividad en sesión de ejercicio, dos tipos
• Personal
• y en equipo
• Se especifica un tiempo por ejercicio
• Los ejercicios deben estar concentrados en un solo lugar: con fecha y firma al final
• En sesión de revisión asiento el total resuelto con firma

​

​

​

Reposición ejercicios

• Sino tienen los ejercicios, los pueden reponer

​

• Pero tienen que hacer todos, Todos, TODOS los ejercicios de las sesiones.

​

​

​

Serie

• Consiste de dos a tres problemas, múltiple aspectos ¡Aleatorios!
• El día de presentaciones se entregan al inicio las soluciones ¡a mano!
• Se vale copiar con atribución
• Hicimos equipo
• Se lo copie a mi compañera o compañero

​

​

Presentación

• Mediante una tómbola se escoge a alguien para que presente una de sus soluciones
• Tener su solución en formato de presentación en pdf
• Tiene tres minutos (3 slides)
• Sino tiene la presentación en pdf lista, son 3 puntos menos de este rubro
• Existe la posibilidad de no salir sorteado (calificación gratis)

​

​

​

Calificación

​

Libreta ejercicios (25%) + serie (50%) + presentación (25%)

Primer final

Calificación no aprobatoria al final, sin 70% de asistencia o voluntario (subir calificación)

​

• Calificación curso 20%
• Calificación final 80%

​

​

​

Segundo final

Calificación no aprobatoria hasta aquí o voluntario, haber hecho el primer final

​

• Calificación curso 40%
• Calificación final 60%

​

​

​

Calificación

Libreta ejercicios + serie + presentación

​

O

​

(Libreta ejercicios + serie + presentación) + final

​

​

Participación

• 1.6 puntos extra sobre calificación
• Hacer preguntas a dudas
• Dar opiniones sobre los temas
• Responder a preguntas mías
• Pasar a pizarrón (+2)
• Corregir errores en notas, pizarrón (+2)

Calificación

Libreta ejercicios + serie + presentación + puntos extra

o

(Libreta ejercicios + serie + presentación) + final + puntos extra

​

​

NPs

NPs dos casos:

• Explicitamente me informan que no presentarán el curso, antes de 3 de actubre

​

• No entregan ningúna serie

​

Preguntas

¿?

Experiencia pasada 2016-II

Experiencia pasada 2017-I

Mis datos

• Ivan Vladimir Meza Ruiz

http://turing.iimas.unam.mx/~ivanvladimir

ivanvladimir@gmail.com

​

• Página curso

http://turing.iimas.unam.mx/~ivanvladimir/page/curso_lfya�

• Trabajo en IIMAS/UNAM

​

​