Algorismia (Primer trimestre del curs 2017-18, FME-UPC)

L'assignatura d'Algorismia i Complexitat al grau de Matemàtiques a la UPC s'imparteix dilluns, dimars, dijous i divendres de x a y. .

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


Temari(tentatiu):

  1. Introducció
  2. Complexitat
  3. Dividir i vèncer: La FFT discreta
  4. Complexitat aritmetica: El problema de la primalitat
  5. Estructures de dades:Hashing
  6. Introducció a la Criptografia
  7. Algorismes voraços i programació dinàmica: compressió de dades
  8. Fluxes
  9. Programació Lineal
  10. Algorismes heuristics i d'aproximació


Preliminars i avaluació:

Els prerequisits per al curs d'Algorismia són un coneixements a nivell de 3er de la llicenciatura de Matemàtiques (per ex. àlgebra modular, probabilitat a nivell l'assignatura de grau).

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


Quizes for the previous years:

Quiz 2015 (pdf)

Final(2015) Short Questions (pdf)

Transparencies (en pdf):

Tema 1: Introducció (Pdf)

Tema 2:Grafs(pdf)

Tema 3:Complexitat de Problemes (P i NP): (pdf)

Tema 4: Dividir i vencer (pdf)

Tema 5: Complexitat aritmetica:El problema de la primalitat (pdf)

Tema 6: Hashing i Aplicacions (pdf)

Tema 7: Introducció a la criptografia (pdf)

Tema 8: Greedy (pdf)

Tema 9: PD (pdf)

Tema 10: Fluxes (pdf)

Tema 11 : Programació Lineal i teoria de jocs (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 (pdf)

Solution R.Perez problem 30 (pdf)

Full 9 (pdf)

Lectures complementaries

J. Eisner's Tutorial on MST (pdf)