PDF de programación - Algoritmos y Estructuras de Datos

Universidad Central de Venezuela

Facultad de Ciencias

Escuela de Computación

Lecturas en Ciencias de la Computación

ISSN 1316-6239

Algoritmos y Estructuras de Datos

Esmitt Ramírez

ND 2015-01

Centro de Computación Gráfica de la UCV

CCG-UCV

Caracas, marzo 2015

Lecturas en Ciencias de la Computación

ND 2015-01

ISSN 1316-6239

Algoritmos y Estructuras de Datos

Esmitt Ramírez

Marzo 2015

Este documento pretende servir como una guía para el estudio de algoritmos y estructuras de datos básicas para la composición
de soluciones computacionales basadas en algoritmos sobre lenguajes imperativos. La estructura del documento corresponde
en gran parte con el programa de estudios que ofrece la Licenciatura en Computación de la Universidad Central de Venezuela
en su Plan de Estudio 2004, específicamente a la asignatura Algoritmos y Estructuras de Datos correspondiente al 2do período
semestral de una carrera de 10 períodos. Así, se busca introducir al estudiante en las destrezas en el área de la algorítmica
y la programación para la construcción de programas de manera sistemática y haciendo un uso eficiente de los recursos
computacionales. Entonces se busca explicar conceptos teóricos involucrando a su vez el desarrollo de ejercicios prácticos.
El documento se divide en seis grandes partes: Tipos de Datos, Recursión, Backtracking, Complejidad, Estructuras Dinámicas,
y Árboles. Para cada parte se trata de mostrar las siguientes secciones:

• Definiciones: Se muestran conceptos básicos dentro de un marco teórico asociado al tema a estudiar.
• Clasificaciones/Implementaciones: Por cada sección se clasifica el tópico de estudio y/o se muestran las diversas imple-

mentaciones algorítmicas de las estructuras de datos o técnicas.

• Ejercicios: Ciertos algoritmos/ejemplos se muestran para ser explicados en detalle.
• Algoritmos: Un conjunto de algoritmos/ejemplos clásicos son mostrados explicando en qué consiste el problema.
• Ideas Finales: Un conjunto de ideas principales para el cierre de cada sección.
• Problemas: Se listan ejercicios simples para ser realizados por los estudiantes o en clases prácticas.

El orden de las secciones no es estricto, pero en muchas de ellas se requiere información previa. Por ejemplo, para el tema
de Árboles se requiere del conocimiento base explicada en la sección Recursión por ser una estructura de datos recursiva por
definición. Igualmente, es el facilitador/docente quién decide el orden al momento de difundir conocimiento.
Este documento no contiene todos los aspectos relacionados con cada sección, ya que trata de ser una guía para un período de
clases de aproximadamente 4 horas semanales durante un período de 14 semanas (56 horas). Así, de antemano se recomienda
complementar su utilización con otros textos o material bibliográfico de los tópicos explicados.
Todo el documento emplea la notación Alpha1 la cual consiste en una notación algorítmica básica basada en pseudocódigo
para la escritura de algoritmos y estructuras de datos. La idea es ser consistente al momento de la docencia y no incurrir en
errores como mezclar notaciones de diversos lenguajes de programación. Además, la notación permite una rápida conversión
a cualquier lenguaje de programación moderno.
Este documento puede contener errores. Por ello, se recomienda buscar la última versión en el repositorio git de dirección
https://github.com/esmitt/notas-docencia-ayed.git. La ayuda siempre es bienvenida por ello puede enviar un pull request en
Github para colaborar.

1La especificación completa de la notación Alpha está disponible en http://goo.gl/SOHo8h

1

Tabla de Contenidos

I Tipos de Datos
1 Definiciones
2 Tipo de Dato Simple

2.1 Tipo Integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Tipo Real
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Tipo Char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Tipo Boolean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Tipo Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Tipo Pointer
2.7 Ejemplo de declaraciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Tipo de Dato Compuesto

3.1 Tipo Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Unidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Bidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Tipo String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Tipo Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Tipo File
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Tipo de Dato Pointer
4.1 Conjunto de valores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Conjunto de operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Operador new . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Operador delete
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Memoria dinámica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Ideas Finales
6 Problemas

II Recursividad
1 Definiciones
2 Algoritmo Recursivo
3 Ejecución
4 Clasificación
5 Iterativo vs. Recursivo
6 Ejercicios

6.1

Imprimir una secuencia de números . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Potenciación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.2 Convertir un decimal a binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Algoritmos

7.1 Collatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Búsqueda Binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Hanoi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 Palíndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5
Invertir un número . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Ideas Finales
9 Problemas

III Backtracking

2

5
5
6
6
7
8
8
8
9
9

10
10
10
11
12
12
13

13
13
13
14
14
15

16
16

18
18
18
19
19
20
20
21
21
22

23
23
23
23
24
24

24
25

26

1 Definiciones
2 Técnica de Backtracking
3 Clasificación
4 Ejercicios

4.1 Suma Parcial
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 n-Reinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Algoritmos

5.1 Laberinto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Problema de la Mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Ideas Finales
7 Problemas

IV Complejidad en Tiempo
1 Definiciones
2 Operaciones Elementales

2.1 Tasas de crecimiento más comunes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Notaciones Asintóticas
4 Análisis de Complejidad

4.1 Regla de la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Regla del Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Complejidad de Algoritmos Iterativos
6 Ejercicios

6.1 Búsqueda Lineal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Búsqueda Binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Algoritmos
8 Complejidad de Algoritmos Recursivos

8.1 Clase de Recurrencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Ejercicios

9 Ideas Finales
10 Problemas

V Estructuras de Datos Dinámicas
1 Tipo List

1.1 Simplemente Enlazada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Especificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 Ejemplos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3
1.2 Doblemente Enlazad