Materia	Carrera	Plan	Año	Periodo
FUNDAMENTOS DE COMPUTACION	ING. INFORM.	026/12- 08/15	2021	1° cuatrimestre
FUNDAMENTOS DE COMPUTACION	ING. EN COMPUT.	28/12	2021	1° cuatrimestre

Docente	Función	Cargo	Dedicación
APOLLONI, JAVIER MARIANO	Prof. Responsable	P.Adj Exc	40 Hs
LEGUIZAMON, MARIO GUILLERMO	Prof. Colaborador	P.Asoc Exc	40 Hs
ROGGERO, PATRICIA BEATRIZ	Prof. Co-Responsable	P.Asoc Exc	40 Hs
LOOR, FABRICIO	Auxiliar de Práctico	A.1ra Simp	10 Hs

Dado que el estudio de la teoría de lenguajes es de gran importancia, para entender de manera formal, las características de los lenguajes de programación, desde el punto de vista de su generación (a través de dispositivos generadores) y su reconocimiento (a través de dispositivos reconocedores o autómatas). Asimismo, el estudio de los modelos formales de computación es necesario para el entendimiento de la idea intuitiva de algoritmo. A través de dichos modelos formales es posible el estudio de la teoría de computabilidad y complejidad, la cual nos permite dividir en clases de problemas no-decidibles y decidibles, y dentro de estos últimos, establecer jerarquías de clases de complejidad, tanto temporal como espacial. Es por ello que, se abordarán los elementos teóricos y prácticos, necesarios, para que los estudiantes puedan incorporar y comprender estos conceptos.
Se propiciará en el alumno una aproximación significativa al aprendizaje favoreciendo la integración de los contenidos de una manera constructivista (pero además considerando el contexto social actual).

Al finalizar el curso se espera que el estudiante sea capaz de comprender la forma en que funciona cada Autómata y la correspondencia entre Autómatas, Gramáticas y Lenguajes, particularmente Lenguajes de Programación. Además, comprender los modelos avanzados de computación, como Máquina de Turing, a los efectos de aprender, con cierta profundidad, la teoría y práctica de computabilidad (lenguajes decidibles y no-decidibles) y complejidad computacional (problemas NP-completos y otros relacionados). Se espera también que los estudiantes puedan vincular ciertos aspectos de la teoría de lenguajes con aplicaciones de la vida real.

Bolilla 1. Nociones Básicas
Alfabeto. Sentencia. Lenguaje. Representación de los lenguajes. Dispositivos generadores y reconocedores. Concepto general de Gramáticas y Autómatas, como dispositivos generadores de lenguajes y reconocedores de lenguajes, respectivamente. Relación general entre autómata y gramática. Jerarquía de Chomsky.

Bolilla 2. Lenguajes Regulares
Lenguajes Regulares (Tipo 3). Autómata Finito Determinístico (AFD) y No-Determinístico (AFND), AFND con transiciones épsilon, Aplicaciones. Expresiones regulares (ER). Equivalencia entre: AFD - AFND, AFD - AFND epsilon, ER - AFND epsilon. Minimización de AFD. Propiedades de clausura de los Lenguajes Regulares.

Bolilla 3. Lenguajes Libres del Contaxto
Gramáticas y lenguajes libres del contexto (Tipo 2). Motivación e introducción. Árbol de derivación. Frontera. Forma sentencial izquierda y derecha. BNF. Ambigüedad. Autómatas a Pila (Push Down). Autómata Push-Down determinístico. Configuraciones. Lenguaje aceptado por Pila Vacía y Estado Final. Equivalencia entre GLC y APD.

Bolilla 4. Máquina de Turing y Computabilidad
Máquinas de Turing (MT). MTs como reconocedor. MT como computadora de funciones numéricas. Extensiones de MTs: No-Determinísticas, con k-cintas, otros modelos. Otros modelos de computación equivalentes a MTs. Equivalencia de los Modelos Formales. Tesis de Church-Turing. Concepto de Algoritmo y Computabilidad.

Bolilla 5. Decibilidad
Problemas decidibles y no-decidibles. Conjuntos recursivos y recursivamente enumerables. Propiedades de los lenguajes recursivos y recursivamente enumerables. MT Universal. Concepto de reducción de un problema a otro. Problema de Detención (Halting). Problemas decidibles y no-decidibles para Lenguajes Tipo 0, 1, 2 y 3.

Bolilla 6. Complejidad Computacional
Complejidad Computacional. Complejidad Temporal y Espacial. Notación O-grande. Jerarquías de complejidades temporales y espaciales. Relación entre complejidades temporales y espaciales. Otras notaciones de complejidad. Problemas tratables e intratables. Clases P y NP. NP-Completitud. Problema de Satisfactibilidad (SAT). Teorema de Cook. Problemas NP-Completos (aplicación del concepto de reducción): 3-SAT, Clique, Cobertura de vértices, etc.

Las clases prácticas consistirán de la resolución de ejercicios donde el alumno pueda también utilizar herramientas informáticas que implementan los conceptos teóricos desarrollados en la asignatura, de manera que pueda poner en práctica los conocimientos adquiridos.

Prácticos de Aula:
Práctico 1: Alfabetos - Cadenas - Lenguajes.
Hacer un análisis de la representación finita de lenguajes, en particular de lenguajes de programación. La metodología a utilizar es la resolución de ejercicios en lápiz y papel.

Práctico 2: Lenguajes Regulares, Autómatas Finitos. Construir autómatas finitos determinísticos y no determinísticos, expresiones regulares. Proponer utilizando autómatas finitos modelos de problemas de la vida real.
La metodología a utilizar es la resolución de ejercicios en lápiz y papel y la corroboración de lo realizado manualmente utilizando la herramienta JFLAP o similar.

Práctico 3: Equivalencias entre Autómatas Finitos y Expresiones Regulares. Minimización.
Aplicación de algoritmos que muestran las equivalencias y uso de algoritmos de minimización. Resolución de ejercicios en lápiz y papel. Corroboración de lo realizado manualmente utilizando herramientas de software JFLAP o similar.

Práctico 4: Gramáticas Libres del Contexto - Autómatas Push-Down.
Resolución de ejercicios en lápiz y papel, básicamente relacionados a lenguajes de programación, utilizando GLC, BNF y APD. Corroboración de los ejercicios realizados a mano utilizando la herramienta de software JFLAP o similar.

Práctico 5: MTs, Extensiones de MTs, ALA. Modelos equivalentes a MT. Se pretende plantear ejercicios que muestren las diferentes formas de resolverlos mediante los distintos modelos de computación.

Práctico 6: Problemas decidibles y no-decidibles. Aplicación del concepto de reducción de un lenguaje a otro para determinar la decidibilidad de problemas relevantes en la teoría de la computación. También se consideran aquí problemas conocidos de la teoría de lenguajes. MTs es el modelo computacional sobre el cual estarán basadas las reducciones a aplicar.

Práctico 7: Complejidad Computacional y NP-Completitud. Similar al práctico 6, pero en este caso, se incluirán varios problemas de la vida real para determinar la complejidad inherente de los mismos a través del uso del concepto de reducción. La primer parte del práctico incluirá problemas de índole general y teórico, mientras que la segunda parte estará orientada a promover la investigación del alumno acerca de la complejidad de ciertos problemas de la vida real y para los cuales se pueda establecer similitudes en cuanto su complejidad inherente respecto a problemas vistos en la primera parte del práctico o en teoría.

Práctico de Laboratorio:
Analizar una GLC para un hipotético lenguaje de programación y desarrollar e implementar un algoritmo que obtenga cadenas válidas asociadas a ese lenguaje.

La propuesta de trabajo, en lo que respecta al régimen de aprobación, está basada en la evaluación continua o formativa, con el objetivo de relacionar la información sobre la evolución del proceso de aprendizaje de los/las estudiantes con las características de la acción didáctica, a medida que se desarrollan y progresan las actividades de enseñanza y aprendizaje. En este sentido, el estudiante puede regularizar (para luego rendir el examen final) o promocionar. Las condiciones en función a la modalidad de dictado mayormente no presencial y a la metodología propuesta en la que se desarrollará el curso, son las siguientes:

A. Régimen para Estudiantes Regulares
Entregar, en tiempo y forma, y aprobar el 100% de las evaluaciones periódicas propuestas por la cátedra, las cuales consistirán en ejercicios de los prácticos de aula, y/o ejercicios prácticos extras propuestos por los docentes, y/o prácticos de laboratorio, y/o trabajos de investigación de temas o problemas particulares sobre los contenidos de la materia.

Con la finalidad de realizar un trabajo colaborativo de comprensión, se efectuarán devoluciones evaluativas como parte del proceso de aprendizaje. Además, todas las evaluaciones pueden tener una instancia de defensa oral posterior a la entrega donde el/la estudiante exponga, explique y responda dudas o inquietudes de sus compañeros y/o docentes acerca del trabajo realizado en sus entregas.

Los/las estudiantes deben contar además con un porcentaje mínimo igual o superior al 60% de participación activa en todas las actividades sincrónicas y asíncronas propuestas por los docentes durante el cursado de la materia.

Nota:
1. Las evaluaciones se aprueban con un porcentaje mínimo de setenta por ciento (70%).
2. Si cualquier punto no fuera cumplimentado implica que el estudiantes pase a condición de libre.

B. Régimen para Estudiantes Promocionales
1. Ídem a lo requerido para estudiantes regulares excepto que se debe alcanzar un porcentaje de asistencia igual o superior al 80%.
2. Además el estudiante tendrá que desarrollar y aprobar un coloquio integrador oral o escrito que incluya el análisis y discusión de conceptos teóricos dados en el curso. Dicho coloquio podrá ser de forma virtual o presencial (en el caso que estén dadas las condiciones para ello).

La nota final de promoción se computará promediando, las notas obtenidas en las evaluaciones requeridas para la regularidad y la nota obtenida en el ítem 2 del punto B. En todas las evaluaciones, la nota obtenida por el alumno debe ser igual a 7 o superior, según lo establece la normativa vigente.

C. El curso no admite rendir el examen final en condición de Libre.

D. El examen final puede ser oral y/o escrito.

[1] - Hopcroft J.; Ullman J.; Motwani R. – “Introduction to automata theory, languages and computation”. Addison Wesley. 3° Edición. (2007).
[2] - Sudkamp, T.A. - “Languages and Machines (An Introduction to the Theory of Computer Science)”. Addison Wesley. 3° Edición. (2005).
[3] - Kozen, D. – “Theory of computation (Texts in Computer Science)”. Springer. 1° Edición (2006).
[4] - Sipser, M. – “Introduction to the Theory of Computation”. PWS Publishing Company. 2° Edición. (2005).
[5] - Martfn-Vide C., Paun, G. y Mitrana, V. (Editores), Formal Languages and Applications (Studies in Fuzziness and Soft Computing). Springer (2004).
[6] - Libkin, L. – “Elements of Finite Model Theory.” Springer (2004).
[7] - Ramón Brena Pinero "Lenguajes Formales y Autómatas" (1997).
[8] - Notas de Clase de la Cátedra.

[1] - Wood, D. – “Theory of computation”. John Wiley & Sons, Inc. (1988).
[2] - Hopcroft J. y Ullman J.- “Introduction to automata theory, languages and computation”. Addison Wesley (1979).

Al finalizar el curso se espera que el alumno sea capaz de comprender la forma en que funcionan los diferentes tipos de autómatas y la correspondencia entre cada tipo, gramática y lenguajes, particularmente en lo referido a lenguajes de programación. Además, comprender los modelos avanzados de computación, como Máquina de Turing, a los efectos de aprender, con cierta profundidad, la teoría y práctica de computabilidad (lenguajes decidibles y no-decidibles) y complejidad computacional (problemas NP-completos y otros relacionados).

Bolilla 1: Sentencias. Lenguajes. Representación de Lenguajes. Jerarquía de Chomsky.

Bolilla 2: Lenguajes Regulares. Autómatas Finitos. Expresiones Regulares. Gramáticas Regulares. Minimización. Propiedades.

Bolilla 3: Gramáticas Libres del Contexto. Autómatas Push-Down. BNF.

Bolilla 4: Máquinas de Turing. Extensiones de Máquinas de Turing. Equivalencia entre los modelos de Máquinas de Turing.

Bolilla 5: Lenguajes Recursivos y Recursivamente Enumerables. Problemas decidibles y no-decidibles.

Bolilla 6: Complejidad Computacional y NP-Completitud. Clases de Complejidad Temporal y Espacial.

De acuerdo al art. 2 de la Resolución Rectoral 1404/20, el Calendario Académico de la Universidad Nacional de San Luis establece que el Primer Cuatrimestre sea de 14 semanas. A los efectos de que se impartan todos los contenidos y se respete el crédito horario establecido en el Plan de Estudios de la carrera para esta asignatura, se establece que se de cómo máximo 7 horas por semana distribuidas en teorías, prácticos de aula y laboratorio y consultas, hasta completar las 90 horas correspondientes al Crédito Horario Total de la asignatura.

Además, en función de la situación epidemiológica provocada por la pandemia COVID-19, los contenidos teóricos y prácticos de este programa se desarrollará mayoritariamente en MODALIDAD NO PRESENCIAL, utilizando para tal fin diferentes herramientas virtuales, para el dictado de clases teóricas, clases de práctica, consultas, etc.


Correo de contacto: javierma@email.unsl.edu.ar (Javier Apolloni)