Curso [2-11] Diseño y Manejo de Estructuras de Datos en Lenguaje JAVA
Contenido CAPITULO 0 - CONCEPTOS BÁSICOS
0.1. Diseño y documentación de algoritmos
0.1.1. Los conceptos de estado y aserción
0.1.2. La especificación de un programa
0.1.3. Dividir y conquistar
0.1.4. Consideración de casos
0.1.5. Ciclos e invariantes
0.2. Recursión
0.2.1. Conceptos básicos
0.2.2. Estructura de una rutina recursiva
0.2.3. Metodología de desarrollo
Ejercicios propuestos
0.3. Análisis de algoritmos
0.3.1. Definición del problema
0.3.2. Tiempo de ejecución de un algoritmo
0.3.3. El concepto de complejidad
0.3.4. Aritmética en notación O
0.3.5. Ejemplos
0.3.6. Complejidad en espacio
0.3.7. Selección de un algoritmo
0.3.8. Complejidad de rutinas recursivas
Ejercicios propuestos
Cap 0 - Ejercicios Implementados
CAPITULO 1 - DISEÑO DE SOFTWARE Y TIPOS ABSTRACTOS
1.1. Ingeniería de software
1.1.1. Ciclo de vida del software
1.1.2. Software de alta calidad
1.1.3. Arquitectura del software
1.1.4. Reutilización de software: genericidad
1.2. Tipos abstractos de datos
1.2.1. Motivación y definiciones
1.2.2. Representación de un objeto abstracto
1.2.3. El invariante de un TAD
1.2.4. Especificación de un TAD
1.2.5. Clasificación de las operaciones
1.2.6. Manejo de error
1.2.7. Metodología de diseño de TAD
1.2.8. Uso de TAD en solución de problemas
1.2.9. Genericidad: TAD paramétricos
Ejercicios propuestos
1.3. Diseño de estructuras de datos
1.3.1. Relación objeto abstracto - estructuras de datos
1.3.2. Consideraciones básicas
1.3.3. Representación de longitud variable
1.3.4. Manejo de información redundante
1.3.5. Representaciones compactas vs. exhaustivas
1.3.6. Ordenamiento físico vs. lógico
1.3.7. Representación implícita vs. explícita
1.3.8. Incorporación de restricciones del problema
1.3.9. Estructuras de datos para el TAD Matriz
1.3.10. Un TAD como estructura de datos
1.3.11. Esquema de persistencia
Ejercicios propuestos
1.4. Implementación de las operaciones de un TAD
1.4.1. Esquema de implementación en C
1.4.2. Documentación
1.4.3. Implementación de la genericidad
1.4.4. Probador interactivo de un TAD
Cap 1 - Ejercicios Implementados
CAPITULO 2 - ESTRUCTURAS LINEALES: LISTAS
2.1. Definiciones y conceptos básicos
2.2. El TAD Lista
2.3. Ejemplos de utilización del TAD
2.4. Otras operaciones interesantes
2.5. Esquema de persistencia
2.6. Algunas implementaciones del TAD Lista
2.6.1. Estructura doblemente encadenada
2.6.2. Vectores
2.6.3. Encadenamiento sencillo con centinela
2.6.4. Encadenamiento sencillo con encabezado
2.6.5. Representación a nivel de bits
2.6.6. Representación compacta de elementos repetidos
2.6.7. Multirrepresentación
2.6.8. Tabla comparativa
Ejercicios propuestos
2.7. El TAD Lista ordenada
2.8. Implementación del TAD Lista ordenada
2.8.1. Sobre el TAD Lista
2.8.2. Estructura sencillamente encadenada
Ejercicios propuestos
Cap 2 - Ejercicios implementados
CAPITULO 3 - ESTRUCTURAS LINEALES: PILAS Y COLAS
3.1. Pilas: definiciones y conceptos básicos
3.2. El TAD Pila
3.3. Ejemplos de utilización del TAD Pila
Ejercicios propuestos
3.4. Implementación del TAD Pila
3.4.1. Listas
3.4.2. Vectores
3.4.3. Estructura sencillamente encadenada
Ejercicios propuestos
3.5. Colas: definiciones y conceptos básicos
3.6. El TAD Cola
3.7. Ejemplos de utilización del TAD Cola
Ejercicios propuestos
3.8. Implementación del TAD Cola
3.8.1. Listas
3.8.2. Vectores circulares
Ejercicios propuestos
3.9. El TAD Cola de prioridad
3.10. Implementación del TAD Cola de prioridad
Ejercicios propuestos
3.11. El TAD Ronda
Ejercicios propuestos
3.12. El TAD Bicola
Ejercicios propuestos
Cap 3 - Ejercicios implementados
CAPITULO 4 - ESTRUCTURAS RECURSIVAS: ARBOLES BINARIOS
4.1. Definiciones y conceptos básicos
4.2. El TAD Arbin: analizadoras para árboles binarios
4.3. Ejemplos de utilización del TAD Arbin
Ejercicios Propuestos
4.4. Recorrido de árboles binarios
4.4.1. Algoritmo de recorrido por niveles
4.4.2. Algoritmo iterativo de recorrido de árboles
4.4.3. Reconstrucción de un árbol a partir de sus recorridos
Ejercicios propuestos
4.5. Algorítmica de manejo de árboles
Ejercicios propuestos
4.6. Implementación de árboles binarios
4.6.1. Árboles sencillamente encadenados
4.6.2. Árboles con encadenamiento al padre
4.6.3. Árboles enhebrados por la derecha
4.6.4. Cursores
4.6.5. Representación secuencial
4.7. Destrucción y persistencia de árboles binarios
4.7.1. Persistencia con cursores
4.7.2. Persistencia con representación secuencial
4.7.3. Destructora del TAD Arbin
Ejercicios propuestos
4.8. El TAD árbol binario ordenado
4.8.1. Proceso de búsqueda
4.8.2. Proceso de inserción
4.8.3. Proceso de eliminación
Ejercicios propuestos
4.9. Árboles binarios ordenados balanceados
4.9.1. El TAD AVL
4.9.2. Estructuras de datos
4.9.3. Algoritmo de inserción
4.9.4. Algoritmo de eliminación
Ejercicios propuestos
4.10. El TAD árbol de sintaxis
4.10.1. Expresiones aritméticas en infijo
4.10.2. Árboles de sintaxis
4.10.3. La tabla de símbolos
4.10.4. El TAD Arsin
Ejercicios propuestos
Cap 4 - Ejercicios Implementados
CAPITULO 5 - ESTRUCTURAS RECURSIVAS: ARBOLES N-ARIOS
5.1. Motivación
5.2. Definiciones y conceptos básicos
5.3. El TAD ArbolN: analizadoras
5.4. Ejemplos de utilización
Ejercicios propuestos
5.5. Implementación del TAD ArbolN.
5.5.1. Vector de apuntadores
5.5.2. Hijo izquierdo - hermano derecho
5.5.3. Vectores dinámicos
5.5.4. Lista de hijos
5.5.5. Representaciones implícitas
5.6. El TAD ArbolN: algunas modificadoras y destructoras
5.6.1. Implementación sobre vector de apuntadores
5.6.2. Implementación sobre apuntadores
5.6.3. Implementación sobre vectores dinámicos
5.6.4. Implementación sobre lista de hijos
Ejercicios propuestos
5.7. El TAD Arbol1-2-3: un árbol triario ordenado
Ejercicios propuestos
5.8. El TAD Arbol2-3: un árbol triario ordenado balanceado
5.8.1. Definiciones y conceptos básicos
5.8.2. Especificación del TAD
5.8.3. Estructuras de datos
5.8.4. Algoritmo de inserción
5.8.5. Algoritmo de eliminación
Ejercicios propuestos
5.9. El TAD Trie: conjunto de palabras
Ejercicios propuestos
5.10. El TAD Cuadtree: representación de imágenes
Ejercicios propuestos
5.11. El TAD Árbol AND-OR
Ejercicios propuestos
5.12. Árboles de juego
Ejercicios propuestos
Cap 5 - Ejercicios Implementados
CAPITULO 6 - ESTRUCTURAS NO LINEALES: GRAFOS DIRIGIDOS
6.1. Motivación
6.2. Definiciones y conceptos básicos
6.3. El TAD Grafo
6.4. Caminos en un grafo
Ejercicios propuestos
6.5. Recorrido de grafos
6.5.1. Recorrido plano sobre el conjunto de vértices
6.5.2. Recorrido en profundidad
6.5.3. Recorrido por niveles
Ejercicios propuestos
6.5.4. Recorridos heurísticos
Ejercicios propuestos
6.6. Más definiciones sobre grafos
Ejercicios propuestos
6.7. El algoritmo de Dijkstra
6.7.1. Costo de los caminos mínimos
6.7.2. Caminos mínimos
Ejercicios propuestos
6.8. Implementación del TAD Grafo
6.8.1. Matrices de adyacencias
6.8.2. Listas de sucesores
6.8.3. Listas encadenadas de adyacencias
6.8.4. Listas de arcos
6.8.5. Estructuras de datos implícitas
Ejercicios propuestos
Cap 6 - Ejercicios implementados
CAPITULO 7 - ESTRUCTURAS DE ACCESO DIRECTO: TABLAS DE HASHING
7.1. Motivación
7.2. Definiciones y conceptos básicos
7.3. El TAD TablaH
7.4. Implementación del TAD TablaH
7.4.1. Listas de clases de equivalencia
7.4.2. Distribución en área primaria
7.4.3. Bloques con área de desbordamiento
Ejercicios propuestos
7.5. Funciones de hashing
7.5.1. Funciones de división
7.5.2. Funciones de truncamiento
7.5.3. Funciones sobre un espacio intermedio