PDF de programación - ESTRUCTURAS DE DATOS Y ANÁLISIS DE ALGORITMOS - Una Introducción usando Java

ESTRUCTURAS DE DATOS Y
AN ´ALISIS DE ALGORITMOS
Una Introducci ´on usando Java

Jos´e Galaviz Casas
Departamento de Matem´aticas
Facultad de Ciencias
Universidad Nacional Aut´onoma de M´exico

´Indice General

1 Introducci ´on
1.1 Motivaci´on
1.2 TDA’s, Estructuras de Datos, Clases y Objetos
1.3 An´alisis de Algoritmos.
1.4 Pruebas de correctez.
1.5 Resumen.

Par´entesis: Complejidad computacional.
Referencias
Ejercicios

2 Arreglos

2.1 Motivaci´on.
2.2 Arreglos multidmensionales.
2.3 Polinomios de direccionamiento.
2.4 Arreglos empacados.

Ejercicios

3 Recursi ´on

3.1 Introducci´on

1
1
4
11
35
38
40
40
41

45
45
50
51
56
60

63
63
iii

iv

´INDICE GENERAL

3.2 Ejemplos

3.2.1 Factorial
3.2.2 La sucesi´on de Fibonacci
3.2.3 Las torres de Hanoi
3.2.4 Retroceso m´ınimo: El problema de las ocho reinas
Par´entesis: Recursi´on y computabilidad.
Referencias
Ejercicios

64
64
65
71
71
82
82
83

Cap´ıtulo 1

INTRODUCCI ´ON

La introducci´on es divertida y hasta traviesa, el autor se regocija en la presentaci´on de los
elementos y recursos de que echar´a mano en el resto de la obra. [...] Sin duda la audiencia
disfrutar´a de la obra sin importar su edad.

—Presentaci´on del cuento sinf´onico Babar el Elefantito, INBA, 1998.

1.1 MOTIVACI ´ON

A menos que se tengan ni˜nos peque˜nos (c´omo es mi caso), los diversos ob-
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, la ropa 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´on para mantener las cosas en un estado por
lo menos cercano a la organizaci´on perfecta, es la eficiencia. Todos hemos
padecido el disgusto, cuando no la desesperaci´on, de buscar algo que hemos
dejado en alg´un lugar ajeno a su colocaci´on habitual. Se pierden miserable-
1

Estructuras de Datos y An´alisis de Algoritmos, una Introducci´on usando Java. Jos´e Galaviz
c(cid:13)2005 Fac. de Ciencias, UNAM.

2

INTRODUCCI ´ON

mente varias horas buscando, a veces infructuosamente, un objeto perdido
en la complejidad de nuestro entorno.

Hay casos extremos en los que la organizaci´on de los objetos es funda-
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´umenes est´an acomodados aleatoriamente o
siguiendo alg´un criterio extravagante (por tama˜no, por grosor o por lo que
sugiere el t´ıtulo). ¿Cuanto tiempo tomar´a encontrar un libro en particular?
No podemos saberlo, pero en el peor de los casos ser´a el ´ultimo luego de
haber recorrido todos los t´ıtulos en el acervo, as´ı que nos tardaremos m´as
cuanto mayor sea este. Los libros est´an organizados estrictamente para po-
der encontrar cualquiera de ellos r´apidamente. Lo mismo ocurre con las
historias m´edicas en un hospital, con los archivos de una escuela, los de la
compa˜n´ıa de tel´efonos o del registro civil. A peque˜na escala tambi´en ocu-
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´on es para poder hacer r´apidamente
ciertas operaciones: poner m´usica, lavar ropa, comer o cepillarse los dientes.
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´on no es dife-
rente. Los programas operan con datos de entrada, los manipulan a trav´es
de una secuencia finita de pasos y luego nos entregan resultados basados en
esos datos. Nuestros programas ser´an m´as eficientes, aprovechar´an mejor
los recursos disponibles (tiempo de procesador, memoria y acceso a dispo-
sitivos de E/S), dependiendo de la manera en que son organizados los datos
de entrada o los resultados parciales del proceso. Igual que en una biblio-
teca, la manera de organizar los datos establece v´ınculos entre ellos y se
conforma lo que denominaremos una estructura de datos, uno de los temas
fundamentales del presente texto.

Para poder evaluar la eficiencia de nuestros algoritmos en general, y en
particular el impacto que diversas estructuras de datos tienen sobre dicha
eficiencia, requeriremos de m´etodos que nos permitan cuantificar los recur-
sos consumidos. El t´ermino adecuado para referirse a esto es: an´alisis de
algoritmos, el otro tema central del texto.

Ambas cosas tienen singular relevancia tanto en el ´ambito de la computa-
ci´on te´orica como en el de la pr´actica de la programaci´on. No puede haber
una propuesta seria de un nuevo algoritmo o un protocolo de comunicaci´on
que no est´e sustentada por un an´alisis te´orico de los mismos. Asimismo
no es posible pensar en que las decisiones de un programador respetable no
sean las adecuadas para optimizar el desempe˜no de sus programas.

MOTIVACI ´ON

3

Figura 1.1. El Quixote de Pablo Picasso. Un buen ejemplo de abstracci´on

El an´alisis de algoritmos y las estructuras de datos, como el resto de las Abstrac-

ci ´on.

cosas que se hacen en ciencia, est´an basados en abstracciones. La abstrac-
ci´on es el camino que los seres humanos utilizamos para comprender la
complejidad. La teor´ıa de la gravitaci´on, el ´algebra de Boole, los modelos
econ´omicos y los ecol´ogicos son ejemplos de ello. Todos son abstraccio-
nes hechas en un intento por comprender fen´omenos complejos en los que
intervienen una multitud de factores con intrincadas relaciones entre ellos.
Una abstracci´on es una descripci´on simplificada de un sistema y lo m´as
importante en ella es que enfatiza las caracter´ısticas esenciales y descarta
aquellas que se consideran sin importancia para explicar el comportamiento
del sistema. En la teor´ıa de la gravitaci´on, por ejemplo, no son consideradas
las propiedades magn´eticas o qu´ımicas de los cuerpos, solo interesan cosas
como su masa y las distancias entre ellos.

Formular una buena abstracci´on es como hacer una buena caricatura. Con
unos cuantos trazos simples el caricaturista representa un personaje que
es posible reconocer sin ambig¨uedad, nada sobra y nada falta, ha sabido
encontrar aquellos rasgos que caracterizan a la persona y ha sabido resaltarlos
aisl´andolos de todos los que no son relevantes. En la figura 1.1. se muestra
un buen ejemplo de abstracci´on. Todos podemos reconocer a Don Quijote
y Sancho en sus respectivas monturas y en el episodio de los molinos de
viento, no hacen falta los colores ni las texturas ni los detalles de rostros,
cuerpos y paisaje.

4

INTRODUCCI ´ON

1.2 TDA’S, ESTRUCTURAS DE DATOS, CLASES Y OBJETOS

Por supuesto la programaci´on de computadoras es un ejercicio de abstrac-
ci´on. Particularmente cuando se definen las propiedades y los atributos de
los datos que han de manipular los programas. En el paradigma actual de
la programaci´on se pretende modelar con entes abstractos llamados objetos,
a los actores reales involucrados en el problema que se intenta resolver con
el uso del programa. Los atributos y el comportamiento de estos objetos
est´an determinados por la abstracci´on que el programador hace de los ac-
tores reales con base en el contexto del problema. Si lo que se pretende es
modelar personas de una cierta localidad con el prop´osito de estudiar sus ca-
racter´ısticas gen´eticas, entonces convendr´a considerar como abstracci´on de
persona un conjunto de atributos como la estatura, el color de ojos, de cabe-
llo, de piel o el tipo sangu´ıneo; si el problema en cambio, est´a vinculado con
las caracter´ısticas socio-econ´omicas entonces los atributos que convendr´ıa
incluir en la abstracci´on son los ingresos mensuales, el gasto promedio y el
tipo de trabajo de las personas reales.

A fin de cuentas lo que hace el programador es crear un nuevo tipo de dato
que modele los objetos involucrados en el problema que pretende resolver.
Al igual que los tipos elementales que posee el lenguaje de programaci´on que
utilizar´a, el tipo definido por el programador posee un conjunto de posibles
valores, un dominio y un conjunto de operaciones b´asicas definidas sobre
los elementos de ese dominio. Un modelo as´ı se conoce como un Tipo de
Dato Abstracto.

Un tipo de dato abstracto o TDA es un modelo que describe a todos los
elementos de un cierto conjunto dominio, especificando su comportamiento
bajo ciertas operaciones que trabajan sobre ellos. El uso del t´ermino abs-
tracto significa, c´omo sabemos, que s´olo atiende a aquellas cualidades que
interesan de los elementos del dominio y que son manifiestas a trav´es de las
operaciones. Esto significa, en t´erminos matem´aticos, que un TDA no dice
m´as que aquello que se puede inferir del comportamiento de sus operacio-
nes, es lo que suele llamarse un sistema formal, c´omo lo son la geometr´ıa
euclidiana, la l´ogica de primer orden o los n´umeros naturales. Como en todo
sistema formal, el comportamiento b´asico de los elementos del dominio est´a
regido por una serie de premisas elementales que se suponen verdaderas a
priori, un conjunto de axiomas.

La cualidad m´as relevante en la abstracci´on de datos es que, al elaborar
un nuevo modelo para un tipo de dato lo importante es decidir qu´e es lo
que se puede hacer con un dato de ese tipo y no c´omo es que se hace.
La especificaci´on de lo que se puede hacer (las operaciones) debe ser lo
suficientemente rigurosa como para explicar completamente su efecto sobre

Tipo de
Dato
Abstracto
(TDA).

TDA’S, ESTRUCTURAS DE DATOS, CLASES Y OBJETOS

5

los datos que componen al tipo, pero no debe especificar c´omo es que se logra
dicho efecto ni c´omo estos datos est´an organizados. Es decir, la definici´on
de un TDA es diferente de su implementaci´on concreta en un lenguaje de
progr