Modelos Abstractos de Cálculo (MAC)

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

1. Presentación. 23-9 mañana, 21-9 tarde. Ejercicios propuestos
2. Preliminares. 25-9 mañana, 21-9 tarde.
3. Problemas. Representación de datos. RAM. 25-9 mañana, 23-9 tarde. Ejercicios propuestos
4. Programas. 30-9 mañana, 30-9 tarde. Ejercicios propuestos
5. Numerabilidad. 2-10 mañana, 28-9 tarde.
6. Diagonalización. 2-10 mañana, 28-9 tarde.
7. Funciones calculables. Problemas decidibles. 7-10 mañana, 5-10 tarde.
8. El problema de parada es indecidible. 9-10 mañana, 5-10 tarde
9. El problema de parada es indecidible. 10-10 mañana, 7-10 tarde Ejercicios propuestos
10. Propiedades de decidibles y semidecidibles. 21-10 mañana, 19-10 tarde (Ejercicio tarde: demostrar que K es semidecidible)
11. Propiedades de decidibles y semidecidibles. 23-10 mañana, 19-10 tarde (Ejercicio mañana: demostrar que K es semidecidible)
12. Propiedades de decidibles y semidecidibles. 23-10 mañana, 21-10 tarde
13. Ejercicios del tema 3: 3.1, 3.7, 3.16 y 3.12. 28-10 mañana, 26-10 tarde Propuestos: 3.2, 3.8 y 3.17
14. Reducciones: definición y ejemplos. 30-10 mañana, 26-10 tarde
15. Reducciones: primeras propiedades. 30-10 mañana, 28-10 tarde
16. Reducciones: ejemplos. 4-11 mañana, 4-11 tarde (Propuestos tarde: 4.5 y 4.6)
17. Reducciones: ejemplos (4.2, 4.3). 9-11 mañana, 4-11 tarde (Propuestos mañana: 4.5 y 4.6)
18. Teorema de Rice. 6-11 mañana, 9-11 tarde
19. Ejercicios del capítulo 4. 11-11 mañana, 13-11 tarde
20. Otros problemas indecidibles. 13-11 mañana, 16-11 tarde
21. Complejidad. 13-11 mañana, 16-11 tarde
22. Complejidad. Codificación de datos. 18-11 mañana, 23-11 tarde
23. Complejidad. Codificación de datos. 20-11 mañana, 20-11 tarde
24. P versus EXP. 20-11 mañana, 18-11 tarde
25. NP. 25-11 mañana, 25-11 tarde
26. NP. 27-11 mañana, 30-11 tarde
27. NP. 27-11 mañana
28. NP, P y EXP. 2-12 mañana, 30-11 tarde Propuesto: Demostrar que TSP está en NP
29. Reducciones. Primer ejemplo. 4-12 mañana, 2-12 tarde Propuesto: Demostrar que la alternativa vista en clase no funciona
30. Propiedades de las reducciones. Ejemplo de HAMconOrigen. 4-12 mañana, 9-12 tarde
31. NP-completos. 9-12 mañana, 14-12 tarde
32. Algunos NP-completos. 11-12 mañana, 14-12 tarde
33. Algunos NP-completos. 11-12 mañana, 16-12 tarde
34. Ejercicios de NP-completos: 63, 69b. 16-12 mañana, 16-12 tarde
35. Ejercicios de NP-completos: 69b, 65, 51a. 18-12 mañana
36. Ejercicios de NP-completos: 69b, 65, 51a. 18-12 mañana
37. Ejercicios de NP-completos: 11.1, 11.4. 8-1 mañana, 11-1 tarde
38. Ejercicios de NP-completos: dHAM, 53, 49. 8-1 mañana, 11-1 tarde Propuesto: 72a
39. Ejercicios. 24a, 25. 13-1 mañana
40. Ejemplo de examen. 15-1 mañana, 13-1 tarde
41. Ejemplo de examen. 15-1 mañana

Etiquetas: contenidos

Publicado por Elvira a las 18:20 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

Clases de teoría

Lugar CPS, Aula A04

Horarios

grupo de mañana

9:00-9:50 miércoles,

9:00-10:50h viernes

grupo de tarde

17:10-19:00 lunes,

18:10-19:00 miércoles

¡Atención! El jueves 15-10 tiene horario de lunes y el viernes 16-10 tiene horario de martes

Prácticas de laboratorio

Lugar CPS, Aula A06 (lunes), A03 (jueves)

Horarios

grupo 1, lunes A 12:00-14:00h, empiezan el 15-10

grupo 2, lunes B 12:00-14:00h, empiezan el 19-10

grupo 3, lunes A 10:00-12:00h, empiezan el 15-10

grupo 4, lunes B 10:00-12:00h, empiezan el 19-10

grupo 5, jueves B 15:00-17:00h, empiezan el 29-10

CALENDARIO detallado del CPS (con días A y B)

Etiquetas: contenidos

Publicado por Elvira a las 18:20 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

• A Compendium of NP Optimization Problems
• Algunas biografías Alan Turing , Kurt Gödel
• Computability and Complexity - Overview de Paul E. Dunne
• How to Read Mathematics de Shai Simonson and Fernando Gouveau.
  

Etiquetas: contenidos

Publicado por Elvira a las 18:19 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

1. Evaluación sin prácticas.

• Se realizarán dos exámenes escritos:
• Examen de teoría, que contribuirá al 37,5% de la nota. En este examen NO se permitirá al alumno el uso de apuntes o material adicional.
• Examen de problemas, que contribuirá al 62,5% de la nota. En este examen se permitirá al alumno el uso de esta página resumen de la asignatura elaborada por la profesora.
• La asignatura se superará con una calificación mayor o igual al 50% del total.

2. Evaluación con prácticas.

• Las prácticas serán de asistencia obligatoria.
• Las prácticas realizadas supondrán hasta un 20% de la nota final.
• Se realizarán dos exámenes escritos:
• Examen de teoría, que contribuirá al 30% de la nota. En este examen NO se permitirá al alumno el uso de apuntes o material adicional.
• Examen de problemas, que contribuirá al 50% de la nota. En este examen se permitirá al alumno el uso de esta página resumen de la asignatura elaborada por la profesora.
• La asignatura se superará con una calificación mayor o igual al 50% del total.

Etiquetas: contenidos

Publicado por Elvira a las 18:12 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

• MAYORDOMO, E.: Apuntes de la asignatura.Servicio de reprografía, 2009.
• JONES, N.: Computability and Complexity From a Programming Perspective. MIT press, 1997.
• KOZEN, D.C.: Automata and Computability. Springer, 1997.
• SERNA, M., ÀLVAREZ, C., CASES,R. y LOZANO, A.. Els límits de la computació. Indecidibilitat i NP-completesa. Edicions UPC. 2001
• CUTLAND, N.J.: Computability: An Introduction to Recursive Function Theory. Cambridge University Press. 1980.
• GAREY, M. y JOHNSON. D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. 1978.
• H.R. LEWIS y C.H. PAPADIMITRIOU: Elements of the Theory of Computation. Prentice-Hall. 1981.

Consulta:

• SOARE, R.: Recursively Enumerable Sets and Degrees. Springer-Verlag. 1987.
• HOPCROFT, J., ULLMAN, J. y MOTWANI, R.: Introduction to Automata Theory. Languages and Computation. Addison-Wesley. 2000. (Disponible traducción al español de 2005)
• MAYORDOMO, E.: P vs NP. Monografías de la Real Academia de Ciencias de Zaragoza, 26, 57-68 (2004)

Nuevo: Referencias en la biblioteca

Etiquetas: contenidos

Publicado por Elvira a las 18:11 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

Etiquetas: contenidos

Publicado por Elvira a las 18:09 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

INGENIERO EN INFORMÁTICA (Plan1994)

Departamento de Informática e Ingeniería de Sistemas

Área de Lenguajes y Sistemas Informáticos

Breve descripción:

Introducción a la complejidad y computabilidad de problemas.

Créditos 4,5

Período de impartición: cuatrimestre de otoño

Tipo: Troncal

Las clases se impartirán de septiembre a enero.

Asignaturas previas

Lenguajes, Gramáticas y Autómatas, Estructuras de Datos y Algoritmos, Matemática Discreta.

Objetivos

Profundizar en el estudio de la clasificación y complejidad de los problemas, iniciado en la asignatura de Lenguajes, Gramáticas y Autómatas. Establecer la distinción fundamental entre problemas resolubles e irresolubles. Adquirir los rudimentos de las teorías de complejidad y calculabilidad de algoritmos. Obtener la capacidad de demostrar la indecidibilidad de un problema y tener una idea de la tratabilidad de los problemas decidibles.

Programa

Parte I: Calculabilidad:

1. Preliminares. Numerabilidad y diagonalización.
2. Problemas y datos. La máquina RAM.
3. Otros modelos de cálculo.
4. Lenguajes recursivos y enumerables recursivamente.
5. Reducciones. El teorema de Rice.
6. Indecidibilidad.

Etiquetas: contenidos

Publicado por Elvira a las 18:05 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)

Etiquetas: anuncios

Publicado por Elvira a las 17:57 | Enlace a esta entrada | Comentarios (firmadlos con nombre y apellido)