Oblikovanje i analiza algoritama — seminarske teme i seminari (2016/17)

Zadnja promjena: 27. siječnja 2017. u 20:45.  (31. svibnja 2018.)

• Prezentacije seminara (objavljeno uz dozvolu autora).

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!
  • 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:
  • Ovdje ide popis imena.
Ako netko ne želi seminar, molim da mi to javi.


• Zadnji rok za prijavu seminara (iza toga smatram da idete na 2. kolokvij):  utorak, 27. prosinca 2016., u 23:59:59 sati.


• Termin za prezentacije seminara — u vrijeme zadnjeg predavanja:  utorak, 24. siječnja 2017., 14–16 sati u (A001).
  • 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. Konveksna ljuska skupa točaka (geometrija)
     • Lit.:   CLR 898–908,   CLRS (33.3) 826–833,   ALS 471–474 (pdf, 488 kB).
  3. Dijametar skupa točaka (geometrija)
     • Lit.:   ALS 474–478 (pdf, 488 kB).
  4. 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.
  5. Segmentirani najmanji kvadrati (dinamičko programiranje)
     • Lit.:   KT (6.3) 261–266.
  6. Približno prepoznavanje uzorka (pretraživanje teksta)
     • Lit.:   JS 398–408 (pdf, 2519 kB).


• Poglavlja (``kolumne'') iz knjige Jona Bentleya ``Programming Pearls (2. izdanje)'':
  21. Tehnike za konstrukciju algoritama, suma potpolja
      • Lit.:   PP2, column 8, str. 77–86.
  23. Stiskanje prostora
      • Lit.:   PP2, column 10, str. 99–111.
  25. Primjer problema, slučajni cijeli brojevi bez ponavljanja
      • Lit.:   PP2, column 12, str. 125–132.
  26. Traženje, implementacija konačnog skupa cijelih brojeva
      • Lit.:   PP2, column 13, str. 133–146.
  27. Hrpe, implementacija, heapsort
      • Lit.:   PP2, column 14, str. 147–159.
  28. Stringovi, riječi, fraze, tekst
      • Lit.:   PP2, column 15, str. 161–173.


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


• Teme po vlastitom izboru studenata:
  41. Barnes–Hut algoritam za problem n tijela
      • Lit.:   Svrha i opis algoritma.

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.