Lógica y Computabilidad

De Cuba-Wiki
Esta página es sobre la materia del plan de estudios 1993.

Lógica y Computabilidad es una materia que estudia formalmente la lógica proposicional y la lógica de primer orden, e introduce la teoría de la computabilidad. La materia es dictada por el Departamento de Matemática en el primer cuatrimestre de cada año y por el Departamento de Computación en el verano y segundo cuatrimestre de cada año. Según el plan de la carrera, es una materia a ser cursada en tercer año. Es correlativa de Algoritmos y Estructuras de Datos II, y es requerida para cursar Paradigmas de Lenguajes de Programación y Teoría de Lenguajes.

Durante el año, la materia se cursa los miércoles y viernes a partir de las 17:00.

Programa[editar]

Abarca los temas de los capítulos 1 al 4 del libro "Computability, Complexity, and Languages" de Davis, Sigal y Weyuker

  • Computabilidad: Lenguajes de programación. Macros. Recursión. Funciones primitivas recursivas. Predicados, operadores lógicos. Minimización. Codificación de Godel. Halting Problem, universalidad. Conjuntos recursivamente enumerables. Teoremas de la recursión, del punto fijo y de Rice.
  • Lógica proposicional: Lenguaje. Semántica. Mecanismo Deductivo. Metateoremas para SP. Compacidad.
  • Lógica de primer orden: Lenguaje. Semántica. Sistema axiomático. Metateoremas para SQ. Indecidibilidad.

Contenidos[editar]

Algunos teoremas vistos en la parte de lógica:

Prácticas[editar]

Departamento de Computación[editar]

Computabilidad[editar]

Lógica[editar]

Departamento de Matemática[editar]

Lógica[editar]

Computabilidad[editar]

Parciales[editar]

Departamento de Computación[editar]

Computabilidad[editar]

Año Cuatrimestre Fecha Instancia Links
2023 Primer Cuatrimestre 30/06/2023 Recuperatorio enunciado + resolución (pdf)
2023 Primer Cuatrimestre x/06/2023 Parcial enunciado
2023 Verano 17/02/2023 Parcial enunciado, resolucion
2022 Segundo Cuatrimestre 25/11/2022 Recuperatorio enunciado (pdf)
2020 Segundo Cuatrimestre 23/10/2020 Parcial enunciado (pdf)
2020 Primer Cuatrimestre 24/07/2020 Recuperatorio enunciado (pdf)
2020 Primer Cuatrimestre 29/05/2020 Parcial enunciado + resolución (pdf)
2020 Verano 19/02/2020 Parcial enunciado, resolución
2019 Segundo cuatrimestre 11/10/2019 Parcial solución por Manu Giménez (video)
2018 Segundo cuatrimestre 23/11/2018 Recuperatorio enunciado
2018 Segundo cuatrimestre 05/10/2018 Parcial enunciado, resolución
2018 Verano 15/03/2018 Recuperatorio enunciado con resolución
2018 Verano 22/02/2018 Parcial enunciado + resolución (pdf)
2017 Segundo cuatrimestre 29/09/2017 Parcial enunciado
2017 Verano 18/03/2017 Recuperatorio enunciado
2017 Verano 21/02/2017 Parcial enunciado, resolución (pdf), resolución2 (pdf)
2016 Verano 13/02/2016 Parcial enunciado, enunciado + resolución (pdf)
2015 Segundo cuatrimestre Parcial enunciado (pdf)
2015 Verano Recuperatorio enunciado (jpg)
2015 Verano 14/02/2015 Parcial enunciado (jpg), resolución (jpg): ej 1, ej 2,
solución por Manu Giménez (video)
2014 Segundo cuatrimestre 03/12/2014 Recuperatorio enunciado (jpg), resolución (jpg): ej 2, ej 3, ej 4
2014 Segundo cuatrimestre 26/09/2014 Parcial enunciado (pdf)
2014 Verano 15/02/2014 Parcial enunciado (jpg)
2012 Segundo cuatrimestre Recuperatorio enunciado (jpg)
2011 Segundo cuatrimestre 07/10/2011 Parcial enunciado + resolución (pdf)

Lógica[editar]

Año Cuatrimestre Fecha Instancia Links
2023 Verano 13/03/2023 Parcial enunciado, resolucion
2022 Segundo Cuatrimestre 18/11/2022 Parcial enunciado + resolución (pdf)
2021 Verano 18/03/2021 Parcial enunciado + resolución (pdf)
2020 Segundo Cuatrimestre 04/10/2020 Parcial enunciado (pdf)
2020 Primer Cuatrimestre 17/07/2020 Parcial enunciado, enunciado + resolución (pdf)
2020 Primer Cuatrimestre 31/07/2020 Recuperatorio enunciado, enunciado + resolución (pdf)
2019 Verano 29/03/2019 Recuperatorio enunciado (pdf)
2018 Segundo Cuatrimestre 16/11/2018 Parcial

enunciado (pdf), resolución (pdf)

2018 Verano 15/03/2018 Parcial

enunciado (pdf), resolución (pdf)

2017 Segundo Cuatrimestre 17/11/2017 Parcial enunciado, resolución
2017 Verano 25/03/2017 Recuperatorio enunciado
2017 Verano 16/03/2017 Parcial enunciado, resolución 1, resolución 2
2016 Segundo cuatrimestre Parcial enunciado (jpg), resolución (jpg/pdf): ej 1, ej 2, ej 3, ej 4
2016 Verano 03/03/2016 Parcial enunciado, enunciado + resolución (pdf)
2015 Segundo cuatrimestre Parcial enunciado (pdf), resolución (pdf): ej 1, ej 2
2015 Verano Recuperatorio enunciado (jpg)
2015 Verano 07/02/2015 Parcial enunciado (jpg), resolución (jpg): ej 2, ej 3
2014 Segundo cuatrimestre 14/11/2014 Parcial enunciado (pdf), resolución (jpg): ej 1, ej 2, ej4

Departamento de Matemática[editar]

Lógica[editar]

Año Cuatrimestre Fecha Instancia Links
2023 Primer cuatrimestre 07/07/2023 Recuperatorio Enunciado + Resolución (pdf)
2018 Primer cuatrimestre recuperatorio Enunciado+resolucion
2018 Primer cuatrimestre Parcial enunciado + resolución (pdf)
2016 Primer cuatrimestre Parcial enunciado + resolución (pdf)
2015 Primer cuatrimestre 15/05/2015 Parcial enunciado (jpg)

Computabilidad[editar]

Año Cuatrimestre Fecha Instancia Links
2018 Primer cuatrimestre 20/07/2018 Recuperatorio enunciado (pdf), enunciado + resolución (pdf), Resolucion
2018 Primer cuatrimestre 06/06/2018 Parcial enunciado + resolución (pdf)
2015 Primer cuatrimestre 03/07/2015 Parcial enunciado (pdf)

Finales[editar]

Departamento de Computación[editar]

En general toma Santiago Figueira. Santiago toma todos los teoremas que aparecen en las diapositivas. No se confíen si algún teorema no aparece en los finales a continuación, se toman todos.

Departamento de Matemática[editar]

Recursos[editar]

Prácticas[editar]

Apuntes[editar]

Videos[editar]

Bibliografía recomendada[editar]

  • Davis, Martin D.; Sigal, Ron y Weyuker, Elaine J., Computability, complexity and languages: fundamentals of theoretical computer science, San Diego: Academic Press, 1994 (Circulante 681 334 Davis en la Biblioteca Central)
  • Mendelson, Elliot, Introduction to mathematical logic, Princeton, N.J.: Van Nostrand, c1964 (Circulante 510 600 Mendelson en la Biblioteca Central)

Enlaces externos[editar]