Programació i estructures de dades ( PRED )
| Crèdits: |
Departament: |
Tipus: |
Requisits: |
| 7.5 |
LSI |
Obligatòria per l'EI
Obligatòria per l'ETIG
Optativa per l'ETIS
|
|
P1
- Pre-requisit per l' EI , ETIG
|
|
|
PRAP
- Pre-requisit per l' EI , ETIG
|
|
|
Professors
| Responsable: | Fernando Orejas Valdés (orejas lsi.upc.edu). |
| Altres: | Cristina Zoltan Torres (zoltanlsi.upc.edu)
Edelmira Pasarella Sanchez (edelmiralsi.upc.edu)
Jordi Delgado Pin (jdelgadolsi.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
- Tipus de dades en llenguatges de programació
- Control de dades en llenguatges de programació
- Abstracció de dades. Especificació i implementació
- Implementacions amb punters, nodes encadenats i memòria dinàmica.
- Gestió de memòria dinàmica. Garbagge collection
- Implementacions de TADs fonamentals: llistes, cues, piles, arbres, taules hash.
- Herència
Habilitats
- Conèixer millor com és un llenguatge de programació
- Prendre contacte amb algunes tècniques avançades de programació.
- Adquirir una metodologia per a l'especificació, l'ús, el disseny i
la implementació de TADs.
- Conèixer i saber utilitzar tècniques d'implementació basades amb punters i memòria dinàmica.
- Conèixer TADs genèrics, saber utilitzar-los i saber adaptar-los per donar
solucions a necessitat específiques.
Competències
- Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
- Capacitat per crear i utilitzar models de la realitat.
- 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.
- (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
- 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.
- Capacitat d'anàlisi i de síntesi.
- 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 "garbagge 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 de teoria tipus test, amb questions curtes (nota NT) i un altre de problemes (nota NP).
La nota de laboratori (nota NL) ve donada per tres exercicis de programació individuals que compten igual. El primer exercici, sobre estructures lineals, es presentarà la sisena setmana de classes. El segon exercici, sobre estructures
arborescents, es presentarà la desena setmana de classes. El tercer exercici,
sobre taules hash, es presentarà la darrera setmana de classes.
La nota final (nota N) és N = 0.4NT+0.4 NP+0.2NL
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ó
|
fib.upc.edu