2011 Algoritmos y estructuras de datos Pablo Nogueira [



Descargar 398.73 Kb.
Página1/15
Fecha de conversión07.07.2017
Tamaño398.73 Kb.
  1   2   3   4   5   6   7   8   9   ...   15





2011




Algoritmos y estructuras de datos
Pablo Nogueira




[GUIÓN DE CLASES TEÓRICAS]

El guión de clases teóricas de algoritmos y estructuras de datos del profesor Pablo Nogueira que complementan las clases, el libro básico y las transparencias. Adaptado a esta versión por el alumno Pau Arlandis.

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 las transparencias. 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 por Pau Arlandis 2

Viernes 11-02-2011 2

Material de la asignatura 2

Fechas importantes: 3

Conceptos de Java y POO 3

Conceptos de Java y POO que los alumnos deben repasar 3

Viernes 18-02-2011 5

Abstracción, estructura de datos, y algoritmos 5

6.1 Array Lists 5

Material 5

Interfaz IndexList 6

Clase ArrayIndexList 7

Complejidad y costes amortizados 8

Interfaz java.util.ArrayList de la JCF 8

6.2 Node Lists 8

Material 8

Repaso del concepto de lista simple y doblemente enlazada 9

Interfaz Position 9

Clase DNode 9

Interfaz PositionList 10

Clase NodePositionList 10

Viernes 25-02-2011 12

6.3 Iterators 12

Material 12

Concepto de Iterador 12

Interfaces Iterator e Iterable 12

6.3.4 List Iterators in Java 20

6.4.2 Sequences 20

4.2 Analysis of Algorithms 21

Material 21

Resumen de principios fundacionales 21

Notación O() 22

Notaciones Omega y Theta 23

Complejidad: comentarios y ejercicios 23

6.4 List ADTs and the Collections Framework 23

Viernes 04-03-2011 24

7 Tree Structures 24

Material 24

7.1 General Trees 24

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 33

Viernes 11-03-2011 38

7 Tree Structures (continuación) 38

7.3 Binary Trees (continuación) 38

8 Priority Queues 40

Material 40

8.1 The Priority Queue Abstract Data Type 41

8.2 Implementing a Priority Queue with a List 46

Viernes 01-04-2011 48

8.3 Heaps 48

Material 48

Motivación de los montículos 49

Arboles Binarios (Casi)Completos 49

Montículos 55

8.3.3 Implementing a Priority Queue with a Heap 55

8.3.4 A Java Heap Implementation 56

8.3.5 Heap Sort 57

Viernes 08-04-2011 57

9.1 Maps 57

Material 57

Motivación de las funciones finitas 57

Definición matemática de función finita 58

9.1.1 The Map ADT 59

9.1.2 A Simple List-Based Map Implementation. 61

Maps en la JCF 63

9.2 Hash tables 63

Material 63

Motivación de tablas de dispersión 64

Definicíon de tablas de dispersión 64

9.2.3 Hash Codes 65

9.2.4 Compression Functions 66

9.2.5 Collision-Handling Schemes 67

9.2.7 Load Factors and Rehashing 71

9.2.6 A Java Hash Table Implementation 72

Viernes 15-04-2011 73

9.5 Dictionaries 73

Material 73

Motivación de los diccionarios 73

9.5.1 The Dictionary ADT 74

9.5.3 An Implementation Using the java.util Package 75

Viernes 06-05-2011 77

9.3 Ordered Maps 77

Material 77

Motivación de las funciones finitas con dominio ordenado 77

9.3.1 Ordered Search Tables and Binary Search 78

10.1 Binary Search Trees 81

Material 81

Motivación de los árboles binarios de búsqueda. 81

Representación mediante árboles binarios 82

10.1.1 Searching 83

10.1.2 Update Operations 84

10.1.3 Java Implementation 87

Críticas a la implementación BinarySearchTreeMap 91

Viernes 13-05-2011 91

10.2 AVL Trees 91

Material 91

Motivación de los árboles AVL 92

Representación mediante árboles binarios de búsqueda 92

10.2.1 Update Operations 92

10.2.2 Java Implementation 100

Críticas a la implementación AVLTreeMap. 103

Viernes 20-05-2011 104

10.4 (2,4) Trees 104

Material 104

Motivación de árboles multicamino de búsqueda y árboles (2,4) 104

10.4.1 Multi-Way Search Trees 104

Definición de árboles (2,4) 107

10.4.2 Update Operations for (2,4) Trees 107

Viernes 27-05-2011 111

14.2 External Memory and Caching 111

Material 111

Algunas notas a las transparencias 111

14.3 External Searching and B-Trees 112

Material 112

Motivación de los árboles (a,b) y B 112

14.3.1 (a,b) Trees 112



14.3.1 B-Trees 112


  1   2   3   4   5   6   7   8   9   ...   15


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal