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.