|
Grafy, grafové algoritmy a jejich užití
Venerová, Lenka ; Dostál,, Jiří (oponent) ; Bobalová, Martina (vedoucí práce)
Bakalářská práce se primárně zabývá problematikou grafů a grafových algoritmů. Jedná se především o vysvětlení a rozšíření daného tématu. Velice často jsou před nás kladeny problémy, které, ač nevědomky, řešíme využitím znalostí grafových algoritmů. Dílčím cílem mojí práce je proto demonstrovat aplikaci některých těchto metod v oblasti řešení distribučních úloh.
|
| |
|
Evoluční resyntéza kombinačních obvodů
Kocnová, Jitka ; Sekanina, Lukáš (oponent) ; Vašíček, Zdeněk (vedoucí práce)
Diplomová práce se zabývá resyntézou kombinačních obvodů pomocí evolučních principů. První část se zabývá logickou syntézou a jejími problémy, evoluční syntézou a výhodami evolučního přístupu, a taktéž jsou zmíněny některé existující syntézní nástroje. V druhé části jsou pak přiblíženy vybrané grafové algoritmy a jejich možné využití v navrhovaném programovém rozšíření pro vybraný syntézní nástroj. Zde je také popsán návrh rozšíření a jeho samotná implementace. Třetí část se zabývá testováním vzniklého rozšíření. Čtvrtou částí je závěr shrnující získané poznatky a dosažené výsledky.
|
|
New Bounds for Combinatorial Problems and Quasi-Gray Codes
Das, Debarati ; Koucký, Michal (vedoucí práce) ; Vassilevska Williams, Virginia (oponent) ; Porat, Ely (oponent)
ABSTRAKTNÍ: Tato práce má dvě části. V první části studujeme řadu kombinatorických problémů souvisejících s řetězci, Booleovskými maticemi a grafy. Pro dané dva řetězce x a y je jejich editační vzdálenost nejmenší počet operací vložení znaku, smazání znaku a náhrada znaku, které jsou potřeba na přeměnu řetězce x na y. V této práci předkládáme algoritmus, který spočítá konstantní aproximaci editační vzdálenosti vpravdě sub-kvadratickém čase. S využitím těchto myšlenek zkonstruujeme další sub-kvadratický algoritmus, který umí nalézt výskyty vzoru P v zadaném textu T, když hledáme i výskyty s malou editační odchylkou. Dále studujeme problém násobení Booleovských matic (BMM) nad Booleovským polo-okruhem. Pro tento problém zavedeme dva kombinatorické výpočetní modely a ukážeme, že v těchto modelech BMM vyžaduje Ω(n3 /2O( √ log n) ) a Ω(n7/3 /2O( √ log n) ) práce. Dále též představíme konstrukci řídkého pod-grafu, který zachovává vzdálenost určitého vrcholu od všech ostatních, ikdyž dojde k celkovému navýšení cen hran o kon- stantu. V druhé části práce studujeme efektivní konstrukci Grayových kódů. Ukážeme konstrukci prostorově optimálních kódů nad abecedou liché velikosti se složitostí...
|
|
Evoluční resyntéza kombinačních obvodů
Kocnová, Jitka ; Sekanina, Lukáš (oponent) ; Vašíček, Zdeněk (vedoucí práce)
Diplomová práce se zabývá resyntézou kombinačních obvodů pomocí evolučních principů. První část se zabývá logickou syntézou a jejími problémy, evoluční syntézou a výhodami evolučního přístupu, a taktéž jsou zmíněny některé existující syntézní nástroje. V druhé části jsou pak přiblíženy vybrané grafové algoritmy a jejich možné využití v navrhovaném programovém rozšíření pro vybraný syntézní nástroj. Zde je také popsán návrh rozšíření a jeho samotná implementace. Třetí část se zabývá testováním vzniklého rozšíření. Čtvrtou částí je závěr shrnující získané poznatky a dosažené výsledky.
|
| |
|
Grafy, grafové algoritmy a jejich užití
Venerová, Lenka ; Dostál,, Jiří (oponent) ; Bobalová, Martina (vedoucí práce)
Bakalářská práce se primárně zabývá problematikou grafů a grafových algoritmů. Jedná se především o vysvětlení a rozšíření daného tématu. Velice často jsou před nás kladeny problémy, které, ač nevědomky, řešíme využitím znalostí grafových algoritmů. Dílčím cílem mojí práce je proto demonstrovat aplikaci některých těchto metod v oblasti řešení distribučních úloh.
|