Národní úložiště šedé literatury Nalezeno 42 záznamů.  1 - 10dalšíkonec  přejít na záznam: Hledání trvalo 0.01 vteřin. 
Möbius function of matrix posets
Medek, Michal ; Jelínek, Vít (vedoucí práce) ; Kantor, Ida (oponent)
In this work, we focus on the M¨obius function µ(X, Y ) of four variants of containment posets of sparse matrices, for which the M¨obius function has not been studied before. A sparse matrix is a binary matrix containing at most one 1-cell in each row and column. We focus mainly on the dominated scattered containment, where X ≤ Y if X can be created from Y by removing some rows and columns and by changing some 1-cells to 0-cells. We consider this poset to be a generalization of the permutation poset, as for permutations σ and π, if σ ≤ π, then the permutation matrices Mσ and Mπ satisfy Mσ ≤ Mπ. For the dominated scattered containment, we study the values of the M¨obius function on intervals of the form [1, Y ], where 1 is the 1 × 1 matrix consisting of a single 1-cell. We show that the situation when Y contains a zero row or column can be reduced to a situation when Y has no such zero line, that is, Y is a permutation matrix. For a permutation matrix Y , we derived a theorem expressing µ(1, Y ) in terms of the blocks of the sum decomposition of Y .
Structural and Algorithmic Properties of Permutation Classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Kozma, László (oponent) ; Bouvel, Mathilde (oponent)
V této práci studujeme vztah mezi strukturou dědičných permutačních tříd a výpo- četní složitostí různých rozhodovacích problémů. Nejdříve zkoumáme strukturu permu- tačních tříd z pohledu několika různých parametrů, zejména stromové šířky. Definujeme nové vlastnosti obecné permutační třídy C, z nichž nejdůležitější je vlastnost dlouhé cesty. Z těchto vlastností pak odvodíme různé dolní odhady na to jakou největší stromovou šířku může mít permutace délky n z třídy C. Například dokážeme, že libovolná třída s vlastností dlouhé cesty má stromovou šířku neomezenou. Hlavní rozhodovací problém, kterým se zabýváme, je znám jako Permutation Pat- tern Matching (PPM). Vstupem pro problém PPM je dvojice permutací τ (text) a π (vzor), a cílem je rozhodnout jestli τ obsahuje π jako podpermutaci. Nejdříve zběžně uvažujeme problém PPM ve své obecné verzi, a poté se zaměříme na jeho variantu C- Pattern PPM, kde navíc požadujeme, aby vzor π pocházel z pevně dané třídy C. Za předpokladu různých strukturálních vlastností třídy C pak odvodíme jak klasické tak pa- rametrizované těžkostní výsledky. Například ukážeme, že problém C-Pattern PPM je NP-úplný kdykoliv třída C má vlastnost dlouhé cesty. Dále se zaměříme na ještě více omezenou variantu problému PPM, ve které požadu- jeme, aby i text pocházel z pevně dané třídy C. Tento...
The combinatorics of pattern-avoiding matrices
Mikšaník, David ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Permutační matice P částečné vynechává kvazi-permutační matici A (jinými slovy, 01- matici takovou, že každý sloupec a řádek matice A obsahuje nejvýše jednu nenulovou hod- notu), pokud neexistuje podmatice P′ matice P stejné velikosti jako A splňující Ai,j ≤ P′ i,j pro každé indexy i a j. Kvazi-permutační matice A a B jsou částečně Wilf-ekvivalentní, pokud pro každé n ∈ N počet permutačních matic řádu n částečné vynechávajících A je stejný jako počet permutačních matic řádu n částečně vynechávajících B. Tyto pojmy zobecňují známý koncept vynechávání permutací a Wilfovy ekvivalence permutací. Stě- žejní oblast výzkumu je klasifikace permutací řádu k do tříd Wilfovy ekvivalence. Tato klasifikace je známa pro k = 1, 2, . . . , 7. V naší práci studujeme stejný problém pro kvazi- permutační matice. Konkrétně, klasifikujeme všech 371 kvazi-permutačních matic veli- kosti nejvýše 4×4 do říd částečné Wilfovy ekvivalence (dvě kvazi-permutační matice patří do stejné třídy právě tehdy, když jsou částečně Wilf-ekvivalentní). V průběhu odvodíme několik obecných výsledků o tom, jak zkonstruovat z jedné či dvou kvazi-permutačních matic více kvazi-permutačních matic, které jsou po dvou částečně Wilf-ekvivalentní. 1
New Intersection Graph Hierachies
Chmel, Petr ; Jelínek, Vít (vedoucí práce) ; Kratochvíl, Jan (oponent)
String grafy jsou průnikové grafy křivek v rovině. Asinowski a kol. [JGAA 2012] za- definovali hierarchii VPG grafů dle počtů zlomů jednotlivých křivek a ukázali, že tato hierarchie obsahuje právě všechny string grafy. Podobnou hierarchii můžeme pozorovat u k-string grafů: string grafů, jež jsou navíc omezeny tím, že každá dvojice křivek může sdílet nejvýše k bodů. V tomto směru pokračujeme zavedením precisely-k-string grafů, jejichž reprezentace je omezenější, neboť požadujeme, aby každá dvojice křivek sdílela buď právě 0, nebo právě k bodů a zároveň se křivky nesmí jen dotýkat. Dokážeme, že pro každé k ≥ 1 je každý precisely-k-string graf i precisely-(k + 2)-string graf, a že třídy precisely-k-string grafů a precisely-(k + 1)-string grafů jsou inkluzí neporovnatelné. Dále hledáme efektivně reprezentovatelnou třídu průnikových grafů objektů v rovině, která obsahuje všechny grafy s fixním maximálním stupněm. V průběhu zavedeme hi- erarchii průnikových grafů sjednocení d svislých a vodorovných úseček, jež nazýváme impure-d-line grafy, a dalších variant této třídy s omezeními na reprezentaci. Dokážeme, že všechny grafy s maximálním stupněm ≤ 2d jsou impure-d-line grafy a pro d = 1 je toto nejlepší možný výsledek. Také studujeme vztah mezi parametrem d v definici impure-d-line grafů a ostatními grafovými...
Möbiova funkce kombinatorických uspořádání
Kopfová, Lenka ; Jelínek, Vít (vedoucí práce) ; Kantor, Ida (oponent)
V této práci se zabýváme částečně uspořádanou množinou znaménkových permutací. Uspořádání na permutacích je zde definováno pomocí obsahování jako podpermutace. Znaménková permutace je taková permutace, ve které má každý prvek zvolené plus nebo mínus znaménko. Znaménkové permutace jsou tak zobecněním neznamínkových permutací, protože ty můžeme dostat tak, že každému prvku zvolíme plus znaménko. Ukážeme několik výsledků týkající se Möbiovy funkce znaménkových permutací, některá z nich jsou zobecněním už dříve dokázaných vět pro neznaménkové permutace. Práce se také zabývá izomorfismem částečně uspořádaných množin znaménkových permutací. Izomor- fismus pak mimo jiné zaručuje, že dané dva intervaly mají stejnou hodnotu Möbiovy funkce.
Algebraické vlastnosti barevnosti grafů
Bulánek, Jan ; Kráľ, Daniel (vedoucí práce) ; Jelínek, Vít (oponent)
V práci se zabýváme algebraickými metodami, pomocí kterých lze rozhodnout, zda existuje obarvení daného grafu. Zaměříme se především na Alon-Tarsiho větu, která bude dokázána, předvedeme její známé aplikace a ukážeme nové použití při barvení druhých mocnin cyklů.
Obecná enumerace číselných rozkladů
Hančl, Jaroslav ; Klazar, Martin (vedoucí práce) ; Jelínek, Vít (oponent)
Název práce: Obecná enumerace číselných rozklad· Autor: Jaroslav Hančl Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: doc. RNDr. Martin Klazar, Dr., KAM MFF UK Abstrakt: Předložená diplomová práce se zabývá asymptotikami počítacích funkcí ideál· číselných rozklad·. Jejím hlavním cílem je zjistit největší možný asympto- tický r·st počítací funkce rozkladového ideálu, která je nekonečněkrát rovna nule. Autor se na základě znalosti asymptotik vybraných rozkladových ideál· snaží po- mocí kombinatorických a základních analytických metod odvodit odhady hledané asymptotiky. Výsledkem je za prvé slabší horní odhad, za druhé poměrně silný dolní odhad a za třetí, pro speciální třídu rozkladových ideál· je nalezen největší asymptotický r·st. Klíčová slova: íselné rozklady, asymptotika rozklad·, rozkladové ideály, počítací funkce, kombinatorická enumerace. 1
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
Generování grafů
Mohelníková, Lucie ; Dvořák, Zdeněk (vedoucí práce) ; Jelínek, Vít (oponent)
Název práce: Generování grafů Autor: Lucie Mohelníková Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: Mgr. Zdeněk Dvořák,Ph.D., Informatický ústav Univerzity Karlovy Abstrakt: Zabýváme se generováním grafů z vybraných tříd, zejména pak grafů nakreslených na plochách. Zaměřujeme se na metodu generování za pomoci dekontrakcí vrcholů, pro níž je zásádní identifikace počátečních (ireducibilních) grafů. Uvádíme přehled výsledků o ireducibilních triangulacích a kvadrangulacích různých ploch, zejména pak nízkého rodu (rovina, projektivní rovina, Kleinova láhev). Hlavním přínosem této práce je identifikace 21 ireducibilních triangulací toru, čímž dokazujeme výsledek Lawrencenka bez použití výpočetní techniky. Klíčová slova: ireducibilní, triangulace, torus
Editor matematických výrazů
Holaň, David ; Jelínek, Vít (vedoucí práce) ; Lidický, Bernard (oponent)
V předložené práci studujeme návrh a implementaci "MaEd for LATEX", přenositelného programu s grafi ckým uživatelským rozhraním. Program je určen na vytváření a upravu LATEXových vzorců. Program je navržen tak aby začátečník mohl vytvořit i složité vzorce bez znalosti LATEXového zdrojového kódu. Uživatel také může importovat vlastní zdrojový kód, přičemž program zbytečně nemění importovaný kód, například odstraněním komentářů, nebo odražení. Návrh popisuje, jak bylo navrženo uživatelské rozhraní programu. LATEXové příkazy dostupné k vytváření matematických vzorců jsou popsány i s jejich syntaxí a úrovní podpory v programu. Práce dále analyzuje strukturu souboru LATEXového zdrojového kódu.

Národní úložiště šedé literatury : Nalezeno 42 záznamů.   1 - 10dalšíkonec  přejít na záznam:
Viz též: podobná jména autorů
4 Jelínek, Vladimír
2 Jelínek, Vojtěch
7 Jelínek, Václav
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.