|
|
Marxismus, neomarxismus - přístupy ke vzdělání
Kratochvíl, Jan ; Kopecký, Martin (vedoucí práce) ; Mužík, Jaroslav (oponent)
Prace se zabyva vzdelavanim v sociologickem a filosofickem kontextu. Vychazi pfitom z marxistickeho resp. neomarxistickeho pohledu, ktery je predstaven v prvni casti. Pozornost je venovana zejmena myslenkam spojenym s Marxovou teorii dejin a odcizovanim cloveka v kapitalismu. Dale jsou strucne probrana dila nekterych autonl, kteri zminena temata rozvijeli spolu s kritikou urCitYch rysu pozdne kapitalisticke spolecnosti. Pojem vzdelavani je nasledne zasazen do socialnich souvislostf a predstaven v ruznych kultume podminenych obmenach. Ukolem teto casti price je ukazat zavislost pojetf vzdelavani na aktualnim historickosocialnim kontextu a promyslet jeho vnimani v pozdne kapitalisticke spolecnosti. Pote je formulovano urcite teoreticke vymezeni, ktere by mohlo byt nosne pri reseni nekterych problemu vyplyvajicich ze soucasne struktury spolecenskYch vztahu. Zaverecna cast se zabyva skolou a odhaluje ji jako urCitY institucionalni konzervant aktualniho pojetf vzdelavani. Ukazuje, ze i skolni vYuka podleha historicko-socialne podminene hodnotove orientaci, a nemuze se proto stat primamim zdrojem predefinovani vzdelanosti tak, aby tato mohla pfispet k reseni nekterych strukturalnich problemu spolecnosti.
|
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Hliněný, Petr (oponent) ; Fomin, Fedor (oponent)
DIZERTAČNÍ PRÁCE Tomáš Gavenčiak Studium strukturálních a složitostních otázek teorie grafů Původní hra na četníky a zloděje, kterou roku 1983 navrhli Nowakowski a Winkler, a nezávisle Quilliot, je kombinatorická pronásledovací hra na grafech. Od té doby bylo navrženo a studováno mnoho podobných a příbuzných her, a to jak s čistě teoretickou motivací, tak pro jejich aplikace v teorii grafů a souvislosti s grafovými parametry. V práci předkládáme přehled této oblasti teorie her a bližší pozornost věnujeme následujícím třem výsledkům. Ukazujeme nová omezení na počet četníků nutných k polapení zloděje v několika typech průnikových grafů; speciálně ukazujeme, že na každém souvislém průnikovém grafu křivek vyhraje už 15 četníků. Dále představujeme polynomiální algoritmus rozhodující hru na četníky a rychlého zloděje na intervalových grafech a jako nástroj zobecňujeme problém defenzivní dominance a nabízíme pro něj polynomiální algoritmus na intervalových grafech. Nakonec navrhujeme a prozkou- máváme zobecnění stromové hloubky, her na maršály a zloděje a grafových minorů na hypergrafy a hypergrafové páry.
|
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Smrž, Otakar (oponent)
V práci se zabýváme variantou tzv. hry na četníky a zloděje s nekonečně rychlým zlodějem a jejími vztahy s ostatními podobnými hrami. Srovnáváme tzv. vrtulníkovou hru charakterizující tree-width, klasickou verzi hry na četníky a zloděje a varianty s různě rychlými zloději. U varianty s nekonečně rychlým zlodějem rozebíráme její složitost a charakterizujeme všechny grafy, kde vyhrává jeden četník. Jako hlavní výsledek ukazujeme polynomiální algoritmus rozhodující hru na intervalových grafech a zodpovídáme tak otevřenou otázku z článku Fomin a kol.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. V důkazu polynomiality rozhodovacího problému zavádíe novou, ekvivalentní pomocnou hru na intervalové reprezentaci grafu, o jejímž rozhodování ukážeme, že je polynomiální. Ekvivalence her je dokázána technikou redukcí herních strategií.
|
|
|
Numerické simulace deformací visko-elastických materiálů, zejména asfaltu
Kratochvíl, Jan ; Málek, Josef (vedoucí práce) ; Rajagopal, K.R. (oponent)
In this thesis we deal with numerical simulations for flows of viscoelastic fluids. First, we introduce two models for viscoelastic fluids: (i) the Oldroyd-B, which is a classical model for viscoelastic fluids and (ii) a new nonlinear model which might be thought of as a generalization of Oldroyd-B to the case of large elastic deformations. Then, the flow at three different situations is discussed. The first of them is stress relaxation in parallel plate flow, which is an example of a 1D problem. The second one is a 4:1 planar contraction flow, which is a standard benchmark for viscoelastic flows. The third problem is stress relaxation in axially symmetric cylinder flow, which is solved as a 1D as well as a 2D problem. If it is possible, the problems are solved analytically, otherwise they are solved numerically with the aid of the finite element method using the software Comsol Multiphysics 3.3. Experimental data that document the stress relaxation of asphalt are available in the cylindrical geometry. Thus, finally, these data are fitted using both considered models.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (vedoucí práce) ; Telle, Jan Arne (oponent) ; Obdržálek, Jan (oponent)
Název práce: Parametrizovaná složitost Autor: Ondřej Suchý Katedra (ústav): Katedra aplikované matematiky Školitel: Prof. RNDr. Jan Kratochvíl, CSc. e-mail školitele: honza@kam.mff.cuni.cz Abstrakt: Tato práce se zabývá parametrizovanou složitostí NP-těžkých grafo- vých problémů. Zkoumáme složitost problémů v různých scénářích, vzhle- dem k rozličným parametrům a jejich kombinacím. Naším cílem je spíše rozlišit v tomto mnohorozměrném smyslu, zda daný parametr dělá problém parametrizovaně dostupným, nebo nedostupným, než představit algorit- mus, který dosahuje nejlepší možné časové složitosti. V otázkách, které studujeme, je typicky parametr první volby neúspěšný a tak využíváme méně standardních parametrů. První zkoumaná množina problémů je společným zobecněním mnoha dobře známých a prostudovaných problémů dominance a nezávislosti. Navrhu- jeme zde použít duální parametrizaci a ukážeme, že narozdíl od standardní parametrizace velikostí řešení, tato parametrizace dokáže ohrančit nevyh- nutelnou kombinatorickou explozi. Další studované problémy jsou analogií Steinerova problému v orientovaných grafech. Parametrizace pomocí počtu terminalů se jeví jako dříve neprobádaná alternativa v...
|
|
| |
|
|
Výpočetní složitost v teorii grafů
Herman, Jan ; Kratochvíl, Jan (vedoucí práce) ; Flusser, Jan (oponent)
Seidelovo přepnutí je grafová operace, která danému grafu G a jeho vrcholu v přiřadí graf, vzniknuvší z G záměnou hran vycházejících z v za nehrany a naopak. Graf H je přepnutím G, pokud lze H získat z G posloupností přepnutí jeho vrcholů. V této práci nejprve uvedeme známé výsledky týkající se výpočetní složitosti problémů, zda pro daný graf G existuje jeho přepnutí ležící v dané třídě grafů g. Dále se pro různé třídy grafů 9 zabýváme charakterizací třídy všech grafů přepnutelných do (} pomocí minimálních zakázaných indukovaných podgrafů. Uvedeme úplnou charakterizaci třídy grafů přepnutelných na disjunktní sjednocení housenek, resp. částečná párování pomocí zakázaných podgrafů. Dokážeme také, že třída grafů, které se dají přepnout na chordální, má nekonečně mnoho neizomorfních zakázaných podgrafů. Nakonec se zabýváme souvislostí Seidelova přepnutí a jiných operací na grafech respektive jejich třídách.
|
|
|
Drawing geometric graphs on red-blue point sets
Soukup, Jan ; Kynčl, Jan (vedoucí práce) ; Kratochvíl, Jan (oponent)
Nechť B je množina modrých bodů v rovinně a R je množina červených bodů v rovinně. Navíc předpokládejme, že R ∪ B je v obecné poloze. Geometrický graf je graf nakreslený v rovinně, jehož hrany jsou nakresleny pomocí úseček. Naším cílem je prozkoumat nekřížící se dobře obarvené geometrické grafy nakreslené na množinu bodů B ∪ R. Ukážeme, že pokud ||B| − |R|| ≤ 1 a pokud podmnožina vrcholů z R tvoří vrcholy mnohoúhelníka oddělující množinu B, ležící uvnitř, od zbytku množiny R, ležící vně, tak existuje nekřížící se dobře obarvená geometrická cesta na bodech B ∪ R procházející všechny tyto body. Pokud množina B ∪ R leží na kružnici, tak velikost největší nekřížící se dobře obarvené cesty je úzce spojená s velikostí největšího separovaného párování. Sepa- rované párování je nekřížící se dobře obarvené geometrické párování v němž jdou všechny hrany protnou jednou přímkou. Diskrepance množiny R ∪ B je největší možný rozdíl mezi velikostmi barevných tříd podmnožiny bodů tvořící interval na kružnici. Ukážeme, že když je diskrepance nejvýše 2, tak existuje separované párování pokrývající asymptoticky 4 5 všech bodů. V důkazu použijeme spojitost separovaných párování s nejdelšími společnými podposloupnostmi mezi dvěma binárními posloupnostmi, ve kterých symboly odpovídají barvám. 1
|
|
|
Partial representation extension for subclasses of interval graphs
Onduš, Daniel ; Kratochvíl, Jan (vedoucí práce) ; Jelínek, Vít (oponent)
Problém rozširovania čiastočných reprezentácii pre intervalové grafy rozhoduje, či je možné reprezentáciu niekoľkých vrcholov rozšíriť na reprezentáciu celého grafu. V tejto práci nadviažeme na výsledok Klavíka a kol., ktorí dokázali, že REPEXT je pre triedy vlastných a jednotkových intervalových grafov rozhodnuteľný v po- lynomiálnom čase. Popíšeme vlastnosti PI± a U± grafov a ich reprezentácií, a predstavíme algorit- mus rozhodujúci REPEXT pre tieto triedy v polynomiálnom čase. V priebehu práce charakterizujeme vzťahy medzi indukovanými K1,3 v grafe a ukážeme že pre každý K1,3 vieme vybrať otvorený vrchol. Tiež definujeme pojmy reprezentácií rovnakých typov zoradenia a lokálne podobných reprezentácií ako aj vynútené a lokálne vynútené uzavreté (otvorené) intervaly. Tieto pojmy sú kľú- čové pri rozširovaní čiastočných reprezentácií tried intervalových grafov, ktoré pri- púšťajú rôzne typy intervalov v jednej reprezentácii. Charakterizujeme vynútené a lokálne vynútené uzavreté intervaly pre U± grafy použitím celočíselných me- dzier v predreprezentácii a skonštruujeme spodné odhady pre najpravejšie konce komponentov v polynomiálnom čase.
|
|
|
Dostavba a úprava náměstí Míru v Brně
Mikel, Jakub ; Štěpánek, Martin (oponent) ; Kratochvíl, Jan (vedoucí práce)
Podoba a budoucí využití brněnského náměstí Míru je dlouhodobě diskutované téma mezi laickou i odbornou veřejností. Diskuse o využití tohoto významného prostoru se akcelerovala poté, co Ministerstvo obrany převedlo v roce 2003 nevyužívaný vojenský areál do majetku města Brna. Obyvatelé Masarykovy čtvrti, jehož je náměstí Míru pomyslným centrem, sepsali řadu protestních petic a uspořádali několik setkání s doporučujícími výstupy pro politickou reprezentaci města. Aktuálně připravovaná urbanisticko-architektonická soutěž, jejíž výsledky mají být zveřejněny v termínu odevzdání bakalářské práce, nabídne zajímavou konfrontaci se studentskými pracemi. Bakalářská práce prověří znalosti v oblastech navrhování městských veřejných prostorů, polyfunkčních domů, interiérového designu a technicko-konstrukčního řešení stavby.
|
host ::
RSS.