Continguts del curs

De què va PRO2

A PRO1 vas aprendre a programar: variables, condicions, bucles, funcions i vectors. A PRO2 no aprens un llenguatge nou. Aprens a fer programes grans.

Quan un programa té milers de línies, ja no n’hi ha prou que funcioni. Ha d’estar ben organitzat perquè s’hi pugui treballar, ha de ser correcte per raons que sàpigues explicar i ha d’anar prou ràpid. Tot el curs gira al voltant de tres preguntes:

• Com l’organitzo? Partint-lo en peces (mòduls i classes) que es poden fer, provar i fer servir per separat.
• On guardo les dades? Triant l’estructura que va bé per a cada problema: una pila, una cua, una llista, un diccionari, un arbre.
• Com sé que està bé? Raonant per què un bucle o una funció recursiva fa el que ha de fer, i quant triga.

Els temes

0 · Introducció

Les eines de cada dia. Com es compila i s’executa un programa des del terminal, com es fa un Makefile perquè compilar un programa de molts fitxers sigui una sola ordre, i un repàs ràpid de C++ i de l’entrada i la sortida. Res de nou si véns de PRO1, però ho faràs servir a cada sessió.

1 · Especificació i programació orientada a objectes

El tema que canvia la manera de pensar. Aprens a partir un programa en mòduls i a definir tipus abstractes de dades: tipus nous (un Estudiant, una Cjt_estudiants) dels quals només et cal saber què fan, no com estan fets. Cada operació s’especifica amb una precondició i una postcondició. I tot això, en C++, es fa amb classes: una part pública que veu tothom (el .hh) i una part privada que només veu qui la programa (el .cc).

2 · Estructures de dades lineals

Les estructures que guarden elements un darrere l’altre i que ja venen fetes a la biblioteca estàndard: piles (stack), cues (queue), llistes (list) i diccionaris (map i set). Per a cada una veuràs què permet fer, què costa i quan convé. Les llistes es recorren amb iteradors, una idea que tornarà a sortir sovint. També veuràs com es fa una classe genèrica, que serveix per a qualsevol tipus d’element.

3 · Arbres

La primera estructura que no és lineal: cada element pot tenir fills. Arbres binaris i generals, les diferents maneres de recórrer-los i com es resolen problemes sobre arbres. Gairebé tots es resolen amb recursivitat, perquè un arbre està fet d’arbres més petits.

4 · Disseny iteratiu

Com s’escriu un bucle que funciona a la primera, i com es justifica. La clau és l’invariant: una propietat que es manté certa a cada volta i que t’explica què has fet fins ara. Amb l’invariant i una funció de fita (que garanteix que el bucle s’acaba) pots demostrar que un bucle és correcte sense provar-lo. També hi veuràs els esquemes de recorregut i de cerca, que resolen la majoria de problemes.

5 · Disseny recursiu

El mateix, però per a funcions recursives: com se’n dissenya una i com es justifica que és correcta. Hi apareix la immersió: afegir paràmetres a una funció perquè el problema es pugui resoldre recursivament. I com es passa d’una solució recursiva a una d’iterativa.

6 · Eficiència

Quant triga un programa i com es compara amb un altre sense cronòmetre. La notació asimptòtica ($O(n)$, $O(n^2)$, $O(\log n)$…) mesura com creix el temps quan creixen les dades. Veuràs com es calcula el cost d’un bucle o d’una funció recursiva, i com les immersions poden fer un programa molt més ràpid.

7 · Implementació d’estructures amb punters

Fins ara has fet servir les piles, les llistes i els arbres de la biblioteca. En aquest tema els programes tu. Veuràs la memòria dinàmica (new i delete), els punters i com s’enllacen nodes per fer una estructura que creix i s’encongeix mentre el programa s’executa. És el tema que lliga tot el curs: classes, estructures de dades, correctesa i eficiència.

Com estan fets els capítols

Cada capítol comença amb un resum i els conceptes clau, segueix amb l’explicació i acaba amb exercicis. Els exercicis porten la solució plegada: prova’ls abans d’obrir-la. L’últim capítol de cada tema és una consolidació, amb un resum d’una pàgina i exercicis que barregen tot el tema.