Curs 2010-11

Estructura de Dades i Algorismes (21417)

Titulació/estudi: Grau en Enginyeria en Informàtica (3377)
Curs: segon
Trimestre: primer
Nombre de crèdits ECTS: 4 crèdits
Hores de dedicació de l'estudiant: 100 hores
Llengua o llengües de la docència: català
Professor: Narcís Parés

 

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

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 de s 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.
 

2. Prerequisits per al seguiment de l'itinerari formatiu

Aquesta assignatura requereix dels coneixements i habilitats assolits a l'assignatura de Fonaments de la Programació (de primer curs, durant el 2n i 3r 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.

3. Competències que s'han d'assolir

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 generals

Competè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ó.

4. 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.

5. Avaluació

5.1 Criteris generals d'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 aportaran una nota de 0, 0,5 o 1,0 la qual farà mitja entre tots els seminaris per acabar-se sumant a la nota d'examen final. 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).

- 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 + NS) * 0,4 + NP * 0,6

On la mitja es calcula tan sols si: NE >= 5,0 i NP >= 5,0

5.2 Concreció per competències

Competències a assolir en l'assignatura	Indicador d'assoliment	Procediment d'avaluació	Temporalització
- 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(). - 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ó.	Respondre amb encert les preguntes tipus test de l'examen final. Respondre amb encert les qüestions curtes de l'examen final. Respondre amb encert el problema llarg de l'examen final. Realitzar amb encert els problemes i exercicis proposats als seminaris. Respondre amb encert les preguntes tipus test de l'examen final. Respondre amb encert les qüestions curtes de l'examen final. Respondre amb encert el problema llarg de l'examen final. Realitzar amb encert els problemes i exercicis proposats als seminaris. Realitzar correctament les pràctiques.	Examen final amb part tipus test per a coneixements generals, amb qüestions curtes per a aprofundiment particular i amb problema llarg per a visió analítica i capacitat de disseny.   Exercicis de classe en sessions de seminari.   Examen final amb part tipus test per a coneixements generals, amb qüestions curtes per a aprofundiment particular i amb problema llarg per a visió analítica i capacitat de disseny.   Exercicis de classe en sessions de seminari.   Correcció de les pràctiques.	Al final del trimestre.   Exercicis a resoldre a sessions de seminari, aproximadament en sessions setmanals.   Al final del trimestre.   Exercicis a resoldre a sessions de seminari, aproximadament en sessions setmanals.     Pràctiques a realitzar en sessions de laboratori. Aproximadament una cada dues setmanes.

6. Continguts

6.1 Blocs de contingut

• Bloc de contingut 1: Introducció als Tipus Abstractes de Dades
• Bloc de contingut 2. Estructures Lineals
• Bloc de contingut 3. Estructures en Arbre
• Bloc de contingut 4. Estructures Associatives
• Bloc de contingut 5. Cues amb Prioritat i Heaps
• Bloc de contingut 6. Anàlisi de Problemes

6.2 Organització i concreció dels 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

7. Metodologia 

Des del punt de vista de continguts teòrics, cada bloc definit correspon a un tema nou i creixent en complexitat fins que en el darrer s'encara la resolució de problemes utilitzant tot el material vist anteriorment.

Cada bloc pot contenir diverses classes magistrals d'introducció de conceptes reforçades per classes de seminaris o s'hi realitzen exercicis per tal de consolidar els conceptes en els alumnes. Les classes teòriques, amb tots els alumnes, requereixen que els alumnes prenguin apunts i els repassin fora d'hores de classe després de cada classe magistral. Els seminaris, amb grups reduïts d'alumnes, suposen un treball individual de l'alumne durant l'hora de classe on pot ser assessorat de forma acurada pel professor i així aclarir dubtes en el moment que apareixen i permetre que l'alumne s'enfronti ell mateix als problemes però sense el risc de quedar bloquejat. 

El darrer bloc està pensat per a entrenar als alumnes en les capacitats analítiques i de disseny estructural de problemes més propers a casos reals.

Al final dels blocs 2, 3, 4 i 5 es realitza una sessió de pràctiques on es planteja la realització d'un treball pràctic en equips de 3. Aquestes sessions serveixen per entendre l'enunciat i aclarir els dubtes que puguin aparèixer. També serveixen per iniciar la realització d'aquests treballs pràctics tot i que aquests hauran de ser plenament desenvolupats i finalitzats com a treball dels equips fora d'hores de classe. Aquests treballs s'hauran de programar en llenguatge C com a continuació de l'assignatura Fonaments de la Programació de primer curs.

Les tres primeres pràctiques són més enfocades a desenvolupar les habilitats de programació dels alumnes, tot i que també promouen en part l'anàlisi i l'abstracció. La darrera pràctica, que serà més llarga que les altres promourà un treball més profund i seriós intentant resoldre un problema més proper a un cas real.

D'aquesta forma, tant la teoria com el treball pràctic progressen en paral·lel i de forma coordinada. 

 

8. Bibliografia i recursos didàctics

Recursos d'informació procedents de diverses fonts: Biblioteca o d'altres; així com d'altres recursos docents necessaris per al procés d'aprenentatge.
Es tracta de classificar-los  d'acord amb criteris diversos: la tipologia del recurs i el grau d'incidència amb l'aprenentatge proposat en l'assignatura.

8.1 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.

8.2 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.

8.3. 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.

8.4. Recursos didàctics. Material docent de l'assignatura

• Transparències de l'Assignatura en format Power Point

• Llista de Problemes de l'Assignatura

8.5. 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.