Poslijediplomski doktorski studij

Nazad   Raspored   Engleski

Brzi algoritmi za NP- probleme ZUMR110

ECTS 8 | P 5 | A 0 | L 0 | K 0 | ISVU | Akademska godina: 2019./2020.

Nastavnici na predmetu

RUDEC TOMISLAV, nositelj

Ciljevi predmeta

Cilj predmeta je dati pregled najpoznatijih NP-teških i online problema; dati pregled aproksimacijskih algoritama za NP-teške i online probleme; studente naučiti kreirati heurističke algoritme za probleme u kojima nema polinomijalno brzih rješenja.

Uvjeti za upis predmeta

Upisan odgovarajući Poslijediplomski sveučilišni studij

Sadržaj

NP-teški i NP-potpuni problemi. NP-teški problemi na grafovima. NP-teški problemi raspoređivanja. Randomiziranje. On-line algoritmi. Problem straničenja. Analiza i usporedba algoritama za problem straničenja. Problem k-poslužitelja. Optimalni offline algoritam za problem k- poslužitelja. Brzi aproksimacijski algoritmi za problem k-poslužitelja.

Znanja i vještine koje se stječu uspješnim svladavanjem kolegija

1. Klasificirati razne teže probleme iz teorije grafova i teorije mreža obzirom na brzinu izvođenja 2. Kreirati nove heurističke metode i aproksimacijske algoritme za probleme u grafovima koristeći se već poznatima 3. Klasificirati algoritme za probleme na grafovima obzirom na njihovu brzinu 4. Samostalno pronalaziti brže algoritme za razne NP-teške i online probleme

Oblici provođenja nastave

predavanja, samostalni zadaci, auditorne vježbe

Obveze studenata

Rješavanje zadaća ili seminarskog rada te usmeni ispit.

Praćenje rada studenata

Pohađanje nastave, seminarski rad, usmeni ispit

Pregled ishoda učenja, nastavnih metoda i procjena ishoda učenja

Ishodi učenja:


Aktivnosti studenta: Vidi tablicu aktivnosti