Diferencia entre revisiones de «Lógica y Computabilidad»

De Cuba-Wiki
Sin resumen de edición
(Reestructuración general (especialmente parciales))
Línea 1: Línea 1:
{{Revisar guías}}
{{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 [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]].
'''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]].


Esta materia se cursa los Miércoles y Viernes a partir de las 17 hs.
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 16:
* [[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 ===


== Prácticas (Dpto. de Computación) ==
==== Computabilidad ====
'''Computabilidad'''
* [[Práctica 1 (LyC Verano) | Práctica 1 - Funciones computables]]
* [[Práctica 1 (LyC Verano) | Práctica 1 - Funciones computables]]
* [[Práctica 2 (LyC Verano) | Práctica 2 - Funciones primitivas recursivas]]
* [[Práctica 2 (LyC Verano) | Práctica 2 - Funciones primitivas recursivas]]
* [[Práctica 3 (LyC Verano) | Práctica 3 - Teoría de Computabilidad]]
* [[Práctica 3 (LyC Verano) | Práctica 3 - Teoría de Computabilidad]]


'''Lógica'''
==== Lógica ====
* [[Práctica 4 (LyC Verano) | Práctica 4 - Logica Proposicional]]
* [[Práctica 4 (LyC Verano) | Práctica 4 - Logica Proposicional]]
* [[Práctica 5 (LyC Verano) | Práctica 5 - Sistemas Deductivos y Compacidad]]
* [[Práctica 5 (LyC Verano) | Práctica 5 - Sistemas Deductivos y Compacidad]]
Línea 32: Línea 33:
* [[Práctica 7 (LyC Verano) | Práctica 7 - Sistemas Deductivos, Completitud y Compacidad (1º Orden)]]
* [[Práctica 7 (LyC Verano) | Práctica 7 - Sistemas Deductivos, Completitud y Compacidad (1º Orden)]]


== Prácticas (Dpto. de Matemática) ==
=== Departamento 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 43:
* [[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 ===
* Parcial de Lógica (2do cuatrimestre '16): [[Media: logicaYcomputabilidad_2p_2c2016.jpg|enunciado]], [[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]]
 
* [[Parcial de Lógica Verano 2016 (LyC)|Parcial de Lógica (Verano '16)]]
==== Computabilidad ====
* Parcial de Lógica (2do cuatrimestre '15): [[Media: logicaYcomputabilidad_2p_2c2015.pdf|enunciado]], [[Media: logicaYcomputabilidad_2p_2c2015_ej1.pdf|ej 1]], [[Media: logicaYcomputabilidad_2p_2c2015_ej2.pdf|ej 2]]
{| class="wikitable sortable"
* Recuperatorio de Lógica (Verano '15): [[Media: LyC_recu_logica_verano_2015.jpg|enunciado]]
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Parcial de Lógica (Verano '15): [[Media: LyC_logica_07-03-15.jpg|enunciado]], [[Media: LyC_2parcial_07-02-15_ej2.jpg|ej 2]], [[Media: LyC_2parcial_07-02-15_ej3.jpg|ej 3]].
|-
* Parcial de Lógica (2do Cuatrimestre '14): [[Media: LyC_2parcial_14-11-14.pdf|enunciado]], [[Media:LyC_2parcial_14-11-14_ej1.jpg|ej 1]], [[Media:LyC_2parcial_14-11-14_ej2.jpg|ej 2]].
| 2016 || Verano              ||            || Parcial          || [[Parcial de Computabilidad Verano 2016 (LyC)|enunciado]]
* 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]].
| 2015 || Segundo cuatrimestre ||            || Parcial          || [[Media: logicaYcomputabilidad_1p_2c2015.pdf|enunciado (pdf)]]
* Parcial de Lógica (2do Cuatrimestre '10): [[Media:10logica (Lógica y Computabilidad).pdf|enunciado]].
|-
* Recuperatorio de Lógica (Verano '09): [[Media:V09reculogica.pdf|enunciado]].
| 2015 || Verano              ||            || Recuperatorio    || [[Media: LyC_recu_compu_verano_2015.jpg|enunciado (jpg)]]
* Parcial de Lógica (Verano '09): [[Media:V09logica.pdf|enunciado]].
|-
* Recuperatorio de Lógica (1er Cuatrimestre '08): [[Media:1c08reculogica.pdf|enunciado]].
| 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)]
* Parcial de Lógica (1er Cuatrimestre '08): [[Media:1c08logica.pdf|enunciado]].
|-
* Recuperatorio de Lógica (Verano '08): [[Media:08reculogica.pdf|enunciado]].
| 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]]
* Parcial de Lógica (Verano '08): [[Media:08logica.pdf|enunciado]].
|-
* Recuperatorio de Lógica (Verano '07): [[Media:07reculogica.pdf|enunciado]].
| 2014 || Segundo cuatrimestre || 26/09/2014 || Parcial           || [[Media: LyC_1parcial_26-09-14.pdf|enunciado]]
* Parcial de Lógica (Verano '07): [[Media:07logica.pdf|enunciado]].
|-
* [[Parcial Lógica 13/10/06 (Lógica y Computabilidad) | Parcial de Lógica del 13/10/06]]
| 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)]]
|-
| 2010 || Segundo cuatrimestre ||            || Recuperatorio     || [[Media:10recucompu (Lógica y Computabilidad).pdf|enunciado]]
|-
| 2010 || Segundo cuatrimestre ||            || Parcial           || [[Media:10compu (Lógica y Computabilidad).pdf|enunciado]]
|-
| 2009 || Verano              ||            || Recuperatorio     || [[Media:V09recucompu.pdf|enunciado]]
|-
| 2009 || Verano              ||            || Parcial           || [[Media:V09compu.pdf|enunciado]]
|-
| 2008 || Primer cuatrimestre  ||            || Recuperatorio     || [[Media:1c08recucompu.pdf|enunciado]]
|-
| 2008 || Primer cuatrimestre  ||            || Parcial           || [[Media:1c08compu.pdf|enunciado]]
|-
| 2008 || Verano              ||            || Recuperatorio     || [[Media:08recucompu.pdf|enunciado]]
|-
| 2008 || Verano              ||            || Parcial           || [[Media:08compu.pdf|enunciado]]
|-
| 2007 || Verano              ||            || Recuperatorio     || [[Media:07recucompu.pdf|enunciado]]
|-
| 2007 || Verano              ||            || Parcial           || [[Media:07compu.pdf|enunciado]]
|}


==== Lógica ====
{| class="wikitable sortable"
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
|-
| 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              ||            || Parcial          || [[Parcial de Lógica Verano 2016 (LyC)|enunciado]]
|-
| 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]]
|-
| 2010 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:10recu2logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2010 || Segundo cuatrimestre ||            || Recuperatorio    || [[Media:10reculogica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2010 || Segundo cuatrimestre ||            || Parcial          || [[Media:10logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2009 || Verano              ||            || Recuperatorio    || [[Media:V09reculogica.pdf|enunciado (pdf)]]
|-
| 2009 || Verano              ||            || Parcial          || [[Media:V09logica.pdf|enunciado (pdf)]]
|-
| 2008 || Primer cuatrimestre  ||            || Recuperatorio    || [[Media:1c08reculogica.pdf|enunciado (pdf)]]
|-
| 2008 || Primer cuatrimestre  ||            || Parcial          || [[Media:1c08logica.pdf|enunciado (pdf)]]
|-
| 2008 || Verano              ||            || Recuperatorio    || [[Media:08reculogica.pdf|enunciado (pdf)]]
|-
| 2008 || Verano              ||            || Parcial          || [[Media:08logica.pdf|enunciado (pdf)]]
|-
| 2007 || Verano              ||            || Recuperatorio    || [[Media:07reculogica.pdf|enunciado (pdf)]]
|-
| 2007 || Verano              ||            || Parcial          || [[Media:07logica.pdf|enunciado (pdf)]]
|-
| 2006 || Segundo cuatrimestre || 13/10/2006 || Parcial          || [[Parcial Lógica 13/10/06 (Lógica y Computabilidad)|enunciado]]
|}


'''Computabilidad'''
=== Departamento de Matemática ===
* [[Parcial de Computabilidad Verano 2016 (LyC)|Parcial de Computabilidad (Verano '16)]]
* Parcial de Computabilidad (2do cuatrimestre '15): [[Media: logicaYcomputabilidad_1p_2c2015.pdf|enunciado]]
* Recuperatorio de Computabilidad (Verano '15): [[Media: LyC_recu_compu_verano_2015.jpg|enunciado]]
* Parcial de Computabilidad (Verano '15): [[Media: LyC_compu_07-03-15.jpg|enunciado]], [[Media:LyC 1parcial 14-02-15 ej1.jpg|ej 1]], [[Media:LyC 1parcial 14-02-15 ej2.jpg|ej 2]], [https://www.youtube.com/watch?v=lTSMBvzDxRo Solución por Manu Giménez (video)]
* Recuperatorio de Computabilidad (2do Cuatrimestre '14): [[Media:LyC_1recu_12-03-14.jpg|enunciado]], [[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]]
* Parcial de Computabilidad (2do Cuatrimestre '14): [[Media: LyC_1parcial_26-09-14.pdf|enunciado]].
* Parcial de Computabilidad (Verano '14): [[Media: LyC_1parcial_15-02-14.jpg |enunciado]]
* Recuperatorio de Computabilidad (2do Cuatrimestre '12): [[Media:RecuComputabilidad2cuat2012DC.jpg|enunciado]].
* Parcial de Computabilidad (2do Cuatrimestre '11): [[Media:LyC_1parcial_07-10-11.pdf|resuelto]]
* 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"
* Parcial de Lógica (1er Cuat '16): [[Medio:parcial_2016_1c_1p.pdf|enunciado + resolución]].
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Parcial de Lógica (1er Cuat '15): [[Medio:logica_1parcial_15052015.jpg|enunciado]].
|-
* Recuperatorio (2) de Lógica (2do Cuat '08): [[Media:08dmrecu2logica (Lógica y Computabilidad).pdf|enunciado]].
| 2016 || Primer cuatrimestre  ||            || Parcial           || [[Medio:parcial_2016_1c_1p.pdf|enunciado + resolución (pdf)]]
* 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]].
| 2015 || Primer cuatrimestre  || 15/05/2015 || Parcial           || [[Medio:logica_1parcial_15052015.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]].
| 2008 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:08dmrecu2logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
* Parcial de Lógica (2do Cuat '07): [[Media:07dmlogica (Lógica y Computabilidad).pdf|enunciado]].
|-
| 2008 || Segundo cuatrimestre ||            || Recuperatorio     || [[Media:08dmreculogica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2008 || Segundo cuatrimestre ||            || Parcial           || [[Media:08dmlogica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:07dmrecu2logica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Recuperatorio     || [[Media:07dmreculogica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Parcial           || [[Media:07dmlogica (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|}


'''Computabilidad'''
==== Computabilidad ====
* Parcial de Computabilidad (1er Cuat '15): [[Medio:LyC_2parcial_03-07-15.pdf|enunciado]].
{| class="wikitable sortable"
* Parcial de Computabilidad (1er Cuat '10): [[Media:1C2010compu.pdf|enunciado]] | [[Media:1C2010compuResolucion.pdf|enunciado + resolución]].
! Año  !! Cuatrimestre        !! Fecha      !! Instancia        !! Links
* Recuperatorio (2) de Computabilidad (2do Cuat '08): [[Media:08dmrecu2compu (Lógica y Computabilidad).pdf|enunciado]].
|-
* Recuperatorio de Computabilidad (2do Cuat '08): [[Media:08dmrecucompu (Lógica y Computabilidad).pdf|enunciado]].
| 2015 || Primer cuatrimestre  || 03/07/2015 || Parcial           || [[Medio:LyC_2parcial_03-07-15.pdf|enunciado (pdf)]]
* Parcial de Computabilidad (2do Cuat '08): [[Media:08dmcompu (Lógica y Computabilidad).pdf|enunciado]].
|-
* Recuperatorio (2) de Computabilidad (2do Cuat '07): [[Media:07dmrecu2compu (Lógica y Computabilidad).pdf|enunciado]].
| 2010 || Primer cuatrimestre  ||            || Parcial           || [[Media:1C2010compu.pdf|enunciado (pdf)]], [[Media:1C2010compuResolucion.pdf|enunciado + resolución (pdf)]]
* Recuperatorio de Computabilidad (2do Cuat '07): [[Media:07dmrecucompu (Lógica y Computabilidad).pdf|enunciado]].
|-
* Parcial de Computabilidad (2do Cuat '07): [[Media:07dmcompu (Lógica y Computabilidad).pdf|enunciado]].
| 2008 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:08dmrecu2compu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2008 || Segundo cuatrimestre ||            || Recuperatorio     || [[Media:08dmrecucompu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2008 || Segundo cuatrimestre ||            || Parcial           || [[Media:08dmcompu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Recuperatorio (2) || [[Media:07dmrecu2compu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Recuperatorio     || [[Media:07dmrecucompu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|-
| 2007 || Segundo cuatrimestre ||            || Parcial           || [[Media:07dmcompu (Lógica y Computabilidad).pdf|enunciado (pdf)]]
|}


== Finales ==
== Finales ==
=== Computación ===  
=== Departamento de Computación ===  
* [[Medio:LyC final preguntas resueltas.pdf|Preguntas de finales resueltas]] ([https://github.com/CubaWiki/LYC-FinalPreguntas-JVanecek Source]): Tomadas por Santiago Figueira.
* [[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)
Línea 127: Línea 196:
* [[Final del 09/05/16 (Lógica y Computabilidad) | Final del 09/05/16]]: Tomado por Santiago Figueira (Escrito)
* [[Final del 09/05/16 (Lógica y Computabilidad) | Final del 09/05/16]]: Tomado por Santiago Figueira (Escrito)


=== Matemática ===  
=== 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) (resuelto)
* [[Final del 21/10/14 (Lógica y Computabilidad) | Final del 21/10/14]]: Tomado por Alejandro Petrovich (Escrito) (resuelto)


== Apuntes ==
== Recursos ==
=== Clases ===  
=== Clases ===  
*[[Media:C2practica (Logica).pdf|Clase práctica número 2 (computabilidad)]]: Ejemplo de demostraciones de funciones primitivas recursivas.
*[[Media:C2practica (Logica).pdf|Clase práctica número 2 (computabilidad)]]: Ejemplo de demostraciones de funciones primitivas recursivas.
Línea 155: Línea 224:
* [[Teorema de Cantor]]
* [[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]])

Revisión del 00:06 19 dic 2016

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

Lógica

Año Cuatrimestre Fecha Instancia Links
2016 Segundo cuatrimestre Parcial enunciado (jpg), resolución (jpg/pdf): ej 1, ej 2, ej 3, ej 4
2016 Verano Parcial enunciado
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
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
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
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

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