Materia	Carrera	Plan	Año	Periodo
COMPUTABILIDAD Y COMPLEJIDAD	LIC.CS.COMP.	RD-3-1/2023	2025	2° cuatrimestre

Docente	Función	Cargo	Dedicación
APOLLONI, JAVIER MARIANO	Prof. Responsable	P.Adj Exc	40 Hs
LEGUIZAMON, MARIO GUILLERMO	Prof. Co-Responsable	P.Asoc Exc	40 Hs
VILLEGAS, MARIA PAULA	Auxiliar de Práctico	A.1ra Semi	20 Hs

El perfil del licenciado incluye el conocimiento científico necesario que le permitir analizar y entender problemas, para los que luego, pueda desarrollar y obtener una solución adecuada, utilizando los beneficios de la tecnología y, en especial, de una computadora. En este contexto, una computadora puede ser vista como un dispositivo de cómputo que realiza tanto operaciones como cálculos de manera automática y que son plasmados en un algoritmo. Al intentar dar una formalización a la idea intuitiva de algoritmo se observa rápidamente que es necesario estudiar los modelos formales de cómputo y con ellos, los lenguajes formales.

Es así que, la actividad curricular “Teoría de la Computación” dio un primer paso en este sentido, analizando los lenguajes formales y conjuntamente con ellos, los modelos formales de cómputo basados en los dispositivos de reconocimiento o aceptación (autómatas o máquinas de estados) y los modelos basados en dispositivos generadores (gramáticas).

La presente actividad curricular, “Computabilidad y Complejidad” continúa el estudio de los lenguajes formales haciendo, en una primera etapa, hincapié y profundizando en los modelos avanzados de cómputo, sus vínculos con los problemas, los algoritmos y las soluciones. En una siguiente etapa, utiliza estos modelos avanzados de cómputos como herramientas para analizar la Teoría de la Computabilidad. Esta teoría estudia las propiedades sobre los lenguajes asociados a los problemas y permite clasificarlos en decidibles y no decidibles. Con ello se establece un límite entre los problemas efectivamente resoluble (o computables) de aquellos que no pueden ser resueltos (o no computables) mediante un algoritmo.

Por último, y en una tercera etapa analiza la Teoría de la Complejidad utilizando también los modelos formales y avanzados de cómputo. En este caso, se estudian las propiedades de los lenguajes decidibles respecto al uso de los recursos, ya sea el tiempo, el espacio o algún otro. La finalidad del estudio es jerarquizar la complejidad de los lenguajes decidibles (y por ende de sus problemas asociados) para dividirlos en lenguajes (o problemas) con soluciones que usen eficientemente el recurso analizado de aquellos que no poseen hasta el momento una solución conocida que utilice eficientemente el recurso analizado.

Esta actividad curricular aborda todos los elementos teóricos y prácticos necesarios para que la/el estudiante pueda incorporar y comprender los conceptos mencionados en los párrafos anteriores. El abordaje se hará desde una perspectiva que aproxime significativamente a la/al estudiante al aprendizaje incremental y constructivista. Propiciará la integración de los contenidos de la actividad curricular con los conocimientos adquiridos en actividades curriculares previas de la carrera, principalmente en Matemática Discreta, Programación I y II, Estructura de Datos y Algoritmos I y II, entre otras, y considerará además el contexto social de la/del estudiante.

Al finalizar el curso se espera que la/el estudiante alcance los siguientes objetivos generales y específicos:

Objetivos generales:
- Vincular los aspectos teóricos y prácticos de la Teoría de Lenguajes Formales, de la Teoría de la Computabilidad y de la Teoría de la Complejidad con la realidad y los problemas de la realidad.
- Fomentar el pensamiento analítico y de interpretación para resolver problemas (de la realidad) dados como enunciados en los ejercicios prácticos utilizando el marco teórico de la materia.
- Mejorar las capacidades y habilidades de la/del estudiante para su futuro laboral.


Objetivos específicos:
-Profundizar el conocimiento de la Teoría de los Lenguajes Formales.
-Diseñar lenguajes (formales) para representar problemas de la realidad.
-Comprender conceptos y funcionamientos relacionados con los modelos avanzados de cómputo: Máquina de Turing, Funciones Recursivas, Lenguajes estructurados a frases y la correspondencia entre ellos y con los lenguajes de programación.
-Diseñar soluciones que resuelvan un problema de la realidad dado en forma de enunciado utilizando el modelo avanzado de cómputos más adecuado al problema.
- Comprender y analizar los conceptos prácticos y teóricos asociados a la Teoría de la Computabilidad utilizando la Máquina de Turing como el modelo avanzados de cómputo y a partir de ello establecer la decibilidad o no de los lenguajes (lenguajes decidibles y no-decidibles).
- Adquirir la capacidad para discernir cuándo un problema es resoluble y cuándo no lo es analizando propiedades de su lenguaje de decisión asociado.
-Comprender y analizar los conceptos vinculados a la Teoría de la Complejidad utilizando modelos avanzados de computación como la Máquina de Turing y con ello establecer la tratabilidad o no del problema al clasificarlos en P, NP, NP-completo y otros relacionados.
- Adquirir la capacidad para detectar cuándo un problema es tratable y cuándo no lo es analizando propiedades de los lenguajes decidibles.

En el transcurso del dictado de esta asignatura se trabajarán de manera transversal los siguientes ejes:

*Identificación, formulación y resolución de problemas de informática.
*Utilización de técnicas y herramientas de aplicación en la informática.
*Fundamentos para el desempeño en equipos de trabajo.
*Fundamentos para la comunicación efectiva.
*Fundamentos para el aprendizaje continuo.

Contenidos mínimos (según OCD 1/23)
Algoritmos y modelos formales de cómputo: Máquina de Turing y variantes de la Máquina de Turing. Otros modelos formales de cómputo. Tesis de Church-Turing. Teoría de la Computabilidad: Problemas y lenguajes. Evaluación de la computabilidad de los problemas de decisión: problemas decidibles y no decidibles. Teoría de la Complejidad Computacional: Computaciones acotadas en tiempo y espacio. Clases de Complejidad computacional. Relaciones entre las clases de complejidades computacionales. Problemas intratables. Clase NP. Problemas NP-Completos.

Estos contenidos mínimos se desarrollan en las siguientes unidades:


Unidad 1. Algoritmo y modelos formales de cómputo.
Introducción. Idea intuitiva de Algoritmo. Modelos formales de cómputo: Máquina de Turing. Máquina de Turing como reconocedor. Máquina de Turing como computadora de funciones. Variantes de la Máquina de Turing: extensiones sobre las Máquinas de Turing (Máquina de Turing No Determinística. Máquina de Turing con k-cintas) y restricciones sobre la Máquina de Turing (Autómata Linealmente Acotado).

Unidad 2. Otros modelos formales de cómputo: Funciones computables y otros.
Funciones recursivas primitivas. Funciones parcialmente computables: Funciones mu-recursivas (operador de minimalización). Otros modelos formales de cómputo. Equivalencia de los Modelos Formales. Tesis de Church-Turing.

Unidad 3. Teoría de la Computabilidad: Problemas y lenguajes.
Lenguajes recursivos y recursivamente enumerables. Propiedades de los lenguajes recursivos y recursivamente enumerables. Relación entre problema y lenguaje y algoritmos.

Unidad 4. Teoría de la Computabilidad: Evaluación de la computabilidad de los problemas de decisión
Problemas asociados a lenguajes formales decidibles del tipo 0, 1, 2 y 3. Problemas asociados a lenguajes no decidibles (recursivamente enumerables pero no recursivos y no recursivamente enumerables). Reducción de un problema a otro. Problema del Lenguaje Universal; Problema de Detención (Halting); Problema de Correspondencia de Post. Aplicación del Problema de Correspondencia de Post a problemas de decisión vinculados a Gramáticas Libres del Contexto. Problemas asociados a lenguajes decidibles y no decidibles. Lenguajes no recursivamente enumerables.

Unidad 5. Teoría de la Complejidad Computacional: Computaciones acotadas en tiempo y espacio.
Introducción al concepto de complejidad computacional. Complejidad temporal y espacial en Máquina de Turing. Medida de complejidad temporal. Clases de complejidades computacionales temporales y espaciales. Relación entre las complejidades computacionales temporales y espaciales.

Unidad 6. Teoría de la Complejidad: Problemas de decisión tratables e intratables
Clases P y NP. NP-completitud. Problema de Satisfactibilidad. Problemas NP-completos. Ejemplos de Problemas NP-Completos: 3-SAT, Clique, Cobertura de vértices, etc.

Durante las semanas que correspondan al dictado se abordarán las 7 unidades del curso tanto desde el contenido teórico como desde las respectivas actividades prácticas. El material de cada unidad estará disponible en el repositorio del curso para que la/el estudiante lo pueda consultar y acceder durante todo el curso.

Las actividades prácticas permitirán el desarrollo y profundización de los contenidos teóricos y será el ámbito donde la/el estudiante alcance los objetivos propuestos para el curso. Las clases prácticas consistirán principalmente en la resolución de ejercicios poniendo en práctica los conocimientos logrados en este curso y aquellos previos utilizando el material didáctico accesible desde el repositorio. En los casos apropiados la/el estudiante podrá hacer uso de las herramientas informáticas que implementan los conceptos teóricos desarrollados en el curso. Se espera que la/el estudiante utilice estas clases prácticas también como ámbito para contrastar ideas y confraternizar con sus compañeros generando y propiciando un espacio de reflexión e intercambio de ideas.

A continuación se desarrolla el plan de trabajos prácticos apuntando en cada caso las habilidades que se esperan que el alumno desarrolle en cada caso.

Plan de Trabajos Prácticos de Aula:

Práctico 1: Máquina de Turing estándar - Extensiones y simplificaciones a la MT,
-Revisar la notación, formas y estructura, ejecución y usos de la Máquina de Turing estándar (MTD).
-Pensar, diseñar y construir MTD que reconozcan y acepten las cadenas de lenguajes específicos.
-Pensar, diseñar y construir MTD que computen funciones numéricas y/o realicen procedimientos varios.
-Modelizar problemáticas de la realidad utilizando MTD.
-Entender la notación, formas y estructura, ejecución y usos de la extensión a la MTD: Máquina de Turing con k cintas (MTD-kcintas).
-Pensar, diseñar y construir MTD-kcintas que resuelvan problemas específicos.
-Entender la notación, formas y estructura, ejecución y usos de la extensión a la MTD: Máquina de Turing No Determinística (MTND).
-Pensar, diseñar y construir MTND que resuelvan problemas específicos.
-Aprender a discernir las facilidades descriptivas de los 3 modelos (MTD, MTD-kcintas, MTND) para diseñar y construir el modelo adecuado al problema a resolver.
-Analizar y comparar las similitudes y diferencias del modelo de cómputo más general existente (Máquina de Turing en cualquiera de sus variantes) y de una computadora tanto desde el poder computacional y como el descriptivo (o representacional) para resolver problemas de la realidad.

Metodología: Resolver los ejercicios utilizando lápiz y papel y compartiendo ideas con los compañeros de aula en un trabajo grupal, y la corroboración de lo realizado manualmente utilizando la herramienta JFLAP o similar, e implementar una versión simplificada y restringida del modelo de MT en una computadora haciendo uso de un lenguaje de programación.


Práctico 2: Funciones Recursivas,
-Entender la notación, los operadores de composición y recursión, la estructura, la ejecución y el usos de las Funciones Recursivas Primitivas (FRP).
-Pensar, diseñar y construir FRP que computen funciones numéricas (totales).
-Entender el operador de minimalización, su notación, su estructura, su ejecución y usos a fin de extender a la Funciones Generales (FG).
-Pensar, diseñar y construir FG que computen funciones numéricas totales y parciales.
-Extender el modelo de FRP a cualquier dominio y modelizar y resolver problemáticas de la realidad utilizando el modelo.


Metodología: Resolver los ejercicios utilizando lápiz y papel y compartiendo ideas con los compañeros de aula en un trabajo grupal, e implementar una versión simplificada y restringida del modelo de FRP en una computadora haciendo uso de un lenguaje de programación.


Práctico 3: Lenguajes Recursivos y Recursivamente Enumerables
-Entender el vínculo entre problemas y lenguajes formales.
-Analizar, entender y aprender a discernir la diferencia entre lenguajes recursivos y recursivamente enumerables.
-Entender la relación entre lenguajes recursivos y algoritmos.
-Construir algoritmos en pseudo-código que realicen los procedimientos de enumeración para lenguajes asociados a problemas de la realidad.
-Construir algoritmos en pseudo-código que computen la función característica para lenguajes asociados a problemas de la realidad.

Metodología: Resolver los ejercicios utilizando lápiz y papel y compartiendo ideas con los compañeros de aula en un trabajo grupal, e implementar en una computadora y haciendo uso de un lenguaje de programación, la función característica para algún lenguaje asociado a un problema de la realidad.


Práctico 4: Problemas decidibles y no decidibles.
-Analizar, entender y aprender a diferenciar los problemas decidibles de los problemas no decidibles.
-Pensar y diseñar codificaciones de instancias de los problemas de la realidad y que sean válidas y adecuadas para el modelo de cómputo general de Máquina de Turing.
-Analizar y diseñar soluciones a lenguajes asociados a problemas decidibles utilizando el modelo general de cómputo de la Máquina de Turing.
-Analizar, entender y resolver y encontrar soluciones (si es posible) a instancias del Problema de Correspondencia de Post (PCP).
-Analizar y entender la no decibilidad del lenguaje asociado al PCP.
-Analizar y diseñar reducciones desde el PCP a problemas relacionados a Lenguajes Libres de Contextos para determinar que los lenguajes asociados a esos problemas son no decidibles.
-Analizar y diseñar soluciones utilizando el modelo general de cómputo de la Máquina de Turing y aplicando el concepto de reducción de un problema a otro para determinar la no decidilidad de ciertos problemas.


Metodología: Resolver los ejercicios utilizando lápiz y papel y compartiendo ideas con los compañeros de aula en un trabajo grupal.


Práctico 5: Complejidad Temporal y Espacial.
-Entender el cálculo de la complejidad temporal en una Máquina de Turing de acuerdo al tamaño de la instancia de entrada (longitud de la cadena de entrada).
-Entender la manera en la que se construye la ecuación para la función de complejidad temporal asociada a una Máquina de Turing M para cadenas de una longitud n (tc_M(n)).
-Analizar una Máquina de Turing M (en cualquiera de sus variantes) y construir la ecuación para la función de complejidad temporal asociada a esa Máquina de Turing M para cadenas de una longitud n (tc_M(n)).
-Analizar la afectación que tiene la variante de Máquina de Turing utilizada para resolver el problema en la complejidad temporal asociada a ese problema.
-Analizar y entender la jerarquía de velocidades de crecimiento de la función de complejidad temporal.


Metodología: Resolver los ejercicios utilizando lápiz y papel y compartiendo ideas con los compañeros de aula en un trabajo grupal.


Práctico de Laboratorio: Problemas NP-Completos.
-Analizar y entender las clases de lenguajes o problemas P, NP y NP-Completo.
-Entender el análisis necesario para determinar que un problema es NP-Completo utilizando ejemplos teóricos.
-Analizar y entender el efecto que un problema NP-Completo causa a quién esté resolviendo un problema de la realidad con esas características.
-Vincular los desarrollos realizados para ejemplos teóricos con los necesarios para ejemplos prácticos de la realidad.

Metodología: Resolver el práctico utilizando lápiz y papel, eligiendo un problema de la realidad y compartiendo ideas con los compañeros de aula en un trabajo grupal.


A continuación se describe cómo se abordan y cómo se evalúan los ejes transversales trabajados en la asignatura:

*Identificación, formulación y resolución de problemas de informática:
¿Cómo se aborda?
Todos los prácticos se basan en abordar problemas de la realidad y/o académicos con características desafiantes para la/el estudiante, y que deben resolverse utilizando los conceptos y modelos de cómputo analizados en la teoría.

¿Cómo se evalúa?
Este eje transversal será evaluado de dos maneras diferentes. Por un lado, se realizará una evaluación formativa en la que durante la cursada se solicita la entrega de ejercicios de los prácticos realizados algunos en forma individual y otros de manera grupal. Todas las entregas tienen una corrección grupal, gradual e individual durante el proceso en le cual se desarrolla el práctico y la entrega. La corrección pretende que la/el estudiante desarrolle de manera gradual su habilidad en resolver los problemas y pueda medir su nivel de apropiación de los conocimientos y los docentes pueda guiar el proceso de aprendizaje de cada uno de los estudiantes. Y por otro lado, durante una evaluación donde la/el estudiante deberá resolver ejercicios al estilo del práctico en el marco de una evaluación (con sus respectivas recuperaciones) para acreditar los conocimientos adquiridos durante las actividades prácticas.

*Utilización de técnicas y herramientas de aplicación en la informática:
¿Cómo se aborda?
Para realizar el práctico 1 se utilizará la herramienta de diseño de modelos formales JFlap o similar y de libre disposición en internet; para realizar ejercicios y resolver problemas de los restantes prácticos se utilizará un lenguaje de programación de alto nivel; y se utilizarán editores de libre disponibilidad para redactar informes a entregar.

¿Cómo se evalúa?
Se evaluará de manera formativa, incremental y continua, verificando la habilidad adquirida por la/el estudiante durante las actividades prácticas y las entregas en la utilización y manipulación de las herramientas.


*Fundamentos para el desempeño en equipos de trabajo:
¿Cómo se aborda?
El desempeño en equipos de trabajo se aborda principalmente en el práctico de laboratorio donde partiendo de pautas establecidas por las/los docentes del curso, las/los estudiantes deben organizarse como un equipo de trabajo para elegir el problema, distribuir las actividades y resolver el práctico.

¿Cómo se evalúa?
El desempeño se evalúa observando la capacidad y habilidad de las/los estudiantes para seguir las pautas establecidas por las/los responsables del curso, llevar a cabo los actividades en un estado de armonía y co-acción entre todos los integrantes del equipo de trabajo y obtener una resolución del práctico y mostrar tanto en el informe escrito como en su exposición oral evidencia la homogeneidad como para defender su solución y que a su vez se demuestre que cada uno de los integrantes cumplió su función adecuadamente.


*Fundamentos para la comunicación efectiva:
¿Cómo se aborda?
Este eje se aborda considerando por un lado, la expresión oral a partir de la participación de la/el estudiante en cada una de las actividades del curso (clases teóricas, prácticas, entregas, debates, etc.) tanto con los docentes como con las/los otros estudiantes del curso. Y por otra lado, se aborda y considera la expresión escrita tanto en los informes de las actividades a entregar y las evaluación tanto prácticas como teóricas.

¿Cómo se evalúa?
La expresión oral se evalúa formativamente, observando a la/el estudiante su capacidad y habilidad para adquirir y utilizar el vocabulario y las expresiones propia del temario del curso de una manera efectiva y eficaz durante sus participaciones orales. Y la expresión escrita se evaluará desde la capacidad y habilidad de la/el estudiante en manejar un vocabulario riguroso, científico y adecuado tanto desde la perspectiva del área disciplinar como desde el temario propio del curso en los informes a entregar y las evaluaciones prácticas y teóricas.


*Fundamentos para el aprendizaje continuo:
¿Cómo se aborda?
Los concepto abordados en las unidades se relacionan entre sí y con conceptos aprendidos en actividades curriculares de años y cuatrimestres anteriores, y por lo tanto, la/el estudiante realizará un proceso de aprendizaje continuo e incremental a medida que avanza el desarrollo de las unidades tanto desde el punto de vista teórico como práctico. El proceso de aprendizaje lo realizará a través de la participación activa en las actividades teóricas, analizando los apuntes propios del curso y la bibliografía propuesta, además del acceso a todo el material públicamente disponible a través de la internet que la/el estudiante necesite. Este proceso de aprendizaje lo concretará también a través de las entregas que deba realizar durante el período del curso.

¿Cómo se evalúa?
La evaluación del proceso de aprendizaje continuo se realizará a través de la continua interacción y participación de la/el estudiante en cada actividad en el aula, de la corrección y posterior debate grupal de las actividades prácticas a entregar en donde la/el estudiante puede analizar y determinar por sí mismo el nivel de apropiación de los contenidos teóricos y prácticos.

La propuesta de trabajo, en lo que respecta al régimen de aprobación, está basada por un lado en la evaluación sumativa y por otro en la evaluación continua o formativa. Esta último es 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 y la metodología propuesta en la que se desarrollará el curso, son las siguientes:

A. Régimen de Regularidad:
1. Los/las estudiantes deben alcanzar un porcentaje mínimo igual o superior al 60% de asistencia y participación activa en las clases prácticas y/o actividades prácticas propuestas por los docentes durante el cursado de la materia.
2. 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 en caso de ser necesario, ejercicios extras referidos a las temáticas abordadas en los prácticos. Como parte del proceso de aprendizaje y con la finalidad de realizar un trabajo formativo y colaborativo de comprensión, los docentes efectuarán devoluciones evaluativas de las entregas. Todas las evaluaciones pueden tener una instancia de defensa oral posterior a la entrega donde la/el estudiante exponga, explique y responda dudas o inquietudes de sus compañeros y/o docentes acerca del trabajo realizado en sus entregas.
3. Cada evaluación se aprueban al alcanzar un porcentaje mínimo de setenta por ciento (70%) sobre el puntaje total de la evaluación.
4. Aprobar 1 examen parcial práctico o alguna de sus dos respectivas recuperaciones, tal como lo establece la reglamentación vigente.
5. El examen parcial se aprueba alcanzando un porcentaje mínimo de setenta por ciento (70%) sobre puntaje total del examen, y ademas habiendo desarrollado correctamente al menos el 50% de cada uno de los ejercicios involucrados en el examen.
6. Si cualquier punto no fuera cumplimentado implica que la/el estudiante pase a condición de libre.

B. Régimen de Aprobación por Promoción sin Examen Final:
1. Ídem a lo requerido para estudiantes regulares excepto que se debe alcanzar el porcentaje de asistencia solicitado por la reglamentación vigente (80%).
2. La/El estudiante tendrá que rendir y aprobar un coloquio integrador oral o escrito donde muestre su capacidad de vinculación, integración y análisis de los conceptos teóricos dados durante el transcurso del curso.
3. El examen integrador se aprueba alcanzando un porcentaje mínimo de setenta por ciento (70%) sobre el puntaje total del examen, y ademas habiendo desarrollado correctamente al menos el 50% de cada uno de los ejercicios involucrados en el examen.

**La nota final de promoción se computará promediando la nota promedio de las obtenidas en el examen parcial y las evaluaciones periódicas requeridas para la regularidad, y la nota obtenida en el coloquio integrador del ítem 2 del punto B. Cada instancia de evaluación (examen parcial, evaluaciones periódicas, coloquio integrador de promoción, etc.) se aprueba con una nota igual a 7 o superior, según lo establece la normativa vigente.


C. Régimen de Aprobación por Examen Final:
1- El examen final puede ser oral y/o escrito siendo necesario desarrollar correctamente al menos el 70% de cada punto involucrado en el examen para aprobarlo.


D. El curso no admite estudiantes en condición de Libre.

[1] J.E. Hopcroft, J. D. Ullman and R. Motwani. "Introduction to automata theory, languages and computation". Tercera Edición. Addison Wesley Publishing Company (2006).
[2] D. Wood. "Theory of computation". John Wiley & Sons, Inc. (1986)
[3] T. A. Sudkamp. "Languages and Machines: An Introduction to the Theory of Computer Science". Tercera Edición. Addison Wesley. (2005)
[4] M. Sipser. "Introduction to the Theory of computation". Tercera Edición. PWS Publishing Company (2012).
[5] P. J. Denning, J. B. Dennis and J. E. Qualitz. "Machine, languages and computation". Prentice-Hall (1978).
[6] Apuntes de la cátedra

[1] C. H. Papadimitriou and K. Steiglitz. "Combinatorial Optimization: Algorithms and Complexity". Prentice Hall (1998)
[2] M. D. Davis and E. J. Weyuker. "Computability, Complexity, and Languages: Fundamentals of Computer Science". Academic Press Inc (1993).
[3] H. R. Lewis and C. H. Papadimitriou. "Elements of the theory of computation". Segunda Edición. Prentice Hall (1998).
[4] C. Teuscher. "Alan Turing: Life and Legacy of a Great Thinker". Springer Verlag (2004).
[5] A. Hodges. "Turing". Routledge (1999)
[6] C. H. Papadimitriou. "Computational Complexity". Addison Wesley Publishing Company (1994).
[7] N. D. Jones, Computability and Complexity: From a Programming Perspective. The MIT press. (1997)

Al finalizar el curso se espera que la/el estudiante sea capaz de: (a) comprender en profundidad la teoría de los lenguajes formales y su jerarquización; (b) entender el funcionamiento de los modelos avanzados y formales de cómputo (máquina de turing, autómata linealmente acotado, funciones recursivas, etc.) y sus relaciones con los lenguajes formales; (c) relacionar los modelos avanzados y formales de cómputo con la idea intuitiva de los algoritmos y con con las estructuras y formas de los lenguajes de programación; (d) reconocer y comṕrender la relación entre problemas, problemas decidibles y lenguajes formales, lenguajes decidibles; (e) comprender con cierta profundidad la teoría de la computabilidad y sus implicancias en la posibilidad de resolver o no problemas (lenguajes decidibles y no decidibles); y (f) comprender también con cierta profundidad la teoría de la complejidad computacional y a través de ella categorizar a los problemas de acuerdo a su propiedades (problemas tratables e intratables) y sus dificultades para resolverlos (problemas de la clases P, NP y NP-Completo).

Unidad 1.
Algoritmo y modelos formales de cómputo: Máquina de Turing (extensiones y restricciones).

Unidad 2.
Otros modelos formales de cómputo: Funciones computables y otros.

Unidad 3.
Teoría de la Computabilidad: Problemas y lenguajes. Relación entre problemas y lenguajes. Lenguajes recursivos y recursivamente enumerables.

Unidad 4.
Teoría de la computabilidad: Evaluación de la computabilidad de los problemas
de decisión. Problemas decidibles y no decidibles. Reducción. Lenguaje Universal. Problema de Halting. Problema de Correspondencia de Post (y su vínculo con problemas relacionados a gramáticas libres del contexto).

Unidad 5.
Teoría de la complejidad computacional: Computaciones acotadas en tiempo y espacio. Medida de complejidad temporal. Jerarquía de complejidades temporales. Relaciones entre complejidades.

Unidad 6.
Teoría de la Complejidad: Problemas de decisión tratables e intratables. Clases P y NP. NP-completitud. Problemas NP-completos. Ejemplos.

 

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