Curs 2014-15
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 |
| Idioma: | Castellà |
| Horari: | |
| Campus: | Campus de la Comunicació - Poblenou |
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.
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.
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 transversals | Competències específiques |
|---|---|
|
Instrumentals CG1: Capacitat de síntesi CG2: Capacitat d’anàlisi Interpersonals CG3: Capacitat de comprendre necessitats de tercers en la resolució de problemes CG4: Dialogar i treballar en equip Sistèmiques CG5: Capacitat d’aplicar el CG6: Interès per la qualitat |
Coneixements (Saber) CE1: Coneixement del concepte de Tipus 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.
CE8: Adequació de les estructures de 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ó. |
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 4 pràctiques 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 4 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:
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
|
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.
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.