Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.
V letním semestru 2012/13 měl kód BI-TS4 (případně MI-TS4) a konal se každé úterý od 16:15 v místnosti A-1030 v budově A.
Seminář vedou společně Ondřej Suchý a Tomáš Valla.
Chcete-li nás kontaktovat, napište na email ondrej.suchy@fit nebo tomas.valla@fit (místo @fit doplňte @fit.cvut.cz).
Program semináře
Seminář v letním semestru 2012/13 skončil.
Těšíme se na setkání v zimním semestru 2013/14, tentokrát pod kódy BI-TS1 a MI-TS1. Přejděte na stránku pro aktuální semestr.
Minulý program
Dne 7.5.2013 byly přednášky opět dvě, takže se seminář opět protáhl.
Nejdříve Michal Polívka představil článek An O(N P) Sequence Comparison Algorithm jehož autory jsou Sun Wu, Udi Manber, Gene Myers a Webb Miller.
Potom Tomáš Pecka představil článek Insertion Sort is O(n log n) jehož autory jsou Michael A. Bender, Martin Farach-Colton a Miguel A. Mosteiro.
Dne 30.4.2013 byly přednášky dvě, takže se seminář protáhl.
Nejdříve Lukáš Lopatovský představil článek Yet Another Hat Game jehož autory jsou Maura B. Paterson a Douglas R. Stinson.
Potom Roman Jelínek představil článek Which rectangular chessboards have a Knight's tour jehož autorem je Allen J. Schwenk.
Dne 23.4.2013 představil Jakub Puchýř článek The Cover Pebbling Number of Graphs jehož autory jsou Betsy Crull, Tammy Cundiff, Paul Feltman, Glenn H. Hurlbert, Lara Pudwell, Zsuzsanna Szaniszlo a Zsolt Tuza.
Dne 16.4.2013 představil Tomáš Šmida článek Non-attacking queens on a triangle jehož autory jsou Gabriel Nivasch a Eyal Lev.
Dne 9.4.2013 představil David Příhoda článek A Linear-time Algorithm for Drawing a Planar Graph on a Grid jehož autory jsou M. Chrobak a T.H. Payne.
Dle harmonogramu byl 2.4.2013 děkanský den, takže seminář odpadl.
Dne 26.3.2013 byly přednášky dvě, takže se seminář protáhl.
Nejdříve Jiří Nádvorník představil článek Sokoban is PSPACE complete jehož autorem je Joseph C. Culberson.
Potom Michal Bukový představil článek Scapegoat Trees jehož autory jsou Igal Galperin a Ronald L. Rive.
Dne 19.3.2013 představil Adam Kučera článek Finding a princess in a palace: A pursuit evasion problem jehož autory jsou John R. Britnell a Mark Wildon.
Dne 12.3.2013 představil Ondřej Fiedler článek Acyclic Digraphs and Eigenvalues of (0; 1)- Matrices jehož autory jsou Brendan D. McKay, Frederique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M. Wanless a Herbert S. Wilf.
Dne 5.3.2013 představil Josef Malík článek A simpler implementation and analysis of Chazelle’s Soft Heaps jehož autory jsou Haim Kaplan a Uri Zwick.
Dne 26.2.2013 představil Ondřej Škrdlant článek A Solution to the Angel Problem jehož autorem je Oddvar Kloster.
Články
Volné články
Jessica Muntza, Sivaram Narayana, Noah Streibb, Kelly Van Ochtena: Optimal pebbling of graphs
Klasicka hra na grafu. Kdyz sundame dva kaminky z jednoho vrcholu muzeme polozit jeden na souseda. Kolik musime mit na zacatku kaminku (libovolne rozlozenych), chceme-li mit na konci na kazdem vrcholu aspon jeden? Ukazuji se horni a dolni meze pro grafy polomeru d. PDF
Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan: Rank-Pairing Heaps
Haldy, ktere jsou stejne rychle jako Fibonacciho, ale na delete potrebuji jen jeden cut. PDF,PDF
Torben Hagerup: An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
Pro dany strom s vahami na hranach a seznam paru vrcholu toho stromu je treba pro kazdy par urcit nejtezsi hranu na ceste mezi nimi. Linearni algoritmus se znal, tenhle je jednodussi. Lze pouzit k overeni, ze strom je skutecne nejlehci kostrou grafu. Implementace v Dcku. PDF
Yoshiaki Yamaguchi, Kazunori Yamaguchi, Tetsuro Tanaka, and Tomoyuki Kaneko: Infinite Connect-Four Is Solved: Draw
Hra kdy hraci X a O hazi kameny do sloupecku a vyhrava ten kdo ma ctyri v rade (svisle, vodorovne nebo diagonalne). V clanku strategie pro nejake varinaty s nekonecne mnoha sloupci. Kdyz oba hraji optimalne, hra je nekonecna. PDF
Antoni Lozano, Merce Mora, Carlos Seara: Distinguishing trees in linear time
Graf je d-odlisitelny, pokud existuje ocislovani jeho vrcholu pomoci {1, ..., d}, ktere je zachovano jen identitou. Clanek obsahuje linearni algoritmus pro urceni nejmensiho d-odlisujiciho cisla pro lesy. Mozna dost zavisi na predchozich O(n log n) algoritmech. PDF
Saieed Akbari, Vahid Liaghat, Afshin Nikzad: Colorful Paths in Vertex Coloring of Graphs
Ukazuje se, ze v grafu obarvenem delta+1 barvami, existuje pro kazdy vrchol cesta, ktera v nem zacina a obsahuje prave jeden vrchol kazde barvy. PDF
Mikkel Thorup: Undirected Single Source Shortest Path in Linear Time
Prvni, ktery toho dosahuje deterministicky. Preklada, ze vahy jsou prirozena ne moc velka cisla. PDF
Mikkel Thorup: Floats, Integers, and Single Source Shortest Paths
Vylepsuje predchozi i na floaty, vyuziva ho jako podproceduru. PDF
Uriel Feige: On optimal strategies for a hat game on graphs
Hra s klobouky, v niz kazdy hrac sedi ve vrcholu grafu a vidi klobouky sousedu. Vsichni vyhraji, pokud aspon jeden tipne spravne a nikdo netipne spatne. Ukazuji se nejlepsi strategie pro bipartitni grafy a rovinne grafy s trojuhelnikem. PDF
Wesley Pegden: A finite goal set in the plane which is not a Winner
Je dana konecna mnozina bodu v rovine a hraci si stridave berou body roviny. Vyhrava ten ktery prvni ziska kopii zadane mnoziny. Zde mnozina o peti prvcich tak, ze druhy hrac muze vzdy vyhrat. PDF
Mike Paterson, Uri Zwick: Overhang
Skladame cihlicky na sebe, jak daleko pres okraj stolu mohou viset? Zde konstrukce s presahem theta(n^{1/3}), drive se znalo jen theta(log n). PDF
E.R. van Dam, M.A. Fiol: A short proof of the odd-girth theorem
Novy dukaz, ze graf s d+1 vlastnimi cisly a lichym obvodem 2d+1 je vzdalenostne regularni (pocet sousedu u ve vzdalenosti j od v je stejny pro vsechny u a v ve vzdalenosti i). Bude asi tezke rict nejak smysluplne bez referenci. PDF
Jozsef Balogh, Andras Pluhar: The positive minimum degree game on sparse graphs
Maker a Breaker spolu hraji hru: Stridave si vybiraji hrany grafu a Maker vyhraje, pokud hrany ktere si vybral tvori graf s urcitym minimalnim stupnem. V clanku se vylepsuje mez na to, kolik musel mit puvodni graf hran, aby mohl Maker vyhrat. Jednoducha aplikace metody vybijeni (discharging). PDF
Sam Ganzfried: Computing Strong Game-Theoretic Strategies in Jotto
Hra kdy si kazdy hrac mysli tajne slovo a klade druhemu otazky ve forme slova. Odpovedi je pocet pismenek ktera jsou v obou slovech. Resi se jak pocitat strategie pocitacem. PDF
Andras Gyarfas, Gabor N. Sarkozy: Monochromatic path and cycle partitions in hypergraphs
Rozdelovani hranove obarvenych uniformnich hypergrafu na jednobarevne cesty a cykly. Asi bude potreba nahlidnout do referenci a nastudovat nazvoslovi. PDF
S. Akbari, N. Ghareghani, G. B. Khosrovshahi, S. Zare: A note on zero-sum 5-flows in regular graphs
Tok s nulovym souctem je prirazeni nenulovych realnych cisel hranam tak, ze soucet u kazdeho vrcholu je 0. Ukazuje se, ze r-regularni graf (r >= 3, r != 5) ma takovy tok pouzivajic jen cisla {-5, ..., -1, 1, ..., 5}. Samotny dukaz ma asi pul stranky, bude potreba nastudovat reference. PDF
Richard Ehrenborg, Chris M. Skinner: The Blind Bartender's Problem
Na otocnem stole ctyri sklenice, se zavazanyma ocima muzete vzdy obratit nejake dve, ale nekdo mezi tim toci stolem. Lze dosahnout toho, ze vsechny stejne? Zobecneni pro vice sklenic a slozitejsi stoly. Asi docela slozite, mozna se da neco vybrat. PDF
Laurie Kirby And Jeff Paris: Accessible Independence Results For Peano Arithmetic
Zabijeni hydry. Tvrzeni prvniho radu nezavisle na Peanove aritmetice. Asi citlive vyzobnout to o te hydre? Nezabyvat se tolik tou nedokazatelnosti z PA, ordinalama apod. PDF
Jiri Matousek, Martin Loebl: Hercules versus Hidden Hydra Helper
Opet boj s hydrou, ale tentokrat se Herkules strida s milovnikem hydry, ktery ji sice seka, ale tak aby prezila co nejdele. Pokud milovnik dela jen jeden sek za kazdy sek Herkula, Herkules muze hydru zabit ``rychle''. Pokud ma milovnik vice seku, bude to trvat ``dlouho''. PDF
Matula, Shiloach, Tarjan: Two linear time algorithms for five-coloring a planar graph
Vi se, ze kazdy rovinny graf je 4 barevny. Zde se ukazuje, jak obarvit rovinny graf 5-i barvami v linearnim case. PDF
Mark K. Goldberg and Malik Magdon-Ismail: Embedding a Forest in a Graph
Kazdy les lze vlozit do kazdeho grafu s dostatkem vrcholu. PDF
Janusz Dybizbanski: Sequences containing no 3-term arithmetic progressions
Jaka je nejdelsi podposloupnost posloupnosti 1, ..., n, ktera neobsahuje aritmetickou podposloupnost delky 3? Odhad s pomoci pocitace pro n <= 122. Velmi kratke. PDF
Joshua Erde, Bruno Golenia, Sylvain Golenia: The closed knight tour problem in higher dimensions
Lze nalezt uzavreny tah konem navstevujici kazde policko ctyr nebo vice dimenzionalni sachovnice prave jednou? Jeden z delsich, ale o to zajimavejsich. PDF
Yang Jiao: On the Sprague-Grundy Values of the F-Wythoff Game
Odebirani sirek ze dvou hromadek - bud z jedne, nebo stejne z obou. Zde navic pri odebirani z obou potreba zachovat celou cast pomeru velikosti. Ukazuji se zajimave vlastnosti o cislech charakterizujicich pozice z nichz jeden ci druhy ma vyherni strategii. PDF
Tamas Matrai: Covering the Edges of a Graph by Three Odd Subgraphs
Kazdy graf se da (hranove) pokryt trojici svych podgrafu, v nichz vsechny stupne jsou liche. PDF
Fan Chung, Ron Graham, Jia Mao, and Andrew Yao: Oblivious and Adaptive Strategies for the Majority and Plurality Problems
Mame n micku obarvenych dvema nebo vice barvami. Kolik porovnani barev je potreba abychom zjistili, jestli je nekterych micku vic nez polovina, nebo kterych je nejvice? PDF
Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes
Kolik polynomu je potreba, abychom pokryli hyperkrychli jejich koreny? PS
David R. Karger, Philip N. Klein, Robert E. Tarjan: A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees PDF
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook: Linear-Time Pointer-Machine Algorithms for Least Common Ancestors,
MST Verification, and Dominators
Sjednoceni disjunktnich mnozin, radix sort s pointery a jejich spolecne pouziti k reseni vyse uvedenych. PDF
Haim Kaplan, Matthew J. Katz, Gila Morgenstern, and Micha Sharir: Optimal cover of points by disks in a simple polygon
Mame mnohouhelnik a v nem nekolik bodu. Chceme body pokryt kruhy ktere budou zcela v mnohouhelniku. Skoro linearni algoritmus. PDF
Články, které už byly
Oddvar Kloster: A Solution to the Angel Problem
Andel se pohybuje po nekonecne ctvercove mrizce, vzdy nevyse do vzdalenosti k, dabel ujida policka mrizky. Clanek ukazuje, ze pro k=2 (a vice) muze andel vzdy uteci. PDF Andras Mathe: The Angel of power 2 wins
Totez co predchozi, kratsi a mozna elegantnejsi. PDF Představil: Ondřej Škrdlant
Haim Kaplan, Uri Zwick: A simpler implementation and analysis of Chazelle’s Soft Heaps
Haldy ktere dovoluji chyby. PDF Představil: Josef Malík
Brendan D. McKay, Frederique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M. Wanless, Herbert S. Wilf: Acyclic Digraphs and Eigenvalues of (0; 1)- Matrices
Ukazuje se, ze pocet acyklickych orientovanych grafu s n ocislovanymi vrcholy je stejny jako pocet 0,1- matic n x n s kladnymi realnymi vlastnimi cisly. PDF Představil: Ondřej Fiedler
John R. Britnell, Mark Wildon: Finding a princess in a palace: A pursuit evasion problem
Princezna se musi kazdy den presunout do sousedniho pokoje (vrcholu grafu). Princ nevi kde princezna je, ale muze se podivat kazdy den do jednoho libolneho pokoje. Kdy ma princ viteznou strategii? Jak dlouho mu to bude trvat? Kratke, hezke, elementarni. PDF Představil: Adam Kučera
Culberson: Sokoban is PSPACE complete
Jak simulovat beh Turingova stroje pomoci zname hry Sokoban. PDF Představil: Jiří Nádvorník
Igal Galperin, Ronald L. Rive: Scapegoat Trees
Binarni vyhledavaci stromy, kde Insert i Delete trva amortizovane O(log N) a pritom potebuji jen dve cisla navic proti obycejnemu BVS. PDF Představil: Michal Bukový
Chrobak, Payne: A Linear-time Algorithm for Drawing a Planar Graph on a Grid
Jak nakreslit rovinny graf rovinne do mrizky cca 2n x n tak, ze hrany jsou usecky. PDF Představil: David Příhoda
Gabriel Nivasch, Eyal Lev: Non-attacking queens on a triangle
Umistovani dam na trojuhelnikovou sachovnici tak aby se neohrozovali- kolik nejvice? Velmi hezke a jednoduche. PDF Představil: Tomáš Šmida
Betsy Crull, Tammy Cundiff, Paul Feltman, Glenn H. Hurlbert, Lara Pudwell, Zsuzsanna Szaniszlo, and Zsolt Tuza: The Cover Pebbling Number of Graphs
Klasicka hra na grafu. Kdyz sundame dva kaminky z jednoho vrcholu muzeme polozit jeden na souseda. Kolik musime mit na zacatku kaminku (libovolne rozlozenych), chceme-li mit na konci na kazdem vrcholu aspon jeden? Ukazuji se optimalni cisla pro stromy a dalsi grafy. Hezke, elementarni. PDF Představil: Jakub Puchýř
Schwenk: Which rectangular chessboards have a Knight's tour
Ktere obdelnikove sachovnice maji uzavreny tah konem, ktery navstivi kazde policko prave jednou? PDF Představil: Roman Jelínek
Maura B. Paterson, Douglas R. Stinson: Yet Another Hat Game
Hadani barvy sveho klobouku, podle urcite informace o kloboucich ostatnich. Shrnuti strategii pro zname hry a design nove hry. Velmi zajimave a nenarocne. PDF Představil: Lukáš Lopatovský
Michael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro: Insertion Sort is O(n log n)
Jak zrychlit insertion sort tim, ze si budeme nechavat mezery. Malinko pravdepodobnosti. PS Představil: Tomáš Pecka
Sun Wu, Udi Manber, Gene Myers, and Webb Miller: An O(N P) Sequence Comparison Algorithm
Hleda se nejkratsi editacni skript pro ziskani jedne sekvence z druhe. N je delka te delsi, P pocet mazani. PDF Představil: Michal Polívka