Estructures de Dades Avançades

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació Avançada)
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Mail
duch@cs.upc.edu
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.

Professorat

Responsable

Altres

Hores setmanals

Teoria
4
Problemes
0
Laboratori
0
Aprenentatge dirigit
0.16
Aprenentatge autònom
7.84

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.

    • Competències Transversals

    Ús solvent dels recursos d'informació

  • CTR4 - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i d'informació de l'àmbit de l'enginyeria informàtica, i valorar de forma crítica els resultats d'aquesta gestió.

    • Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

    • Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.
  • CB8 - Que els estudiants sàpiguen comunicar les seves conclusions i els coneixements i raons darreres que les sustenten- a públics especialitzats i no especialitzats d'una manera clara i sense ambigüitats.
  • CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.

    • Objectius

    1. Become acquainted with the main and classic data structures of central areas of computer science and identify their major properties.
      Competències relacionades: CB8, CB9, CTR4,
    2. Become familiar with the mathematical tools usually used to analyze the performance of data structures.
      Competències relacionades: 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.
      Competències relacionades: CG1, CG3, CEE3.1, CEE3.2, CB6, CB8, CB9, CTR4, CTR6,
    4. Select, design and implement appropriate data structures to solve given problems.
      Competències relacionades: CG1, CG3, CEE3.1, CEE3.2, CB6, CB9, CTR4, CTR6,

    Continguts

    1. Preliminars.
      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.

    Activitats

    Activitat Acte avaluatiu



    Programming Projects

    Programming Projects
    Objectius: 1 4 3 2
    Setmana: 14 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h


    Validation Exam.

    The validation exam, graded out of 10 points, aims to evaluate the student's knowledge consolidation and mastering of the programming projects.
    Objectius: 1 4 3 2
    Setmana: 14 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    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ètode d'avaluació

    The final grade F is calculated using the following formula:

    F = 0.5 (VE) + 0.5 ((P1 + P2 + P3 + P4) / 4);

    with:

    VE = exam (0--10 points), P_i = programming project (0--10 points), i = 1,2,3,4

    Bibliografia

    Bàsic

    Capacitats prèvies

    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.