Seminar za teorijsko računarstvo
U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
26. ožujka 2018. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo te njezini
studenti Alen Andrašek, Dajana Jerončić i Paula Vujasić održat će
predavanje pod naslovom:
"Problem sortiranja palačinki".
Sažetak: Problem sortiranja palačinki (eng. pancake sorting) je problem
sortiranja zadane permutacije koristeći samo okretaje prvih k članova
permutacije. Naziv problema dolazi od vizualne analogije s problemom
sortiranja palačinki spatulom. 2011. godine dokazano je da je problem
NP-težak. Na predavanju se izlaže rješenje dobiveno primjenom dviju
meta-heuristika - to su hill-climbing i pčelinji algoritam. Korištena
varijanta pčelinjeg algoritma posebno je prilagođena diskretnoj prirodi
problema. Uspoređuju dobiveni rezultati s onima dobivenim od strane Tomasa
Rokickog, pobjednika programskog natjecanja za pancake sorting. Kao testni
primjeri korišteni su testni primjeri iz spomenutog natjecanja.
Pozivaju se svi članovi Seminara kao i ostali zainteresirani da prisustvuju
ovom predavanju. Provjera algoritama na stvarnim palačinkama nije predviđena
:)
Robert Manger