7th workshop of the Center of Modern Computer Science
7. seminář Centra moderní informatiky
The seventh workshop of the Center of Modern Computer Science will take place on June 26—27, 2015 in the Mala Strana building.
Centrum moderní informatiky zve na sedmý seminář. Přednášky juniorů centra se konají v průběhu programu v pátek 26. a sobotu 27. 6. 2015 v budově MFF UK na Malé Straně. Seminář se konal v rámci STTI 2015.
| Páteční přednášky | |
|---|---|
| 9:00 | Milan Hladík: Míra řešitelnosti a neřešitelnosti lineárních soustav |
| 15:15 | Zdeněk Dvořák: Velké nezávislé množiny v rovinných grafech bez trojúhelníků |
| Sobotní přednášky | |
| 10:35 | Martin Tancer: Vnořitelnost do 3-sféry je rozhodnutelná |
Abstracts
Milan Hladík: Míra řešitelnosti a neřešitelnosti lineárních soustav
Metoda totálních nejmenších čtverců spočíá v nalezení nejmenší perturbace matice dané soustavy lineárních rovnic tak, aby soustava byla řešitelná. V principu můžeme uvažovat minimum v jakékoli maticové normě. My se zaměříme na hledání minima v Čebyševově normě. Ukážeme, že problém je nejenom NP-těžký, ale dokonce i neaproximovatelný. Na druhou stranu, při pevném počtu už se stává polynomiálním.
Výše zmíněný problém dále zobecníme na obecné soustavy rovnic a nerovnic, a kromě míry řešitelnosti budeme uvažovat i míru neřešitelnosti. Pro všechny tyto problémy ukážeme explicitní formulaci problému jako optimalizační úlohy a klasifikujeme v rámci P/NP hierarchie. Zmíníme vztahy mezi různými mírami a jednoduché horní odhady. Na závěr ponecháme zobecnění na neuniformní perturbace.
Zdeněk Dvořák: Velké nezávislé množiny v rovinných grafech bez trojúhelníků
Každý rovinný graf na n vrcholech, který neobsahuje trojúhelníky, má nezávislou množinu velkosti alespoň (n+1)/3 a tento dolní odhad je těsný. Popíšeme algoritmus, který pro zadaný rovinný graf G na n vrcholech bez trojúhelníků a pro zadané celé číslo k≥0 rozhodne, zda G má nezávislou množinu velikosti alespoň (n+k)/3 v čase 2^O(sqrt(k))n. Tento problém je tedy efektivně řešitelný, je-li parametrizován hodnotou k. Jako důsledek tvrzení používaného v důkazu správnosti tohoto algoritmu také ukážeme, že pro nějaké epsilon>0 má každý rovinný graf obvodu 5 na n vrcholech nezávislou množinu velikosti alespoň n/(3-epsilon).
(obsahuje výsledky společné práce s Matthiasem Mnichem)
Martin Tancer: Vnořitelnost do 3-sféry je rozhodnutelná
Během přednášky nastíníme důkaz, že je algoritmicky rozhodnutelné, zda lze daný 2-rozměrný simpliciální komplex (topologicky) vnořitelný do R^3. Pomocí známé redukce stačí rozhodnout vnořitelnost dané triangulované 3-variety X do trojrozměrné sféry S^3. Hlavní krok, který umožňuje zjednodušit X a pokračovat rekurzivně, je důkaz následujícího tvrzení: Pokud je X vnořitelné do S^3, potom také má vnoření, ve kterém má X krátký meridián, tj. esenciální křivku na hranici X, která ohraničuje disk v S^3/X a jejíž délka je omezená vyčíslitelnou funkcí v počtu čtyřstěnů triangulace X.
(obsahuje výsledky společné práce s J. Matouškem, E. Sedgwickem a U. Wagnerem)
