Algorismia (Primer trimestre del curs 2016-17, FME-UPC)

Nota Final del Curs):

1. PC 7.5
2. RLP 7.5
3. RP 8.5
4. FVD 8
5. TJW 8

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

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

Temari(tentatiu):

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

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

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

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)