Programació II (Curs 2002/2003)

L'assignatura es divideix en tres parts clarament diferenciades, tant pel que fa al seu contingut com pels seus objectius. En la primera part, s'estudien diverses tècniques de programació, com pot ser el Divide & Conquer, el Backtracking, el Branch & Bound, etc. En la segona part s'introdueix a l'alumne dins del desenvolupament formal de programes. Es veu com demostrar la correctessa formal d'algorismes recursius simples i d'algorismes iteratius, també s'estudia com es poden derivar programes iteratius a partir d'especificacions formals. En cap moment es perd de vista els aspectes de complexitat algorísmica dels programes dissenyats. Finalment, en la tercera part, es fa una petita introducció a la programació paral·lela, seguint els conceptes elementals del CSP d'en Hoare.

1. MODULARITAT I DISSENY DEL SOFTWARE (6 hores)
1. El disseny del sotfware
2. La modularitat del software
3. Estils de disseny


2. ESPECIFICACIÓ D'ALGORISMES. CONCEPTES BÀSICS (2 hores)
1. Introducció
2. Com especificar algorismes?
3. Cap a on anem?
4. Exemples

3. COST DELS ALGORISMES (4 hores)
1. Introducció
2. Mesures assimptòtiques per descriure la taxa de creixement
3. Consideracions sobre la taxa de creixement
4. Càlcul del temps d'execució

4. DISSENY D'ALGORISMES RECURSIUS (9 hores)
1. Introducció
2. Etapes i metodologia del disseny recursiu simple
3. Algun exemple de disseny
4. Disseny recursiu per immersió
5. Transformació recursiu-iteratiu simple
6. Recursivitat múltiple. Divide & Conquer
7. Exemples de recursivitat múltiple
8. Transformació recursiu-iteratiu múltiple

5. LA TÈCNICA DEL BACKTRACKING (12 hores)
1. Caracterització dels problemes. Terminologia
2. Esquema recursiu i iteratiu del backtracking
3. Metodologia de resolució
4. Exemples
5. Backtracking per trobar la millor de les solucions
6. Millora en l'eficiència

6. EL MÈTODE DE BRANCH & BOUND (5 hores)
1. Introducció al mètode. Caracterització dels problemes
2. Esquema d'un algorisme de Branch & Bound
3. Exemple

7. ALGORISMES GREEDY (2 hores)
1. Introducció al mètode. Caracterització dels problemes
2. Esquema d'un algorisme Greedy
3. Exemples

8. ESPECIFICACIÓ FORMAL D'ALGORISMES (4 hores)
1. Introducció. Repàs de l'especificació d'algorismes
2. Estats i la seva caracterització. Càlcul proposicional
3. Especificació formal en termes de pre i post condició

9. VERIFICACIÓ FORMAL D'ALGORISMES RECURSIUS SIMPLES (10 hores)
1. Intrroducció. Recordatoris i objectius
2. La verificació formal. Esquema de demostració.
3. Exemples

10. DISSENY I VERIFICACIÓ FORMAL D'ALGORISMES ITERATIUS SENZILLS (12 hores)

1. Introducció
2. La precondició més feble
3. Verificació formal d'un algorisme iteratiu senzill
4. Derivació d'algorismes.

11. DISSENY PARAL·LEL I CONCURRENT (12 hores)

1. Introducció
2. Breu repàs històric del pal·lelisme
3. Terminologia
4. Notació algorísmica
5. Metodologia de programació paral·lela
6. Esquemes de disseny paral·lel
7. Problemes de competència
8. Problemes de cooperació

• Primer trimestre: Temes 1, 2, 3, 4 i 5
• Segon trimestre: Temes 5, 6, 7, 8 , 9 i 10
• Tercer trimestre: Temes 10 i 11

• E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1989.
• E. Dijkstra, A discipline of Programming, Prentice-Hall, 1976.
• D. Gries, The Science of Programming, Springer-Verlag, 1981.
• M. Ben-Ari, Principles of Concurrent Programming, Prentice-Hall, 1982.
• J.L. Balcazar, Programacion Metodica, McGraw Hill, 1993.

Durant el curs s'hauran de realitzar dues pràctiques en grups de dos alumnes. La primera plantejarà un conjunt d'exercicis de cara a practicar algunes de les tècniques de programació estudiades en la segona part del curs. La segona pràctica tindrà com a objectiu la cerca de solucions òptimes en un espai de cerca no trivial per a algun problema real. Tot seguit, i per a cada pràctica, es dóna el títol, una breu descripció, el temps estimat necessari per resoldre-la, i les dates de publicació de l'enunciat i de lliurement de la memòria.

Pràctica 1

Pràctica 2

Les pràctiques es podran presentar dins del calendari establert (convocatòries ordinàries) o bé en una convocatòria extraordinària al mes de juny. També existirà una convocatòria ordinària durant el mes de setembre.

La teoria i les pràctiques s'han d'aprovar per separat i les notes d'una cosa i de l'altra, es guarden fins al mes de setembre.

Respecte a la teoria hi haurà dos parcials (P1 i P2) i un final. El final podrà ser un examen que només reculli la temàtica del tercer trimestre de classes (a aquest examen en direm P3), o bé un examen final (F) pròpiament dit on i entra tot el temari de l'assignatura. Evidentment, durant el mes de setembre hi haurà un altre examen final que recollirà tots els continguts explicats a classe.

La teoria es pot aprovar de dues maneres: en l'examen final o per parcials. El sistema per aprovar per parcials es basa en el concepte d'"OFFSET". Per aprovar per parcials s'ha de complir que:

P1 + P2 + P3 >= 15 + OFFSET

on:

OFFSET = OFFSET1 + OFFSET2 + OFFSET3

Cada OFFSETi es calcula de la manera següent. Si la nota Pi es igual a superior a 4, llavors OFFSETi = 0. Altrament, OFFSETi = (4 - Pi).

Aquest sistema de puntuació ofereix la possibilitat que un alumne que hagi tret una mala nota en un parcial, la pugui recuperar en un altre.

Sempre que es consideri que la teoria estigui aprovada per parcials, per calcular la nota mitjana de teoria obtinguda a partir de les notes P1, P2 i P3; es procedirà a realitzar un escalat de les notes segons la fórmula següent:

Nota de parcials = ( 5 * (P1+P2+P3) ) / (15 + OFFSET)

La nota final de l'assignatura es calcularà a partir de la nota de teoria i la nota de pràctica. La nota de teoria tindrà un pes del 75% sobre la nota final, mentre que la nota de pràctica en tindrà un 25%.

Pel que fa a les pràctiques, la primera es puntuarà com a apte i no-apte, la segona s'avaluarà amb nota.