AED Gui N De Clases Te Ricas





Algoritmos y Estructura de Datos
Guión de clases teóricas del Profesor Pablo Nogueira
Adaptado a doc, pdf y ePub por Pau Arlandis
Este fichero es un guión que se complementa en clase con transparencias, explicaciones en la pizarra y discusiones.
Las secciones y subsecciones en general siguen el orden de secciones del libro. Los corchetes encierran referencias al libro, al código o a lastransparencias. Los dobles corchetes encierran referencias al texto dentro del fichero que todavía no existen (existirán en el futuro). Se pone texto en negrita para enfatizarlo. Existen vínculos a zonas del propio texto o a páginas externas que permiten enlazar o aumentar conocimientos.
Los errores y erratas en el libro y las transparencias se indican en párrafos que comienzan con la palabra‘Errores’. También se proponen cuestiones y ejercicios (señalados con la palabra ‘Ejercicio’) cuya resolución ayudará al alumno a comprender mejor y, en el caso de ejercicios avanzados, a profundizar en los contenidos de la asignatura. Algunos o parte de estos ejercicios se utilizarán como preguntas de examen.
Contenido
Guión de clases teóricas del Profesor Pablo Nogueira 2
Adaptado a doc, pdf y ePub porPau Arlandis 2
Viernes 11-02-2011 6
Material de la asignatura 6
Fechas importantes: 6
Conceptos de Java y POO 6
Conceptos de Java y POO que los alumnos deben repasar 6
Viernes 18-02-2011 7
Abstracción, estructura de datos, y algoritmos 7
6.1 Array Lists 8
Material 8
Interfaz IndexList 8
Clase ArrayIndexList 9
Complejidad y costes amortizados 10
Interfaz java.util.ArrayList de la JCF 10
6.2Node Lists 10
Material 10
Repaso del concepto de lista simple y doblemente enlazada 11
Interfaz Position 11
Clase DNode 11
Interfaz PositionList 12
Clase NodePositionList 12
Viernes 25-02-2011 14
6.3 Iterators 14
Material 14
Concepto de Iterador 14
Interfaces Iterator e Iterable 14
6.3.4 List Iterators in Java 21
6.4.2 Sequences 22
4.2 Analysis of Algorithms 22
Material 22
Resumende principios fundacionales 22
Notación O() 23
Notaciones Omega y Theta 24
Complejidad: comentarios y ejercicios 24
6.4 List ADTs and the Collections Framework 24
Viernes 04-03-2011 25
7 Tree Structures 25
Material 25
7.1 General Trees 25
7.2 Tree Traversal Algorithms 30
7.2.2 Preorder Traversal 31
7.2.3 Postorder Traversal 31
Traversals: comentarios y ejercicio 32
7.3 Binary Trees 32
Viernes11-03-2011 37
7 Tree Structures (continuación) 37
7.3 Binary Trees (continuación) 37
8 Priority Queues 39
Material 39
8.1 The Priority Queue Abstract Data Type 40
8.2 Implementing a Priority Queue with a List 44
Viernes 01-04-2011 46
8.3 Heaps 46
Material 46
Motivación de los montículos 47
Arboles Binarios (Casi)Completos 47
Montículos 52
8.3.3 Implementing a Priority Queue with a Heap 53
8.3.4 AJava Heap Implementation 54
8.3.5 Heap Sort 54
Viernes 08-04-2011 54
9.1 Maps 54
Material 54
Motivación de las funciones finitas 54
Definición matemática de función finita 55
9.1.1 The Map ADT 56
9.1.2 A Simple List-Based Map Implementation. 57
Maps en la JCF 60
9.2 Hash tables 60
Material 60
Motivación de tablas de dispersión 60
Definicíon de tablas de dispersión 60
9.2.3 Hash Codes 61
9.2.4Compression Functions 63
9.2.5 Collision-Handling Schemes 63
9.2.7 Load Factors and Rehashing 67
9.2.6 A Java Hash Table Implementation 67
Viernes 15-04-2011 68
9.5 Dictionaries 68
Material 68
Motivación de los diccionarios 69
9.5.1 The Dictionary ADT 69
9.5.3 An Implementation Using the java.util Package 70
Viernes 06-05-2011 72
9.3 Ordered Maps 72
Material 72
Motivación de las funciones finitas condominio ordenado 72
9.3.1 Ordered Search Tables and Binary Search 73
10.1 Binary Search Trees 75
Material 75
Motivación de los árboles binarios de búsqueda. 76
Representación mediante árboles binarios 77
10.1.1 Searching 77
10.1.2 Update Operations 78
10.1.3 Java Implementation 81
Críticas a la implementación BinarySearchTreeMap 84
Viernes 13-05-2011 85
10.2 AVL Trees 85
Material 85
Motivación de...

Leer documento completo

Regístrate para leer el documento completo.