Curs 2015-16

Estructures de Dades i Algorismes

Titulació: Codi: Tipus:
Grau en Enginyeria Informàtica 21417 Obligatòria 2n curs
Grau en Enginyeria Telemàtica 21769 Optativa
Grau en Enginyeria en Sistemes Audiovisuals 21655 Optativa

 

Crèdits ECTS: 4 Dedicació: 100 hores Trimestre: 1r

 

Departament: Dept. de Tecnologies de la Informació i les Comunicacions
Coordinador: Ricardo Baeza Yates
Professorat:

Ricardo Baeza Yates, Diego Sáez Trumper, Ana Freire

Idioma:

Castellà

Horari:
Campus: Campus de la Comunicació - Poblenou

 

Presentació de l'assignatura

Estructures de Dades i Algorismes forma part del grup d’assignatures de l’àrea de Llenguatges de Programació, juntament amb les assignatures: Fonaments de la Programació (de primer curs, durant els 2on i 3er trimestres) i Programació Orientada a Objectes (de segon curs, durant el 1er trimestre i en paral·lel amb la nostra). Mentre aquestes dues darreres assignatures del grup són comunes als tres graus (Enginyeria en Informàtica, Enginyeria en Telemàtica i Enginyeria en Sistemes Audiovisuals), la nostra assignatura és una especialització per tan sols l’Enginyeria en Informàtica. D’aquesta manera, l’assignatura parteix de la voluntat de començar a plantejar als alumnes una mentalitat d’analistes de problemes i no només de programadors. No obstant, les capacitats i habilitats de programació de les estructures de dades i els tipus abstractes de dades són importants en aquesta assignatura.

L’assignatura pressuposa haver adquirit uns coneixements i habilitats bàsics de programació en l’assignatura de Fonaments de la Programació de primer curs. Els dos trimestres d’aquesta assignatura hauran donat un domini en les tècniques i tipus elementals de programació i estructures de control de flux. A Estructures de Dades i Algorismes s’aprofundirà tot concentrant-nos en les formes d’estructurar la informació utilitzada en un programa, en com poder gestionar aquesta informació i en com aconseguir-ho de forma que no pugui tenir efectes col·laterals en la resta del programa. A més veurem la forma d’avaluar-ne la seva implementació òptima tant en ocupació d’espai de memòria com en temps d’execució de les operacions i algorismes amb els quals gestionarem les dades.

Les estructures elementals que es veuran seran les Estructures Lineals, les Estructures en Arbre i les Estructures Associatives. La programació d’aquestes estructures i els seus algorismes es realitzarà en llenguatge C, ja après durant Fonaments de la Programació. A més l’assignatura promourà de forma especial la capacitat d’analitzar un problema des del punt de vista de la informació utilitzada i gestionada en aquest, i de com es pot dissenyar i programar la millor solució pel que fa a les estructures de dades i les seves operacions de gestió. En aquest sentit l’aprenentatge de l’alumne estarà molt encaminat a resoldre problemes que presentin escenaris el més propers possibles a casos reals.

Objectius d'aprenentatge

L’assignatura vol, en darrer terme, que l’alumne adquireixi una primera visió de les tasques associades amb l’analista informàtic. És a dir, vol aconseguir que un alumne pugui partir de la descripció verbal/textual d’un problema a ser resolt informàticament i pugui dissenyar i desenvolupar els Tipus Abstractes de Dades (TADs) que el resolen, a partir dels següents passos essencials:

* Comprendre i especificar formalment les necessitats funcionals del problema, és a dir, especificar la signatura dels TADs (tipus abstractes de dades) necessaris.

* Seleccionar i dissenyar les estructures de dades que seran utilitzades en els TADs, optimitzant-ne l’ocupació en memòria i la complexitat temporal d’execució.

* Realitzar un esquema complert de les estructures de dades seleccionades.

* Implementar de forma òptima els TADs dissenyats per tal d’incorporar-los a l’aplicació que resol el problema inicial.

L’alumne ha de ser capaç, a més, de poder entendre per si sol noves estructures de dades més complexes que vagi trobant en el futur i de poder-les incorporar en el seu repertori per a l’anàlisi i resolució de problemes.

Tot això ha d’enllaçar amb la filosofia de disseny de programes descendent de l’assignatura prèviament realitzada Fonaments de la Programació i ha de mostrar els clars vincles amb l’assignatura paral·lela Programació Orientada a Objectes.

 

Prerequisits

Aquesta assignatura requereix dels coneixements i habilitats assolits a l’assignatura de Fonaments de la Programació (de primer curs, durant el 2on i 3er trimestres). Essencialment, l’assignatura pressuposa haver adquirit uns coneixements i habilitats bàsics de programació que hauran donat un domini en les tècniques i tipus elementals de programació i estructures de control de flux.

 

Competències

A continuació es detallen aquelles competències que els alumnes d’Estructures de Dades i Algorismes hauran d’haver adquirit en finalitzar l’assignatura. Aquestes competències estan relacionades amb l’anàlisi, disseny i desenvolupament d’estructures de dades i les operacions per a la seva gestió, en programes de mida mitjana.

Competències transversalsCompetències específiques

Instrumentals

CG1: Capacitat de síntesi
L’alumne ha de ser capaç d’escriure solucions amb els elements essencials, de forma simple, elegant i tan eficient com sigui possible.

CG2: Capacitat d’anàlisi
L’alumne ha de ser capaç d’analitzar un problema concret i proposar solucions adequades per a resoldre’l.

Interpersonals

CG3: Capacitat de comprendre necessitats de tercers en la resolució de problemes
L’alumne a de ser conscient que com a professional haurà d’analitzar i solucionar problemes plantejats per tercers i per tant els haurà de saber escoltar i entendre.

CG4: Dialogar i treballar en equip
La feina d’un informàtic rarament és en solitari donada la complexitat del desenvolupament d’aplicacions de gran format, i per això és important que l’alumne ja es vagi acostumant a treballar en grup.

Sistèmiques

CG5: Capacitat d’aplicar el
coneixement a la pràctica
L’alumne ha de ser capaç d’aplicar els coneixements adquirits en la resolució de problemes concrets, triant la tècnica que s’ajusti millor a cada cas.

CG6: Interès per la qualitat
L’alumne ha de mostrar atenció en la qualitat del seu treball.

 Coneixements (Saber)

CE1: Coneixement del concepte de Tipus
Abstracte de Dades les seves components (Conjunt de Suport i Interfície o Signatura) i aquells conceptes que porta implicats (encapsulament, independència d’implementació, reutilització, robustesa, etc.) i com estan definits formalment (conjunt d’operacions constructores, conjunts pur/impurs, etc.)

CE2: Coneixement de les estructures de dades bàsiques. Concretament:estructures lineals (piles, cues i llistes), estructures en arbre (arbres binaris de cerca, arbres balancejats o AVL, arbres parcialment ordenats), estructures associatives (taules, taules de hash, taules amb AVLs), cues amb prioritat (pilons o heaps).

CE3: Coneixement de com es poden combinar aquestes estructures bàsiques per tal de formar-ne de més complexes.

CE4: Coneixement dels algorismes associats a les estructures. Operacions bàsiques de gestió (creació, inserció, modificació, esborrat, etc.); Algorismes de cerca, funcions de hash, etc.

CE5: Coneixement dels conceptes de funcions de complexitat o cost espacial i d’execució. Essencialment funció del cas pitjor O().

Habilitats (Saber fer)

CE6: Capacitat d’anàlisi i abstracció de les necessitats estructurals i funcionals d’un problema.


CE7: Especificació formal de problemes informàtics, concretament de les seves necessitats estructurals i de les seves necessitats funcionals.

CE8: Adequació de les estructures de
dades bàsiques a certs problemes arquetípics.

CE9: Aplicació de les estratègies elementals d’Implementació dels tipus abstractes de dades, optimitzant-ne l’ocupació en memòria i la complexitat temporal d’execució.

CE10: Capacitat de comprensió de noves estructures de dades i de la seva aplicació.

 

Avaluació

Seguint l’esperit de l’EEES, els alumnes seran avaluats mitjançant una fórmula mixta de forma continuada i de forma global final mitjançant un examen.


Notes de Seminaris (NS): els alumnes aniran sent avaluats a partir d’exercicis realitzats a classe durant les sessions de seminaris. Aquests exercicis de seminaris, que es realitzaran de forma individual en classes reduïdes, permetran als professors fer un seguiment més acurat de l’alumne per tal de conèixer-lo millor i poder avaluar amb més coneixement les diverses fases del curs (seminaris, pràctiques i examen). La nota de seminaris tan sols es tindrà en compte si l’alumne assisteix a tots o com a màxim en falla un.


Notes de Pràctiques (NP): els alumnes realitzaran 2 pràctiques (dobles) al llarg del curs, les quals es començaran durant l’hora de classe i s’acabaran fora de classe. Aquestes es realitzaran en equips de 3 alumnes per tal que aprenguin a treballar en equip. S’avaluaran per a cada lliurament que l’equip realitzi i la nota serà la mateixa pels tres membres de l’equip. L’avaluació es farà sempre que la pràctica compili correctament i s’executi sense errors de sistema. En aquest cas, la pràctica s’avaluarà en base a l’adequació de la solució al problema i als criteris d’eficiència de la solució, claredat i netedat del codi, documentació del codi i funcionament amb els jocs de dades aportats pels professors. Les 2 pràctiques faran mitja per obtenir una nota global de pràctiques.


Nota d’Examen (NE): a final de l’assignatura, els alumnes realitzaran un examen que constarà de tres parts: (a) una part de tipus test que avaluarà conceptes generals, (b) una part amb dues qüestions de resposta curta i/o d’exercici de càlcul de funcionament d’estructures de dades, i finalment (c) un problema llarg que avaluarà la capacitat d’analitzar un problema, dissenyar-ne les estructures de dades adients, especificar-ne formalment la solució i els tipus abstractes de dades amb les operacions de la interfície i l’esquema de les estructures, i analitzant la complexitat en espai i en temps.

Autoavaluació: L’alumne disposarà d’una col·lecció d’exercicis amb solucions per anar-se auto-avaluant al llarg del curs. Aquests exercicis seran voluntaris i no comptaran en la nota final.


Nota Final (NF): la nota final serà calculada de la següent forma:


NF = NE * 0,5 + NP * 0,3 + NS * 0,2

Condicions:

 

Continguts

 Bloc de contingut 1. Introducció als Tipus Abstractes de Dades

Conceptes

Procediments

Actituds

1. Introducció a les Estructures de Dades

2. Breu context històric

3. Necessitat dels Tipus Abstractes de Dades

4. Definició dels Tipus Abstractes de Dades

5. Noció de Cost Espacial i Temporal -> Funció d’Ordre de Cost: O()

6. Beneficis dels Tipus Abstractes de Dades

1. Exemple de problemes de no utilització dels Tipus Abstractes de Dades.

 

1. Abstracció

 

2. Comprensió matemàtica

 

Bloc de contingut 2. Estructures Lineals

Conceptes

Procediments

Actituds

1. Aproximació Estructural a les Estructures Lineals

2. Introducció a l’Especificació formal de Tipus Abstractes de Dades a partir de les Est. Lineals

3. Implementació de les Est. Lineals

4. Comparativa de les Est. Lineals.

1. Analogia de les Estructures Lineals a funcionament d’activitats quotidianes

2. Formalització de les operacions de la interfície dels tipus abstractes de dades: operacions constructores, modificadores i consultores

3.  Implementació estàtica i dinàmica de les Est. Lineals

4. Complexitat en Temps i Espai de les Est. Lineals.

1. Abstracció

 

2. Anàlisi

 

 

Bloc de contingut 3. Estructures en Arbre

Conceptes

Procediments

Actituds

1. Propietats, terminologia i conceptes associats als Arbres.

2. Recorreguts d’Arbres Binaris.

3. Estructures d’Arbres Binaris (AB).

4. Arbres Binaris de Cerca (ABC).

5. ABCs Balancejats: Arbres Adelson-Velskii Landis (AVL)

6. Arbres Parcialment Ordenats (APO)

1. Algorismes de recorreguts d’Arbres Binaris.

2. Especificació Formal d’AB.

3. Implementació Dinàmica d’AB.

4. Implementació Estàtica d’AB.

5. Operacions de balanceig d’AVL.

6. Operacions d’inserció, modificació i esborrat.

7. Complexitat en Espai i Temps dels Arbres.

1. Abstracció

 

2. Anàlisi

 

 

Bloc de contingut 4. Estructures Associatives

Conceptes

Procediments

Actituds

1. Estructures Associatives: Taules

2. Concepte de Clau i relació Clau-Valor, Cerca per Clau, etc.

3. Aproximació de Taules amb Llistes: Eficiència

4. Taules de Hash: Conceptes, Propietats, Eficiència.

6. Fórmules de Hashing.

7. Gestió de Sobreeiximent de Hashing: Encadenament, Adreçament Obert, etc.

8. Taules amb AVL: Conceptes, Eficiència.

1. Especificació Informal: Operacions Generals

 

2. Implementació de Taules de Hash.

 

 

3. Implementació de Taules amb AVL.

1. Abstracció

 

2. Anàlisi

 

 

Bloc de contingut 5. Cues amb Prioritat i Heaps

Conceptes

Procediments

Actituds

1. Diferències funcionals respecte la Cua normal.

2. Especificació Informal

3. Funcionament a partir d’Arbres Parcialment Ordenats i Complerts à Heaps.

 

1. Operacions amb Arbre Parcialment Ordenat: Insercions (Flotació), Consulta, Esborrats (Enfonsat)

2. Implementació Estàtica a partir d'APO amb Pilons (Heaps)

3. Algorisme de cerca i ordenació: Heapsort.

1. Abstracció

 

2. Anàlisi

 

 

Bloc de contingut 6. Anàlisi de Problemes

Conceptes

Procediments

Actituds

1. Comprensió i especificació formal de les necessitats funcionals d’un problema.

2. Selecció i disseny de les estructures de dades que seran utilitzades en els Tipus Abstractes de Dades, optimitzant-ne l’ocupació en memòria i la complexitat temporal d’execució.

3. Repàs i consolidació del tots els TADs vistos.

1. Especificació formal de la signatura dels TADs necessaris.

2. Realitzar un esquema complert de les estructures de dades seleccionades.

3. Implementar de forma òptima els TADs dissenyats per tal d’incorporar-los a l’aplicació que resol el problema inicial.

1. Abstracció

 

2. Anàlisi

 

 


 

Metodologia

Les activitats d’aprenentatge es divideixen de la forma següent:


• Sessions de Teoria: els professors presenten una sèrie de conceptes i tècniques, així com exemples d’ús. Els alumnes hauran de repassar, fora d’hores de classe, els apunts presos a classe per tal de consolidar aquests continguts.


• Sessions de Seminari: els alumnes, en grups reduïts, resoldran exercicis que ajudaran a consolidar els conceptes teòrics així com a fer d’enllaç vers els treballs pràctics. La realització és en solitari i durant la classe. Aquests exercicis seran supervisats de prop pels professors per aclarir qualsevol dubte i ajudar l’alumne en aquesta consolidació.


• Sessions de Pràctiques: els alumnes, en equips de tres, hauran de resoldre aspectes pràctics de resolució de problemes de l’assignatura. Bàsicament exercitaran les tècniques de programació de les estructures de dades i de les operacions de gestió, però també hauran de saber analitzar la forma més òptima de fer-ho. Aquestes pràctiques es començaran en aula d’ordinadors però s’hauran d’acabar de realitzar for d’hores de classe donada la intensitat que requereixen aquesta problemes pràctics.


• Exercicis d’Autoavaluació: aquests exercicis pertanyen a una llista accessible des de l’aula global per tal que els alumnes, fora d’hores de classe, puguin fer un seguiment del seu aprenentatge de cada bloc de l’assignatura.

 

Recursos

Fonts d’informació per a l’aprenentatge. Bibliografia bàsica (suport paper i electrònic)

-        AHO, A.V. i d'altres. Data Structures and Algorithms. Addison-Wesley, 1983.

-        FRANCH GUTIÉRREZ, X. Estructuras de datos. Especificación, diseño e implementación. Edicions UPC, 1994.

Fonts d’informació per a l’aprenentatge. Bibliografia complementària (suport paper i electrònic)

-        WEISS, M. Data Structures and Algorithm Analysis in C. Benjamin Cummings, 1993.

-        PEÑA, R. Diseño de programas. Prentice Hall, 2a Edició, 1999.

Fonts d’informació per a l’aprenentatge. Bibliografia de reforç (suport paper i electrònic)

-        NYHOFF, L. TADs, Estructuras de datos y resolución de problemas con C++ (2ª Edición), Pearson/Prentice Hall, 2005.

 Recursos didàctics. Material docent de l’assignatura

 -       Transparències de l’Assignatura en format Power Point

-        Llista de Problemes de l’Assignatura

 Recursos didàctics. Materials i eines de suport

-        Web de l’assignatura on es recolliran enllaços interessants, informació puntual d’enunciats i lliurament de pràctiques, solucions d’exercicis, etc.