EPSEVG

Guia Docent EPSEVG
Curs 2006/07
EDAL: ESTRUCTURES DE DADES I ALGORISMES

 DADES GENERALS
 PlaETIG Codi11701 TipusOBT Crèdits9 Intensitat presencial
 Curs3 SiglaEDAL Periocitat1,2 Depart723
 Idioma Clases     Català:        Espanyol:        Anglès:   Responsable   BERNARDINO CASAS FERNANDEZ

 Descripció [Català]
 Proporcionar a l'alumne la capacitat d'especificar, dissenyar, implementar i avaluar estructures de dades i l'habilitat d'identificar els algorismes més adients sobre aquestes estructures. Igualment, es pretén proporcionar a l'alumne més experiència en el camp de la programació mitjançant la realització de pràctiques.
  1. Especificar: L'estudiant haurà d'aprendre algunes eines d'especificació formal que li permetran descriure amb total rigor i precisió el comportament de TAD's. També haurà d'assimilar els principis generals que hauran d'aplicar-se per a especificar un TAD ja sigui formal o informalment.
  2. Dissenyar: L'estudiant haurà d'aprendre a seleccionar i combinar les tècniques algorísmiques i les estructures de dades apropiades per a elaborar dissenys modulars corresponents a problemes de mitjana dificultat.
  3. Implementar: L'estudiant aprendrà les principals tècniques d'organització de les dades que permetin accedir i modificar la informació de manera eficient respectant la corresponent especificació.
  4. Avaluar: L'estudiant serà capaç de comparar l'eficiència relativa de solucions alternatives a un mateix problema i prendre decisions de disseny en funció de criteris objectius basats en l'eficiència en temps d'execució i espai de memòria utilitzada.
El llenguatge de programació utilitzat durant aquest curs tant durant les classes teòriques com a les classes pràctiques és C++.

 Descripció [Castellà]
Proporcionar al alumno la capacidad de especificar, diseñar, implementar y evaluar estructuras de datos y la habilidad de identificar los algoritmos más adecuados sobre estas estructuras. Igualmente, se pretende proporcionar al alumno más experiencia en el campo de la programación mediante la realitzación de prácticas.
  1. Especificar: El estudiante tendrá que aprender algunes herramientas de especificación formal que le permitan describir con total rigor y precisión el comportamiento de TAD's. También tendrá que asimilar los principios generales que se tendrán que aplicar para especificar un TAD ya sea formal o informalmente.
  2. Diseñar: El estudiante tendrá que aprender a seleccionar y combinar las técnicas algorítmicas y las estructuras de datos apropiadas para elaborar diseños modulares correspondientes a problemas de dificultad media.
  3. Implementar: El estudiante aprenderá las principales técnicas de organitzación de los datos que permiten acceder y modificar la información de manera eficiente respetando la especificación correspondiente.
  4. Evaluar: El estudiante será capaz de comparar la eficiència relativa de soluciones alternativas a un mismo problema y tomar decisiones de diseño en función de criterios objectivos basados en la eficiencia en tiempo de ejecución y espacio de memoria utilizado.

 Descripció [Anglès]
 MÒDULS
OrdreDescripcióTipusHores
1Conceptes bàsicsTemes 16
Hores exposicions teòriques: 6       Hores treball pràctic:  2      
Hores treball grup: 0       Hores treball individual: 8
Objectius
  • Repasar el concepte de TAD
  • Presentar el concepte de Classes i Objectes (programació orientada a objectes).
  • Proporcionar eines per mesurar el cost en temps i espai dels algorismes.
Continguts
  1. Concepte de “Tipus Abstracte de Dades”
  2. Especificació del TAD
  3. Mecanismes per crear especificacions
  4. Criteris en la implementació de TAD's. Programació orientada a objectes.
  5. Lligam entre implementació i especificació d'un TAD
  6. Relació entre els TADs i la programació orientada a objectes
  7. Notacions asimptòtiques
  8. Anàlisi asimptòtica de l'eficiència temporal d'un algorisme
  9. Anàlisi asimptòtica de l'eficiència espacial d'un algorisme
Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

2Estructures LinealsTemes 30
Hores exposicions teòriques: 10       Hores treball pràctic:  5      
Hores treball grup: 0       Hores treball individual: 15
Objectius
  • Repàs del concepte de seqüència
  • Mostrar diverses estructures lineals: Piles, cues, llistes, multillistes
  • Veure implementacions de les estructures lineals en vector i enllaçada
  • Aprendre a utilitzar la memòria dinàmica
  • Conèixer l'ordenació per fusió
Continguts
  1. Concepte de seqüència
  2. Concepte de pila i de cua
  3. Implementació de piles i cues
  4. Llistes amb punt d'interès
  5. Implementació d'estructures de dades lineals amb punters
  6. Criteris per implementar TCD
  7. Ordenació per fusió
  8. Multillistes
Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

3ArbresTemes 28
Hores exposicions teòriques: 9       Hores treball pràctic:  5      
Hores treball grup: 0       Hores treball individual: 14
Objectius
  • Repàs del concepte d'arbre: arbres binaris, arbres generals
  • Algorismes per fer recorreguts en preodre, postordre, inordre i per nivells
  • Veure diferents aplicacions que tenen els arbres
  • Implementació d'arbres: en vector, en vector de punters als fills, punters a primer fill/següent germà
Continguts
  1. Concepte d'arbre general
  2. Especificació d'arbres generals
  3. Especificació d'arbres binaris (m-aris)
  4. Usos dels arbresArbres generals
    Especificació d'arbres generals
    Especificació d'arbres binaris (m-aris)
    Usos dels arbres
    Recorreguts d'un arbre

    Implementació d'arbres binaris

    Implementació d'arbres generals

  5. Recorreguts d'un arbre
  6. Implementació d'arbres binaris
  7. Implementació d'arbres generals

 

 

 

Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

4DiccionarisTemes 30
Hores exposicions teòriques: 10       Hores treball pràctic:  5      
Hores treball grup: 0       Hores treball individual: 15
Objectius
  • Especificació del TAD "Diccionari"
  • Aplicacions dels diccionaris
  • Tècniques d'implementació senzilles:
    • Llistes
    • Llistes ordenades
    • Llistes autorganitzades
  • Tècniques d'implementació avançades:
    • Arbres binaris de cerca (BST)
    • Arbres binaris de cerca balancejats (AVL)
    • Taules de dispersió (Hash tables)
    • Arbres digitals (Tries)
    • Llistes de dreceres (Skip lists)
  • Algorismes d'ordenació QuickSort i RadixSort
Continguts
  1. Conceptes i especificació
  2. Usos dels diccionaris
  3. Implementació
  4. Arbres Binaris de Cerca (Binary Search Trees)
  5. Arbres Binaris de Cerca Equilibrats (AVL’s)
  6. Algorisme d'ordenació Quicksort
  7. Taules de dispersió (hash tables)
  8. Tries
  9. Algorisme d'ordenació Radix Sort
  10. Llistes de dreceres (Skip Lists)


Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

5Cues de prioritatTemes 10
Hores exposicions teòriques: 3       Hores treball pràctic:  2      
Hores treball grup: 0       Hores treball individual: 5
Objectius
  • Què és una "Cua de prioritat"?
  • Conèixer les aplicacions de les cues de prioritat
  • Veure la implementació mitjançant turons (Heaps)
  • Algorisme d'ordenació HeapSort
Continguts
  1. Especificació de TAD "Cua de prioritat"
  2. Aplicacions de les cues de prioritat
  3. Implementació mitjançant turons (Heaps)
  4. Algorisme d'ordenació HeapSort
Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

6ParticionsTemes 8
Hores exposicions teòriques: 2       Hores treball pràctic:  2      
Hores treball grup: 0       Hores treball individual: 4
Objectius
  • Què és una partició?
  • Conèixer aplicacions de les particions
  • Veure la implementació amb Merge-Find-Sets (MFSets)
Continguts
  1. Especificació
  2. Implementació amb MFSets
    1. Quick-find
    2. Quick-union
    3. Tècniques per millorar la Quick-union
Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

7GrafsTemes 18
Hores exposicions teòriques: 7       Hores treball pràctic:  2      
Hores treball grup: 0       Hores treball individual: 9
Objectius
  • Repàs del concepte de graf i definicions
  • Veure la implementació amb matrius i llistes d'adjacència
  • Recorreguts en profunditat prioritària, en amplada i ordenació topològica
  • Algorisme de Kruskal per calcular l'arbre d'expansió mínima
  • Algorismes de Dijkstra i Floyd per calcular camins mínims
Continguts
  1. Especificació i definicions
  2. Implementació de grafs
    1. Matrius d'adjacència
    2. Llistes d'adjacència
    3. Multillistes d'adjacència
  3. Algorismes sobre grafs
    1. Recorregut en profunditat prioritària
    2. Recorregut en amplada
    3. Recorregut en ordenació topològica
    4. Arbres d'expansió mínima: Algorisme de Kruskal
    5. Camins mínims: Algorismes de Dijkstra i Floyd

 

Activitats, coneixements, habilitats, aptituds

Planificació

Comentaris / Bibliografia

8Laboratori: SessionsPràctiques 41
Hores exposicions teòriques: 1       Hores treball pràctic:  8      
Hores treball grup: 32       Hores treball individual: 0
Objectius
Els exercicis pràctics d'aquest mòdul permeten familiaritzar-se amb l'entorn de treball i el llenguatge de programació C++, i d'aquesta manera assolir els coneixements necessaris per més endavant realitzar la pràctica.

Aquestes sessions es realitzen en equips de dos estudiants i el llenguatge de programació és C++.
Continguts
  1. Introducció al Llenguatge C++
  2. Classes i Objectes
  3. Punters, Referència i pas de paràmetres
  4. Memòria Dinàmica
  5. Excepcions i generecitat
  6. Introducció a la llibreria stàndard STL
  7. Herència i Polimorfisme
Activitats, coneixements, habilitats, aptituds
  • En aquestes classes el professor exposa una sèrie de conceptes i tècniques directament vinculats amb la realització de la pràctica i amb el que són les últimes etapes del desenvolupament del software:
    • implementació,
    • codificació,
    • testing,
    • etc.
  • L'estudiant realitza els exercicis de programació que se li proposen, consistents fonamentalment en:
    • implementació d'una classe
    • ús de les taules
    • ús de la memòria dinàmica
    • les classes genèriques i els errors
    • ús de la llibreria estàndard STL
Planificació
Aquestes sessions es realitzen a les primeres setmanes de curs, i cada sessió té dues hores de duració.

El seguiment per part de l'alumne d'aquest mòdul es considera imprescinble per tal de poder continuar amb el següent mòdul, és a dir, la pràctica.


Comentaris / Bibliografia

9Laboratori: PràcticaPràctiques 36
Hores exposicions teòriques: 0       Hores treball pràctic:  6      
Hores treball grup: 30       Hores treball individual: 0
Objectius
La pràctica consisteix en la implementació d'un disseny modular. La tasca de l'estudiant és implementar diferents mòduls del disseny modular donat a l'enunciat.

La pràctica es realitza en equips de dos estudiants i el llenguatge de programació és C++.
Continguts
Aquest tipus de sessions serveixen per controlar el seguiment de la pràctica i tenen lloc a les aules de informàtica. Durant aquestes sessions, els estudiants tenen l'oportunitat de consultar els seus dubtes sobre la pràctica, i discutir sobre els progressos del seu treball.
Activitats, coneixements, habilitats, aptituds
 
Planificació
Cada sessió té dues hores de duració.

Comentaris / Bibliografia


Hores Exposicions Teòriques: [48]
Hores Treball Pràctic: [42]
Hores de Treball en Grup: [62]
Hores treball individual: [70]
Hores totals: [222]
Crèdits ECTS: [8,9]
 
 Dependència entre Mòduls

OrdreDescripcióTipus
1Conceptes bàsicsTemes
2Estructures LinealsTemes
Arbres
3ArbresTemes
Diccionaris
4DiccionarisTemes
Grafs
5Cues de prioritatTemes
6ParticionsTemes
7GrafsTemes
8Laboratori: SessionsPràctiques
Laboratori: Pràctica
9Laboratori: PràcticaPràctiques
 
 Mètode d'avaluació

Hores Avaluació: 5

Per determinar la nota es consideren dos paràmetres:

  1. NControl : Nota Controls = max ((C1+C2)/2, C2), on:
    • C1 : Primer Control. Constarà de Teoria i Problemes (2 hores)
    • C2 : Segon Control. Constarà de Teoria i Problemes (3 hores)
  2. NPràctica: Nota Pràctica = Nota corresponent a la pràctica


Nota Final = NControl * 2/3 + NPràctica * 1/3

 
 CRÈDITS ECTS: Detall dels crèdits totals, separats per tipus

Treball en curs Treball encarregat durant el curs, realitzat de forma individual, en un termini prefixat
Treball en grup Treball encarregat durant el curs, realitzat en grup, en un termini prefixat
Projecte individual Treball realitzat de forma individual, integrant diversos coneixements de la matèria, i diferent per a cada estudiant
Pràctiques (PC) Treball d'aplicació dels coneixements de la matèria en el cas pràctic real, realitzat de forma individual o en grup
Treball escrit (WW) Treball realitzat de forma individual i per escrit, en un termini prefixat
Exàmen escrit (WE) Prova individual realitzada per escrit en un temps fixat i en un lloc predeterminat i controlat
Ex. Teòric/pràctic (TP) Prova individual relacionada amb aspectes teòrics i pràctics de la matèria, realitzada en un temps fixat i en un lloc predeterminat i controlat
 
 Bibliografia Bàsica

Autor Títol EditorialAny
Jordi Esteve Apunts d'EDAL. Transparències pels alumnes. Copisteria Vilanova 2005
Enrique Hernández Orallo, José Hernández Orallo, Mª Carmen Juan Lizandra C++ estándar : [programación con el estándar ISO y la biblioteca de plantilla (STL)] Madrid : Paraninfo 2002
Narciso Marí, Yolanda Ortega, José Alberto Verdejo Estructuras de datos y métodos algorítmicos. Ejercicios resueltos. Person Prentice Hall 2003
 
 Materials Complementaris

Autor Títol EditorialAny
Jordi Esteve Col·lecció de problemes Copisteria Vilanova 2004
Stroustrup, Bjarne El lenguaje de programación C++ Addison Wesley 2002
Zenón José Hernández Figueroa, Juan Carlos Rodríguez del Pino, José Daniel González Domínguez, Margarita Díaz Roca, José Rafael Pérez Aguilar, Gustavo Rodríguez Rodríguez Fundamentos de Estructuras de Datos Thomson 2005
Luis Joyanes Aguilar Programación en C++ : algoritmos, estructuras de datos y objetos Madrid : McGraw-Hill 2000
Bernardino Casas, Conrado Martínez, Jorge Orozco, Sergio Pérez Sessions de laboratori. Estructures de Dades i Algorismes Copisteria Vilanova 2005