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:.


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)

Examens al curs 2010-11:

Parcial 1 (pdf)

Parcial 2 (pdf)

Final (pdf)

Lectures complementaries

Article-Roura (pdf)

Article original Diffie i Hellman (pdf)

Article original de B. Bloom (pdf)

Article traduit a l'algles de Boruvka sobre el MST (ps.gz)

Article complexitat i primalitat (ps.gz)