Aproximácia permanentu v čase O*(n^7)
Ivona Bezáková, University of Chicago, USA
Streda, 15. decembra 2004, 10:00-10:40 (Informatika I.: Teoretická informatika)
Jerrum, Sinclair a Vigoda (STOC '00) publikovali prvý randomizovaný aproximačný algoritmus počítajúci permanent matice s nezápornými prvkami. Ich algoritmus mal časovú zložitosť O*(n^26). Tí istí autori vylepšili svoj algoritmus na O*(n^10). V tomto článku uvádzame algoritmus bežiaci v čase O*(n^7). Naša metóda, podobne ako v JSV, je založena na Markovových reťazcoch. Algoritmus v JSV je založený na "simulovanom anulovaní" s uniformným chladením. Hlavnou odlišnosťou nášho algoritmu je použitie neuniformného chladiaceho mechanizmu. Taktiež uvádzame novú nerovnosť, ktorá vylepšuje odhad "congestion" v pôvodnom algoritme. Spoluautori: Daniel Štefankovič, Vijay Vazirani, Eric Vigoda.
Ivona Bezaková absolvovala magisterské štúdium informatiky na FMFI UK v rokoch 1995-2000, so zameraním na teoretickú informatiku a počítačovú grafiku. Od roku 2000 je Ph.D. študentkou na University of Chicago, kde sa zaoberá (prevažne teoretickým) štúdiom Markovových reťazcov pod vedením Erica Vigodu.
Locally testable cyclic codes
Daniel Štefankovič, University of Chicago, USA
Streda, 15. decembra 2004, 10:40-11:20 (Informatika I.: Teoretická informatika)
Cyclic linear codes of block length n over a finite field F_q are linear subspaces of F_q^n that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes.
A code C is r-testable if there exists a randomized algorithm which, given a word x in F_q^n, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that (i) if x is in C then x is surely accepted; (ii) if Hamming distance of x and C is at least epsilon*n then x is probably rejected. A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCPs. Goldreich and Sudan asked whether there exist good, locally testable families of codes.
In this paper we prove that there are no good, locally testable families of cyclic codes over any (fixed) finite field. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.
Daniel Štefankovič študoval informatiku na FMFI UK v rokoch 1993 - 1998. Vedúcim jeho diplomovej práce bol Peter Ružička. Od roku 1998 je doktorand na University of Chicago.
Roboty a roboti
Andrej Lúčny, FMFI UK, Bratislava
Streda, 15. decembra 2004, 15:20-16:00 (Informatika II.)
Príspevok podáva krátku správu o snažení sa robotickej komunity v Bratislave za posledné obdobie. Špeciálny dôraz sa kladie na úlohu FMFI v tomto snažení, ktorá spočíva práve v definovaní požiadaviek na hardwarové schopnosti robotov a v ich oživení netriviálnym softwarom vychádzajúcim z techník umelej inteligencie.
Andrej Lúčny absolvoval FMFI UK v roku 1994. Odvtedy pôsobí vo firme MicroStep-MIS kde vyvíja monitorovacie systémy reálneho času. Od roku 1997 učí na FMFI multiagentové systémy. Predmetom jeho výskumu je softwarová architektúra na tvorbu interaktívnych komplexných systémov vychádzajúca z Brooksovej subsumpčnej architektúry a agentovo-orientovaného programovania.
Robotnačka - výukový robot k Imagine Logu
Pavel Petrovič, NTNU, Nórsko / FMFI UK, Bratislava
Streda, 15. decembra 2004, 16:00-16:40 (Informatika II.)
V nedávnej minulosti bol v spolupráci autorov Imagine Loga a firmy Microstep vyvinutý mobilný autonómny robot - robotnačka, ktorý vie komunikovať s detským programovacím jazykom Imagine Logo a kresliť to, čo kreslí korytnačka v Logu. Mojim cieľom je vytvorenie rámca pre učiteľov matematiky, fyziky a informatiky na stredných a základných školách pre použitie robotnačky ako učebnej pomôcky - čím zároveň Imagine Logo získava možnosti interaktívnych konferencií cez internet a počítačového videnia. Súčasťou prezentácie bude praktická ukážka systému.
Pavel Petrovič študoval informatiku na MFF UK v odbore umelá inteligencia v rokoch 1993-1998. Od roku 1998 pôsobíi ako doktorand na NTNU Trondheim, Nórsko, kde študuje evolúciu arbitračných mechanizmov pre behaviour-based robotics. V súčasnosti hosťuje na FMFI UK v rámci civilnej služby.
Senzorové siete: lokalizácia strelca
Branislav Kusý, Vanderbilt University, USA
Piatok, 17. decembra 2004, 14:20-15:00 (Informatika III.: Aplikovaná informatika)
V prvej časti príspevku predstavím senzorové siete, hardware, s ktorým pracujeme, a možnosti využitia týchto sietí. V druhej časti popíšem systém využívajúci senzorové siete, ktorý odhalí pozíciu nepriateľského ostreľovača nájdením pozície výstrelu zo zbrane a dráhy šokovej vlny vznikajúcej následkom letu náboja. Priblížim problémy, s ktorými sme sa museli vysporiadať, aby sa dal náš systém použiť aj v prípadoch, keď je pre človeka takmer nemožné zistiť, odkiaľ sa strieľalo (napr. boj v uliciach mesta). Na záver ukážem video z testovania tohto systému.
Braňo Kusý študoval informatiku na MFF UK v odbore grafika a teoretická informatika v rokoch 1997-2002. Vedúcim jeho diplomovej práce "Algorithms to embed graphs into surfaces" bol Doc. Martin Škoviera. Od roku 2002 je doktorandom na Vanderbilt University, USA, kde sa zaoberá senzorovými sieťami.
Inverzné skladanie proteínov v dvojrozmernom HP modeli
Ján Maňuch, PIMS, Kanada
Piatok, 17. decembra 2004, 15:00-15:40 (Informatika III.: Aplikovaná informatika)
Vyriešiť problém inverzného skladania proteínov znamená navrhnúť sekvenciu aminonukleových kyselín (monomérov), ktorá sa poskladá do predurčenej podoby. Tento problém je dôležitý pri hľadaní nových liekov, kde určitá priestorová štruktúra je nevyhnutná na zaručenie interakcie medzi proteínmi (liekom a proteínom v organizme). Ukázali sme, že tento problém sa dá vyriesiť pre veľkú triedu priestorových štruktúr v Dillovom dvojrozmernom HP (hydrofóbno-polárnom) modeli. Táto trieda štruktúr blízko aproximuje akúkoľvek priestorovú štruktúru. Tiež sme ukázali, že pre veľa našich jednoduchých štruktúr sa navrhnuté sekvencie jednoznačne poskladajú do predurčených dvojrozmerných štruktúr, a teda sa nebudú simultánne skladať do iných tvarov, čo je dôležitá podmienka pri návrhu efektívnych liekov.
Ján Maňuch študoval magisterské štúdium na MFF UK v odbore teoretická informatika. Po skončení štúdia absolvoval doktorandské štúdium na Univerzite v Turku, Fínsko, kde sa zaoberal nekonečnými sekvenciami a efektom defektu. V súčasnosti pôsobí ako postdoc na Simon Fraser University vo Vancouveri, Kanada. Zaujíma sa o rôzne kombinatorické problémy, v poslednom čase s aplikáciou v bioinformatike.
Formálna verifikácia
Ivana Černá, Masarykova Univerzita, Brno
Streda, 5. januára 2005, 10:00-10:40 (Informatika IV.: Formálna verifikácia)
Cieľom príspevku je predstaviť formálnu verifikáciu ako metódu umožňujúcu overovať vlastnosti softwarových a hardwarových systémov. Ukážeme techniky, ktoré sa používajú v procese verifikácie, možnosti ich použitia, ako aj limity, s ktorými sa v praxi stretávame.
Ivana Černá študovala na MFF UK v Bratislave v rokoch 1981-1986. Po skončení magisterského štúdia pokračovala v doktorandskom štúdiu, ktoré ukončila v roku 1990. Od roku 1994 pôsobí na Fakulte informatiky Masarykovej univerzity v Brne. Jej záujmy zahŕňajú formálne metódy špecifikácie a verifikácie súbežných systémov.
Syntéza dynamických interfaceov
Pavol Černý, University of Pennsylvania, USA
Streda, 5. januára 2005, 10:40-11:20 (Informatika IV.: Formálna verifikácia)
Typický softvérový komponent má jasne definovaný (statický) interface - zoznam metód a ich vstupných a výstupných parametrov. Informácie o tom, v akom poradí môže užívateľ volať tieto metódy sú ale často nedokumentované. V tomto príspevku popíšeme, ako sa takéto dynamické (behaviorálne) špecifikácie dajú automaticky extrahovať z kódu Java tried. Dynamický interface pre danú triedu a daný invariant (napríklad "výnimka E nemôže byť vyvolaná") popisuje najvšeobecnejší spôsob ako volať metódy triedy tak, aby invariant zostal pravdivý. Prvý krok našej metódy spočíva v zostrojení symbolickej reprezentácie konečného modelu triedy pomocou predikátovej abstrakcie. Konštrukcia interface-u potom spočíva v hľadaní víťaznej stratégie pre hru dvoch hráčov s neúplnou informáciou. Ukážeme spôsob, ako aproximovať riešenie tejto úlohy s vysokou výpočtovou zložitosťou pomocou algoritmov pre učenie regulárnych automatov a model-checking algoritmov.
Pavol Černý študoval informatiku na FMFI UK v rokoch 1998-2000 a na ENS v Paríži v rokoch 2000-2003. Od roku 2003 je doktorandom na University of Pennsylvania, kde sa zaoberá formálnou verifikáciou.
Algorithms for Independent
Task Placement and Their Tuning in the Context
of Demand-Driven Parallel Ray Tracing
Tomáš Plachetka, University of Bristol, Veľká Británia
Streda, 5. januára 2005, 13:40-14:20 (Informatika V.)
This talk presents deterministic assignment strategies (load balancing algorithms) for process farms. These strategies solve the problem of placement of a constant number of independent tasks with given, but unknown, time complexities onto a homogeneous network of processors with a given (and known) latency.
Aproximačné algoritmy pre stochastickú optimalizáciu
Martin Pál, DIMACS, Rutgers University, USA
Streda, 5. januára 2005, 14:20-15:00 (Informatika V.)
Tradičný problém v diskrétnej optimalizácii môže vyzerať napríklad takto: majme daný ohodnotený graf G a množinu terminálov, ktorú chceme navzájom poprepájať. Úlohou je skonštruovať súvislú sieť (množinu hrán), ktorá poprepája všetky terminály tak, aby jej cena bola čo najmenšia. Nájsť riešenie (Steinerov strom) je NP-ťažká úloha, ktorá však má efektívne aproximačné algoritmy a je aj pomerne dobre prakticky riešiteľná.
Čo sa však stane, ak nevieme presne, ktoré terminály máme spojiť? Akú sieť má zmysel postaviť v takomto prípade? V mojej prednáške predstavím jednoduchý dvojetapový stochastický model: v prvej fáze nepoznáme terminály, ktoré treba spojiť, avšak môžeme kupovať hrany za nízku cenu. V druhej fáze sa dozvieme požiadavky našich zákazníkov (t.j. polohu a počet požadovaných terminálov), a našou úlohou je dokúpiť dostatok (za vyššiu cenu) hrán tak, aby sme mohli pospájať všetky terminály. V prvej fáze predpokladáme že máme k dispozícii nejaký štatistický model správania zákazníkov (historické údaje o tom, ktoré terminály boli požadované v minulosti, prieskum trhu a pod).
Martin Pál vyštudoval za magistra na MFF UK v roku 2000 a nedávno skončil Ph.D. štúdium na Cornell University. V súčastnosti je postdoc v DIMACS, centre pre diskrétnu matematiku a počítačovú vedu. Medzi jeho záujmy patrí diskrétna optimalizácia, aproximačné algoritmy na riešenie NP-ťažkých optimalizačných problémov, navrhovanie komunikačných a transportných sietí a riešenie problémov s neúplnou informáciou.