Innovacion

ESTRUCTURAS DE DATOS Y ´ ANALISIS DE ALGORITMOS
Una Introduccion usando Java ´

Jose Galaviz Casas ´
Departamento de Matematicas ´ Facultad de Ciencias Universidad Nacional Autonoma de Mexico ´ ´

´ndice General I

1 Introduccion ´ 1.1 1.2 1.3 1.4 1.5 Motivaci´ n o TDA’s, Estructuras de Datos, Clases y Objetos An´ lisis de Algoritmos. a Pruebas de correctez. Resumen. Par´ ntesis:Complejidad computacional. e Referencias Ejercicios

1 1 4 11 35 38 40 40 41 45 45 50 51 56 60 63 63
iii

2 Arreglos 2.1 2.2 2.3 2.4 Motivaci´ n. o Arreglos multidmensionales. Polinomios de direccionamiento. Arreglos empacados. Ejercicios

3 Recursion ´ 3.1 Introducci´ n o

iv

´NDICE GENERAL I

3.2 Ejemplos 3.2.1 Factorial 3.2.2 La sucesi´ n de Fibonacci o 3.2.3 Las torres de Hanoi 3.2.4Retroceso m´nimo: El problema de las ocho reinas ı Par´ ntesis: Recursi´ n y computabilidad. e o Referencias Ejercicios

64 64 65 71 71 82 82 83

Cap´tulo 1 ı

´ INTRODUCCION

La introducci´ n es divertida y hasta traviesa, el autor se regocija en la presentaci´ n de los o o elementos y recursos de que echar´ mano en el resto de la obra. [...] Sin duda la audiencia a disfrutar´ de la obrasin importar su edad. a —Presentaci´ n del cuento sinf´ nico Babar el Elefantito, INBA, 1998. o o

´ 1.1 MOTIVACION

A menos que se tengan ni˜ os peque˜ os (c´ mo es mi caso), los diversos obn n o jetos en casa suelen estar acomodados de acuerdo a cierto orden, agrupados con los de su clase: los libros en un librero, la despensa en la alacena, los alimentos perecederos en el refrigerador, laropa en el ropero o en el “closet”, etc. En nuestros lugares de trabajo las cosas son similares, en general los objetos de los que nos servimos suelen estar organizados de acuerdo con un orden preestablecido. La raz´ n para mantener las cosas en un estado por o lo menos cercano a la organizaci´ n perfecta, es la eficiencia. Todos hemos o padecido el disgusto, cuando no la desesperaci´ n, de buscaralgo que hemos o dejado en alg´ n lugar ajeno a su colocaci´ n habitual. Se pierden miserableu o
Estructuras de Datos y An´ lisis de Algoritmos, una Introducci´ n usando Java. Jos´ Galaviz a o e c 2005 Fac. de Ciencias, UNAM.

1

2

´ INTRODUCCION

mente varias horas buscando, a veces infructuosamente, un objeto perdido en la complejidad de nuestro entorno. Hay casos extremos en los quela organizaci´ n de los objetos es fundao mental. En el caso de una biblioteca, por ejemplo, el orden de los libros en la estanter´a debe ser perfecto. Pensemos en buscar un libro espec´fico en ı ı una biblioteca en la que los vol´ menes est´ n acomodados aleatoriamente o u a siguiendo alg´ n criterio extravagante (por tama˜ o, por grosor o por lo que u n sugiere el t´tulo). ¿Cuanto tiempo tomar´encontrar un libro en particular? ı a No podemos saberlo, pero en el peor de los casos ser´ el ultimo luego de a ´ haber recorrido todos los t´tulos en el acervo, as´ que nos tardaremos m´ s ı ı a cuanto mayor sea este. Los libros est´ n organizados estrictamente para poa der encontrar cualquiera de ellos r´ pidamente. Lo mismo ocurre con las a historias m´ dicas en un hospital, con los archivos deuna escuela, los de la e compa˜ ´a de tel´ fonos o del registro civil. A peque˜ a escala tambi´ n ocunı e n e rre en nuestros hogares. Idealmente organizamos los CD’s, los libros, las cuentas por pagar, las facturas, la despensa, el contenido del refrigerador y la ropa por lavar. Toda esta organizaci´ n es para poder hacer r´ pidamente o a ciertas operaciones: poner m´ sica, lavar ropa, comer ocepillarse los dientes. u Poseer cierta estructura en los objetos que manipulamos permite optimizar el tiempo invertido en las operaciones que hacemos con ellos. En el contexto de los programas de computadora la situaci´ n no es difeo rente. Los programas operan con datos de entrada, los manipulan a trav´ s e de una secuencia finita de pasos y luego nos entregan resultados basados en esos datos....