Seminar za teorijsko racunarstvo - 10.01.2011.

10 views

Skip to first unread message

Robert Manger

unread,

Jan 5, 2011, 12:19:19 PM1/5/11

to seminar-za-teori...@googlegroups.com, lista...@math.hr

Dragi kolege,

U okviru poslijediplomskog Seminara za teorijsko racunarstvo, Konrad Burnik ce u ponedjeljak 10.01.2011 u 15h u dvorani 105 odrzati predavanje pod naslovom:

Randomizirani algoritmi za NP-teske probleme.

Sazetak: NP-teske probleme je tesko efikasno rijesiti deterministiciki, stoga se nadamo da mozda slucajnim odabirom nekih dijelova rjesenja za konkretnu instancu mozda mozemo "pogoditi" rjesenje ili se barem pribliziti rjesenju polinomijalnom broju koraka. Ovdje na mogucnost slucajnog biranja (randomizaciju) gledati kao na alternativu nedeterminizmu i najprije cemo definirati teorijsku osnovu: pojam randomiziranog (probabilistiskog) Turingovog stroja, tipove randomiziranih algoritama, te njihovu analizu pomocu teorije vjerojatnosti. Ukratko cemo objasniti i opcenite vjerojatnosne metode i paradigme koje se koriste za konstrukciju randomiziranih algoritama. Na primjeru problema ispunjivosti boolovskih formula (SAT) cemo objasniti uvedene pojmove te pokazati algoritam koji ima ocekivano polinomijalno vrijeme rjesavanja za SAT instance. Vidjet cemo takodjer na primjeru da se prosjecne instance NP-potpunog problema trazenja Hamiltonovog ciklusa u grafu te instance mogu rijesiti u ocekivanom broju koraka koji je strogo manji od eksponencijalnog.

Pozivam sve clanove Seminara i ostale zainteresirane da prisustvuju ovom predavanju.