Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
   Přihlásit přes CAS
On the Hardness of General Caching
Název práce v češtině: O těžkosti obecného cachování
Název v anglickém jazyce: On the Hardness of General Caching
Klíčová slova: caching, general caching, NP-hardness, work function
Klíčová slova anglicky: cachování, obecné cachování, NP-těžkost, work function
Akademický rok vypsání: 2014/2015
Typ práce: bakalářská práce
Jazyk práce: angličtina
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
Řešitel: Mgr. Lukáš Folwarczný - zadáno a potvrzeno stud. odd.
Datum přihlášení: 22.02.2015
Datum zadání: 24.02.2015
Datum potvrzení stud. oddělením: 26.02.2015
Datum a čas obhajoby: 07.09.2015 00:00
Datum odevzdání elektronické podoby:28.07.2015
Datum odevzdání tištěné podoby:31.07.2015
Datum proběhlé obhajoby: 07.09.2015
Oponenti: Mgr. Martin Koutecký, Ph.D.
 
 
 
Zásady pro vypracování
Řešitel bude studovat vhodné speciální případy problému cachování souborů a pokusí se klasifikovat je z hlediska výpočetní složitosti. Cílem jsou buď nové výsledky zesilující známé výsledky o NP-úplnosti z článku Chrobak et al. anebo nové polynomiálně řešitelné podproblémy.
Seznam odborné literatury
- A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
- Chrobak, M., Woeginger, G. J., Makino, K., and Xu, H. Caching is hard – even in the fault model. Algorithmica 63, 4 (2012), 781–794.
- Achlioptas, D., Chrobak, M., and Noga, J. Competitive analysis of randomized paging algorithms. Theoretical Computer Science 234, 1-2 (2000), 203–218.
- Další odborné články dle konzultace s vedoucím práce.
 
Univerzita Karlova | Informační systém UK