Algorismia (Primer trimestre del curs 2010-11, FME)

Notes (Examen Final i Nota curs):

1. A.B. 33 ,8.5
2. R.DM. 30, 7
3. V. GM. 21, 5
4. J.P. 37 . 7

L'assignatura d'Algorismia de la llicenciatura de Matematiques de la UPC s'imparteix dilluns i divendres de de 10 a 12. (edifici U).

El curs aprofondeix en els conceptes del disseny i analisi d'algorismes.

Temari:

1. Introducció
2. Recurrències
3. Grafs
4. Dividir i vèncer
5. Mètodes probabilistics
6. Algorísmes modulars
7. Algorismes voraços i compressió de dades
8. Programació dinàmica.
9. Programació Lineal
10. Complexitat
11. Algorísmes i estructura de dades probabilistics

Preliminars i avaluació:

Els prerequisits per al curs d'Algorismia son un coneixements a nivell de 3er de la llicenciatura de Matemàtiques (per ex. àlgebra modular, el teorema de Fermat, teorema d'Euler, variable aleatória condicional, variable complexa).

Hi han 2 llibres de text que cobreixen gran part del material al curs:.

• Dasgupta, Papadimitriou, Vazirani: Algorithms. Addison Wesley, 2007..
• Moore and Merten: The Nature of Computation, Oxford UP, 2011.

Avaluació: 2 exámens trimestrals curts, cadascun 2 punts, participació a classe i resolució de problemes 1,5 punts, l'examen final 4,5 punts.

Transparencies (en pdf):

Tema 1: Introducció (Pdf)

Tema 2: Recurrències (Pdf)

Tema 3: Estructura de dades i grafs. (pdf)

Tema 4: Dividir i vencer (pdf)

Tema 5: Aritmètica modular i el RSA (pdf)

Tema 6: Algorismes Voraços i compressió de dades (Pdf)

Tema 7: Progamacio Dinàmica (pdf)

Tema 8: Progamació Lineal (pdf)

Tema 9: Complexitat (pdf)

Tema 10: Estructura de dades i algorismes probabilistics (pdf)

Els fulls de problemes repartits a classe:

Full 1 (pdf)

Full 2 (pdf)

Full 3 (pdf)

Full 4 (pdf)

Full 5 (pdf)

Full 6 (pdf)

Full 7 (pdf)

Full 8

Full 10 (pdf)