Disseny d'estructures de dades Codi:  05.613    :  6
Consulta de les dades generals   Descripció   L'assignatura en el conjunt del pla d'estudis   Camps professionals en què es projecta   Coneixements previs   Objectius i competències   Continguts   Consulta dels recursos d'aprenentatge de què disposa l'assignatura   Recursos d'aprenentatge i eines de suport   Informacions sobre l'avaluació a la UOC   Consulta del model d'avaluació  
Aquest és el pla docent de l'assignatura. Us servirà per planificar la matrícula (consulteu si l'assignatura s'ofereix aquest semestre a l'espai del Campus Més UOC / La Universitat / Plans d'estudis). Un cop comenci la docència, heu de consultar-lo a l'aula. (El pla docent pot estar subjecte a canvis.)

En aquesta assignatura s'estudien les diverses estratègies de representació de dades en un ordinador i els criteris per avaluar-les. En funció del tipus de tractament que s'hagi de fer amb aquesta informació (mida, criteris d'accés, etc), es pot seleccionar l'estratègia que ofereixi un balanç òptim entre el consum de memòria i el temps de manipulació.

Aquesta assignatura és fonamental dins l'àmbit de la programació, donat que l'ús apropiat d'estructures de dades és crític en qualsevol aplicació que manegui grans volums d'informació o bé que tingui uns requeriments d'eficiència molt estrictes.

Les assignatures prèvies de l'àmbit de programació ja introduïen algunes estructures de dades bàsiques, com ara llistes, piles, cues o arbres. En aquesta assignatura, es presenta el concepte de tipus abstracte de dades (TAD) com a model general per descriure una estructura de dades i estudiar-ne l'eficiència. Finalment, el nucli central de l'assignatura consisteix en aprendre a utilitzar adequadament cada estructura de dades i saber seleccionar l'estructura de dades més adient a cada situació.

Amunt

L'assignatura Disseny d'Estructures de Dades es pot cursar com a assignatura optativa o bé com a part dels itineraris d'Enginyeria del Software o de Computació.

Els seus continguts estan directament relacionats amb les assignatures obligatòries de programació (Fonaments de programació, Pràctiques de programació i Disseny i Programació Orientada a l'Objecte), on ja s'havien introduït estructures de dades senzilles. Altres estratègies de representació, com ara els mètodes basats en dispersió, s'havien estudiat a l'assignatura obligatòria Disseny de bases de dades. Finalment, l'assignatura Grafs i Complexitat presenta el concepte de graf i introdueix aspectes d'eficiència dels algorismes.

Amunt

El disseny d'estructures de dades és molt important en l'àmbit del desenvolupament de programari, especialment en sistemes on l'eficiència és un factor crític.

Amunt

L'assignatura requereix disposar de les nocions fonamentals d'algorísmica (assignacions, condicionals, bucles) i de programació utilitzant el paradigma imperatiu (ús de compiladors i depuradors, ús d'un entorn de desenvolupament integrat -IDE-, ...). A més, l'assignatura requereix uns bons coneixements de programació orientada a objectes, específicament en llenguatge Java.

Per altra banda, es requereixen nocions bàsiques sobre el càlcul del cost d'un algorisme.

Abans de cursar aquesta assignatura, és molt recomanable haver cursat prèviament les assignatures bàsiques i obligatòries següents:

  • Fonaments de Programació.
  • Pràctiques de Programació.
  • Disseny i Programació Orientada a l'Objecte.
  • Grafs i Complexitat.

Amunt

Els objectius d'aquesta assignatura són els següents:

  • Conèixer en profunditat les estructures de dades més habituals per representar la informació d'una aplicació a memòria.
  • Saber calcular l'eficiència espacial i temporal d'una estructura de dades i comparar diferents alternatives.
  • Ser capaç d'identificar l'estructura de dades utilitzada en un programa i entendre'n el funcionament.
  • Conèixer les llibreries de components més habituals per a representar estructures de dades.
  • Saber implementar un programa que utilitzi estructures de dades utilitzant les possibilitats que ofereix la programació orientada a objectes i les llibreries disponibles.
  • Saber proposar l'estructura de dades més apropiada per una aplicació concreta tenint en compte les seves característiques.

Les competències transversals del Grau que es desenvolupen en aquesta assignatura són:

  • Ús i aplicació de les TIC en l'àmbit acadèmic i professional.
  • Capacitat per a innovar i generar noves idees.

Les competències específiques del Grau que es desenvolupen en aquesta assignatura són:

  • Capacitat per analitzar un problema en el nivell d'abstracció adequat a cada situació i aplicar les habilitats i coneixements adquirits per a resoldre'l.
  • Capacitat per dissenyar i construir aplicacions informàtiques mitjançant tècniques de desenvolupament, integració i reutilització.
  • Capacitat per proposar i avaluar diferents alternatives tecnològiques per resoldre un problema concret.

Amunt

L'assignatura s'estructura en vuit mòduls (el mòdul 8 dels materials no s'estudia):

Mòdul

Continguts

Descripció

1. Tipus Abstractes de Dades
  1. Contenidors
  2. Disseny per contracte
  3. Desenvolupament d'una col·lecció d'exemple
  4. Tipus genèrics o paramètrics
  5. Biblioteca de col·leccions de l'assignatura
  6. Presentació de la resta de mòduls

Estudi del concepte de TAD i d'aspectes relatius a la seva definició i implementació en classes mitjançant una jerarquia.

2. Complexitat algorísmica
  1. Introducció a la complexitat algorísmica
  2. Notació asimptòtica de la complexitat algorísmica
  3. Complexitat algorísmica dels tipus abstractes de dades
Descripció dels mètodes utilitzats per comparar el cost de diferents programes en termes de temps d'execució o consum de memòria.
3. Contenidors seqüencials
  1. Piles
  2. Cues
  3. Representacions encadenades
  4. Llistes
  5. Representacions amb vector: redimensionament
  6. Els contenidors seqüencials a la Java Collections Framework
Estudi de les col·leccions d'objectes amb accés seqüencial (piles, cues, llistes).
4. Arbres
  1. Arbres generals i binaris. Definicions i conceptes relacionats
  2. Recursivitat
  3. Arbres generals
  4. Arbres binaris
  5. Recorreguts
  6. Un exemple de sistema de fitxers
Presentació de les estructures de dades emprades per representar relacions jeràrquiques i introducció del concepte de recursivitat.
5. Cues amb prioritat
  1. El concepte de cua amb prioritat
  2. Funcionament de les cues amb prioritat
  3. Implementacions de les cues amb prioritat
  4. Les cues amb prioritat a les biblioteques JDK
  5. Ordenació per piló: l'algorisme heapsort
  6. Exemple d'ús: algorisme de Huffman

Estudi del disseny i implementació de col·leccions on l'ordre d'accés als elements depèn de la seva prioritat.

6. El TAD Taula
  1. Presentació del TAD Taula
  2. Implementació per dispersió del TAD Taula
  3. El TAD Conjunt
  4. Exemple d'aplicació: una taula de símbols per a un llenguatge modular
  5. Les taules i els conjunts a la Java Collections Framework
Estudi del concepte de dispersió, presentació del TAD taula i les estratègies per la seva implementació.
7. Arbres de cerca
  1. Els arbres de cerca
  2. Implementació de col·leccions ordenades amb arbres binaris de cerca
  3. Arbres multicamí i arbres B
  4. Els arbres de cerca a la Java Collections Framework
Aprofundiment en el concepte d'arbre i les seves aplicacions per representar col·leccions ordenades.
8. Grafs

(Aquest mòdul no s'estudia)

  1. El concepte de graf
  2. El tipus abstracte de dades Graf
  3. Interfícies Java per a grafs dirigits i no dirigits
  4. Implementació de grafs
  5. Exemple d'ús: TAD Acadèmia
Revisió del concepte de graf i descripció d'estratègies per implementar diferents tipus de grafs (dirigits o no dirigits, etiquetats o no etiquetats, ...).

9. Biblioteques de col·leccions

  1. Disseny de TAD nous usant una biblioteca de col·leccions
  2. Disseny de biblioteques de col·leccions
  3. Biblioteques de col·leccions existents
Anàlisi del disseny de nous TADs a partir d'altres existents. Estudi de les consideracions que afecten al disseny de llibreries de col·leccions i presentació d'algunes llibreries existents (Java Collections Framework, Java Data Structure Library, ...).

Amunt

Disseny d'estructures de dades PDF

Amunt

Els mòduls didàctics constitueixen la part més important dels materials de l'assignatura. Aquests materials els podeu descarregar en format PDF des de l'apartat Recursos de l'aula.

Per a realitzar les Pràctiques, l'assignatura es recolza en una llibreria de tipus abstractes de dades que ofereix una jerarquia amb les estructures de dades més usuals. Podeu descarregar aquesta llibreria de TADs des de l'aula virtual, dins de l'apartat de Recursos.

Igualment, disposareu d'exemples de PACs de semestres anteriors (de l'assignatura equivalent del pla d'estudis LRU) en aquest mateix espai de Recursos. Per a resoldre dels vostres dubtes en programació Java o l'ús de la llibreria, disposeu d'un Laboratori de Java de Disseny d'Estructures de Dades.

Amunt

El procés d'avaluació es fonamenta en el treball personal de l'estudiant i pressuposa l'autenticitat de l'autoria i l'originalitat dels exercicis realitzats.

La manca d'autenticitat en l'autoria o d'originalitat de les proves d'avaluació; la còpia o el plagi; l'intent fraudulent d'obtenir un resultat acadèmic millor; la col·laboració, l'encobriment o l'afavoriment de la còpia, o la utilització de material o dispositius no autoritzats durant l'avaluació, entre d'altres, són conductes irregulars que poden tenir conseqüències acadèmiques i disciplinàries greus.

D'una banda, si es detecta alguna d'aquestes conductes irregulars, pot comportar el suspens (D/0) en les activitats avaluables que es defineixin en el pla docent –incloses les proves finals– o en la qualificació final de l'assignatura, sigui perquè s'han utilitzat materials o dispositius no autoritzats durant les proves, com ara xarxes socials o cercadors d'informació a internet, perquè s'han copiat fragments de text d'una font externa (internet, apunts, llibres, articles, treballs o proves d'altres estudiants, etc.) sense la citació corresponent, o perquè s'ha practicat qualsevol altra conducta irregular.

De l'altra, i d'acord amb les normatives acadèmiques, les conductes irregulars en l'avaluació, a més de comportar el suspens de l'assignatura, poden donar lloc a la incoació d'un procediment disciplinari i a l'aplicació, si escau, de la sanció que correspongui.

Amunt

Aquesta assignatura només es pot superar a partir de l'avaluació contínua (AC), nota que es combina amb una nota de pràctiques (Pr) per a obtenir la nota final de l'assignatura. No es preveu fer cap prova d'avaluació final. La fórmula d'acreditació de l'assignatura és la següent: AC + Pr.

 
 

Amunt