Lógica y Computabilidad

De Cuba-Wiki
Saltar a: navegación, buscar
Text-x-boo.svg Esta materia necesita que se revisen sus guías de ejercicios.
Desde el momento en que se crearon las correspondientes páginas para las guías de ejercicios ocurrieron cambios en la materia que pueden haber dejado inconsistente la numeración, nombres, cantidad o contenidos de las mismas.

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
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)
2010 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2010 Segundo cuatrimestre Parcial enunciado (pdf)
2009 Verano Recuperatorio enunciado (pdf)
2009 Verano Parcial enunciado (pdf)
2008 Primer cuatrimestre Recuperatorio enunciado (pdf)
2008 Primer cuatrimestre Parcial enunciado (pdf)
2008 Verano Recuperatorio enunciado (pdf)
2008 Verano Parcial enunciado (pdf)
2007 Verano Recuperatorio enunciado (pdf)
2007 Verano Parcial enunciado (pdf)

Lógica[editar]

Año Cuatrimestre Fecha Instancia Links
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
2010 Segundo cuatrimestre Recuperatorio (2) enunciado (pdf)
2010 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2010 Segundo cuatrimestre Parcial enunciado (pdf)
2009 Verano Recuperatorio enunciado (pdf)
2009 Verano Parcial enunciado (pdf)
2008 Primer cuatrimestre Recuperatorio enunciado (pdf)
2008 Primer cuatrimestre Parcial enunciado (pdf)
2008 Verano Recuperatorio enunciado (pdf)
2008 Verano Parcial enunciado (pdf)
2007 Verano Recuperatorio enunciado (pdf)
2007 Verano Parcial enunciado (pdf)
2006 Segundo cuatrimestre 13/10/2006 Parcial enunciado

Departamento de Matemática[editar]

Lógica[editar]

Año Cuatrimestre Fecha Instancia Links
2016 Primer cuatrimestre Parcial enunciado + resolución (pdf)
2015 Primer cuatrimestre 15/05/2015 Parcial enunciado (jpg)
2008 Segundo cuatrimestre Recuperatorio (2) enunciado (pdf)
2008 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2008 Segundo cuatrimestre Parcial enunciado (pdf)
2007 Segundo cuatrimestre Recuperatorio (2) enunciado (pdf)
2007 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2007 Segundo cuatrimestre Parcial enunciado (pdf)

Computabilidad[editar]

Año Cuatrimestre Fecha Instancia Links
2015 Primer cuatrimestre 03/07/2015 Parcial enunciado (pdf)
2010 Primer cuatrimestre Parcial enunciado (pdf), enunciado + resolución (pdf)
2008 Segundo cuatrimestre Recuperatorio (2) enunciado (pdf)
2008 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2008 Segundo cuatrimestre Parcial enunciado (pdf)
2007 Segundo cuatrimestre Recuperatorio (2) enunciado (pdf)
2007 Segundo cuatrimestre Recuperatorio enunciado (pdf)
2007 Segundo cuatrimestre 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]

Clases[editar]

Prácticas[editar]

Apuntes[editar]

Videos[editar]

Curiosidades[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]