Modelos Abstractos

Modelos Abstractos de C´lculo a
Elvira Mayordomo C´mara a
18 de enero de 2008

Cap´ ıtulo 0

Presentaci´n o
La asignatura de Modelos Abstractos de C´lculo consta de dos para tes: computabilidad (tambi´n llamada recursividad) y complejidad, cae da una de ellas ocupa aproximadamente un 50 % de las clases de teor´ ıa y problemas. Parte I: Computabilidad. Los contenidos fundamentales son lossiguientes: Existen problemas que no se pueden resolver con ning´n algoritmo. u Veremos ejemplos importantes de estos problemas “irresolubles” y m´todos para saber que un problema es de este tipo. e Se conjetura que cualquier noci´n razonable de algoritmo da lugar o al mismo conjunto de problemas resolubles. EJERCICIOS Escribir los siguientes procedimientos ada (y probarlos): 0.1. Functioncheck(f:file type; n:integer) return boolean; {Pre: f es un fichero que contiene un programa ada que lee de teclado un unico valor entero. ´ Post: devuelve true si el programa contenido en f con entrada n termina; devuelve false si se queda “colgado”} 0.2. Procedure fermat(n:in integer; x,y,z:out integer);
1

´ CAP´ ITULO 0. PRESENTACION

2

{Pre: n ∈ IN Post: x, y, z ∈ IN tales que xn + y n = z n} Parte II: Complejidad. En esta parte veremos: C´mo medir la velocidad de un algoritmo en funci´n del tama˜o o o n de la entrada. Existen problemas que se pueden resolver en tiempo razonable y otros no, se trata de los problemas tratables e intratables. Nos dedicaremos a los segundos. EJERCICIO Escribir un programa en ada que resuelva el siguiente problema (atenci´n a la eficiencia): o 0.3. Setrata de un viajante que necesita recorrer n ciudades en el menor tiempo posible. Disponemos de la distancia correspondiente a cada pareja de ciudades, d(i, j) es la distancia de la ciudad i a la j, las ciudades est´n numeradas correlativamente de 1 a n. a Escribir un programa que dados n y d(i, j) para todo i, j encuentre un camino (una ordenaci´n de las n ciudades) de forma que la suma o de lasdistancias recorridas en ese camino sea la m´ ınima posible.

Bibliograf´ ıa
[Jones] N. Jones: “Computability and Complexity From a Programming Perspective”, MIT press, 1997. [Cu80] N.J. Cutland: “Computability: An Introduction to Recursive Function Theory”, Cambridge University Press, 1980. [So87] R. Soare: “Recursively Enumerable Sets and Degrees”, SpringerVerlag, 1987. [LP81] H.R. Lewis, C.H.Papadimitriou: “Elements of the Theory of Computation”, Prentice-Hall, 1981. [GJ78] M. Garey, D. Johnson: “Computers and Intractability: A Guide to the Theory of NP-Completeness”, Freeman, 1978. [HMU02] J.E. Hopcroft, R. Motwani, J.D. Ullman, “Introducci´n a la o Teor´ de Aut´matas, Lenguajes y Computaci´n”, Addisonıa o o Wesley, 2002. ` [SACL01] M. Serna, C. Alvarez, R. Cases, A. Lozano: “Els l´ımits de la computaci´. Indecidibilitat i NP-completesa”, Edicions UPC, o 2001.

3

Cap´ ıtulo 1

Preliminares. Numerabilidad y diagonalizaci´n o
Referencia: Cap´ ıtulo 1 de [LP81]. En el estudio de la calculabilidad y la complejidad, es imprescindible formular afirmaciones rigurosas y relacionarlas mediante deducciones rigurosas. En este contexto el lenguaje matem´tico nos permitir´ exa apresarnos con precisi´n y agilidad. o Este cap´ ıtulo contiene un repaso de la notaci´n y conceptos principales o de l´gica, demostraciones, teor´ de conjuntos, lenguajes y alfabetos, y o ıa funciones, adem´s de una breve introducci´n a la teor´ de cardinales y a o ıa a la diagonalizaci´n. o

1.1.
1.1.1.

Preliminares
Notaci´n l´gica: proposiciones o o

Una proposici´n o enunciado es unafrase declarativa ´ sentencia que o o podemos clasificar como cierta o falsa, por ejemplo “α es la primera letra del alfabeto griego”, o “el sol se pone por el este”. Si P y Q son dos proposiciones, podemos formar otras mediante las conectivas l´gicas o ¬, ∧, ∨, ⇒, ⇔:

4

CAP´ ITULO 1. PRELIMINARES. NUMERABILIDAD Y ...

5

Notaci´n formal o ¬P P ∨Q P ∧Q P ⇒Q P ⇔Q

Significado informal...