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!
Na ovom popisu povremeno će se dodavati imena studenata uz već
izabrane teme i termine.
- Studenti koji imaju pravo na seminar:
Ako netko ne želi seminar, molim da mi to javi.
- 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):
- ponedjeljak, 18. siječnja 2016., 11--14 sati u (A101) --- termin predavanja (popunjen):
- petak, 22. siječnja 2016., 16--19 sati u (A101) --- dodatni termin.
- 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:
-
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.
-
Sortiranje prebrajanjem i Radix Sort (sortiranje)
- Lit.:
JS 257--262
(pdf, 1107 kB),
CLR 172--184 (140--180),
KN3.
-
Presjek segmenata u ravnini (geometrija)
- Lit.:
CLR 886--898,
CLRS (33.1, 33.2) 813--826,
ALS 467--471
(pdf, 488 kB).
-
Grupiranje (klasteriranje) --- primjena Kruskalovog algoritma (``pohlepa'')
- Lit.:
KT (4.7, 4.6) 157--161, 151--157.
-
Najkraći putevi iz jednog vrha u grafu --- Dijkstra (``pohlepa'')
- Lit.:
KT (4.4) 137--142,
CLR 527--532,
ALS 232--239.
-
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.
-
Najdulji zajednički podniz (dinamičko programiranje)
-
Ulančano množenje matrica
-
Svi najkraći putevi u grafu --- Floyd--Warshall
(dinamičko programiranje)
-
Sume podskupova i 0/1 ruksak --- (dinamičko programiranje)
-
Segmentirani najmanji kvadrati (dinamičko programiranje)
-
Rabin--Karp algoritam (pretraživanje teksta)
- Lit.:
JS 371--379
(pdf, 2519 kB),
CLR 857--862 (853--885).
-
Knuth--Morris--Pratt algoritam (pretraživanje teksta)
- Lit.:
JS 379--391
(pdf, 2519 kB),
CLR 869--876 (853--885).
-
Boyer--Moore--Horspool algoritam (pretraživanje teksta)
- Lit.:
JS 392--398
(pdf, 2519 kB),
CLR 876--883 (853--885).
-
Približno prepoznavanje uzorka (pretraživanje teksta)
-
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)'':
-
Tehnike za konstrukciju algoritama, suma potpolja
- Lit.:
PP2, column 8, str. 77--86.
-
Ubrzavanje koda, binarno traženje
- Lit.:
PP2, column 9, str. 87--98.
-
Stiskanje prostora
- Lit.:
PP2, column 10, str. 99--111.
-
Sortiranje, Quicksort, ubrzanje
- Lit.:
PP2, column 11, str. 115--124.
-
Primjer problema, slučajni cijeli brojevi bez ponavljanja
- Lit.:
PP2, column 12, str. 125--132.
-
Traženje, implementacija konačnog skupa cijelih brojeva
- Lit.:
PP2, column 13, str. 133--146.
-
Hrpe, implementacija, heapsort
- Lit.:
PP2, column 14, str. 147--159.
-
Stringovi, riječi, fraze, tekst
- Lit.:
PP2, column 15, str. 161--173.
-
Poglavlja (``kolumne'') iz knjige Jona Bentleya ``More Programming Pearls'':
-
Uzorak briljantnosti, slučajni brojevi, slučajne permutacije
- Lit.:
More_PP, column 13, str. 139--145.
-
Rođenje drobilice brojeva, euklidska udaljenost, računanje korijena
- Lit.:
More_PP, column 14, str. 147--158.
-
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):
- 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.