Fundamentación y Objetivos

El contenido de esta materia corresponde a los elementos clásicos y contemporáneos de fundamentos de ciencias de la computación.
Los tópicos fundamentales a seguir en la materia son: teoría de autómatas, lenguajes formales, computabilidad de máquinas de Turing, redes de Petri y funciones recursivas.

El objetivo de desarrollar estos temas en la currícula de segundo año es familiarizar a los alumnos con los problemas de la computación clásica y mostrarles la contemporaneidad de los mismos. Así mismo se busca enseñarles los elementos teóricos mínimos que fundamentan la ciencia de la computación para que asimilen cómo los desarrollos teóricos clásicos son aún hoy un peldaño hacia nuevas aplicaciones.

Contenidos

Programa Sintético

Autómatas Finitos - Lenguajes Regulares.

Autómatas a Pila - Lenguajes Libres de Contexto - Lenguajes Sensibles al Contexto.

Computabilidad: Máquinas de Turing y Tesis de Turing-Church - Lenguajes Estructurados por Frases.

Redes de Petri.

Funciones Recursivas Parciales.

Programa Analítico

Autómatas Finitos - Lenguajes Regulares.

Autómatas Finitos. Reconocedores. Traductores. Diagrama de Estados. Autómatas Finitos no Deterministas. Equivalencia entre AF deterministas y no deterministas. Minimización de autómatas. Propiedades de lenguajes aceptados por autómatas. Expresiones regulares. Relación entre gramáticas regulares, lenguajes regulares y autómatas finitos. Elementos para la determinación de si un lenguaje dado es o no regular. Pumping Lemma.

Autómatas a Pila - Lenguajes Libres de Contexto - Lenguajes Sensibles al Contexto.

Gramáticas Libres de Contexto. Clasificación de Chomsky. Relación entre gramáticas regulares y libres de contexto. Arboles de Derivación. Ambiguedad. Notación BNF. Autómata a Pila. No determinismo. Relación entre los autómatas a Pila y las gramáticas libres de contexto. Propiedades de los lenguajes libres de contexto. Pumping Lemma. Gramáticas Sensibles al Contexto. Autómatas acotados linealmente. Características de los lenguajes de programación procedurales que forman lenguajes libres de contexto y sensibles al contexto.

Computabilidad: Máquinas de Turing y Tesis de Turing-Church - Lenguajes Estructurados por Frases.

Computabilidad: Máquinas de Turing. Procedimiento Efectivo. Funciones Turing-Computables. Lenguajes Turing-Decidibles y Turing-Aceptables. Tesis de Turing-Church. Máquina Universal de Turing. Gramáticas estructuradas por frases. Lenguajes recursivos y recursivos enumerables. Problemas de decisión. El problema de la parada. Reducibilidad al problema de la parada. Poder computacional de las gramáticas estructuradas por frases en relación con el de las máquinas de Turing.

Redes de Petri.

Definición de red de Petri, marcado y transición. Redes de Petri como reconocedoras de lenguajes, secuencia de disparos, lenguajes de secuencias de disparos. Concurrencia y Conflicto. Redes de Petri como modelos de sistemas concurrentes. Etiquetado. Propiedades de clausura de los lenguajes reconocidos por redes de Petri. Poder computacional de las Redes de Petri en relación con el de las máquinas de Turing.

Funciones Recursivas Parciales.

Funciones recursivas primitivas sobre naturales. Funciones recursivas primitivas sobre cadenas. Predicados recursivos. Minimización no acotada. Relación entre las funciones recursivas parciales y las máquinas de Turing. Relación entre las funciones recursivas parciales y los lenguajes de programación procedurales.

Se tomarán dos exámenes parciales con sus respectivos recuperatorios. En cualquier caso, un parcial se considera aprobado cuando cumple con el 60% de lo requerido, sin errores conceptuales graves.

Mg. Gerardo Parra. Asistente de Docencia a Cargo de Cátedra.
AC. Ana Carolina Alonso de Armiño. Ayudante de Primera
AC. Daniel Dolz. Ayudante de Primera.
Gastón Tagni. Ayudante Alumno.
AC. Luciana Benotti. Ayudante de Primera.