Oblikovanje i analiza algoritama 2015/16

Oblikovanje i analiza algoritama — seminarske teme i seminari (2015/16)

Zadnja promjena: 4. ožujka 2016. u 18:56. (31. svibnja 2018.)

Prezentacije nekih seminara (objavljeno uz dozvolu autora).

Obavijest: U petak, 15. siječnja 2016., može 7 seminara, od 16–19:40 sati u (A101), pa sve odradimo u 2 termina!

Seminarske teme su podijeljene u dvije grupe: standardne teme i poglavlja (``kolumne'') iz knjiga Jona Bentleya. Detaljni popis je malo niže.

Link na topic na forumu za kolegij za pregled izabranih tema i prijavu.

Kako se bira tema?
- Izbor teme ide po sistemu: tko se prvi (pri)javi, njegova je!
- Potpuno isto vrijedi i za termine!
- Realizacija prijave ide preko topica na forumu za kolegij.
- Prije izbora teme, prvo pogledajte na forum koje teme su već izabrane. To je jedini mjerodavni popis!

Studenti koji imaju pravo na seminar:
- Ovdje ide popis imena.

ne želi

Zadnji rok za prijavu seminara (iza toga smatram da idete na 2. kolokvij): nedjelja, 3. siječnja 2016., u 23:59:59 sati.

Termini za prezentacije seminara (max. 6 seminara po terminu, može 7 seminara u petak, 15. siječnja 2016.):
- ponedjeljak, 11. siječnja 2016., 11--14 sati u (A101) --- termin predavanja:
- petak, 15. siječnja 2016., 16--19 sati u (A101) --- dodatni termin (popunjen):
  - Ovdje ide popis imena.
- ponedjeljak, 18. siječnja 2016., 11--14 sati u (A101) --- termin predavanja (popunjen):
  - Ovdje ide popis imena.
- petak, 22. siječnja 2016., 16--19 sati u (A101) --- dodatni termin.
  - Ovdje ide popis imena.

Upute za prezentaciju / izlaganje seminara:
- Trajanje izlaganja je 20 minuta, tj. dva seminara na sat, uz vrijeme za diskusiju (i pauze).
- Ne morate se strogo držati teksta iz literature. Poneke stvari smijete skratiti ili proširiti (na primjer, koristeći zadatke na kraju poglavlja).
- U Bentleyevim knjigama, na kraju knjige, postoje i rješenja nekih zadataka.
- Dozvoljeno (poželjno) je koristiti i dodatnu literaturu. Propisno navedite što ste koristili.
- Bitno je da cijelo izlaganje ima ``glavu, sredinu i rep''.
- Poželjna struktura prezentacije:
  - uvod --- što je problem?
  - potrebni matematički rezultati o problemu (ako treba),
  - kratki opis algorit(a)ma i složenosti,
  - ukratko o implementaciji (ako ima zanimljivih detalja),
  - opis testiranja i prikaz rezultata.

Napomena: Linkovi na dostupnu literaturu kod pojedinih tema isti su kao i linkovi na dnu (po poglavljima), tako da ne skidate dva puta isto.
Za navedenu literaturu koja nije dostupna ovdje (posebno, knjige), pogledajte uputu malo niže!
- Kod skidanja literature potrebna je autorizacija = "kolegijsko" korisničko ime (login) i lozinka (password).

Popis tema po područjima

Standardne seminarske teme:
1. Najbliži par točaka (``podijeli pa vladaj'', geometrija)
  - Lit.: JS 225--232 (pdf, 962 kB), CLR 908--912, CLRS (33.4) 834--840, KT (5.4) 225--231, ALS 192--195.
2. Sortiranje prebrajanjem i Radix Sort (sortiranje)
  - Lit.: JS 257--262 (pdf, 1107 kB), CLR 172--184 (140--180), KN3.
3. Presjek segmenata u ravnini (geometrija)
  - Lit.: CLR 886--898, CLRS (33.1, 33.2) 813--826, ALS 467--471 (pdf, 488 kB).
4. Grupiranje (klasteriranje) --- primjena Kruskalovog algoritma (``pohlepa'')
  - Lit.: KT (4.7, 4.6) 157--161, 151--157.
5. Najkraći putevi iz jednog vrha u grafu --- Dijkstra (``pohlepa'')
  - Lit.: KT (4.4) 137--142, CLR 527--532, ALS 232--239.
6. Najkraći put između dva vrha u grafu --- Bellman--Ford (dinamičko programiranje)
  - Lit.: KT (6.8, 6.9) 290--297, 297--301 CLR 532--536.
7. Najdulji zajednički podniz (dinamičko programiranje)
  - Lit.: JS 342--349 (pdf, 1261 kB), DM 40--44 (pdf, 1210 kB), CLR 314--320 (301--328), CLRS (15.4) 300--305, ALS 205--208, 214--215 (pdf, 6097 kB).
8. Ulančano množenje matrica
  - Lit.: JS 336--342 (pdf, 1261 kB), DM 50--54 (pdf, 1210 kB), CLR 301--314 (301--328), CLRS (15.2) 284--290, ALS 208--213, 214--215 (pdf, 6097 kB).
9. Svi najkraći putevi u grafu --- Floyd--Warshall (dinamičko programiranje)
  - Lit.: JS 350--361 (pdf, 1261 kB), CLR 558--565 (550--578), ALS 215--217, 214--215 (pdf, 6097 kB).
10. Sume podskupova i 0/1 ruksak --- (dinamičko programiranje)
  - Lit.: KT (6.4) 266--272, CLR 335--337, ALS 217--220, 214--215 (pdf, 6097 kB).
11. Segmentirani najmanji kvadrati (dinamičko programiranje)
  - Lit.: KT (6.3) 261--266.
12. Rabin--Karp algoritam (pretraživanje teksta)
  - Lit.: JS 371--379 (pdf, 2519 kB), CLR 857--862 (853--885).
13. Knuth--Morris--Pratt algoritam (pretraživanje teksta)
  - Lit.: JS 379--391 (pdf, 2519 kB), CLR 869--876 (853--885).
14. Boyer--Moore--Horspool algoritam (pretraživanje teksta)
  - Lit.: JS 392--398 (pdf, 2519 kB), CLR 876--883 (853--885).
15. Približno prepoznavanje uzorka (pretraživanje teksta)
  - Lit.: JS 398--408 (pdf, 2519 kB).
16. Vremenski raspored intervala (``pohlepa'')
  - Lit.: KT (4.1) 116--125, DM 24--26 (pdf, 1210 kB).

Poglavlja (``kolumne'') iz knjige Jona Bentleya ``Programming Pearls (2. izdanje)'':
1. Tehnike za konstrukciju algoritama, suma potpolja
  - Lit.: PP2, column 8, str. 77--86.
2. Ubrzavanje koda, binarno traženje
  - Lit.: PP2, column 9, str. 87--98.
3. Stiskanje prostora
  - Lit.: PP2, column 10, str. 99--111.
4. Sortiranje, Quicksort, ubrzanje
  - Lit.: PP2, column 11, str. 115--124.
5. Primjer problema, slučajni cijeli brojevi bez ponavljanja
  - Lit.: PP2, column 12, str. 125--132.
6. Traženje, implementacija konačnog skupa cijelih brojeva
  - Lit.: PP2, column 13, str. 133--146.
7. Hrpe, implementacija, heapsort
  - Lit.: PP2, column 14, str. 147--159.
8. Stringovi, riječi, fraze, tekst
  - Lit.: PP2, column 15, str. 161--173.

Poglavlja (``kolumne'') iz knjige Jona Bentleya ``More Programming Pearls'':
1. Uzorak briljantnosti, slučajni brojevi, slučajne permutacije
  - Lit.: More_PP, column 13, str. 139--145.
2. Rođenje drobilice brojeva, euklidska udaljenost, računanje korijena
  - Lit.: More_PP, column 14, str. 147--158.
3. Izbor (selekcija), k-ti po veličini, medijan
  - Lit.: More_PP, column 15, str. 159--170.

Literatura

Literatura po poglavljima (scan iz knjiga):
- JS 133–162 (dio 3. poglavlja): Strukture podataka, Heapsort (pdf, 1058 kB)
- JS 213–238 (5. poglavlje): ``Podijeli pa vladaj'' algoritmi (pdf, 962 kB)
- JS 239–270 (6. poglavlje): Sortiranje i pretraživanje (pdf, 1107 kB)
- JS 275–295 (dio 7. poglavlja): Pohlepni algoritmi — Kruskal, Prim (pdf, 788 kB)
- JS 323–365 (8. poglavlje): Dinamičko programiranje (pdf, 1261 kB)
- JS 367–428 (9. poglavlje): Pretraživanje teksta (pdf, 2519 kB)
- ALS 203–226 (7. poglavlje): Dinamičko programiranje (pdf, 6097 kB)
- ALS 462–480 (18. poglavlje): Geometrijski algoritmi (pdf, 488 kB)

Dodatna literatura (predavanja s weba):
- DM08 1–137: David M. Mount, Design and Analysis of Computer Algorithms, Spring 2008 (pdf, 1210 kB)

Kako do knjiga? Za izravni link na knjigu treba spojiti tri stvari:
- na prvi dio "http://degiorgi.math.hr/oaa/oaa_lit/"
- treba dodati ime s ekstenzijom
  - "ALS" (pdf, 21552 kB)
  - "CLR" (pdf, 54952 kB)
  - "CLRS" (pdf, 13081 kB) (novije izdanje CLR, stranice i sadržaj nisu isti kao u CLR, fale neki specijalni simboli!)
  - "KT" (pdf, 44859 kB)
  - Programming Pearls (2. izdanje) — "PP2" (djvu, 2074 kB)
  - Programming Pearls (1. izdanje) — "PP1" (djvu, 1784 kB, ili pdf, 11028 kB)
  - More Programming Pearls — "More_PP" (djvu, 1555 kB, ili pdf, 11291 kB).
  - Dodatni materijali uz Programming Pearls (2. izdanje) — "PP2_add_web" (pdf, 1294 kB).
    Sve stranice (nekadašnjeg) weba s dodatnim materijalima za PP2 (link na to više ne radi).

Čitanje: Sumatra PDF — besplatni program koji čita "pdf" i "djvu" na Windowsima.