Programació de Sistemes ( PS )

Professors

Responsable:	Conrado Martínez Parra (conradolsi.upc.edu).
Altres:	Gabriel Valiente Feruglio (valientelsi.upc.edu).

Objectius Generals

Proveir l'estudiant de la capacitat de dissenyar, implementar i avaluar estructures de dades, així com la capacitat de dissenyar, implementar i avaluar algorismes sobre aquestes estructures.

Objectius Específics

Coneixements

1. Tipus abstractes de dades: especificació, ús, disseny, implementació.
2. Programació orientada a objectes: classes, objectes, mètodes, herència, polimorfisme, vinculació dinàmica.
3. Anàlisi d'algorismes: eficiència, costos, casos, notació asimptòtica, resolució de recurrències simples.
4. Estructures de dades elementals: piles, cues, llistes.
5. Estructures de dades avançades: arbres,diccionaris.
6. Memoria dinàmica: gestió de memoria dinàmica, destructors, construcció per còpia, assignació, garbage collection.
7. Algorismes d'ordenació: quicksort, mergesort, heapsort

Habilitats

1. Adquirir una metodologia per a l'especificació, l'ús, el disseny i la implementació de tipus abstractes de dades.
2. Conèixer i saber usar una varietat de tècniques d'implementació eficient d'estructures de dades.
3. Conèixer tipus abstractes de dades genèrics, saber usar-los i saber adaptar-los per donar solucions a necessitats específiques.
4. Saber raonar sobre la correcció i eficiència tant de les implementacions dels tipus abstractes de dades com dels algorismes que els usen.
5. Disposar de criteris que permetin, durant les etapes d'especificació, disseny i implementació, escollir l'alternativa més adequada, i disposar d'elements per argumentar de forma raonada sobre les eleccions realitzades.
6. Conèixer els mecanismes fonamentals de l'orientació a objectes que permeten el desenvolupament de software a gran escala amb les propietats de modularitat, escalabilitat, robustesa, eficiència, correctesa, etc. necesràries.

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
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. 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.
5. Capacitat per relacionar i estructurar informació de diverses fonts, per integrar idees i coneixements.

Continguts

Hores estimades de:

Metodologia docent

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

Les classes es divideixen en tres tipus: sessions de teoria, sessions de problemes i sessions de laboratori. De mitjana, les classes de teoria es distribueixen en dues hores setmanals, les de problemes en dues hores setmanals i les de laboratori en una hora setmanal. El professor adaptarà la repartició d'aquestes classes de la millor forma possible, depenent del temari.

Les sessions de teoria són classes de tipus magistral, on el professor aporta als estudiants conceptes nous o tècniques noves, així com exemples seleccionats que els motivin o els il·lustrin.

Les classes de problemes tenen com a objectiu desenvolupar una sèrie d'exercicis o casos d'estudi. El professor és qui proposa els problemes que s'han de resoldre. Pel que fa els exercicis, la seva finalitat és la presentació i discussió de solucions a enunciats relativament simples que involucrin uns pocs coneixements teòrics o unes poques tècniques. En general, es tracta d'exercicis triats per tal d'il·lustrar conceptes que s'han intriduït a les sessions de teoria més recents. Pel que fa als casos d'estudi, els problemes proposats tenen una complexitat més gran que la dels exercicis i, a més, involucren diferents conceptes teòrics que cal combinar per obtenir una bona solució.

Les classes de laboratori tenen com a objectiu implementar solucions a una sèrie d'exercicis pràctics. El professor és qui proposa els exercicis pràctics que s'han de resoldre. Els estudiants resoldrà els exercicis proposats amb la supervisió personalitzada del professor.

Mètode d'avaluació

S'avaluarà tant el seguiment de l'assignatura, a través de proves d'avaluació continuada (P), com la realització d'un examen final (F) que cobreix tot el temari de l'assignatura i la realització de pràctiques de laboratori (L).

La nota final de l'assignatura es calcularà per la fórmula:
0.2 L + 0.8 * max(F, 0.6 * F + 0.4 * P)

Bibliografía bàsica

• WEISS, Mark A. Data Structures and Problem Solving Using Cpp, 2nd edition, Addison-Wesley, 2000.
• SEDGEWICK, Robert Algorithms in Cpp, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, 3rd edition, Addison-Wesley, 1999.

Bibliografía complementària

• WEISS, Mark A. Data Structures and Algorithm Analysis in Cpp, 2nd edition, Addison-Wesley, 1998.

Enllaços web

1. http://www.fib.upc.edu/~ps
   Pàgina de l'assignatura (en construcció).

Capacitats prèvies

Domini de les tècniques de programació imperativa. Coneixement d'almenys un llenguatge de programació imperatiu i/o orientat a objectes. Recursivitat. Coneixements bàsics de matemàtica discreta. Capacitat per seguir raonaments matemàtics i formals. Alguns coneixements elementals d'estadística i probabilitat.