Diferencia entre revisiones de «Lógica y Computabilidad»

De Cuba-Wiki
(Agregada otra resolución del parcial del 21/02/2017.)
(No se muestran 39 ediciones intermedias de 23 usuarios)
Línea 32: Línea 32:


==== Lógica ====
==== Lógica ====
* [[Práctica 4 (LyC Verano) | Práctica 4 - Logica Proposicional]]
* '''2do Cuatrimestre 2017'''
* [[Práctica 5 (LyC Verano) | Práctica 5 - Sistemas Deductivos y Compacidad]]
** [[Práctica 5 LyC 2do Cuatrimestre 2017 (Depto. de Computación)|Práctica 5 - Sistemas Deductivos y Compacidad]]
* [[Práctica 6 (LyC Verano) | Práctica 6 - Logica de Primer Orden]]
* '''Verano'''
* [[Práctica 7 (LyC Verano) | Práctica 7 - Sistemas Deductivos, Completitud y Compacidad (1º Orden)]]
** [[Práctica 4 (LyC Verano) | Práctica 4 - Logica Proposicional]]
** [[Práctica 5 (LyC Verano) | Práctica 5 - Sistemas Deductivos y Compacidad]]
** [[Práctica 6 (LyC Verano) | Práctica 6 - Logica de Primer Orden]]
** [[Práctica 7 (LyC Verano) | Práctica 7 - Sistemas Deductivos, Completitud y Compacidad (1º Orden)]]


=== Departamento de Matemática ===
=== Departamento de Matemática ===
Línea 58: Línea 61:
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 2019 || Segundo cuatrimestre              || 11/10/2019 || Parcial          || [https://youtu.be/C3tRCfueIx0 solución por Manu Giménez (video)]
|-
| 2018 || Segundo cuatrimestre              || 23/11/2018 || Recuperatorio|| [[Media:Recuperatorio Computabilidad 23-11-2018.pdf|enunciado]]
|-
| 2018 || Segundo cuatrimestre              || 05/10/2018 || Parcial    || [[Media:Parcial Computabilidad 2018-10-05.pdf|enunciado]], [[Media:Resolucion-parcial-computabilidad-2018-2c.pdf|resolución]]
|-
| 2018 || Verano                            || 15/03/2018 || Recuperatorio    || [[Recuperatorio_de_computabilidad_Verano_2018_(DC)|enunciado con resolución]]
|-
| 2018 || Verano                            || 22/02/2018 || Parcial    || [[Media:Parcial_de_computabilidad_Verano_2018_(LyC).pdf|enunciado + resolución (pdf)]]
|-
| 2017 || Segundo cuatrimestre              || 29/09/2017 || Parcial    || [[Media:Parcial_de_computabilidad_Segundo_cuatrimestre_2017_(LyC).pdf|enunciado]]
|-
|-
| 2017 || Verano              || 18/03/2017 || Recuperatorio    || [[Recuperatorio de computabilidad Verano 2017 (LyC)|enunciado]]
| 2017 || Verano              || 18/03/2017 || Recuperatorio    || [[Recuperatorio de computabilidad Verano 2017 (LyC)|enunciado]]
Línea 105: Línea 120:
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 2019 || Verano              || 29/03/2019 || Recuperatorio|| [[Media:Recuperatorio Computabilidad 29-03-2019.pdf|enunciado (pdf)]]
|-
| 2018 || Segundo Cuatrimestre || 16/11/2018 || Parcial          ||
[[Medio:LyC_2parcial_16-11-18_depto_de_computación_enunciado.pdf|enunciado (pdf)]],
[[Media:LyC_2parcial_16-11-18_depto_de_computación_resolucion.pdf|resolución (pdf)]]
|-
| 2018 || Verano || 15/03/2018 || Parcial          ||
[[Medio:LyC_2parcial_15-03-18_depto_de_computación.pdf|enunciado (pdf)]], [[Media:LyC_2parcial_15-03-18_depto_de_computación_resolucion.pdf|resolución (pdf)]]
|-
| 2017 || Segundo Cuatrimestre || 17/11/2017 || Parcial          || [[Medio:LyC_2parcial_17-11-17_depto_de_computacion.pdf|enunciado]], [[Media:LyC_2parcial_17-11-17_depto_de_computación_resolucion.pdf|resolución ]]
|-
| 2017 || Verano              || 25/03/2017 || Recuperatorio    || [[Recuperatorio de Lógica Verano 2017 (LyC)|enunciado]]
|-
|-
| 2017 || Verano              || 16/03/2017 || Parcial          || [[Parcial de Lógica Verano 2017 (LyC)|enunciado]], [[Media:LyC_2parcial_16-03-17.pdf|resolución 1]], [[Media:LyC_2parcial_16-03-17_bis.pdf|resolución 2]]
| 2017 || Verano              || 16/03/2017 || Parcial          || [[Parcial de Lógica Verano 2017 (LyC)|enunciado]], [[Media:LyC_2parcial_16-03-17.pdf|resolución 1]], [[Media:LyC_2parcial_16-03-17_bis.pdf|resolución 2]]
Línea 118: Línea 146:
| 2015 || Verano              || 07/02/2015 || Parcial          || [[Media:LyC_logica_07-03-15.jpg|enunciado (jpg)]], resolución (jpg): [[Media: LyC_2parcial_07-02-15_ej2.jpg|ej 2]], [[Media: LyC_2parcial_07-02-15_ej3.jpg|ej 3]]
| 2015 || Verano              || 07/02/2015 || Parcial          || [[Media:LyC_logica_07-03-15.jpg|enunciado (jpg)]], resolución (jpg): [[Media: LyC_2parcial_07-02-15_ej2.jpg|ej 2]], [[Media: LyC_2parcial_07-02-15_ej3.jpg|ej 3]]
|-
|-
| 2014 || Segundo cuatrimestre || 14/11/2014 || Parcial          || [[Media:LyC_2parcial_14-11-14.pdf|enunciado (pdf)]], resolución (jpg): [[Media:LyC_2parcial_14-11-14_ej1.jpg|ej 1]], [[Media:LyC_2parcial_14-11-14_ej2.jpg|ej 2]]
| 2014 || Segundo cuatrimestre || 14/11/2014 || Parcial          || [[Media:LyC_2parcial_14-11-14.pdf|enunciado (pdf)]], resolución (jpg): [[Media:LyC_2parcial_14-11-14_ej1.jpg|ej 1]], [[Media:LyC_2parcial_14-11-14_ej2.jpg|ej 2]], [[Solución Ejercicio 4 Parcial Lógica 14/11/2014 (Lógica y Computabilidad - Departamento de Computación)|ej4]]
|-
|-
| 2010 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:10recu2logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
| 2010 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:10recu2logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
Línea 150: Línea 178:
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 2018 || Primer cuatrimestre  ||            || recuperatorio    || [https://drive.google.com/file/d/1kA1wNiMcucfjzprubwmZIlb4W0H0UQgN/view?usp=sharing Enunciado+resolucion]
|-
| 2018 || Primer cuatrimestre  ||            || Parcial          || [[Medio:logica_1parcial_01-06-2018.pdf|enunciado + resolución (pdf)]]
|-
|-
| 2016 || Primer cuatrimestre  ||            || Parcial          || [[Medio:parcial_2016_1c_1p.pdf|enunciado + resolución (pdf)]]
| 2016 || Primer cuatrimestre  ||            || Parcial          || [[Medio:parcial_2016_1c_1p.pdf|enunciado + resolución (pdf)]]
Línea 171: Línea 203:
{| class="wikitable sortable"
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 2018 || Primer cuatrimestre                || 20/07/2018 || Recuperatorio  || [[Media:LyC_2recu_20-07-18_consigna.pdf|enunciado (pdf)]], [[Media:LyC_2recu_20-07-18_resuelto.pdf|enunciado + resolución (pdf)]], [https://drive.google.com/open?id=19PfPR8ua-fOFtoq_u-ygbwxDLdqSuHta Resolucion]
|-
| 2018 || Primer cuatrimestre  || 06/06/2018 || Parcial          || [[Medio:LyC_2parcial_06-07-2018.pdf|enunciado + resolución (pdf)]]
|-
|-
| 2015 || Primer cuatrimestre  || 03/07/2015 || Parcial          || [[Medio:LyC_2parcial_03-07-15.pdf|enunciado (pdf)]]
| 2015 || Primer cuatrimestre  || 03/07/2015 || Parcial          || [[Medio:LyC_2parcial_03-07-15.pdf|enunciado (pdf)]]
Línea 209: Línea 245:
* [[Final del 10/03/17 (Lógica y Computabilidad) | Final del 10/03/17]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 10/03/17 (Lógica y Computabilidad) | Final del 10/03/17]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 22/06/17 (Lógica y Computabilidad) | Final del 22/06/17]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 22/06/17 (Lógica y Computabilidad) | Final del 22/06/17]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 21/12/17 (Lógica y Computabilidad) | Final del 21/12/17]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 22/02/18 (Lógica y Computabilidad) | Final del 22/02/18]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 17/05/18 (Lógica y Computabilidad) | Final del 17/05/18]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 07/03/19 (Lógica y Computabilidad) | Final del 07/03/19]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 24/04/19 (Lógica y Computabilidad) | Final del 24/04/19]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 12/05/19 (Lógica y Computabilidad) | Final del 12/05/19]]: Tomado por Santiago Figueira (Escrito)


=== Departamento de Matemática ===  
=== Departamento de Matemática ===  
Línea 214: Línea 256:
* [[Final del 10/09/14 (Lógica y Computabilidad) | Final del 10/09/14]]: Tomado por Alejandro Petrovich (Escrito)
* [[Final del 10/09/14 (Lógica y Computabilidad) | Final del 10/09/14]]: Tomado por Alejandro Petrovich (Escrito)
* [[Final del 21/10/14 (Lógica y Computabilidad) | Final del 21/10/14]]: Tomado por Alejandro Petrovich (Escrito) (resuelto)
* [[Final del 21/10/14 (Lógica y Computabilidad) | Final del 21/10/14]]: Tomado por Alejandro Petrovich (Escrito) (resuelto)
* [[Final del 23/10/18 (Lógica y Computabilidad) | Final del 23/10/18]]: Tomado por Alejandro Petrovich (Escrito)
* [[Final del 13/11/18 (Lógica y Computabilidad) | Final del 13/11/18]]: Tomado por Alejandro Petrovich (Escrito) (resuelto 50%)


== Recursos ==
== Recursos ==
Línea 243: Línea 287:


== Enlaces externos ==
== Enlaces externos ==
*[http://www.dc.uba.ar/lyc Pagina Oficial de la Materia (DC)]
*[http://www.dm.uba.ar/materias/logica_computabilidad/ Pagina Oficial de la Materia (DM)]
*[http://www.dm.uba.ar/materias/logica_computabilidad/ Pagina Oficial de la Materia (DM)]



Revisión del 18:38 14 oct 2019

Plantilla:Revisar guías 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

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

Algunos teoremas vistos en la parte de lógica:

Prácticas

Departamento de Computación

Computabilidad

Lógica

Departamento de Matemática

Lógica

Computabilidad

Parciales

Departamento de Computación

Computabilidad

Año Cuatrimestre Fecha Instancia Links
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)
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

Año Cuatrimestre Fecha Instancia Links
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
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

Lógica

Año Cuatrimestre Fecha Instancia Links
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)
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

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)
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

Departamento de Computación

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

Recursos

Clases

Prácticas

Apuntes

Videos

Curiosidades

Bibliografía recomendada

  • 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