Augmentar lletres   Inici   Informació   Contactar   Mapa
Castellano   English

Programació i estructures de dades (PRED)

Crèdits Dept. Tipus Requisits
7.5 (6.0 ECTS) LSI
  • Obligatòria per a l'EI
  • Obligatòria per a l'ETIG
 P1 - Pre-requisit per la EI , ETIG
PRAP - Pre-requisit per la EI , ETIG

Professors

Responsable:  Fernando Orejas Valdés (orejas@lsi.upc.edu)
Altres:Ana Cristina Zoltan Torres (zoltan@lsi.upc.edu)
Ana Edelmira Pasarella Sanchez (edelmira@lsi.upc.edu)
Nicolas Eduardo Mylonakis Pascual (nicos@lsi.upc.edu)

Objectius Generals

D'una banda, es pretén que l'estudiant conegui millor com és un llenguatge
de programació, en particular un llenguatge orientat a objectes. Amb aquest
objectiu s'estudiaran aspectes com són l'estructura de tipus, el control de
dades, la gestió de memòria i els mecanismes d'abstracció d'un llenguatge
d'aquestes característiques.

D'altra banda, es pretén que l'estudiant conegui noves tècniques de programació.
En particular, l'us de la memòria dinàmica i les estructures de dades enllaçades, que estan a la base de moltes aplicacions.

Objectius Específics

Coneixements

  1. Tipus de dades en llenguatges de programació
  2. Control de dades en llenguatges de programació
  3. Abstracció de dades. Especificació i implementació
  4. Implementacions amb punters, nodes encadenats i memòria dinàmica.
  5. Gestió de memòria dinàmica. Garbagge collection
  6. Implementacions de TADs fonamentals: llistes, cues, piles, arbres, taules hash.
  7. Herència

Habilitats

  1. Conèixer millor com és un llenguatge de programació
  2. Prendre contacte amb algunes tècniques avançades de programació.
  3. Adquirir una metodologia per a l'especificació, l'ús, el disseny i
    la implementació de TADs.
  4. Conèixer i saber utilitzar tècniques d'implementació basades amb punters i memòria dinàmica.
  5. Conèixer TADs genèrics, saber utilitzar-los i saber adaptar-los per donar
    solucions a necessitat específiques.

Competències

  1. Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
  2. Capacitat per crear i utilitzar models de la realitat.
  3. Capacitat per dissenyar sistemes, components o processos que s'ajustin a unes necessitats, utilitzant els mètodes, tècniques i eines més adients en cada cas.
  4. (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
  5. Saber aplicar el cicle de resolució de problemes típic de la ciència i l'enginyeria: especificació, generació d'idees i alternatives, disseny d'una estratègia de solució, execució de l'estratègia, validació, interpretació i avaluació dels resultats. Capacitat d'analitzar el procés un cop acabat.
  6. Capacitat d'anàlisi i de síntesi.
  7. Capacitat d'aprendre autònomament.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Abstracció de dades: Especificació i implementació
T      P      L      Alt    L Ext. Est    A Ext. Total 
7,0 3,0 0 0 0 10,0 0 20,0
Concepte de tipus abstracte de dades:
Descripció informal del concepte de tipus abstracte de dades. Motivació i avantatges de la programació usant TADs. La programació per contracte. Descomposició per funcions i descomposició per dades en el disseny descendent.

Especificació de TADs:
Metodologia de construcció d'especificacions. Tipus d'operacions (constructores, consultores, generadores, modificadores...).

TADs i programació basada en objectes:
Els TADs com a concepte bàsic de la programació basada en objectes. Objectes. Classes. Mètodes. Funcionalitat de gestió: construcció, destrucció i assignació. Mecanismes d'ocultació d'informació i funcionalitat.

Genericitat:
TADs parametritzats. Instanciació. Contenidors. Iteradors

Implementació de TADs:
Estructures de dades concretes. Concepte d'implementació d'un TAD. Invariant de representació. Funció d'abstracció.

2. Estructures lineals
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 2,0 2,0 0 12,0 6,0 0 26,0
Piles
Especificació. Aplicacions. Implementació amb taula estàtica. Implementació amb
taula dinàmica. Implementació amb nodes encadenats.

Cues
Especificació. Aplicacions. Implementació amb taula circular. Implementació amb
nodes encadenats.

Llistes
Especificació. Aplicacions. Implementació amb nodes
encadenats. Variacions.
  • Laboratori:
    Plantejament i discussió del treball pràctic a realitzar. Aquest treball es realitzarà sense la presència del professor.
  • Activitats de laboratori addicionals:
    Realització d'una petita pràctica o execici sobre estructures lineals. Bàsicament, la implementació d'una variant de llista.

3. Estructures arborescents
T      P      L      Alt    L Ext. Est    A Ext. Total 
4,0 2,0 2,0 0 8,0 6,0 0 22,0
Arbres generals, binaris i m-aris:
Especificació d'arbres generals. Especificació d'arbres $m$-aris.
Especificació d'arbres binaris. Exemples: arbres d'expressió. Implementació
enllaçada d'arbres binaris. Implementació enllaçada d'arbres $m$-aris.
Isomorfisme entre arbres generals i arbres binaris. Implementació d'arbres
generals utilitzant punters al primer fill i al següent germà.

Esquemes de recorregut d'arbres:
Recorreguts en preordre, postordre, inordre i per nivells.
Aplicació: Avaluació d'expressions, derivació formal d'expressions.
  • Laboratori:
    Plantejament i discussió del treball pràctic a realitzar. Aquest treball es realitzarà sense la presència del professor.
  • Activitats de laboratori addicionals:
    Realització d'una petita pràctica o execici sobre estructures arborescents. Bàsicament, la implementació d'una variant d'arbre.

4. Llenguatges de programació
T      P      L      Alt    L Ext. Est    A Ext. Total 
2,0 0 0 0 0 2,0 0 4,0
Criteris de disseny d'un llenguatge de programació
Implementació d'un llenguatge de programació. Màquines abstractes

5. Tipus de dades
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 2,0 0 0 0 0 0 8,0
Concepte de tipus
Tipus de dades i característiques d'un llenguatge de programació
Polimorfisme i sobrecarrega.
Definició d'un sistema de tipus mitjançant regles d'inferència
Comprovació de tipus

6. Memòria dinàmica
T      P      L      Alt    L Ext. Est    A Ext. Total 
5,0 2,0 0 0 7,0 0 0 14,0
Punters. new i delete.
Destructor, constructor de còpia i operador d'assignació.
Assignació dinàmica de memòria.
Algorismes de "garbage collection"

7. Control de Dades
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Noms i entitats
Visibilitat i vida d'una entitat
Ambits estàtics i dinàmics. Acces a entitats: cadena
estàtica i dinàmica
Pas de paràmetres.

8. Hashing
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 2,0 2,0 0 6,0 8,0 0 24,0
Especificació de taules i diccionaris
Implementació amb taules hash: hash obert, tancat i altres variacions.
Funcions de hash
  • Laboratori:
    Plantejament i discussió del treball pràctic a realitzar. Aquest treball es realitzarà sense la presència del professor.
  • Activitats de laboratori addicionals:
    Realització d'una petita pràctica o execici sobre taules hash. Bàsicament, la implementació d'una variant de taula.

9. Herència
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 1,0 0 0 0 4,0 0 8,0
Herència i subtipus
Herència com a eina de disseny
Herència i modificabilitat dels programes


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
40,0 16,0 6,0 0 33,0 41,0 0 136,0
Hores addicionals dedicades a l'avaluació 6,0
Total hores de treball per l'estudiant 142,0

Metodologia docent

Es pretén exposar el temari de forma molt pràtica, a través de la presentació de molts exemples.

Les classes es divideixen en tres tipus: sessions de teoria, sessions de
problemes i sessions de laboratori. En particular, al llarg del curs es faran
4 hores setmanals de teoria i problemes. Pel que fa al laboratori, només es
faran 2 o 3 sessions al llarg del curs. La resta del temps de laboratori
es dedica al treball individual dels estudiants.

Mètode d'avaluació

Es realitzaran dos examens: un dels aspectes més teòrics de l'assignatura, amb qüestions curtes (nota NT) i un altre de problemes de disseny d'estructures de dades (nota NP).

La nota de laboratori (nota NL) ve donada per dos exercicis de programació individuals que compten igual. El primer exercici, sobre estructures lineals, es presentarà cap a la sisena setmana de classes. El segon exercici,
sobre taules hash, es presentarà la darrera setmana de classes.

La nota final (nota N) és N = 0.4 NT + 0.4 NP + 0.2 NL



Bibliografía bàsica

  • B. Meyer Object oriented software construction (2nd edition), Prentice Hall, 2000.
  • J. Mitchell Concepts in programming languages, Cambridge University Press, 2001.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • M. Weiss Estructuras de datos en Java, Prentice Hall, 2000.
  • R. Peña Diseño de programas, formalismo y abstracción, Prentice Hall, 2004.

Bibliografía complementària

  • N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

Enllaços web

(Informació no introduïda)

Capacitats prèvies

PREREQUISITS: Pràctiques de Programació



 
logo FIB © Facultat d'Informàtica de Barcelona - webmaster@fib.upc.edu - RSS RSS