NOTA: Los ejercicios resueltos pueden entregarse por
escrito hasta la siguiente clase.
- Presentación. 24-9 mañana, 22-9 tarde.
Ejercicios propuestos
Comentarios
- Preliminares. 26-9 mañana, 22-9 tarde.
- Problemas. Representación de datos. RAM. 26-9 mañana, 24-9
tarde. Ejercicios propuestos
Comentarios
- Programas. 1-10 mañana, 29-9 tarde.
Ejercicios propuestos
SOLUCIÓN
- Funciones calculables. Problemas decidibles. 3-10 mañana, 29-9 tarde
- El problema de parada es indecidible. 3-10 mañana, 1-10 tarde
Ejercicios propuestos
SOLUCIÓN
- Problemas semidecidibles. 8-10 mañana, 6-10 tarde
Ejercicio: demostrar que K es
semidecidible
- Propiedades de los semidecidibles. 15-10 mañana, 6-10 tarde
Propuesto: terminar 1-->3 y 3-->1
del teorema 3.12 (se resolverá en clase)
- Propiedades de decidibles y semidecidibles. 17-10
mañana,15-10 tarde Propuesto:
Escribir un programa que genere H
- Propiedades de decidibles y semidecidibles. 17-10 mañana,
20-10 tarde
- Ejercicios del tema 3: 3.1, 3.7, 3.12 y 3.16. 22-10 mañana,
20-10 tarde Propuestos: 3.2, 3.8 y
3.17
- Reducciones: definición y ejemplos. 24-10 mañana, 22-10
tarde Propuesto: Demostrar que si
A<= B y B semidecidible entonces A es semidecidible.
- Reducciones: primeras propiedades. 24-10 mañana, 27-10 tarde
- Reducciones: ejemplos. 29-10 mañana, 27-10 tarde
- Reducciones: ejemplos. 31-10 mañana, 29-10 tarde
- Reducciones: ejercicios. 31-10 mañana, 3-11 tarde
Propuesto: Demostrar que {p | p calcula una función inyectiva
y p para con alguna entrada} no es decidible
- Reducciones. Otros problemas indecidibles.
5-11 mañana, 3-11 tarde
El miércoles 19 de noviembre en las dos clases
haremos problemas de reducciones (capítulo 4, páginas 60-61 y 12.2
(páginas 129 a 136). CAMBIO DE DÍA: Será el miércoles 26
de noviembre
- Complejidad. 12-11 mañana, 5-11 tarde
- Complejidad. Codificación de datos. 14-11 mañana, 10-11 tarde
Propuesto: Dar un algoritmo para TSP2 a partir de uno para
TSP y calcular el tiempo que tarda (TSP2 es la versión general de TSP,
calcular cuánto mide el camino más corto)
- Complejidad. Codificación de datos. 10-11 tarde
- P versus EXP. 14-11 mañana, 12-11
tarde
- NP. El problema de la mochila. 19-11 mañana, 17-11 tarde
- NP. El problema SAT. 17-11 tarde
- NP. 19-11 tarde
|