Estructuras de Datos Avanzadas

Usted está aquí

Inicio » Estudios » Másteres » Máster en Innovación e Investigación en Informática » Plan de estudios » Asignaturas » Estructuras de Datos Avanzadas
Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
Mail
Efficient strategies and techniques for "structured data" are key in modern computer science to design fast algorithms useful in a variety of every day applications (like web archiving, mail servers, network routers, video games).
This course explores selected topics on fundamental data structures that may be multidimensional, metric, geometric, kinetic, self-adjusting, concurrent, distributed, etc.
The tour covers, for each topic, major results and characteristic ways of analysis as well as possible directions of research.

Profesorado

Responsable

  • Amalia Duch Brown ( )

Otros

  • Conrado Martínez Parra ( )
  • Salvador Roura Ferret ( )
  • Xavier Messeguer Peypoch ( )

Horas semanales

Teoría
4
Problemas
0
Laboratorio
0
Aprendizaje dirigido
0.16
Aprendizaje autónomo
4

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

Competencias Transversales

Uso solvente de los recursos de información

  • CTR4 - Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información del ámbito de la ingeniería informática y valorar de forma crítica los resultados de esta gestión.

Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.
  • CB8 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

Objetivos

  1. Become acquainted with main and classical data structures of central areas of computer science and with their major properties.
    Competencias relacionadas: CB8, CB9, CTR4,
  2. Become familiar with the mathematical tools usually used to analyze the performance of data structures.
    Competencias relacionadas: CG3, CEE3.1, CEE3.2, CB9, CTR6,
  3. Examine ideas, analysis and implementation details of data structures in order to assess their fitness to different classes of problems.
    Competencias relacionadas: CG1, CG3, CEE3.1, CEE3.2, CB6, CB8, CB9, CTR4, CTR6,
  4. Select, design and implement appropriate data structures to solve given problems.
    Competencias relacionadas: CG1, CG3, CEE3.1, CEE3.2, CB6, CB9, CTR4, CTR6,

Contenidos

  1. Preliminares
    Review of required previous knowledge: asymptotic notation, basic algorithm analysis, arrays, linked lists, stacks and queues, basics of hashing, binary search trees, AVL trees, red-black trees, heaps.
  2. Techniques.
    Techniques: Experimental algorithmics. Probabilistic analysis of algorithms. Amortized analysis.
  3. Disjoint Sets.
    Disjoint Sets: Union-find data structures (a.k.a. merge-find sets). Union by weight. Path compression heuristics. Applications.
  4. Priority Queues.
    Priority Queues: Heaps. Binomial queues. Fibonacci heaps.
  5. Data Structures for Strings
    Data Structures for Strings: Tries. Patricia tries. Suffix trees and suffix arrays.
  6. Self-adjusting data structures.
    Self-adjusting data structures: List updates, Splay trees.
  7. Randomized data structures.
    Randomized data structures: randomized BSTs, treaps.
  8. Multidimensional and metric data structures, searching in metric spaces, associative retrieval and object representation.
    Multidimensional and metric data structures, searching in metric spaces, associative retrieval and object representation: grid files, kd trees, point quad trees, PR quad trees, octrees.
  9. Geometric and kinetic data structures.
    Geometric and kinetic data structures: interval, segment and partition trees, sweep lines.
    Data structures for points in motion.
  10. External memory / cache oblivious.
    External memory / cache oblivious: models, B-trees, ordered-file maintenance, van Emde-Boas layout.
  11. Succinct Data Structures.
    Succinct rank and select operations.
  12. Miscellaneous.
    Miscellaneous: concurrent, distributed, augmented, persistent data structures.

Actividades

Actividad Acto evaluativo



Deliverables.

Deliverables.
Objetivos: 1 4 3 2
Semana: 14 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Final Work.

Presentation or deliberation of the Final Work (resulting from the Research Assignment).
Objetivos: 1 4 3 2
Semana: 18 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
10h

Assignments.

Assignments.
Objetivos: 1 4 3 2
Semana: 18 (Fuera de horario lectivo)
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h


Metodología docente

The lectures are theoretical/practical merged sessions.
The lecturer will allocate the hours in accordance with the subject matter.

The theory hours take the form of lectures in which the lecturer sets
out new concepts or techniques and examples illustrating them.
Sessions will consist of a presentation of the main topics of each content's item,
mainly based in selected original research papers.
A high level of students' participation is expected at each session.
Current lines of research in each topic will be discussed at the end of each topics' presentation.

The practical classes are used to explain implementations and show the performance
of selected data structures. Students are required to take an active part in the class by
discussing the various possible solutions/alternatives in class.

Método de evaluación

Grade = Minimum(H + FW + P, 10)

H = 3 tasks (graded from 0 to 2 points each), one for each lecturer, to choose from a list of proposals given by each lecturer.

FW = Final Work (graded from 0 to 4) to choose between (i) two more different tasks from the list of proposals of H
or (ii) a project. The project consists of choosing a published research paper
(previously authorised by the coordinator) and prepare either an oral presentation or a written document containing concrete explanations of the paper's motivation, topic's background, overview of the key ideas,
brief description of the most important details and experimental results obtained through a program that implements the ideas introduced therein.

P = Participation (graded from -1 to 1 points) that valorates, among other things, the student comitment to the course in terms of its attendance to lectures, participation, attendance at classmates' presentations, etc.

Bibliografía

Básica:

Capacidades previas

Knowledge any programming language (preferably C++).
Basic knowledge of algorithm analysis methods (in particular asymptotic complexity).
Basic knowledge of elementary data structures such as stacks, queues, linked lists, trees, and graphs as well as of sorting methods such as insertion sort, heap sort, merge sort, and quick sort.