Está página se ha trasladado a

 http://webdiis.unizar.es/asignaturas/MAC/

 


 

 

 

 

 


 

 

 

NOTA: Los ejercicios resueltos pueden entregarse por escrito hasta la siguiente clase.

 

  1. Presentación. 24-9 mañana, 22-9 tarde. Ejercicios propuestos Comentarios
  2. Preliminares. 26-9 mañana, 22-9 tarde.
  3. Problemas. Representación de datos. RAM. 26-9 mañana, 24-9 tarde. Ejercicios propuestos Comentarios
  4. Programas. 1-10 mañana, 29-9 tarde. Ejercicios propuestos SOLUCIÓN
  5. Funciones calculables. Problemas decidibles. 3-10 mañana, 29-9 tarde
  6. El problema de parada es indecidible. 3-10 mañana, 1-10 tarde Ejercicios propuestos SOLUCIÓN
  7. Problemas semidecidibles. 8-10 mañana, 6-10 tarde Ejercicio: demostrar que K es semidecidible
  8. 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)
  9. Propiedades de decidibles y semidecidibles. 17-10 mañana,15-10 tarde Propuesto: Escribir un programa que genere H
  10. Propiedades de decidibles y semidecidibles. 17-10 mañana, 20-10 tarde
  11. 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
  12. 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.
  13. Reducciones: primeras propiedades. 24-10 mañana, 27-10 tarde
  14. Reducciones: ejemplos. 29-10 mañana, 27-10 tarde
  15. Reducciones: ejemplos. 31-10 mañana, 29-10 tarde
  16. 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
  17. 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

 

  1. Complejidad. 12-11 mañana, 5-11 tarde
  2. 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)
  3. Complejidad. Codificación de datos. 10-11 tarde
  4. P versus EXP. 14-11 mañana, 12-11 tarde
  5. NP. El problema de la mochila. 19-11 mañana, 17-11 tarde
  6. NP. El problema SAT. 17-11 tarde
  7. NP. 19-11 tarde