Diferencia entre revisiones de «Lógica y Computabilidad»

De Cuba-Wiki
Sin resumen de edición
 
(No se muestran 143 ediciones intermedias de 67 usuarios)
Línea 1: Línea 1:
{{Revisar guías}}
{{Plan 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 [http://www.dm.uba.ar 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 [[Plan de la Carrera#Tercer año|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]].


Esta materia se cursa los Miércoles y Viernes a partir de las 17 hs.
'''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 [http://www.dm.uba.ar 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|plan de la carrera]], es una materia a ser cursada en [[Plan de la Carrera#Tercer año|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 ==
== Programa ==
Abarca los temas de los capítulos 1 al 4 del libro "Computability, Complexity, and Languages" de Davis, Sigal y Weyuker
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.
* '''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 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.
 
* '''Lógica de Primer Orden''': Lenguaje. Semántica. Sistema axiomático. Metateoremas para SQ. Indecidibilidad.


== Contenidos ==
== Contenidos ==
Línea 18: Línea 17:
* [[Teorema de Completitud]]
* [[Teorema de Completitud]]
* [[Teorema de Compacidad]]
* [[Teorema de Compacidad]]
* [[Definiciones y Teoremas varios (Lógica y Computabilidad)|Resumen de Definiciones y Teoremas varios]]
* [[Definiciones y Teoremas varios (Lógica y Computabilidad)|Resumen de definiciones y teoremas varios]]
 
== Prácticas ==
 
=== Departamento de Computación ===
 
==== Computabilidad ====
* '''2do Cuatrimestre 2017'''
** [[Medio:Práctica_1_LyC_2do_Cuatrimestre_2017.pdf|Práctica 1 - Funciones primitivas recursivas y clases PRC]]
 
* '''Verano'''
** [[Práctica 1 (LyC Verano) | Práctica 1 - Funciones computables]]
** [[Práctica 2 (LyC Verano) | Práctica 2 - Funciones primitivas recursivas]]
** [[Práctica 3 (LyC Verano) | Práctica 3 - Teoría de Computabilidad]]


== Prácticas (Dpto. de Computación) ==
==== Lógica ====
'''Computabilidad'''
* '''2do Cuatrimestre 2017'''
* [[Práctica 1 (LyC Verano) | Práctica 1 - Funciones computables]]
** [[Práctica 5 LyC 2do Cuatrimestre 2017 (Depto. de Computación)|Práctica 5 - Sistemas Deductivos y Compacidad]]
* [[Práctica 2 (LyC Verano) | Práctica 2 - Funciones primitivas recursivas]]
* '''Verano'''
* [[Práctica 3 (LyC Verano) | Práctica 3 - Teoría de Computabilidad]]
** [[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)]]


'''Lógica'''
=== Departamento de Matemática ===
* [[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)]]


== Prácticas (Dpto. de Matemática) ==
==== Lógica ====
'''Lógica'''
* [[Práctica 1: Lógica Proposicional (Lógica y Computabilidad) | Práctica 1: Lógica Proposicional]]
* [[Práctica 1: Lógica Proposicional (Lógica y Computabilidad) | Práctica 1: Lógica Proposicional]]
* [[Práctica 2: Semántica del Cálculo Proposicional (Lógica y Computabilidad) | Práctica 2: Semántica del Cálculo Proposicional]]
* [[Práctica 2: Semántica del Cálculo Proposicional (Lógica y Computabilidad) | Práctica 2: Semántica del Cálculo Proposicional]]
Línea 41: Línea 51:
* [[Práctica 6: Árboles del Cálculo de Predicados (Lógica y Computabilidad) | Práctica 6: Árboles del Cálculo de Predicados]]
* [[Práctica 6: Árboles del Cálculo de Predicados (Lógica y Computabilidad) | Práctica 6: Árboles del Cálculo de Predicados]]


'''Computabilidad'''
==== Computabilidad ====
* [[Práctica 7: Computabilidad y Programas (Lógica y Computabilidad) | Práctica 7: Computabilidad y Programas]]
* [[Práctica 7: Computabilidad y Programas (Lógica y Computabilidad) | Práctica 7: Computabilidad y Programas]]
* [[Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad) | Práctica 8: Funciones Primitivas Recursivas]]
* [[Práctica 8: Funciones Primitivas Recursivas (Lógica y Computabilidad) | Práctica 8: Funciones Primitivas Recursivas]]
* [[Práctica 9: Recursividad (Lógica y Computabilidad) | Práctica 9: Recursividad]]
* [[Práctica 9: Recursividad (Lógica y Computabilidad) | Práctica 9: Recursividad]]


== Parciales (Dpto. de Computación) ==
== Parciales ==
'''Lógica'''
=== Departamento de Computación ===
* Recuperatorio (2) de Lógica (2do Cuatrimestre '10): [[Media:10recu2logica (Lógica y Computabilidad).pdf|enunciado]].
 
* Recuperatorio de Lógica (2do Cuatrimestre '10): [[Media:10reculogica (Lógica y Computabilidad).pdf|enunciado]].
==== Computabilidad ====
* Parcial de Lógica (2do Cuatrimestre '10): [[Media:10logica (Lógica y Computabilidad).pdf|enunciado]].
{| class="wikitable sortable"
* Recuperatorio de Lógica (Verano '09): [[Media:V09reculogica.pdf|enunciado]].
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Parcial de Lógica (Verano '09): [[Media:V09logica.pdf|enunciado]].
 
* Recuperatorio de Lógica (1er Cuatrimestre '08): [[Media:1c08reculogica.pdf|enunciado]].
|-
* Parcial de Lógica (1er Cuatrimestre '08): [[Media:1c08logica.pdf|enunciado]].
| 2023 || Primer Cuatrimestre              || 30/06/2023 || Recuperatorio   || [[Media:Recu-Computabilidad-2023C1_c.pdf|enunciado + resolución (pdf)]]
* Recuperatorio de Lógica (Verano '08): [[Media:08reculogica.pdf|enunciado]].
|-
* Parcial de Lógica (Verano '08): [[Media:08logica.pdf|enunciado]].
| 2023 || Primer Cuatrimestre             || x/06/2023 || Parcial    || [[Media:Parcial-Computabilidad-2023C1_c.pdf|enunciado]]
* Recuperatorio de Lógica (Verano '07): [[Media:07reculogica.pdf|enunciado]].
|-
* Parcial de Lógica (Verano '07): [[Media:07logica.pdf|enunciado]].
| 2023 || Verano        || 17/02/2023 || Parcial|| [[Media:Parcial1_Computabilidad_2023_verano.pdf|enunciado]], [[Media:1parcial_verano_2023_LyC.pdf|resolucion]]
* [[Parcial Lógica 13/10/06 (Lógica y Computabilidad) | Parcial de Lógica del 13/10/06]]
 
|-
| 2022 || Segundo Cuatrimestre              || 25/11/2022 || Recuperatorio   || [[Media:LyC_1recu_22-11-25.pdf|enunciado (pdf)]]
|-
| 2020 || Segundo Cuatrimestre             || 23/10/2020 || Parcial    || [[Media:LyC_1parcial_23-10-2020.pdf|enunciado (pdf)]]
|-
| 2020 || Primer Cuatrimestre              || 24/07/2020 || Recuperatorio    || [[Media:LyC_1parcial_recuperatorio_24-07-2020.pdf|enunciado (pdf)]]
|-
| 2020 || Primer Cuatrimestre              || 29/05/2020 || Parcial   || [[Media:LyC_1parcial_29-05-2020.pdf|enunciado + resolución (pdf)]]
|-
| 2020 || Verano              || 19/02/2020 || Parcial|| [[Media: Parcial Computabilidad 19-02-2020.jpeg|enunciado]], [[Media:Resolucion-parcial-computabilidad-2020.pdf|resolución]]
|-
| 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               || 21/02/2017 || Parcial          || [[Parcial de computabilidad Verano 2017 (LyC)|enunciado]], [[Media:LyC_1parcial_21-02-17.pdf|resolución (pdf)]], [[Media:LyC_1P_21-02-17.pdf|resolución2 (pdf)]]
|-
| 2016 || Verano              || 13/02/2016 || Parcial          || [[Parcial de Computabilidad Verano 2016 (LyC)|enunciado]], [[Media:LyC_1parcial_13-02-16.pdf|enunciado + resolución (pdf)]]
|-
| 2015 || Segundo cuatrimestre ||            || Parcial          || [[Media: logicaYcomputabilidad_1p_2c2015.pdf|enunciado (pdf)]]
|-
| 2015 || Verano              ||            || Recuperatorio     || [[Media: LyC_recu_compu_verano_2015.jpg|enunciado (jpg)]]
|-
| 2015 || Verano               || 14/02/2015 || Parcial          || [[Media: LyC_compu_07-03-15.jpg|enunciado (jpg)]], resolución (jpg): [[Media:LyC 1parcial 14-02-15 ej1.jpg|ej 1]], [[Media:LyC 1parcial 14-02-15 ej2.jpg|ej 2]], <br> [https://www.youtube.com/watch?v=lTSMBvzDxRo solución por Manu Giménez (video)]
|-
| 2014 || Segundo cuatrimestre || 03/12/2014 || Recuperatorio    || [[Media: LyC_1recu_12-03-14.jpg|enunciado (jpg)]], resolución (jpg): [[Media:LyC_1parcial_26-09-14_ej2.jpg|ej 2]], [[Media:LyC_1parcial_26-09-14_ej3.jpg|ej 3]], [[Media:LyC 1parcial_26-09-14_ej4.jpg|ej 4]]
|-
| 2014 || Segundo cuatrimestre || 26/09/2014 || Parcial          || [[Media: LyC_1parcial_26-09-14.pdf|enunciado (pdf)]]
|-
| 2014 || Verano              || 15/02/2014 || Parcial          || [[Media: LyC_1parcial_15-02-14.jpg |enunciado (jpg)]]
|-
| 2012 || Segundo cuatrimestre ||            || Recuperatorio    || [[Media:RecuComputabilidad2cuat2012DC.jpg|enunciado (jpg)]]
|-
| 2011 || Segundo cuatrimestre || 07/10/2011 || Parcial           || [[Media:LyC_1parcial_07-10-11.pdf|enunciado + resolución (pdf)]]
|}


==== Lógica ====
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 2023 || Verano            || 13/03/2023 || Parcial    || [[Media:Parcial2_Lógica_verano23.pdf|enunciado]],  [[Media:Resolución_Parcial_Lógica_verano23.pdf|resolucion]]
|-
| 2022 || Segundo Cuatrimestre              || 18/11/2022 || Parcial    || [[Media:2doPacialLyC.pdf|enunciado + resolución (pdf)]]
|-
| 2021 || Verano              || 18/03/2021 || Parcial    || [[Media:LyC_2parcial_18-03-2021.pdf|enunciado + resolución (pdf)]]
|-
| 2020 || Segundo Cuatrimestre              || 04/10/2020 || Parcial    || [[Media:LyC_2parcial_04-10-2020.pdf|enunciado (pdf)]]
|-
| 2020 || Primer Cuatrimestre    || 17/07/2020 || Parcial || [[Media:Parcial_Lógica_1erC_2020(LyC).pdf|enunciado]], [[Media:LyC_2parcial_17-07-2020.pdf|enunciado + resolución (pdf)]]
|-
| 2020 || Primer Cuatrimestre    || 31/07/2020 || Recuperatorio || [[Media:Recuperatorio_Lógica_1erC_2020(LyC).pdf|enunciado]], [[Media:LyC_2parcial_recuperatorio_31-07-2020.pdf|enunciado + resolución (pdf)]]
|-
| 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]]
|-
| 2016 || Segundo cuatrimestre ||            || Parcial          || [[Media: logicaYcomputabilidad_2p_2c2016.jpg|enunciado (jpg)]], resolución (jpg/pdf): [[Media: logicaYcomputabilidad_2p_2c2016_ej1.jpg|ej 1]], [[Media: logicaYcomputabilidad_2p_2c2016_ej2.pdf|ej 2]], [[Media: logicaYcomputabilidad_2p_2c2016_ej3.pdf|ej 3]], [[Media: logicaYcomputabilidad_2p_2c2016_ej4.pdf|ej 4]]
|-
| 2016 || Verano              || 03/03/2016 || Parcial          || [[Parcial de Lógica Verano 2016 (LyC)|enunciado]], [[Media:LyC_2parcial_03-03-16.pdf|enunciado + resolución (pdf)]]
|-
| 2015 || Segundo cuatrimestre ||            || Parcial          || [[Media: logicaYcomputabilidad_2p_2c2015.pdf|enunciado (pdf)]], resolución (pdf): [[Media: logicaYcomputabilidad_2p_2c2015_ej1.pdf|ej 1]], [[Media: logicaYcomputabilidad_2p_2c2015_ej2.pdf|ej 2]]
|-
| 2015 || Verano              ||            || Recuperatorio    || [[Media:LyC_recu_logica_verano_2015.jpg|enunciado (jpg)]]
|-
| 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]], [[Solución Ejercicio 4 Parcial Lógica 14/11/2014 (Lógica y Computabilidad - Departamento de Computación)|ej4]]
|}


'''Computabilidad'''
=== Departamento de Matemática ===
* Recuperatorio de Computabilidad (2do Cuatrimeste '12): [[Media:RecuComputabilidad2cuat2012DC.jpg|enunciado]].
* Recuperatorio de Computabilidad (2do Cuatrimestre '10): [[Media:10recucompu (Lógica y Computabilidad).pdf|enunciado]].
* Parcial de Computabilidad (2do Cuatrimestre '10): [[Media:10compu (Lógica y Computabilidad).pdf|enunciado]].
* Recuperatorio de Computabilidad (Verano '09): [[Media:V09recucompu.pdf|enunciado]].
* Parcial de Computabilidad (Verano '09): [[Media:V09compu.pdf|enunciado]].
* Recuperatorio de Computabilidad (1er Cuatrimestre '08): [[Media:1c08recucompu.pdf|enunciado]].
* Parcial de Computabilidad (1er Cuatrimestre '08): [[Media:1c08compu.pdf|enunciado]].
* Recuperatorio de Computabilidad (Verano '08): [[Media:08recucompu.pdf|enunciado]].
* Parcial de Computabilidad (Verano '08): [[Media:08compu.pdf|enunciado]].
* Recuperatorio de Computabilidad (Verano '07): [[Media:07recucompu.pdf|enunciado]].
* Parcial de Computabilidad (Verano '07): [[Media:07compu.pdf|enunciado]].


== Parciales (Dpto. de Matemática) ==
==== Lógica ====
'''Lógica'''
{| class="wikitable sortable"
* Recuperatorio (2) de Lógica (2do Cuat '08): [[Media:08dmrecu2logica (Lógica y Computabilidad).pdf|enunciado]].
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Recuperatorio de Lógica (2do Cuat '08): [[Media:08dmreculogica (Lógica y Computabilidad).pdf|enunciado]].
|-
* Parcial de Lógica (2do Cuat '08): [[Media:08dmlogica (Lógica y Computabilidad).pdf|enunciado]].
| 2024 || Primer cuatrimestre  || 12/07/2024 || Recuperatorio     ||  [[Medio:LyC_1recu_12-07-24.jpg| Enunciado (jpg) ]]
* Recuperatorio (2) de Lógica (2do Cuat '07): [[Media:07dmrecu2logica (Lógica y Computabilidad).pdf|enunciado]].
|-
* Recuperatorio de Lógica (2do Cuat '07): [[Media:07dmreculogica (Lógica y Computabilidad).pdf|enunciado]].
| 2024 || Primer cuatrimestre  || 10/05/2024 || Parcial    ||  [[Medio:LyC_1parcial_10-05-24.jpg| Enunciado (jpg) ]]
* Parcial de Lógica (2do Cuat '07): [[Media:07dmlogica (Lógica y Computabilidad).pdf|enunciado]].
|-
| 2023 || Primer cuatrimestre  || 07/07/2023 || Recuperatorio    ||  [[Medio:LyC_2parcial_recuperatorio_07-07-2023.pdf| Enunciado + Resolución (pdf)]]
|-
| 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)]]
|-
| 2015 || Primer cuatrimestre  || 15/05/2015 || Parcial           || [[Medio:logica_1parcial_15052015.jpg|enunciado (jpg)]]
|}


'''Computabilidad'''
==== Computabilidad ====
* Parcial de Computabilidad (1er Cuat '10): [[Media:1C2010compu.pdf|enunciado]] | [[Media:1C2010compuResolucion.pdf|enunciado + resolución]].
{| class="wikitable sortable"
* Recuperatorio (2) de Computabilidad (2do Cuat '08): [[Media:08dmrecu2compu (Lógica y Computabilidad).pdf|enunciado]].
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Recuperatorio de Computabilidad (2do Cuat '08): [[Media:08dmrecucompu (Lógica y Computabilidad).pdf|enunciado]].
|-
* Parcial de Computabilidad (2do Cuat '08): [[Media:08dmcompu (Lógica y Computabilidad).pdf|enunciado]].
| 2024 || Primer cuatrimestre  || 05/07/2024 || Parcial     ||  [[Medio:LyC_2parcial_05-07-24.jpg| Enunciado (jpg) ]]
* Recuperatorio (2) de Computabilidad (2do Cuat '07): [[Media:07dmrecu2compu (Lógica y Computabilidad).pdf|enunciado]].
|-
* Recuperatorio de Computabilidad (2do Cuat '07): [[Media:07dmrecucompu (Lógica y Computabilidad).pdf|enunciado]].
| 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]
* Parcial de Computabilidad (2do Cuat '07): [[Media:07dmcompu (Lógica y Computabilidad).pdf|enunciado]].
|-
| 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)]]
|}


== Finales ==
== 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.
* [[Medio:LyC final preguntas resueltas.pdf|Preguntas de finales resueltas]] ([https://github.com/CubaWiki/LYC-FinalPreguntas-JVanecek Source]): Tomadas por Santiago Figueira.
* [[Final del 17/03/07 (Lógica y Computabilidad) | Final del 17/03/07]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 17/03/07 (Lógica y Computabilidad) | Final del 17/03/07]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 23/02/10 (Lógica y Computabilidad) | Final del 23/02/10]]: Tomado por Santiago Figueira (Oral)
* [[Final del 23/02/10 (Lógica y Computabilidad) | Final del 23/02/10]]: Tomado por Santiago Figueira (Oral)
Línea 103: Línea 208:
* [[Final del 07/03/14 (Lógica y Computabilidad) | Final del 07/03/14]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 07/03/14 (Lógica y Computabilidad) | Final del 07/03/14]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 11/12/14 (Lógica y Computabilidad) | Final del 11/12/14]]: Tomado por Santiago Figueira (Oral)
* [[Final del 11/12/14 (Lógica y Computabilidad) | Final del 11/12/14]]: Tomado por Santiago Figueira (Oral)
* [[Final del 22/11/14 (Lógica y Computabilidad) | Final del 07/03/14]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 22/12/14 (Lógica y Computabilidad) | Final del 22/12/14]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 13/04/15 (Lógica y Computabilidad) | Final del 13/04/15]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 21/12/15 (Lógica y Computabilidad) | Final del 21/12/15]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 09/05/16 (Lógica y Computabilidad) | Final del 09/05/16]]: 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 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)
* [[Final del 06/12/19 (Lógica y Computabilidad) | Final del 06/12/19]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 20/02/20 (Lógica y Computabilidad) | Final del 20/02/20]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 05/03/20 (Lógica y Computabilidad) | Final del 05/03/20]]: Tomado por Santiago Figueira (Escrito)
* [[Medio:LyC_final_20-12-2020_santi-figueria-virtual.pdf | Final del 20/12/20]]: Tomado por Santiago Figueira (Virtual) + [[Resolucion final del 05/03/20 (Lógica y Computabilidad) | resolución]]
* [[Final del 07/12/22 (Lógica y Computabilidad) | Final del 07/12/22]]: Tomado por  (Oral)
* [[Final del 22/12/22 (Lógica y Computabilidad) | Final del 22/12/22]]: Tomado por Ariel (Oral)
* [[Final del 22/02/23 (Lógica y Computabilidad) | Final del 22/02/23]]: Tomado por Sergio Abriola (Escrito)
* [[Final del 08/03/23 (Lógica y Computabilidad) | Final del 08/03/23]]: Tomado por Sergio Abriola (Escrito)
* [[Final del 11/04/23 (Lógica y Computabilidad) | Final del 11/04/23]]: Tomado por Sergio Abriola (Escrito)
 
=== Departamento de Matemática ===
* [[Final del 16/07/13 (Lógica y Computabilidad) | Final del 16/07/13]]: Tomado por Alejandro Petrovich (Escrito)
* [[Final del 16/07/13 (Lógica y Computabilidad) | Final del 16/07/13]]: 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 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)
* [[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)
== Apuntes ==
* [[Final del 13/11/18 (Lógica y Computabilidad) | Final del 13/11/18]]: Tomado por Alejandro Petrovich (Escrito) (resuelto 50%)
=== Clases ===
* [[Final del 22/10/18 (Lógica y Computabilidad) | Final del 22/10/19]]: Tomado por Juan José Guccione (Escrito) (resuelto 25%)
*[[Media:C2practica (Logica).pdf|Clase práctica número 2 (computabilidad)]]: Ejemplo de demostraciones de funciones primitivas recursivas.
* [[Final del 11/08/21 (Lógica y Computabilidad) | Final del 11/08/21]]: Tomado por Ariel Bendersky (Oral)
*[[Media:C3practica (Logica).pdf|Clase práctica número 3 (computabilidad)]]: Esquemas recursivos p.r.
* [https://www.cubawiki.com.ar/images/8/81/Proba_final_20-10-21.pdf Final del 20/10/21]: Tomado por Alejandro Petrovich (Escrito)
*[[Media:C5practica (Logica).pdf|Clase práctica número 5 (computabilidad)]]: Apunte de clases de funciones y ejercicios de Halt.
*[[Media:C6practica (Logica).pdf|Clase práctica número 6 (computabilidad)]]: Teorema de la recursión, teorema del parámetro, etc.
*[[Media:C7practica (Logica).pdf|Clase práctica número 7 (computabilidad)]]: Conjuntos r.e., Rice.
*[[Media:L1practica (Logica).pdf|Clase práctica número 1 (lógica)]]: Lógica proposicional.
*[[Media:L2practica (Logica).pdf|Clase práctica número 2 (lógica)]]: Conjuntos maximales consistentes.
*[[Media:L3practica (Logica).pdf|Clase práctica número 3 (lógica)]]: Conjuntos maximales consistentes, teorema de la deducción, árboles LP, compacidad.


== Recursos ==
=== Prácticas ===
=== Prácticas ===
*[[Media:Resueltos Tobis 2005 (Logica).zip|Prácticas resueltas de LyC del 2005]].
*[https://github.com/maurosch/Logica-y-Computabilidad Prácticas resueltas de LyC Verano 2021].


=== Apuntes ===
=== Apuntes ===
*[[Media:Logica_apunte_ltaravilse.pdf | Apunte de Computabilidad]], hecho por Leopoldo Taravilse, durante la cursada del segundo cuatrimestre de 2012 [ [[Media:Logica_apunte_ltaravilse.tex | fuente .tex]] ].
* [https://github.com/CubaWiki/LyC-ApunteComputabilidad-Taravilse/releases/download/1.0/Logica_apunte_ltaravilse.pdf Apunte de Computabilidad]([https://github.com/CubaWiki/LyC-ApunteComputabilidad-Taravilse Repositorio de fuentes]), hecho por Leopoldo Taravilse, durante la cursada del segundo cuatrimestre de 2012.
* [[Medio:LyC_apunte_ldisalvo.pdf| Apunte de clases teóricas]], hecho por Lucas Di Salvo.
 
=== Videos ===
* [https://www.youtube.com/watch?v=lTSMBvzDxRo Video explicando resolución de un parcial de Computabilidad (por Manu Gimenez)]


== Curiosidades ==
* [https://youtube.com/playlist?list=PLdGJ0-FVbCq_UKAVA3wRRecf-o0Dm0DWK&si=RzXoqMjBu-CXxlOJ Playlist con más videos explicando cosas (por Manu Gimenez)]
* [[Teorema de Cantor]]


== Bibliografía Recomendada ==
== 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]])
*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]])
*Mendelson, Elliot, ''Introduction to mathematical logic'', Princeton, N.J.: Van Nostrand, c1964 ('''Circulante 510 600 Mendelson''' en la [[Biblioteca Central]])


== Enlaces externos ==
== Enlaces externos ==
*[http://www-2.dc.uba.ar/materias/logica/ 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 actual - 06:14 28 jul 2024

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

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

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

Lógica

Año Cuatrimestre Fecha Instancia Links
2024 Primer cuatrimestre 12/07/2024 Recuperatorio Enunciado (jpg)
2024 Primer cuatrimestre 10/05/2024 Parcial Enunciado (jpg)
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

Año Cuatrimestre Fecha Instancia Links
2024 Primer cuatrimestre 05/07/2024 Parcial Enunciado (jpg)
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

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

Prácticas

Apuntes

Videos

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

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Lógica_y_Computabilidad&oldid=17482»