Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Programació i estructures de dades (PRED)

Crèdits Dept. Tipus Requisits
7.5 (6.0 ECTS) CS
  • 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:  (-)
Altres:(-)

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, s'estudia 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. Garbage 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. 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 autònom dels estudiants.

Mètode d'avaluació

A mig quadrimestre es farà un examen parcial (nota NP), de caire pràctic, sobre els temes d'estructures lineals i gestió de memòria.

L'examen final (nota NF) cobreix tota l'assignatura. Aquest examen té un caràcter més conceptual, però torna a incloure els temes ja avaluats en el parcial.

La nota de laboratori (nota NL) ve donada per dos exercicis de programació que compten igual. Els exercicis es resolen en grups de dos estudiants. El primer exercici, sobre estructures lineals, es proposarà cap a la tercera o quarta setmana de classes. El segon exercici, sobre taules hash, es proposarà unes tres setmanes abans de l'acabament de classes. En tots dos casos hi ha unes quatre setmanes per resoldre'ls.

La nota total de l'assignatura es calcula amb la fòrmula:

NT = max(0,2*NP + 0,6*NF, 0,8*NF) + 0,2*NL

Bibliografía bàsica

  • Bertrand Meyer Object-oriented software construction, Prentice Hall, 1997.
  • John C. Mitchell. Concepts in programming languages, Cambridge University Press, 2003.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • Mark Allen Weiss Estructuras de datos en Java : compatible con Java 2, Addison Wesley, 2000.
  • Ricardo Peña Marí Diseño de programas : formalismo y abstracción, Prentice Hall, 2005.

Bibliografía complementària

  • Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

Enllaços web

(Informació no introduïda)

Capacitats prèvies

PREREQUISITS: Pràctiques de Programació


Compartir
Share

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil