Seminar za teorijsko racunarstvo 30.06.2008
Matko Botincan
U ponedjeljak 30. lipnja 2008. s pocetkom u 15:00h (u sobi 109)
Paola Glavan s Fakulteta strojarstva i brodogradnje odrzat ce
predavanje na Seminaru za teorijsko racunarstvo pod naslovom:
"ASM model memorijskog modela Jave (2)"
Pozivaju se svi clanovi seminara kao i ostali zainteresirani da
prisustvuju ovom predavanju.
Lijepi pozdrav,
Matko Botincan
Robert Manger
Dragi kolege,
U ponedjeljak 7. srpnja 2008. s pocetkom u 15:00 h (u sobi 109)
Anamari Nakic s Fakulteta elektrotehnike i racunarstva odrzat ce
predavanje na Seminaru za teorijsko racunarstvo pod naslovom:
"Algoritam za medjusobno iskljucivanje s filozofima."
Pozivaju se svi clanovi seminara kao i ostali zainteresirani da
prisustvuju ovom predavanju.
Lijep pozdrav,
Robert Manger.
Robert Manger
Dragi kolege,
U ponedjeljak 17. studenog 2008. s pocetkom u 15:00 h (u sobi 109) Robert
Manger s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom
Seminaru za teorijsko racunarstvo pod naslovom:
"Nekompetitivnost modificiranog algoritma s radnom funkcijom za rješavanje
on-line problema k poslužitelja".
Robert Manger
U ponedjeljak 24. studenog 2008. s pocetkom u 15:00 h (u sobi 109) Krunoslav
Puljic s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom
Seminaru za teorijsko racunarstvo pod naslovom:
"Složeniji operatori evolucijskog algoritma za problem usmjeravanja vozila".
Robert Manger
U ponedjeljak 19. sijecnja 2009. s pocetkom u 15:00 h (u sobi 109) Tomislav
Rudec sa Sveucilista u Osijeku odrzat ce predavanje na poslijediplomskom
Robert Manger
Dragi kolege,
U ponedjeljak 02. veljace 2009. s pocetkom u 15:00 h (u sobi 109) Matko
Botincan s PMF-Matematickog odjela Sveucilista u Zagrebu odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Verifikacija C programa pomocu logike separacije i SMT solvera".
Sazetak:
U ovom seminaru prezentirat ce se metodologija za automatsku modularnu verifikaciju C programa obzirom na specifikaciju zapisanu pomocu logike separacije. Osnovne znacajke pristupa su vjerodostojna reprezentacija C memorijskog modela i upotreba SMT solvera u sprezi s automatskim dokazivacem za logiku separacije.
Matko Botincan
U ponedjeljak 09. veljace 2009. s pocetkom u 15:00 h (u sobi 109) Matko
Botincan s PMF-Matematickog odjela Sveucilista u Zagrebu odrzat ce
predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod
naslovom:
"VCC - Verifikacija konkurentnih C programa".
Sazetak:
VCC (Verified C Compiler) inkorporira modularnu metodologiju za
konkurentne C programe primjenjivu na stvarni produkcijski kod. VCC se
trenutno koristi za verifikaciju jezgre Microsoftovog Hyper-V-a,
platforme za virtualizaciju u Windows Server 2008, koja se sastoji od
vise od 60,000 linija sistemskog C koda. Osnovu metodologije cini
tipizirani memorijski model za C, koncept vlasnistva po uzoru na onaj u
Spec#-u zajedno s fleksibilnim invarijantama, te modularno tretiranje
konkurentnosti pomocu invarijanti dva stanja.
Pozivaju se svi clanovi seminara kao i ostali zainteresirani da
prisustvuju ovom predavanju.
Lijep pozdrav,
Matko Botincan
Robert Manger
U ponedjeljak 23. veljace 2009. s pocetkom u 15:00 h (u sobi 109) Josip
Sumecki, student PMF-Matematickog odjela Sveucilista u Zagrebu odrzat ce
predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod
naslovom:
"Mravlja optimizacija na primjeru problema trgovackog putnika".
Sazetak:
Mravlja optimizacija (Ant Colony Optimization) jedna je od najefikasnijih metaheuristika. Neke podvrste takve optimizacije smatraju se najboljim
postupcima za rjesavanje problema trgovackog putnika (Traveling Salesman)
i problema kvadraticnog dodjeljivanja (Quadratic Assignment). Mravlja optimizacija se temelji na istrazivanjima biologa o ponasanju mrava te njihovoj sposobnosti trazenja putova od mravinjaka do hrane bez vizualne predodzbe o putu kojim se krecu.
Pozivaju se svi clanovi seminara kao i ostali zainteresirani da
prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 11. svibnja 2009. s pocetkom u 15:00 h (u sobi 109) Robert Manger s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Klasifikacija metoda za rjesavanje NP-teskih problema kombinatorne optimizacije".
Sazetak:
Cilj predavanja je: predstaviti, klasificirati i usporediti metode za rjesavanje NP-teskih problema kombinatorne optimizacije. Metode su podijeljene u tri skupine: egzaktni algoritmi, aproksimacijski algoritmi i heuristike. Egzaktni algoritam daje tocno rjesenje, no zbog velike racunske slozenosti primjenjiv je samo na relativno male primjerke problema. Aproksimacijski algoritam daje u polinomijalnom vremenu priblizno rjesenje, te takodjer i garanciju da je to rjesenje "blizu" egzaktnom. Heuristika je brzi priblizni algoritam koji se pokazao upotrebljivim unatoc nedostatku garancije "dobrote".
Robert Manger
Danasnje predavanje na Seminaru za teorijsko racunarstvo nismo mogli odrzati zato jer nije bio prisutan nitko od onih koji su taj seminar upisali (!?). Molim vas da ubuduce ozbiljnije shvatite seminar, jer on je sastavni dio poslijediplomske nastave, a prisustvo na njemu je OBAVEZNO. Uostalom, za seminar na kraju morate dobiti i potpis kojim se potvrdjuje uredno dolazenje.
Propusteno predavanje pokusat cu odrzati u sljedecem terminu, dakle u ponedjeljak 18.05.2009 u 15 h (soba 109). Molim vas dodjite u malo vecem broju nego danas. Moguce je da ce biti problema zbog strajka, na primjer zgrada bi mogla biti zakljucana, no ja cu u tom slucaju doci po vas na vrata fakulteta.
Lijep pozdrav, Robert Manger.
Neva Slani
kuce (pa sam bas za pon dogovorila montazu) tako da nisam ni gledala
mejl...
Do ponedjeljka,
neva
Neva Slani
neva
On May 11, 2009, at 3:48 , Robert Manger wrote:
>
Robert Manger
U ponedjeljak 15. lipnja 2009. s pocetkom u 15:00 h (u sobi 109) Robert Manger s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Klasifikacija metoda za rjesavanje NP-teskih problema kombinatorne optimizacije (drugi dio)".
Sazetak:
Cilj predavanja je: predstaviti, klasificirati i usporediti metode za rjesavanje NP-teskih problema kombinatorne optimizacije. Metode su podijeljene u tri skupine: egzaktni algoritmi, aproksimacijski algoritmi i heuristike. Egzaktni algoritam daje tocno rjesenje, no zbog velike racunske slozenosti primjenjiv je samo na relativno male primjerke problema. Aproksimacijski algoritam daje u polinomijalnom vremenu priblizno rjesenje, te takodjer i garanciju da je to rjesenje "blizu" egzaktnom. Heuristika je brzi priblizni algoritam koji se pokazao upotrebljivim unatoc nedostatku garancije "dobrote".
Pozivaju se svi clanovi seminara kao i ostali zainteresirani da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 12. listopada 2009. s pocetkom u 15 h (u sobi 109) Krunoslav Puljic s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Distribuirani evolucijski algoritmi za problem usmjeravanja vozila (prvi dio)".
Robert Manger
Mali ispravak u vezi sa Seminarom za teorijsko racunarstvo. Ove godine rezervirana nam je dvorana 203, a ne 109 kao sto sam napisao u prethodnom mailu. Znaci vidimo se u ponedjeljak 12.10 u 15 h u dvorani 203. Ova promjena nam je povoljna jer 203 ima ugradjeni projektor a 109 nema.
Lijep pozdrav, Robert Manger.
-----Original Message-----
From: seminar-za-teori...@googlegroups.com [mailto:seminar-za-teori...@googlegroups.com] On Behalf Of Robert Manger
Sent: Tuesday, October 06, 2009 3:56 PM
To: seminar-za-teori...@googlegroups.com
Cc: lista...@math.hr; shumi...@gmail.com; 'Dario Orescanin'; 'Dinko Cicvarić'
Robert Manger
U ponedjeljak 19. listopada 2009. s pocetkom u 15 h (u sobi 203) Krunoslav Puljic s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Distribuirani evolucijski algoritmi za problem usmjeravanja vozila (drugi dio)".
Robert Manger
Nazalost, moram otkazati seminar iz prethodnog maila. Predavac je sprijecen zbog privatnih razloga. Ujedno najavljujem da ce se isti seminar odrzati sljedeci tjedan u istom terminu i istoj dvorani. Dakle iduci sastanak Seminara za teorijsko racunarstvo bit ce u ponedjeljak 26.10.2009. u 15 h (soba 203).
Lijep pozdrav, Robert Manger.
-----Original Message-----
From: seminar-za-teori...@googlegroups.com [mailto:seminar-za-teori...@googlegroups.com] On Behalf Of Robert Manger
Sent: Tuesday, October 13, 2009 9:10 AM
To: seminar-za-teori...@googlegroups.com
Cc: lista...@math.hr; shumi...@gmail.com; 'Dario Orescanin'; 'Dinko Cicvarić'
Robert Manger
U ponedjeljak 2. studenog 2009. s pocetkom u 15 h (u sobi 203) Krunoslav Puljic s PMF-Matematickog odjela odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Distribuirani evolucijski algoritmi za problem usmjeravanja vozila (treci dio)".
Pozivaju se svi clanovi seminara, pogotovo oni clanovi koji su ujedno i polaznici poslijediplomskog doktorskog studija, kao i ostali zainteresirani, da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 16. studenog 2009. s pocetkom u 17:15 h (u sobi 203) odrzat ce se zajednicki sastanak poslijediplomskog Seminara za matematicku logiku i osnove matematike i Seminara za teorijsko racunarstvo. Predavanje ce odrzati Filip Niksic, a tema ce biti iz podrucja propozicionalne dinamicke logike.
Pozivaju se svi clanovi Seminara za teorijsko racunarstvo, pogotovo oni clanovi koji su ujedno i polaznici poslijediplomskog doktorskog studija, kao i ostali zainteresirani, da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 14. prosinca 2009. s pocetkom u 15 h (u sobi 203) Marko Špoljarec, student poslijediplomskog doktorskog studija matematike, odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
" Algoritmi za izbor vodje u prstenu ".
Tema predavanja spada u podrucje distribuiranih algoritama. Pozivaju se svi clanovi seminara, pogotovo oni clanovi koji su ujedno i polaznici poslijediplomskog doktorskog studija, kao i ostali zainteresirani, da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 8. veljace 2010. s pocetkom u 15 h (u sobi 203) Andro Gregov i Antonija Malenica odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Meta-heuristicki algoritmi za problem bojanja vrhova grafa".
U seminaru ce biti prezentirana implementacija hibridnog genetskog (HG) i mravljeg (AC) algoritma za problem bojanja vrhova grafa te dobiveni rezultati. Oba algoritma testirana su na standardnim testnim primjerima grafova (DIMACS).
Robert Manger
U ponedjeljak 15. veljace 2010. s pocetkom u 15 h (u sobi 203) Dario Kresic s FOI Varazdin odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"O nekim problemima verifikacije vezanim uz vremenske automate".
Sazetak: Vremenski automati (engl. timed automata) proširuju ω-automate za skup tzv. satnih varijabli koje mjere vrijeme medju dogadjajima. Nakon predstavljanja sintakse i semantike Büchijevih i Mullerovih vremenskih automata bit ce diskutiran problem inkluzije dvaju (vremenskih) jezika vazan za verifikaciju modela zasnovanih na ovim automatima. S tim u vezi bit ce predstavljen i problem diskretizacije i tzv. eksplozije prostora stanja te diskutirane poteskoce automatske verifikacije.
Robert Manger
U ponedjeljak 22. veljace 2010. s pocetkom u 15h (u sobi 203) Hrvoje Peradin i Ilija Pavlic odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod naslovom:
"Meta-heuristicki algoritam za problem trgovackog putnika".
U seminaru ce biti prezentirana implementacija algoritma BCO (Bee Colony Optimization) za problem trgovackog putnika te analizirani dobiveni rezultati. Algoritam je testiran na primjerima grafova iz biblioteke TSPLIB sveucilista u Heidelbergu.
Robert Manger
U ponedjeljak 1. ozujka 2010. s pocetkom u 15h (u sobi 203) Snjezana
Majstorovic s Odjela za matematiku Sveucilista u Osijeku odrzat ce
predavanje na poslijediplomskom Seminaru za teorijsko racunarstvo pod
naslovom:
"Fischer-Lynch-Paterson-ov teorem".
Sazetak: Fundamentalni rezultat teorije distribuiranog racunanja, teorem
Fischer-Lynch-
Paterson (FLP), kaze da u asinkronoj mrezi problem konsenzusa nije rjesiv
cim dozvolimo mogucnost nenajavljenog prestanka rada samo jednog procesa.
Dokaz teorema je slozen, a bazira se na rezultatu o nemogucnosti konsenzusa
u asinkronoj R/W zajednickoj memoriji, cak i ako dozvolimo prestanak rada
najvise jednog procesa u sustavu. Formalni model za asinkroni sustav sa
zajednickom memorijom prezentiran je pomocu jednostavnog I/O automata A.
Zatim se pokaze da postoji ekvivalencija modela asinkronog racunanja sa i
bez zajednicke memorije. U dokazu FLP teorema potreban je jedino smjer
pretvorbe sustava bez zajednicke memorije u sustav sa zajednickom memorijom.
Robert Manger
U ponedjeljak 15. ozujka 2010. s pocetkom u 15 h (u sobi 203) Denis Kezman i
Jurica Levatic odrzat ce predavanje na poslijediplomskom Seminaru za
teorijsko racunarstvo pod naslovom:
"Usporedba razlicitih heuristickih algoritama za rjesavanje problema n
kraljica".
U seminaru se testira efikasnost pojedinih generickih heuristickih metoda
(Simulated Annealing ,Tabu Search, Harmony Search, Particle Swarm
Optimization), te prezentira jedan modificirani algoritam konstruiran i
optimiziran specificno za problem n kraljica.
Danijel Domazet
Meni ne polazi za rukom...
Pozdrav,
*Danijel Domazet*
/Codec Developer/
www.MainConcept.com <http://www.mainconcept.com/>
Robert Manger
nisam ni osnovao tu listu. Pretpostavljam da to moze uciniti Matko Botincan,
nekadasnji tajnik seminara. Stavite tog posiljatelja medju spam, pa ste
rijesili problem.
Lijep pozdrav, Robert Manger.
-----Original Message-----
From: seminar-za-teori...@googlegroups.com
[mailto:seminar-za-teori...@googlegroups.com] On Behalf Of
Danijel Domazet
Sent: Monday, March 08, 2010 9:20 AM
To: seminar-za-teori...@googlegroups.com
Cc: Robert Manger; lista...@math.hr; shumi...@gmail.com; 'Dario
Orescanin'; 'Dinko Cicvarić'
Pozdrav,
--
Lista Seminara za teorijsko računarstvo:
http://groups.google.com/group/seminar-za-teorijsko-racunarstvo?hl=en
Davor Runje
Lp,
Davor
Robert Manger
U ponedjeljak 29. ozujka 2010. s pocetkom u 15 h (u sobi 101) Marko
Spoljarec odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko
racunarstvo pod naslovom:
"KOR Point of Sale - studijski primjer razvoja aplikacije".
Sadrzaj predavanja je sljedeci:
1. Uvod u sustav ciji je aplikacija sastavni dio. Komunikacija među
dijelovima. Alati koji se koriste.
2. Opis i prikaz rada aplikacije.
3. Dizajn aplikacije (od baze podataka do korisnickog sucelja).
4. Razne zanimljivosti (pregledi, servis za ispis "KOR Print" itd.)
5. Tehnike programiranja i savjeti.
Robert Manger
u ponedjeljak 12. travnja 2010. s pocetkom u 15 h (u sobi 101) Marena
Markasovic i Sladjana Trac odrzat ce predavanje na poslijediplomskom
Seminaru za teorijsko racunarstvo pod naslovom:
"Metaheuristicki algoritam za problem ispunjivosti."
U seminaru ce biti prezentirana implementacija te rezultati dobiveni
primjenom tehnike simuliranog kaljenja za rjesavanje 3-SAT problema.
Pozivaju se svi clanovi seminara, pogotovo oni clanovi koji su ujedno i
polaznici poslijediplomskog doktorskog studija, kao i ostali zainteresirani,
da prisustvuju ovom predavanju. Usput koristim priliku da svima zazelim
sretan Uskrs.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 19. travnja 2010. s pocetkom u 15 h (u sobi 101) Marko
Spoljarec odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko
racunarstvo pod naslovom:
"KOR Point of Sale - studijski primjer razvoja aplikacije (drugi dio)".
Sadrzaj predavanja je sljedeci:
1. Uvod u sustav ciji je aplikacija sastavni dio. Komunikacija među
dijelovima. Alati koji se koriste.
2. Opis i prikaz rada aplikacije.
3. Dizajn aplikacije (od baze podataka do korisnickog sucelja).
4. Razne zanimljivosti (pregledi, servis za ispis "KOR Print" itd.)
5. Tehnike programiranja i savjeti.
Pozivaju se svi clanovi seminara, pogotovo oni clanovi koji su ujedno i
Robert Manger
U ponedjeljak 10. svibnja 2010. s pocetkom u 15 h (u sobi 203) Jurica
Bradaric odrzat ce predavanje na poslijediplomskom Seminaru za teorijsko
racunarstvo pod naslovom:
"Funkcionalno programiranje".
Sadrzaj predavanja je sljedeci:
- osnovno o funkcionalnom programiranju (povijest, primjeri, ...),
- prednosti i nedostatci funkcionalnog programiranja,
- jezik Haskell i primjeri njegovog korištenja,
- drugi funkcionalni jezici.
Pozivaju se svi clanovi seminara, pogotovo oni clanovi koji su ujedno i
polaznici poslijediplomskog doktorskog studija, kao i ostali zainteresirani,
da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U ponedjeljak 7. lipnja 2010. odrzat ce se dva predavanja na
poslijediplomskom Seminaru za teorijsko racunarstvo, jedno u 15h, drugo u
17h, oba u dvorani 101.
Prvo predavanje u 15 sati:
Predavac: Andreja Jeresic.
Naslov: Tipovi i sustavi tipova.
Sazetak: Proucavanje sustava tipova, u kontekstu programskih jezika,
proizlazi iz potrebe za sprecavanjem gresaka tijekom izvodjenja programa. U
seminaru ćemo govoriti o sustavima tipova, njihovoj povijesti, podjeli i
svrsi. Također cemo dodirnuti tematiku teorije tipova i usporediti s
teorijom skupova. Na kraju cemo ilustrirati neke pojmove kroz primjere u
CoQ-u.
Drugo predavanje u 17 sati:
Predavac: Ksenija Hodak
Naslov: Intuicionisticka logika i njen konstruktivni karakter.
Sazetak: Definirat cemo osnovne pojmove: sintaksu i pravila izvodjenja u
intuicionistickoj logici (sudova, te prvoga reda), zatim
Brouwer-Heyting-Kolmogorov interpretaciju tih pravila, te je usporediti s
klasicnom logikom (Goedelov i Glivenkov teorem). Osim toga, navesti cemo
nekoliko primjera dokaza u klasicnoj logici koji se ne smatraju dokazom u
intuicionistickoj logici. Navesti cemo nekoliko primjera semantika, te medju
njima jednu varijantu formulas-as-types realizacije u smislu Curry-Howard
izomorfizma, popracenu primjerima iz Coq-a.
Robert Manger
U sklopu Seminara za matematicku logiku i osnove matematike i Seminara za
teorijsko racunarstvo, u ponedjeljak 14. lipnja 2010. u 15 sati, u
predavaonici 101 PMF-MO, Andre Scedrov, University of Pennsylvania, odrzat
ce predavanje pod naslovom
Toward An Operational Semantics for Network Datalog
Network Datalog (NDlog) is a recursive query language that extends Datalog
by allowing programs to be distributed in a network. In our initial efforts
to formally specify NDlog's operational semantics, we have found several
problems with the current evaluation algorithm used, including unsound
results, unintended multiple derivations of the same table entry, and
divergence. In this work, we make first steps towards correcting these
problems by formally specifying a new operational semantics for NDlog and
proving its correctness for the fragment of non-recursive programs. Our
formalization uses linear logic with subexponentials. We also argue that if
termination is guaranteed, then the results also extend to recursive
programs. Finally, we identify a number of potential implementation
improvements to NDlog. This is joint work with Vivek Nigam, Limin Jia, Anduo
Wang, and Boon Thau Loo.
Pozivaju se svi clanovi obaju seminara, pogotovo oni clanovi koji su ujedno
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
13. rujna
2010. u 15 sati u predavaonici 101 PMF-MO, Konrad Burnik održat će
predavanje pod naslovom:
Težina aproksimacije rješenja u problemu traženja maksimalne klike.
Sažetak: Poznato je da je problem traženja maksimalne klike NP-težak
problem, i jedan prirodan pokušaj rješavanja ovog problema je tražiti
aproksimacijski algoritam. Na predavanju ćemo primjenom PCP teorema,
pokazati rezultat da je čak i aproksimacija optimalnog rješenja (do na
konstantni faktor) također NP-težak problem. U nastavku ćemo uvesti pojam
expander grafa te pomoću slučajne šetnje na expanderu pokazati i jači
rezultat, da je aproksimacija do na faktor 1/{n^\epsilon} za \epsilon > 0
također NP-težak problem.
Pozivaju se svi članovi seminara, kao i ostali zainteresirani, da
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
13. rujna 2010. u 15 sati u predavaonici 105 PMF-MO, Konrad Burnik održat će
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
15. studenog 2010. u 15 sati u predavaonici 105 PMF-MO, Dinko Cicvarić iz
tvrtke Ledo d.d. održat će predavanje pod naslovom:
Poslovna inteligencija (Business Intelligence).
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
06. prosinca 2010. u 15 sati u predavaonici 105 PMF-MO, Tomislav Rudec s
Elektrotehničkog fakulteta Sveučilišta u Osijeku održat će predavanje pod
naslovom:
Rješavanje problema k poslužitelja metodom povećavanja toka u mreži (prvi
dio).
Bit će riječi općenito o problemu k poslužitelja i algoritmima za rješavanje
tog problema, posebno o optimalnom offline algoritmu te o online algoritmu
radne funkcije (WFA). Raspravljat će se o implementacijama spomenutih
algoritama koje su zasnovane na traženju maksimalnog toka minimalne cijene
(MCMF)u pogodno konstruiranim mrežama. Umjesto uobičajenog postupka traženja
MCMF metodom smanjivanja cijene predložit će se metoda povećavanja toka.
Objasnit će se motivacija za takav novi pristup, te će se na konkretnim
primjerima demonstrirati njegova uspješnost i brzina.
Robert Manger
Dragi kolege,
Oprostite na ponovnom javljanju, no u prethodnom mailu mi se potkrala
ozbiljna greška.
Dakle: u sklopu poslijediplomskog Seminara za teorijsko računarstvo, u
ponedjeljak 06. prosinca 2010. u 15 sati u predavaonici 105 PMF-MO, Tomislav
Rudec s Elektrotehničkog fakulteta Sveučilišta u Osijeku održat će
predavanje pod naslovom:
Rješavanje problema k poslužitelja metodom smanjivanja cijene toka u mreži
(prvi
dio).
Bit će riječi općenito o problemu k poslužitelja i algoritmima za rješavanje
tog problema, posebno o optimalnom offline algoritmu te o online algoritmu
radne funkcije (WFA). Raspravljat će se o implementacijama spomenutih
algoritama koje su zasnovane na traženju maksimalnog toka minimalne cijene
(MCMF)u pogodno konstruiranim mrežama. Umjesto uobičajenog postupka traženja
MCMF metodom povećavanja toka predložit će se metoda smanjivanja cijene
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
13. prosinca 2010. u 15 sati u predavaonici 105 PMF-MO, Tomislav Rudec s
Elektrotehničkog fakulteta Sveučilišta u Osijeku održat će predavanje pod
naslovom:
Rješavanje problema k poslužitelja metodom smanjivanja cijene toka u mreži
(drugi dio).
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
20. prosinca 2010. u 15 sati u predavaonici 105 PMF-MO, Matko Botinčan
održat će predavanje pod naslovom:
Automatsko dokazivanje svojstava sigurnosti konkurentnih programa s
asinkronim memorijskim operacijama
Sažetak:
U ovom seminaru bit će dan pregled metodologije za automatsko dokazivanje
svojstava sigurnosti konkurentnih programa s asinkronim memorijskim
operacijama. Metodologija je bazirana na varijanti konkurentne logike
separacije za jezik sličan C-u proširen primitivama za višenitno izvođenje
procedura te asinkronih memorijskih operacija. Primjeri takvih operacija su
npr. DMA operacije u IBM Cellu, I/O Acceleration Technology u Intel Xeon
procesorima te asinkrono kopiranje memorije u OpenCL i CUDA platformama.
Abduktivni dokazni sustav omogućava automatsko otkrivanje preduvjeta komandi
jezika, koje uklopljeno u simboličko izvođenje programa vodi k automatskom
otkrivanju preduvjeta i postuvjeta procedura pomoću novog algoritma za
kompozicionalnu interproceduralnu analizu. Pravila izvoda dokaznog sustava
su korektna u smislu da ukoliko program zadovoljava danu (ili otkrivenu)
specifikaciju onda zadovoljava svojstva memorijske sigurnosti, te posebno ne
sadrži uvjete utrke na podacima. Metodologija je implementirana u vidu
eksperimentalnog alata za analizu C programa te validirana na više
paradigmatskih testnih programa.
Robert Manger
Nažalost, moram otkazati predavanje na poslijediplomskom Seminaru za
teorijsko računarstvo koje je bilo najavljeno za danas, dakle za ponedjeljak
20. prosinca 2010. u 15 sati. Predavač Matko Botinčan nije uspio doputovati
u Hrvatsku zbog snijega i prekida zračnog prometa iz Londona. Nadam se da
ćemo čuti Matka uoči Uskrsa ako ne prije.
Lijep pozdrav, Robert Manger.
Robert Manger
Nažalost, moram otkazati današnje predavanje na Seminaru za teorijsko
računarstvo. Predavač se razbolio. Ispričavam se zbog eventualnih
neugodnosti.
Lijep pozdrav, Robert Manger.
Robert Manger
Dragi kolege,
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
24. siječnja 2011. u 15 sati u predavaonici 105 PMF-MO, Konrad Burnik
održat će predavanje pod naslovom:
Randomizirani algoritmi za NP-teške probleme
Sažetak:
NP-teške probleme je teško efikasno riješiti deterministički, stoga se
nadamo da slučajnim odabirom nekih dijelova rješenja možda možemo "pogoditi"
rješenje ili se barem približiti rješenju u polinomijalnom broju koraka.
Ovdje na mogućnost slučajnog biranja(randomizaciju) treba gledati kao na
alternativu nedeterminizmu i najprije ćemo definirati teorijsku osnovu:
pojam randomiziranog
(probabilističkog) Turingovog stroja, tipove randomiziranih algoritama, te
njihovu analizu pomoću teorije vjerojatnosti.
Ukratko ćemo objasniti općenite vjerojatnosne metode i paradigme koje se
koriste za konstrukciju randomiziranih algoritama. Na primjeru problema
ispunjivosti boolovskih formula (SAT) objasnit ćemo uvedene pojmove te
pokazati algoritam koji ima očekivano polinomijalno vrijeme rješavanja za
SAT instance. Vidjet ćemo takodjer na primjeru da se prosječne instance
NP-potpunog problema traženja Hamiltonovog ciklusa u grafu mogu riješiti u
očekivanom broju koraka koji je strogo manji od eksponencijalnog.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
07. veljače 2011. u 15 sati u predavaonici 105 PMF-MO, Konrad Burnik
održat će predavanje pod naslovom:
Randomizirani algoritmi za NP-teške probleme (drugi dio)
Sažetak:
NP-teške probleme je teško efikasno riješiti deterministički, stoga se
nadamo da slučajnim odabirom nekih dijelova rješenja možda možemo "pogoditi"
rješenje ili se barem približiti rješenju u polinomijalnom broju koraka.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo i Seminara za
matematičku logiku, u ponedjeljak 28. veljače 2011. u 15 sati u predavaonici
105 PMF-MO, Goranka Nogo sa svojim studentima Tihomirom Lolićem i Matejem
Mihelčićem održat će predavanje pod naslovom:
Heuristike za rješavanje problema SAT
Sažetak: U okviru predavanja autori će prezentirati dva heuristička
algoritma za rješavanje problema SAT i max-SAT. Prvi algoritam baziran je na
UnitWalk algoritmu. Bit će predstavljeno kombiniranje greedy pristupa s
navedenim algoritmom te poboljšanje dobiveno računanjem 2-rezolventi. U
drugom dijelu predavanja bit će predstavljen algoritam za rješenje problema
max-SAT baziran na SGAV algoritmu. Nakon opisa algoritama, slijede detalji
implementacije te demonstracija na poznatim testnim primjerima.
Pozivaju se svi članovi oba seminara, kao i ostali zainteresirani, da
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
21. ožujka 2011. u 15 sati u predavaonici 105 PMF-MO, Goranka Nogo sa svojim
studentima Nikolom Adzagom i Ivom Dokom održat će predavanje pod naslovom:
"Evolucijski algoritam za rješavanje problema maksimalne klike".
Sažetak: Autori će prikazati heuristički algoritam za traženje najveće klike
(potpunog podgrafa) u proizvoljnom grafu. Algoritam je evolucijski i nastao
je modifikacijom jednog starijeg evolucijskog algoritma, čiji je ključni dio
križanje klika na temelju bipartitnog sparivanja. Nakon detaljnog opisa svih
dijelova algoritma, bit će prezentirani neki dijelovi implementacije. Zatim
slijedi prikaz rezultata testiranja te usporedba originalnog i modificiranog
algoritma na poznatim testnim primjerima.
Robert Manger
Kao prvo ispričavam se zbog kasne obavijesti. U sklopu poslijediplomskog
Seminara za teorijsko računarstvo DANAS u ponedjeljak 28. ožujka 2011. u 15
sati u predavaonici 105 PMF-MO, Goranka Nogo sa svojim studentima Marijanom
Milišić, i Dejanom Peretinom održat će predavanje pod naslovom:
"Problem rasporeda".
Pozivaju se svi članovi seminara, kao i ostali zainteresirani, da
Robert Manger
Danas 4.4.2011. nema Seminara za teorijsko računarstvo, no u istom terminu u
15 sati u predavaonici 105 PMF-MO održava se obrana doktorske disertacije
Tomislava Rudeca s Elektrotehničkog fakulteta u Osijeku. Naslov disertacije
je:
"Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima
u mrežama".
Pozivam sve članove seminara ako ih zanima da prisustvuju ovoj obrani.
Lijep pozdrav, Robert Manger.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
18. travnja 2011. u 15 sati u predavaonici 105 PMF-MO, Goranka Nogo i
njezini studenti Saša Buzov i Petar Paradžik održat će predavanje pod
naslovom:
"Metaheuristički algoritmi za problem nelinearnog programiranja".
Sažetak: U okviru seminara bit će izložena dva metaheuristička algoritma za
problem nelinearnog programiranja. Nakon opisa i analize algoritama, slijedi
prikaz implementacije te rezultati testiranja na standardnom skupu testnih
funkcija.
Pozivaju se svi članovi seminara, kao i ostali zainteresirani, da
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
6. lipnja 2011. u 15 sati u predavaonici 105 PMF-MO, Neva Slani i njezin
student Matej Mihelčić održat će predavanje pod naslovom:
"Automatizirana dedukcija".
Sažetak: Cilj seminara je upoznati slušatelje s osnovnim principima,
metodama i upotrebama automatizirane dedukcije. U uvodnom dijelu seminara
govoriti ćemo o povijesti automatizirane dedukcije i navesti značajnije
činjenice o postignutim rezultatima, razvijenim metodama i algoritmima. U
nastavku detaljnije prezentiramo metode i algoritme koji se koriste kod
automatskih dokazivača (theorem prover) kao što su Davis-Putnam odnosno DPLL
metoda i Stalmarckov algoritam, te isto za tzv. model checkere. Navesti ćemo
i neke njihove primjene. U završnom dijelu vizualizirati ćemo rad DPLL
algoritma te pokazati rad automatskog dokazivača E na konkretnim primjerima.
Pozivaju se svi članovi ovog seminara, kao i ostali zainteresirani, posebno
oni sa Seminara za logiku, da prisustvuju ovom predavanju.
Lijep pozdrav, Robert Manger.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
13. lipnja 2011. u 15 sati u predavaonici 105 PMF-MO, Neva Slani i njezini
studenti Danijel Mandić i Tihomir Lolić održat će predavanje pod naslovom:
"Funkcionalno programiranje".
Sažetak: Na seminaru će biti obrađene osnove funkcionalnog programiranja.
Kao čisti funkcionalni jezik prezentirati će se jezik Haskell, sa osnovama
sintakse i primjerima koda. Od naprednijih tehnika biti će objašnjene monade
i primjeri njihovog korištenja u Haskellu. Za kraj ćemo reći nešto o jeziku
Scala kao spoju objektne i funkcionalne paradigme, rezimirati prednosti i
nedostatke funkcionalnog programiranja te zaključiti s pregledom korištenja
kako funkcionalne paradigme, tako spoja funkcionalne i objektne paradigme u
komercijalnom te akademskom programiranju.
Pozivaju se svi članovi ovog seminara, kao i ostali zainteresirani, da
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
3. listopada 2011. u 15 sati u predavaonici 105 PMF-MO, Slobodan Jelić s
Odjela za matematiku Sveučilišta u Osijeku održat će predavanje pod
naslovom:
"Odnos između povezanog skupovnog pokrivača i problema grupnog Steinerovog
stabla"
Sažetak se nalazi u privitku.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo u ponedjeljak
17. listopada 2011. u 15 sati u predavaonici 104 PMF-MO, dr.sc. Zvonimir
Rakamarić s University of Utah, SAD, održat će predavanje pod naslovom:
"Formal Software Verification: Focus on Concurrency".
Izlaganje će biti na engleskom jeziku. Sažetak predavanja i kratka
biografija predavača nalaze se u nastavku ovog maila.
Pozivaju se svi članovi ovog seminara, kao i ostali zainteresirani, da
prisustvuju ovom predavanju. POSEBNO se pozivaju studenti koji su
zainteresirani za izradu doktorata u području verifikacije softvera na
University of Utah.
Lijep pozdrav, Robert Manger.
--------------------------------------------------
Abstract:
Software is large, complex, and error-prone. The trend in hardware design of
switching to multi-core architectures makes software development even more
complex. Cutting software development costs and ensuring higher reliability
of software is of global interest and a grand challenge. Formal software
verification is an important part of a spectrum of techniques for achieving
that goal.
I will start this lecture by motivating the need for software verification,
in particular for concurrent software verification.
Then, I'll introduce the theory behind a simple software verifier that is
based on a theorem prover, followed by a brief overview of the practical
research I did on checking concurrent systems code. The lecture should
provide you with a basic understanding of what formal software verification
is and why we need it, and it will also give you a flavor of one of my
research contributions in this area.
--------------------------------------------------
Short biography:
Currently, Zvonimir Rakamaric is a postdoctoral fellow at Carnegie Mellon
University in Silicon Valley, where he works closely with researchers from
the Robust Software Engineering Group at NASA Ames Research Center. In the
spring of 2012, Zvonimir will join the School of Computing at the University
of Utah as a tenure-track assistant professor. He received his Ph.D. and
M.Sc. from the Department of Computer Science at the University of British
Columbia, where his supervisor was Alan Hu. Zvonimir completed his
undergraduate studies in Croatia at the University of Zagreb.
The main focus of Zvonimir's research is developing practical methods,
techniques, and tools for improving reliability and correctness of complex
systems. Currently, his emphasis is on highly automatic and scalable
analysis techniques for software, in particular for concurrent software. He
is interested in any technique that supports those goals, such as extended
static checking, automated theorem proving, model checking, and runtime
verification.
Zvonimir was the recipient of a Microsoft Research Graduate Fellowship from
2008-2010. He also won the Silver Medal in the ACM Student Research
Competition at the 32nd International Conference on Software Engineering
(ICSE) 2010 and the Outstanding Student Paper Award at the 13th
International Conference on Tools and Algorithms for the Construction and
Analysis of Systems (TACAS) 2007.
For more information about Zvonimir, visit www.zvonimir.info.
Photo:
http://www.zvonimir.info/wp-content/uploads/2011/03/zvonimir_rakamaric.jpg
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
7. studenog 2011. u 15 sati, predavaonica 104 PMF-MO, Robert Manger će
održati predavanje pod naslovom:
"Novi pristup rješavanju problema k poslužitelja zasnovan na tokovima u
mrežama i smanjivanju cijene toka".
Riječ je o zajedničkom radu s Tomislavom Rudecom sa Sveučilišta u Osijeku.
Sažetak: Rad se bavi s dva algoritma za rješavanje problema k poslužitelja:
optimalni off-line algoritam (OPT) i on-line algoritam radne funkcije (WFA).
Oba algoritma obično se implementiraju pomoću tokova u mrežama uz korištenje
metode povećavanja toka. U radu se predlaže novi pristup koji je opet
zasnovan na tokovima u mrežama ali koristi jednostavnije mreže i metodu
smanjivanja cijene toka. Rad detaljno opisuje odgovarajuće nove
implementacije za OPT odnosno WFA. Daju se svi potrebni dokazi korektnosti.
Također se prikazuju rezultati eksperimenata koji potvrđuju da je nova
implementacija WFA znatno brža od uobičajene.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
14. studenog 2011. u 15 sati, predavaonica 104 PMF-MO, Robert Manger će
održati predavanje pod naslovom:
"Novi pristup rješavanju problema k poslužitelja zasnovan na tokovima u
mrežama i smanjivanju cijene toka" (drugi dio).
Riječ je o nastavku izlaganja o radu koji je nastao u suradnji s Tomislavom
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
21. studenog 2011. u 15 sati, predavaonica 104 PMF-MO, Krunoslav Puljić s
PMF-MO održat će predavanje pod naslovom:
"Usporedba operatora križanja u evolucijskim algoritmima za problem
usmjeravanja vozila".
Sažetak: Rad se bavi evolucijskim algoritmima za rješavanje problema
usmjeravanja vozila (vehicle routing problem - VRP). Točnije, rad proučava
neke operatore križanja koji su izvorno bili oblikovani za problem
trgovačkog putnika (traveling salesman problem - TSP) no također se mogu
koristiti i za VRP. Razmatrana križanja testiraju se na skupu poznatih
"benchmark" primjeraka VRP. Dobiveni eksperimentalni rezultati jasno
pokazuju da je ponašanje operatora u kontekstu VRP sasvim drukčije nego za
TSP.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
23. siječnja 2012. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo s PMF-MO
i njeni studenti Mario Berljafa, Ilija Gavran i Saša Stanko održat će
predavanje pod naslovom:
"Objedinjeni pristupi za rješavanje problema particioniranja grafa".
Sažetak: U uvodnom dijelu seminara bit će opisan problem particioniranja
grafa te njegove najčešće modifikacije. Potom će biti izložena tri pristupa
koja su korištena za rješavanje problema - višerazinski (multilevel)
pristup, spektralno i BFS particioniranje te evolucijski pristup. Navedeni
načini rješavanja su objedinjeni u algoritam koji koristi prednosti svakog
od njih. Rezultati dobiveni testiranjem tako dobivenog algoritma na
standardnim testnim primjerima bit će uspoređeni s do sada najboljim
poznatim rezultatima.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
20. veljače 2012. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo s PMF-MO
i njeni studenti Marko Božić i Ivan Gavran održat će predavanje pod
naslovom:
"Računalno potpomognuta mamografija - određivanje veličine žljezdanog
tkiva".
Sažetak: Posljednjih godina razvijaju se računalni programi kojima je
zadatak asistirati liječniku pri otkrivanju struktura koje ukazuju na rizik
od raka. Njihov je važan dio određivanje gustoće tj. veličine žljezdanog
tkiva u dojki. Na seminaru će biti prezentiran pokušaj rješenja tog problema
u čijoj osnovi je algoritam postupnog širenja žljezdanog područja, tzv.
regiongrowing. Najtvrđi problem je automatska ocjena kvalitete pronađenog
žljezdanog tkiva za dane parametre regiongrowinga. Za optimiziranje
parametara korišten je algoritam roja čestica. Nakon izloženog problema,
opisa metode i korištenih postupaka, dobiveni rezultati bit će uspoređeni s
rezultatima drugih istraživača na ovom području.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
27. veljače 2012. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo s PMF-MO
i njeni studenti Sven Majerić i Ivo Matijašević:održat će predavanje pod
naslovom:
"Društveno-hijerarhijska meta-heuristika za nalaženje maksimalnog reza u
težinskom grafu".
Sažetak: Na seminaru će biti izložen algoritam Hierarchical Social
Metaheuristic (HSM) za pronalaženje maksimalnog reza u težinskom grafu. U
uvodnom dijelu seminara bit će definiran problem te u kratkim crticama
opisane povijest i priroda problema. Zatim će ukratko biti opisani algoritam
GRASP i memetički algoritam, a nakon toga detaljno objašnjen HSM. Slijede
detalji implementacije HSM-a u C#-u i C++-u te analiza dobivenih rezultata i
njihova usporedba s najboljim, do sada poznatim, rezultatima.
Robert Manger
Dragi kolege,
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
05. ožujka 2012. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo s PMF-MO i
njezini studenti Sara Dadić, Lovro Rožić i Ivan Stojić održat će predavanje
pod naslovom:
"Genetski algoritam s otočnim pristupom za heterogeni problem raspoređivanja
poslova".
Sažetak: Heterogeni problem raspoređivanja poslova bavi se raspoređivanjem
poslova na strojeve, pri čemu su vremena izvršavanja pojedinih poslova
različita za svaki stroj. Poznato je da je problem NP-težak (generalizacija
je dva NP-teška problema - homogenog raspoređivanja i raspoređivanja na dva
stroja) pa se stoga ne rješava egzaktnim algoritmima, već se traži
aproksimativno rješenje. U seminaru se izlaže genetski algoritam s otočnim
pristupom za dobivanje rješenja te uspoređuje taj pristup s rezultatima
različitih srodnih metoda predstavljenih u nekoliko znanstvenih članaka.
Također, prezentira se algoritam implementiran u C++, s grafičkim sučeljem
realiziranim pomoću GTK biblioteke. Prilikom testiranja korištene su
instance problema koje koriste i autori spomenutih članaka. Analiziran je
utjecaj različitih parametara algoritma na konačni rezultat izvršavanja
(veličina i broj populacija, učestalost mutacija, broj točaka
rekombinacije...)te su uočeni faktori koji utječu na brzinu izvođenja
programa (tzv. "uska grla").
Robert Manger
Ovotjedni Seminar za teorijsko računarstvo nažalost nije bio održan zbog
spriječenosti jednog od (brojnih) predavača. Ispričavam se ako je to bilo
kome stvorilo bilo kakve neugodnosti. No isti seminar održat će se idući
tjedan. Dakle, nova obavijest glasi:
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
12. ožujka 2012. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo s PMF-MO i
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
23. travnja 2012. u 15 sati, predavaonica 104 PMF-MO, Tomislav Rudec s
Elektrotehničkog fakulteta Sveučilišta u Osijeku održat će predavanje pod
naslovom:
"Brza približna implementacija algoritma radne funkcije za rješavanje
problema k poslužitelja".
Sažetak: U radu se predlaže približna implementacija algoritma radne
funkcije (work function algoritam - WFA) za rješavanje on-line problema k
poslužitelja. Implementacija je zasnovana na originalnom mrežnom modelu,
računanju tokova u mreži i metodi reduciranja cijene toka. Biranjem
vrijednosti odgovarajućeg parametra implementacija se može podešavati tako
da postigne željeni odnos točnosti i brzine računanja. U radu se prikazuju
rezultati eksperimenata koji pokazuju da nova implementacija uz pogodno
odabranu vrijednost parametra savršeno oponaša originalni WFA, a pritom je
barem za red veličine brža od bilo koje do sada poznate egzaktne
implementacije WFA.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
student Aleksandar Milković održat će predavanje pod naslovom:
" Računalno provjereni dokaz Teorema četiri boje".
Sažetak: Kroz ovaj seminar upoznati ćemo se sa problemom Teorema četiri
boje, te idejom dokaza koja slijedi originalan pokušaj od Kempea, ali je
vremenom nadopunjena. Definirati ćemo potrebne matematičke pojmove,
definicije i rezultate koji su Gonthieru biti potrebni pri dokazu u Coq-u.
Posebnu pažnju posvetiti ćemo načinu dokazivanja na koji je problem riješen,
te objasniti sve ideje vezane uz njegovu formalizaciju.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo, u ponedjeljak
Sadržaj: Kolmogorovljeva složenost kao mjera kompresibilnosti niza.
Predviđanje nizova klađenjem na bitove. Nizovi koji su kompresibilni, a nisu
predvidivi.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
19. studenog 2012. u 15 sati, predavaonica 104 PMF-MO, Robert Manger i
Krunoslav Puljić održat će predavanje pod naslovom:
"Nova usporedba operatora križanja u evolucijskim algoritmima za problem
Sažetak: Rad se bavi evolucijskim algoritmima za rješavanje problema
izvorno bili oblikovani za problem trgovačkog putnika (TSP), no mogu se
koristiti i za VRP. Ta križanja testiraju se na skupu dobro poznatih
"benchmark" primjeraka VRP. Cilj ispitivanja je provjeriti podobnost
razmatranih križanja za VRP, utvrditi njihov relativni poredak u smislu
kvalitete rješavanja VRP, te vidjeti je li taj poredak drukčiji nego za TSP.
Robert Manger
Kolega Cicvarić,
Nažalost pomicanje termina seminara gotovo je nemoguće izvesti zbog zauzetosti svih dvorana. Također, ponedjeljkom od 5h održava se seminar za matematičku logiku, pa nije zgodno da se ta dva seminara koji imaju neprazan presjek publike održavaju u isto vrijeme. Dešavat će se da ćemo imati zajedničke sjednice oba seminara – tada ćemo koristiti kasniji termin koji vama više odgovara. No naš osnovni termin mora ostati isti.
Lijep pozdrav, Robert Manger.
From: Dinko Cicvarić [mailto:dinko.c...@gmail.com]
Sent: 13. studenog 2012. 13:43
To: Robert Manger
Cc: seminar-za-teori...@googlegroups.com; lista...@math.hr; Marko Špoljarec
Subject: Re: Seminar za teorijsko racunarstvo 19.11.2012.
Pozdrav svima,
postoji li mogućnost da se termin seminara pomakne na kasnije (idealno bi bilo pola 5)? Ja radim do 4 i ne mogu izlaziti ranije kako bih stigao na seminar.
Lp,
Dinko
2012/11/13 Robert Manger <man...@math.hr>
--
Dinko Cicvarić
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo i Seminara za
matematičku logiku, u ponedjeljak 26. studenog 2012. u 17 sati (DA IZNIMNO U
17 SATI), predavaonica 104 PMF-MO, Ružica Piskač (Max Planck institut,
Saarbrücken), održat će predavanje pod naslovom:
"Software Synthesis using Automated Reasoning".
Sažetak:
Software synthesis is a technique for automatically generating code from a
given specification. The goal of software synthesis is to make software
development easier, while increasing both the productivity of the programmer
and the correctness of the produced code. In this talk I will present an
approach to synthesis that relies on the use of automated reasoning and
decision procedures. First I will describe how to generalize decision
procedures into predictable and complete synthesis procedures. Here
completeness means that the procedure is guaranteed to find code that
satisfies the given specification. I will illustrate the process of turning
a decision procedure into a synthesis procedure using linear integer
arithmetic as an example. This approach is implemented in Comfusy. Comfusy
is an extension to the Scala compiler and a tool for complete functional
synthesis. It accepts as an input expressions with input and output
variables and outputs code that computes output values as a function of
input values. In addition, it also outputs the preconditions that the input
variables have to satisfy in order for a solution to exist. Next I will
outline a synthesis procedure for specifications given in the form of type
constraints. The procedure derives code snippets that use given library
functions. The procedure takes into account polymorphic type constraints as
well as code behavior. We implemented this approach in a tool called
Insynth. To help developers in composing functionality from existing
libraries and from the user defined values, InSynth synthesizes and suggests
valid expressions of a given type at a given program point.
Robert Manger
U ponedjeljak 17. prosinca 2012. u 17 sati (SEDAMNAEST SATI!) u predavaonici
104 PMF-MO održat će se zajednički sastanak poslijediplomskih Seminara za
teorijsko računarstvo i Seminara za matematičku logiku. Predavač je Domagoj
Vrgoč koji je trenutno na doktorskom studiju računarstva u Edinburghu.
Naslov predavanja je: "Querying Graph Databases with XPath".
Sažetak: XPath plays a prominent role as an XML navigational language due to
several factors, including its ability to express queries of interest, its
close connection to yardstick database query languages (e.g., first-order
logic), and the low complexity of query evaluation for many fragments.
Another common database model-graph databases-also requires a heavy use of
navigation in queries; yet it largely adopts a different approach to
querying, relying on reachability patterns expressed with regular
constraints. Our goal here is to investigate the behavior and applicability
of XPath-like languages for querying graph databases, concentrating on their
expressiveness and complexity of query evaluation. We are particularly
interested in a model of graph data that combines navigation through graphs
with querying data held in the nodes, such as, for example, in a social
network scenario. As navigational languages, we use analogs of core and
regular XPath and augment them with various tests on data values. We relate
these languages to first-order logic, its transitive closure extensions, and
finite variable fragments thereof, proving several capture results. In
addition, we describe their relative expressive power. We then show that
they behave very well computationally: they have a low-degree polynomial
combined complexity, which becomes linear for several fragments.
Furthermore, we introduce new types of tests for XPath languages that let
them capture first-order logic with data comparisons and prove that the low
complexity bounds continue to apply to such extended languages.
Pozivaju se svi članovi oba seminara kao i ostali zainteresirani da
Robert Manger
U srijedu 19. prosinca 2012. u 18 sati (OSAMNAEST SATI!) u predavaonici 002
PMF-MO održat će se još jedan zajednički sastanak poslijediplomskih Seminara
za teorijsko računarstvo i Seminara za matematičku logiku. Predavač je Matko
Botinčan (Programming, Logic, and Semantics Group, University of Cambridge
Computer Laboratory).
Naslov predavanja je: "Formal verification-driven concurrent program
synthesis".
Sažetak: As industry shifted its focus towards multicores and manycores,
concurrent programming became not merely an option, but a daunting necessity
to utilise the available processing power. In many cases concurrency is an
optimization, rather than intrinsic to the functional behavior of a program.
That is, a concurrent program is often intended to achieve the same effect
of a simpler sequential counterpart, but faster. Error-free concurrent
programming remains a tricky problem, beyond the capabilities of most
programmers; consequently, an attractive alternative to manually writing a
concurrent program is to automatically synthesise one. I will present two
methods that are aimed at synthesising concurrent programs by using rigorous
mathematical, formal analysis and verification techniques. The first one
<http://www.cl.cam.ac.uk/~mb741/papers/popl12.pdf> uses a program proof
written in separation logic to discover fine-grained dependency patterns
between different parts of the program, and guide the synchronization
synthesis. The second one <http://www.cl.cam.ac.uk/~mb741/papers/popl13.pdf>
uses symbolic model checking and grammatical inference to infer a faithful
behavioural specification that can be easily parallelised. I will discuss
few practical applications of both methods and future research directions.
Pozivaju se svi članovi oba seminara kao i ostali zainteresirani da
Dinko Cicvarić
na žalost, zbog zdravstvenih razloga, danas neću biti u mogućnosti doći na seminar.
lp,
dinko
--
Lista Seminara za teorijsko računarstvo:
http://groups.google.com/group/seminar-za-teorijsko-racunarstvo?hl=en
--
Dinko Cicvarić
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Marija Idžojtić održat će predavanje pod naslovom:
"Paralelni genetski algoritam za problem trgovačkog putnika - metoda
MapReduce".
Sažetak: U seminaru se promatra simetrični euklidski problem trgovačkog
putnika. Metodom MapReduce paralelizira se genetski algoritam kojim se
rješava navedeni problem. Funkcija Map izvodi evaluaciju jedinki; poziva se
onoliko puta koliko ima jedinki u svim subpopulacijama. Funkcija Reduce
izvodi selekciju, križanje i mutaciju jedinki u jednoj subpopulaciji; broj
poziva jednak je broju subpopulacija. Ispituju se brzina konvergencije i
kvaliteta rješenja s obzirom na broj i veličinu subpopulacija te utjecaj
različitih operatora migracije, broja migriranih jedinki i dužine intervala
migracije.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
"Paralelni genetski algoritam za problem trgovačkog putnika - metoda
MapReduce".
ponedjeljak, no bilo je otkazano zbog bolesti predavačice.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Brodarić i Josip Matijević održat će predavanje pod naslovom:
"Kapacitivni problem usmjeravanja vozila".
Sažetak: U seminaru se promatra kapacitivni problem usmjeravanja vozila.
Problem se rješava primjenom modifikacije mravljeg algoritma. Unutar svake
iteracije, svaki mrav konstruira jedno rješenje. Sljedeći grad u svom
rješenju mrav bira na jedan od tri načina, koji se u samom seminaru
detaljnije opisuju. Koristi se i lokalno pretraživanje. Ažuriranje
feromonskih tragova odvija se nakon što svaki mrav konstruira svoje rješenje
te nakon svake iteracije. Algoritam se testira na dva skupa testnih primjera
koji se razlikuju po načinu raspodjele gradova. Testira se utjecaj pojedinih
parametara algoritma na kvalitetu rješenja. Analiziraju se dobiveni
rezultati i donose se zaključci o primjenjivosti algoritma na zadani
problem.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Ševo i Miloš Trifunović održat će predavanje pod naslovom:
"Genetski algoritam za igru Sudoku".
Sažetak: U seminaru se izlaže genetski algoritam za rješavanje poznate i
zanimljive puzzle igre "Sudoku". Rješenje je implementirano prema
modifikaciji genetskog algoritma poznatoj pod nazivom "Retrievable Genetic
Algorithm"
(http://www.cse.psu.edu/~sub194/papers/sudokuTechReport.pdf).Program je
testiran na laganim, srednje teškim i teškim testnim primjerima preuzetim s
internetske adrese http://www.talktalk.co.uk/games/play/sudoku/index.html.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Grbić i Hermina Petric Maretić održat će predavanje pod naslovom:
"Problem upotpunjenja grafa do Hamiltonovog".
Sažetak: U seminaru se promatra problem upotpunjenja grafa. Za neusmjereni,
bestežinski graf G potrebno je pronaći minimalni broj bridova koji se
trebaju dodati u graf G kako bi on postao Hamiltonov, tj. kako bi postojao
Hamiltonov ciklus u grafu G. Problem je rješavan genetskim, imunološkim i
mravljim algoritmom te njihovim modificiranim varijantama. Algoritmi su
testirani za grafove u kojima je vjerojatnost pojavljivanja svakog brida
recipročna broju vrhova. Promatrana je brzina konvergencije rješenja te je
dana usporedba dobivenih rezultata.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Čabraja, Anamarija Fofonjka i Andrija Štajduhar održat će predavanje pod
naslovom:
"Metaheuristički pristup rješavanju problema 3-SAT".
Sažetak: U seminaru se izlažu načini kombiniranja i prilagođavanja
različitih genetskih algoritama za rješavanje problema 3-SAT. Za
pojednostavljivanje formule korištena je metoda rezolucije. Analiziraju se
rezultati dobiveni testiranjem sekvencijalne i paralelne implementacije
algoritama.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Krajina održat će predavanje pod naslovom:
"Modificirani mravlji algoritam za rješavanje problema minimalnog
Steinerovog stabla u grafovima na grafičkim procesnim jedinicama".
Sažetak: Problem minimalnog Steinerovog stabla u grafovima možemo
formulirati na sljedeći način: za neprazan podskup vrhova danog težinskog
grafa, cilj nam je pronaći podgraf minimalne težine koji ga razapinje. S
obzirom da je problem NP-potpun, za rješavanje se koriste razne heurističke
i metaheurističke metode. Mravlji algoritam se pokazao kao uspješan
metaheuristički pristup za aproksimiranje rješenja ovog problema, no samo
generiranje kandidata se u suštini oslanja na pretraživanje u dubinu -
problem koji je vrlo teško paralelizabilan, a s time i nepogodan za
implementaciju na grafičkim procesnim jedinicama. U ovom seminaru bit će
opisana modifikacija mravljeg algoritma u kojoj mravi,umjesto na bridovima,
feromonske tragove ostavljaju na čvorovima grafa, te kao kandidat za
rješenje daju minimalno razapinjajuće stablo induciranog podgrafa. Osim
samog algoritma, bit će opisana i implementacija na grafičkim procesnim
jedinicama pomoću biblioteke Thrust, te prodiskutirana brzina generiranja
rješenja i njihova kvaliteta u usporedbi s nekim drugim implementacijama
mravljeg algoritma.
Robert Manger
U sklopu poslijediplomskih Seminara za teorijsko računarstvo i Seminara za
vjerojatnost, u ponedjeljak 20. svibnja 2013. u 15 sati, predavaonica 104
PMF-MO, Ivo Ugrina održat će predavanje pod naslovom:
"Hijerarhijska analiza svojstava nizova znakova metodama znanstvenog
računanja i statistike".
Sažetak: U prvom dijelu prezentira se rezultat o distribuciji broja
palindroma fiksne duljine u nizu znakova. Palindrom definiramo kao niz
znakova koji je jednak komplementarnom nizu znakova pročitanom od suprotne
strane. Komplementarnost definiramo kao neku relaciju među znakovima (npr. u
DNA nizovima komplementarnost je definirana relacijom C~G, A~T). Prikazani
su uvjeti pod kojima se aproksimacija Normalnom distribucijom može
koristiti.
U drugom dijelu prezentira se metoda izvlačenja semantički ispravnih
poštanskih adresa s hrvatskih Internet stranica. Semantički ispravnim
poštanskim adresama smatramo one koje je autor imao namjeru napisati te nisu
produkt slučajnog rasporeda riječi. Metoda koristi metriku sličnosti među
riječima izvedenu iz modela Skrivenih Markovljevih lanaca te stabla
odlučivanja kao algoritam učenja. Za početnu pretragu gradova i ulica
koristi se baza poštanskih adresa.
U trećem dijelu promatra se problem semantičke analize slobodnog teksta na
Internetu kao hipergrafa u kojem su dokumenti čvorovi.
Pozivaju se svi članovi oba seminara kao i ostali zainteresirani da
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
će predavanje pod naslovom:
"Poboljšana implementacija algoritma radne funkcije zasnovana na tokovima u
mrežama, smanjivanju cijene toka i kratkim negativnim ciklusima".
Sažetak: Izložit će se rad koji je nastao u koautorstvu s Tomislavom Rudecom
sa Sveučilišta u Osijeku. Opisat će se približna implementacija algoritma
radne funkcije (WFA) za rješavanje problema k poslužitelja. Implementacija
je zasnovana na novom modelu toka u mreži i smanjivanju cijene toka.
Također, implementacija je opskrbljena parametrom koji omogućuje
balansiranje (kompromis) između točnosti i brzine. Prikazat će se rezultati
eksperimenata koji pokazuju da nova implementacija može savršeno oponašati
originalni WFA i pritom raditi barem za jedan red veličine brže nego bilo
koja poznata egzaktna implementacija.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Čakmak, Nacionalni CERT, održat će predavanje pod naslovom:
"Računalna sigurnost na Internetu u Republici Hrvatskoj".
Sažetak: Predavanje će obuhvatiti trenutno stanje računalne sigurnosti u
Republici Hrvatskoj, uočene trendove u računalno sigurnosnim incidentima te
metode koje Nacionalni CERT koristi kako bi se situacija poboljšala.
Predavanje uključuje prezentiranje tehnika kojima su se napadači koristili u
napadima i pregled metoda obrane od napada.
Robert Manger
Nažalost moram otkazati predavanje pod naslovom "Računalna sigurnost na
Internetu u Republici Hrvatskoj" koje se trebalo održati u sklopu
poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak 18.
studenog 2013. u 15 sati. Razlog otkazivanja je iznenadna spriječenost
predavača (odlazak na hitni službeni put). Javit ću vam novi termin ako ga
bude.
Uz isprike, lijep pozdrav, Robert Manger.
Dinko Cicvarić
--
Lista Seminara za teorijsko računarstvo:
http://groups.google.com/group/seminar-za-teorijsko-racunarstvo?hl=en
---
Ovu ste poruku primili jer ste pretplaćeni na grupu "Seminar za teorijsko računarstvo" kao jednu od Google Grupa.
Da biste poništili pretplatu na tu grupu i prestali primati e-poruke s nje, pošaljite e-poruku na seminar-za-teorijsko-r...@googlegroups.com.
Dodatne opcije potražite na adresi https://groups.google.com/groups/opt_out.
--
Dinko Cicvarić
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
će predavanje pod naslovom:
"Korekurzivna prebrojivost i izračunljivost u euklidskom prostoru".
Sažetak: Navodimo osnovne definicije teorije izračunljive analize u
euklidskom prostoru R^n. Posebno uvodimo pojam izračunljive funkcije R^n ->
R, te slabo izračunljivog zatvorenog podskupa u R^n kao skupa nultočaka
takve funkcije. Traženje rekurzivnih nultočaka izračunljive funkcije je
motivacija za proučavanje slabo izračunljivih skupova. Pokazuje se da je
slaba izračunljivost ekvivalentna korekurzivnoj prebrojivosti. Skup je
korekurzivno prebrojiv ako se njegov komplement može efektivno prekriti
otvorenim kuglama. Skup S u R^n je izračunljiv ako je funkcija udaljenosti
x->d(x,S) izračunljiva. Uvedeni pojmovi predstavljaju poopćenje klasičnih
definicija u teoriji izračunljivosti nad prirodnim brojevima. Na
jednostavnim primjerima ćemo objasniti uvedene pojmove. Posebno, bavimo se
pitanjem pod kojim topološkim uvjetima je korekurzivno prebrojiv skup u
euklidskom prostoru izračunljiv.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo, u ponedjeljak
Cicvarić održat će predavanje pod naslovom:
"BI alati za krajnjeg korisnika".
Sažetak: Opisat će se tipovi i primjeri takozvanih "Business Intelligence"
alata (BI), dakle softverskih alata za analizu podataka u poslovanju.
Raspravljat će se o upotrebljivosti istih u stvarnome životu. Govorit će se
o aspektima BI koji su važni sa stanovišta informatike: priprema i
skladištenje podataka, održavanje baza podataka i ETL-a, priprema i
održavanje BI alata, edukacija krajnjih korisnika BI alata. Pokrit će se i
aspekti zanimljivi sa stanovišta poslovanja: izvještavanje, analitika,
predviđanje događaja, kvaliteta podataka, održavanje i razvoj poslovnih
procesa.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
je to uobičajeno.
Lijep pozdrav, Robert Manger.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo te Seminara za
matematičku logiku i osnove matematike, u četvrtak 19. prosinca 2013 u 17
sati, predavaonica 105 PMF-MO, Hannes Mehnert sa Sveučilišta u Kopenhagenu
Sažetak: In this talk the functional correctness of a solution to the point
location problem will be verified. The point location problem is of
geometric nature: in a plane, which is divided into disjoint polygonal
regions, find the smallest region which contains a queried point. Several
solutions have space complexity linear in the number of edges that form the
regions and provide a logarithmic query time also in the number of edges.
The speaker will describe implementation and outline a functional
correctness proof of one solution which meets these time and space
complexity by using shared mutable state. He will use a snapshotable tree
data structure, which is formally verified in his previous work, to achieve
the correctness proof of the planar point algorithm. A higher-order
separation logic will be used for verification of its correctness, which
will be explained in detail in this talk.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
Robert Manger
Nažalost moram otkazati predavanje na poslijediplomskom Seminaru za
teorijsko računarstvo koje se trebalo održati u četvrtak 19. prosinca 2013 u
17 sati. Predavač se razbolio pa nije uspio doći u Zagreb. Koristim priliku
da svima čestitam Božić te da zaželim više sreće našem seminaru u Novoj
godini.
Lijep pozdrav uz isprike, Robert Manger.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo te Seminara za
sati, predavaonica 109 PMF-MO, Domagoj Vrgoč s University of Edinburgh
Sažetak: U seminaru ćemo dati kratak pregled različitih metoda teorije
automata i regularnih izraza za definiranje jezika nad beskonačnim
alfabetima. Uz osnovne teoreme teorije konačnih jezika također ćemo
razmotriti i kako se ovi formalizmi mogu primijeniti za pretraživanje baza
podataka zasnovanih na modelu grafa.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
13. siječnja 2014 u 15 sati, predavaonica 104 PMF-MO, Bruno Brodarić održat
će predavanje pod naslovom:
"Meta-heuristički pristup traženju minimalnog Steinerovog stabla u
euklidskoj ravnini".
Sažetak: U seminaru se promatra problem traženja minimalnog Steinerovog
stabla u euklidskoj ravnini. Definiraju se pojmovi iz teorije grafova i
teorije složenosti potrebni za rješavanje problema i navodi se da je problem
NP-težak. Problem se rješava primjenom prilagođene verzije genetskog
algoritma. Svako moguće rješenje problema predstavlja jednu jedinku unutar
populacije genetskog algoritma, a u svakoj iteraciji algoritma formira se
nova populacija jedinki. Pritom se koristi i lokalno pretraživanje, za koje
nam služe tri različita operatora, koji se u samom seminaru detaljnije
opisuju. Algoritam se testira na poznatim testnim primjercima. Testira se i
utjecaj pojedinih parametara na kvalitetu rješenja. Analiziraju se dobiveni
problem.
ovom predavanju.
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
predavanje pod naslovom:
"Predviđanje vremenskih serija multivarijatnim metaučenjem".
Sažetak: : Multivarijatno metaučenje je način izbora modela za regresiju
vremenskih serija pomoću kojeg se može iskoristiti informacije o uspješnosti
regresije na naoko nepovezivim problemima predviđanja vremenskih serija.
Može se koristiti kod izbora optimalnog algoritma za nepoznate probleme i za
smanjenje pogreške predviđanja pretragom gušćeg prostora algoritama.
Primjeri će biti poglavito iz područja predviđanja potrošnje električne
energije.
O autoru: Dr.sc. Marin Matijaš voditelj je prodaje krajnjim kupcima u Petrol
d.o.o. gdje se bavi razvojem poslovanja na tržištu električne energije u
Hrvatskoj i analizom tržišta električne energije u srednjoj i jugoistočnoj
Europi.
Robert Manger
Na zajedničkom sastanku poslijediplomskog Seminara za matematičko
programiranje i teoriju igara te poslijediplomskog Seminara za teorijsko
računarstvo, u četvrtak 13. ožujka 2014 u 12 sati, dvorana 34 na Ekonomskom
fakultetu Sveučilišta u Zagrebu, Mario Bambulović održat će predavanje pod
naslovom:
"Nelinearni problemi ruksaka".
Sažetak: Cilj ovog seminara je izvesti efikasne algoritme za rješavanje
problema cjelobrojnog programiranja, konkretno za klasu cjelobrojnih
nelinearnih problema ruksaka (NPR). Pri tome ćemo uvesti neke osnovne
pojmove i iskazali teorijske rezultate potrebne za implementaciju efikasnih
algoritama. Također ćemo uvesti pojmove parcijalne i potpune enumeracije kao
i pojmove pridruženih relaksiranih problema te iskazati neka njihova
svojstva. Osim toga, izvest ćemo neke efikasne algoritme za njihovo
rješavanje. Na kraju ćemo prikazati metodu 0-1 linearizacije za konveksne
probleme ruksaka i navesti neke od primjera problema iz svakodnevice koje
možemo modelirati kao probleme (NPR).
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
Ruđer Bošković održat će predavanje pod naslovom:
"Vjerojatnosne formulacije nenegativne matrične faktorizacije".
Sažetak: Jedna od prednosti korištenja formulacija nenegativne matrične
faktorizacije (NMF) kao vjerojatnosnih grafičkih modela je neposredna
primjena dobro razvijenih metoda za vjerojatnosno učenje (ML, MAP, EM -
Bayesianske i ne-Bayesianske metode) kako bi se dobili algoritmi za NMF
dekompoziciju. Vjerojatnosni grafički modeli također omogućuju ugrađivanje
bogatijeg a-priori znanja u model kako bi se dobile prikladnije,
aplikacijski specifične dekompozicije. S te perspektive, standardne
divergencije korištene u nenegativnoj matričnoj faktorizaciji (NMF)
baziranoj na divergencijama dobivaju vjerojatnosnu interpretaciju. Kao
vježba u vjerojatnosnom učenju, inačice algoritama za NMF dekompoziciju bit
će izvedene na konkretnom NMF modelu.
Robert Manger
Na zajedničkom sastanku poslijediplomskog Seminara za matematičku logiku i
osnove matematike te Seminara za teorijsko računarstvo u ponedjeljak 14.
travnja 2014 u 17 sati, predavaonica 104 PMF-MO, Filip Nikšić s Max Planck
Institute for Software Systems održat će predavanje pod naslovom:
"Parikhov teorem, semilinearni skupovi i Presburgerova aritmetika".
Sažetak: Tokom šezdesetih godina prošloga stoljeća otkrivena je poveznica
između kontekstno-slobodnih jezika i Presburgerove aritmetike. S jedne
strane, ako u pojedinoj riječi kontekstno-slobodnog jezika pogledamo samo
broj pojavljivanja terminalnih simbola zanemarujući njihov poredak, odnosno
ako pogledamo Parikhovu sliku kontekstno-slobodnog jezika, dobit ćemo
semilinearan skup. To je sadržaj Parikhovog teorema. S druge strane,
semilinearni skupovi su točno skupovi definabilni formulama Presburgerove
aritmetike, što su dokazali Ginsburg i Spanier. Kombinirajući ta dva
rezultata, svakom kontekstno-slobodnom jeziku možemo pridružiti
Presburgerovu formulu koja opisuje njegovu Parikhovu sliku. Zanimljivo je da
se linearna i relativno jednostavna konstrukcija Presburgerove formule iz
gramatike kontekstno-slobodnog jezika pojavila tek 2005.
Pozivaju se svi članovi Seminara za teorijsko računarstvo kao i ostali
Robert Manger
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u srijedu 23.
travnja 2014 u 17 sati, predavaonica 002 PMF-MO, Robert Manger održat će
predavanje pod naslovom:
"Robusna optimizacija, s naglaskom na robusnu diskretnu optimizaciju".
Sažetak: Robusna optimizacija predstavlja jedan način izlaženja na kraj s
neizvjesnošću u pogledu vrijednosti parametara u optimizacijskom problemu.
Promatraju se razni "scenariji" te se bira rješenje čije "najgore ponašanje"
(gledano na skupu svih scenarija) je "najbolje moguće". U ovom predavanju
proučavamo robusne varijante nekih klasičnih problema diskretne
optimizacije: najkraći putovi u grafu, minimalna razapinjuća stabla, problem
ranca. Pokazujemo da se uvođenjem robusnosti bitno mijenja vremenska
složenost. Npr. problem koji je u osnovnoj varijanti bio rješiv u
polinomijalnom vremenu može u robusnoj varijanti postati NP-težak.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju
održavanja drukčiji nego inače.
Lijep pozdrav, Robert Manger.