Oblikovanje i analiza algoritama — seminarske teme (2011/12)

Zadnja promjena: 18.01.2012. u 12:56.  (31. svibnja 2018.)

Seminarske teme: Kako se bira tema?

• Izbor teme ide po sistemu: tko se prvi (pri)javi, njegova je!
• Potpuno isto vrijedi i za termine!
• Realizacija prijava, u načelu, ide preko foruma za kolegij (link je malo niže).
• 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.

Zadnji rok za prijavu seminara (iza toga smatram da idete na 2. kolokvij):  utorak, 13. prosinca 2011. u 24 sata.

Link na forum za kolegij za pregled izabranih tema i prijavu.

Termin za prezentacije prije kolokvija (max. 10 seminara po terminu) --- u vrijeme (i nakon) zadnjeg predavanja:

• utorak, 20. prosinca 2011. (13--18 sati):   Ovdje ide popis imena.

Termini za prezentacije u doba kolokvija (max. 4 seminara po terminu):

• petak, 13. siječnja 2012. (10--12 sati):   Ovdje ide popis imena.
• petak, 20. siječnja 2012. (11:30--12 sati):   Ovdje ide popis imena.
• petak, 27. siječnja 2012. (10--12 sati):  

Ako ne stignete napraviti seminar za neki od ovih termina, javite se prije zadnjeg termina za dogovor. Iza toga, nema spasa.

Upute za prezentaciju / izlaganje seminara:

• Trajanje izlaganja je 20 minuta (dva seminara na sat).
• 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.

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!
Napomena: Kod skidanja literature potrebna je autorizacija = "kolegijsko" korisničko ime (login) i lozinka (password).

Popis tema po područjima

Seminarske teme:

1. Maksimalni element skupa točaka (višedimenzionalni ``podijeli pa vladaj'')
   • Lit.:   članak (pdf, 1730 kB), str. 1–2, 7–9.
2. Traženje raspona u skupu točaka (višedimenzionalni ``podijeli pa vladaj'')
   • Lit.:   članak (pdf, 1730 kB), str. 1–2, 9–11.
3. Heapsort (sortiranje)
   • Lit.:   JS 133--149 (pdf, 1058 kB),   CLR 140--152 (140--180),   KN3.
4. Generalizirani Heapsort (sortiranje)
   • Lit.:   članak (pdf, 74 kB).
5. Sortiranje prebrajanjem i Radix Sort (sortiranje)
   • Lit.:   JS 257--262 (pdf, 1107 kB),   CLR 172--184 (140--180),   KN3.
6. Selekcija (izbor) i medijan
   • Lit.:   JS 262--267 (pdf, 1107 kB),   CLR 185--194 (140--180).
7. Presjek segmenata u ravnini (geometrija)
   • Lit.:   CLR 886--898,   ALS 467--471 (pdf, 488 kB).]
8. Dijametar skupa točaka (geometrija)
   • Lit.:   ALS 474--478 (pdf, 488 kB).
9. Najdulji zajednički podniz (dinamičko programiranje)
   • Lit.:   JS 342--349 (pdf, 1261 kB),   CLR 314--320 (301--328),   ALS 205--208, 214--215 (pdf, 6097 kB).
10. Svi najkraći putevi u grafu --- rekurzivno (dinamičko programiranje)
    • Lit.:   CLR 550--558 (550--578).
11. 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).
12. Svi najkraći putevi u grafu --- Johnson za šuplje grafove (dinamičko programiranje)
    • Lit.:   CLR 565--570 (550--578).
13. Rabin--Karp algoritam (pretraživanje teksta)
    • Lit.:   JS 371--379 (pdf, 2519 kB),   CLR 857--862 (853--885).
14. Knuth--Morris--Pratt algoritam (pretraživanje teksta)
    • Lit.:   JS 379--391 (pdf, 2519 kB),   CLR 869--876 (853--885).
15. Boyer--Moore--Horspool algoritam (pretraživanje teksta)
    • Lit.:   JS 392--398 (pdf, 2519 kB),   CLR 876--883 (853--885).
16. Približno prepoznavanje uzorka (pretraživanje teksta)
    • Lit.:   JS 398--408 (pdf, 2519 kB).
17. Stabilno sparivanje, stabilni brakovi (Gale--Shapley algoritam)
    • Lit.:   DM 4--8 (pdf, 1210 kB).
18. Vremenski raspored intervala (``pohlepa'')
    • Lit.:   DM 24--26 (pdf, 1210 kB).

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):
  
  • DM 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)


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