|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
|
|
Graph communication protocols
Folwarczný, Lukáš ; Pudlák, Pavel (vedoucí práce) ; Sgall, Jiří (oponent)
Grafové komunikační protokoly jsou zobecněním klasických komunikačních protokolů na případ, kdy je grafem protokolu orientovaný acyklický graf. Motivováni možnými aplikacemi v důkazové složitosti studujeme varianty grafových komunikačních protokolů a vztahy mezi nimi. Hlavním výsledkem je porovnání síly dvou typů protokolů, protokolů s rovností a protokolů s konjunkcí konstantního počtu nerovností. Dokazujeme, že protokoly prvního typu jsou alespoň tak silné jako protokoly druhého typu v následujícím smyslu: Necht' f je booleovská funkce. Pokud existuje protokol s konjunkcí konstantního počtu nerovností polynomiální velikosti řešící f, pak existuje protokol s rovností polynomiální velikosti řešící f. Rovněž zavádíme dva nové typy grafových komunikačních protokolů, protokoly s disjunktností a protokoly s nedisjunktností, a dokazujeme, že protokoly prvního typu jsou alespoň tak silné jako doposud uvažované protokoly a že protokoly druhého typu jsou příliš silné na to, aby mohly být aplikovány.
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
host ::
RSS.