|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Major index permutace π je součet všech indexů i takových, že πi > πi+1. V této práci zkoumáme distribuci major indexu na permutacích neobsahujích zakázané vzory. Zajímá nás hodnota Mm n (Π), což je počet permutací délky n s major indexem m a množinou zakázaných vzorů Π. Podařilo se nám ukázat, že pro jednoprvkovou množinu Π = {σ} krom okrajových triviálních pří- padů, se hodnoty Mm n (Π) chovají monotónně, nebo-li Mm n (Π) ≤ Mm n+1(Π). Hlavním výsledkem je rozbor asymptotického chování hodnot Mm n (Π) pro n jdoucí k nekonečnu. Ukážeme, že pro každé pevné m, Π a dostatečně velké n jsou hodnoty Mm n (Π) rovny polynomu v proměnné n a navíc jsme schopni určit stupně těchto polynomů pro různé množiny zakázaných vzorů. 1
|
|
|
Enumerace kompozic čísel se zakázanými vzory
Dodova, Borjana ; Klazar, Martin (vedoucí práce) ; Jelínek, Vít (oponent)
Enumerace kompozic čísel se zakázanými vzory Abstrakt Tato práce si klade za cíl odvodit některé výsledky pro 3-regulární kompozice, tedy kompozice se zakázaným vzorem {121, 212, 11}, které jsou jistým zobecněním Carlitzových kompozic. Pomocí generujících funkcí příslušejících kompozicím se zakázanou množinou vzorů {121, 11} a {212, 11} počítáme horní asymptotický odhad koeficientů mocninného rozvoje generující funkce příslušející 3-regulárním kompozicím. S využitím teorie konečných automatů dostáváme také dolní odhad. Ten posléze zpřesňujeme na základě 3-blokových kompozic. Pro generující funkci příslušející 3- regulárním kompozicím se zvýrazněnou předposlední a poslední částí dokazujeme rekurzivní vztah. Kromě 3-regulárních kompozic a úloh, které s nimi přímo souvisejí, se zabýváme také kompozicemi s množinou zakázaných vzorů {312, 321} s částmi z konečné množiny [d], pro něž odvozujeme maticový tvar generující funkce. V závěru práce dokazujeme transcendentalitu generující funkce příslušející Carlitzovým kompozicím.
|
|
|
Extremal combinatorics of matrices, sequences and sets of permutations
Cibulka, Josef ; Valtr, Pavel (vedoucí práce) ; Füredi, Zoltán (oponent) ; Jelínek, Vít (oponent)
Název práce: Extremální kombinatorika matic, posloupností a množin permutací Autor: Josef Cibulka Katedra: Katedra aplikované matematiky Vedoucí disertační práce: Doc. RNDr. Pavel Valtr, Dr., Katedra aplikované ma- tematiky Abstrakt: V této práci se zabýváme oblastmi extremální teorie {0, 1}-matic, posloupností a množin permutací, které mají četná využití v oblasti kombina- torické a výpočetní geometrie. VC-dimenze množiny n-prvkových permutací P je největší celé číslo k takové, že množina zúžení permutací z P na některou k-tici pozic je množina všech k-prvkových permutací. Projdeme všemi třemi zmíněnými oblastmi extremální kombinatoriky, abychom dokázali horní a dolní meze, rostoucí kvaziexponenciálně v n, na maximální možnou velikost množiny n- permutací s VC-dimenzí shora omezenou konstantou. Tento výsledek využívá ve svém článku Jan Kynčl k výraznému snížení horního odhadu na počet tříd slabého izomorfismu úplného topologického grafu na n vrcholech. Dále pro některé, ze- jména permutační, matice M dokážeme nové meze na počet jedniček v M-prosté {0, 1}-matici velikosti n × n. Například pro každé k zkonstruujeme matici s k2 n/2 jedničkami prostou jedné konkrétní permutační matice velikosti k ×...
|
|
| |
|
|
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
|
|
|
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
|
|
| |
|
|
Editor matematických výrazů
Holaň, David ; Lidický, Bernard (oponent) ; Jelínek, Vít (vedoucí práce)
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.
|
|
| |
|
| |
host ::
RSS.