Tema 1Anàlisi d'algorismes
Com es mesura l'eficiència d'un algorisme sense dependre de l'ordinador. Notació asimptòtica, cas pitjor i mitjà, i recurrències.
- 1.1Llegit
- 1.2Llegit
- 1.3Llegit
- 1.4Llegit
- 1.5Llegit
EDA
Estructures de Dades i Algorismes
Com triar l'estructura de dades i l'algorisme adequats i saber quant costen. Anàlisi asimptòtica, dividir i vèncer, diccionaris, cues de prioritat, grafs i cerca exhaustiva, amb la STL de C++.
Temes
Tema 2Dividir i vèncer
L'esquema que divideix un problema en subproblemes més petits, els resol i combina els resultats. Algorismes clàssics de cerca, ordenació i aritmètica.
- 2.1Llegit
- 2.2Llegit
- 2.3Llegit
- 2.4Llegit
- 2.5Llegit
- 2.6Llegit
- 2.7Llegit
Tema 3Diccionaris
Estructures per desar parelles clau-valor i trobar-les ràpid. Taules de hash i arbres de cerca equilibrats.
- 3.1Llegit
- 3.2Llegit
- 3.3Llegit
- 3.4Llegit
- 3.5Llegit
Tema 4Cues de prioritat
Una estructura que et dona sempre l'element més prioritari. Els heaps i l'ordenació per heapsort.
- 4.1Llegit
- 4.2Llegit
- 4.3Llegit
- 4.4Llegit
Tema 5Grafs
Com es representen els grafs i els algorismes bàsics per recórrer-los i trobar camins i arbres d'expansió.
- 5.1Llegit
- 5.2Llegit
- 5.3Llegit
- 5.4Llegit
- 5.5Llegit
- 5.6Llegit
Tema 6Cerca exhaustiva
Quan no hi ha cap algorisme ràpid, cal explorar totes les possibilitats amb intel·ligència: backtracking i branch and bound.
- 6.1Llegit
- 6.2Llegit
- 6.3Llegit
Tema 7Intractabilitat
Hi ha problemes que, pel que sabem, no es poden resoldre ràpid. Classes P i NP, reduccions i NP-completesa.
- 7.1Llegit
- 7.2Llegit
- 7.3Llegit