Jedná se o témata z oblasti teorie algoritmů, zejména jde o online algoritmy a algoritmy pro rozvrhování. Všechna uvedená témata jsou teoretická, případně s poměrně malým prostorem pro počítačové experimenty apod. Jsou tedy vhodná jako obtížnější témata diplomových prací nebo jako témata pro doktorandské studium. Popisy jsou poměrně všeobecné, některé již nejsou aktuální, před případným zapsáním tématu je třeba se osobně domluvit a upřesnit je dle zájmu.
1. Teorie her a online algoritmy
Velmi aktuální a široké téma v současném světovém výzkumu je
studium systémů, kde jednotliví hráči optimalizují svůj okamžitý zisk
bez ohledu na celkové, tzv. sociální, optimum, obdobně jako v
mnoha partiích klasické teorie her. V této oblasti vzniká i řada
zajímavých algoritmických otázek. Studuje se například vztah ekvilibria
(tj. výsledku dosažitelného sobeckými strategiemi) a sociálního optima,
nebo se navrhují mechanismy (pro různé aukce apod.), jak dosáhnout
toho, aby byli hráči motivováni přiblížit se sociálnímu optimu. Tyto
jevy se studují na mnoha konrétních příkladech, jako např. směrování v
sítích, rozvrhování, finanční problémy. Široké téma s možnostmi jak pro
doktorskou tak diplomovou
práci.
2. Online algoritmy pro komunikační sítě
V řadě aktuálních článků se studují online algoritmy pro buffery v
komunikačních sítích. Cílem je navrhnout algoritmy tak, aby vždy
přijaly a zpracovaly co nejvíce úloh (packetů), srovnatelně s
optimálním řešením. Pro případy jednotlivých bufferů jsou známy
dobré algoritmy v různých situacích, viz. např. články zadavatele pro obecný případ, pravděpodobnostní algoritmus a různé
speciální případy. Velmi málo je však známo pro sítě s více
buffery. Široké téma s možnostmi jak pro doktorskou tak diplomovou
práci.
3. Rozvrhování v přetížených systémech
V této variantě rozvrhování je třeba rozvrhnout co nejvíce postupně
přicházejících úloh v daném časovém intervalu. Jsou známy netriviální
výsledky v případě jednoho počítače a identických úloh, viz článek zadavatele.
Zajímavé by bylo studium variant s více počítači či s neidentickými
úlohami. Vhodné jako teoretická diplomová práce případně jako součást
širší doktorské práce.
4. Rozvrhování s konflikty
V této variantě on-line rozvrhování je dán graf, který udává konflikty
procesorů, tj. množina procesorů pracujících současně musí být
nezávislá
v tomto grafu. Předpokládá se, že úlohy přicházející na jednotlivé
počítače
mohou být uloženy v lokální frontě, a cílem je navrhnout takové on-line
algoritmy, které nepotřebují o mnoho delší frontu než optimální řešení.
Práce by navazovala na článek zadavatele
a studovala některé speciální případy tohoto problému, např. když daný
graf je cesta. Vhodné jako teoretická diplomová práce případně jako
součást
širší doktorské práce.
5. Pravděpodobnostní online algoritmy pro rozvrhování
V základní variantě tohoto problému přichází posloupnost úloh, které
je třeba přidělit na jeden z daných počítačů tak, aby celková délka
rozvrhu
byla co nejbližší optimu. Cílem práce by bylo studovat zejména
pravděpodobnostní
algoritmy, o kterých máme relativně malé znalosti, viz např. článek
zadavatele. V dalších variantách rozvrhování mají počítače různé
rychlosti, také se studuje preemptivní rozvrhování, kdy je možné úlohy
rozdělovat na více počítačů. Viz přehledový
článek zadavatele. Široké téma s možnostmi jak pro doktorskou tak
diplomovou
práci.
6. Online algoritmy: k-server problém
V k-server problému máme k serverů pohybujících se
v
metrickém prostoru. Vždy po požadavku na některý bod v prostoru je
třeba
jeden z nich do tohoto bodu přesunout, cílem je minimalizovat celkovou
procestovanou vzdálenost. Práce by studovala pravděpodobnostní
algoritmy
pro některé speciální případy tohoto problému, s cílem zlepšit buď
dolní
odhady nebo navrhnout a analyzovat algoritmy. Široké téma s možnostmi
jak pro doktorskou tak diplomovou
práci.
7. Algoritmy pro bin-packing a jeho varianty
Cílem práce by bylo studium aproximačních algoritmů pro
bin-packing,
porozumění Karp-Karmarkarova algoritmu a jeho případné zlepšení či
zjednodušení. Vhodné jako teoretická diplomová práce případně jako
součást
širší doktorské práce.