|
|
Demonstrace skákajících automatů
Růžička, Ladislav ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato práce se zabývá demonstrací nově zkoumaného výpočetního modelu pro popis formálních jazyků, a to skákajícího automatu. Místo souvislého čtení vstupního řetězce, jak je tomu u konvenčních konečných automatů, tak u skákajícího automatu je proveden skok přes nějaké symboly, a poté je přečten symbol. V této práci se zejména budeme zabývat hledáním praktického algoritmu pro určení problému členství vstupního řetězce do jazyka popsaného skákajícím automatem. Ukážeme, že problém členství může být redukován na problém hledání nějakého nezáporného celočíselného řešení pro formuli v Presburgové aritmetice bez kvantifikátorů. Z této formule jsme schopni jednoznačně definovat jazyk přijímaný skákajícím automatem. Najdeme podmnožinu takových skákajících automatů, pro které lze vyřešit problém členství v polynomiálním čase. Zmíníme se také, že předchozí formule lze převést na konečný automat s více čtecími hlavami. Bohužel pro problém členství obecného skákajícího automatu hledání nezáporné číselného řešení je nedostačující, nicméně metoda může zmenšit prohledávaný stavový prostor. Uvedeme další možné heuristiky, které výrazně urychlují výpočet problému členství pro obecné skákající automaty.
|
|
|
Demonstrace skákajících automatů
Růžička, Ladislav ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato práce se zabývá demonstrací nově zkoumaného výpočetního modelu pro popis formálních jazyků, a to skákajícího automatu. Místo souvislého čtení vstupního řetězce, jak je tomu u konvenčních konečných automatů, tak u skákajícího automatu je proveden skok přes nějaké symboly, a poté je přečten symbol. V této práci se zejména budeme zabývat hledáním praktického algoritmu pro určení problému členství vstupního řetězce do jazyka popsaného skákajícím automatem. Ukážeme, že problém členství může být redukován na problém hledání nějakého nezáporného celočíselného řešení pro formuli v Presburgové aritmetice bez kvantifikátorů. Z této formule jsme schopni jednoznačně definovat jazyk přijímaný skákajícím automatem. Najdeme podmnožinu takových skákajících automatů, pro které lze vyřešit problém členství v polynomiálním čase. Zmíníme se také, že předchozí formule lze převést na konečný automat s více čtecími hlavami. Bohužel pro problém členství obecného skákajícího automatu hledání nezáporné číselného řešení je nedostačující, nicméně metoda může zmenšit prohledávaný stavový prostor. Uvedeme další možné heuristiky, které výrazně urychlují výpočet problému členství pro obecné skákající automaty.
|
|
|
Optimalizace výroby potravinových produktů
Slámová, Dominika ; Sekničková, Jana (vedoucí práce) ; Kuncová, Martina (oponent)
Tématem bakalářské práce je optimalizace výroby potravinových produktů zaniklé společnosti ing. Petra Němce. Společnost se zabývala výrobou potravinových směsí pro pekárny, cukrárny, zmrzlinárny a gastronomii. Hlavním cílem práce je sestavit model k nalezení optimální struktury výroby za účelem maximalizace zisku a současně minimalizace nákladů a maximalizace tržeb. Dílčím úkolem je zjistit optimální počet vyrobených produktů a množství vyráběných směsí. Jednotlivá řešení jsou v práci popsána pomocí simplexové metody a celočíselného lineárního programování. Kompromisní řešení je získáno užitím vícekriteriálního programování. Splnění stanovených cílů a jejich zhodnocení jsou popsány v závěru práce.
|
|
|
Modifikované úlohy čínského listonoše - experimenty
Jelínek, Tomáš ; Fábry, Jan (vedoucí práce) ; Pelikán, Jan (oponent)
Diplomová práce popisuje modifikované úlohy čínského listonoše. Úlohy jsou řešeny pomocí (smíšeného) celočíselného lineárního programování. Modifikované úlohy i použitá metoda řešení (celočíselné programování) patří minimálně do NP složitých úloh. Práce analyzuje, porovnává a odhaduje výpočetní složitost jednotlivých modelů. Z této analýzy je vyvozena použitelnost (tj. řešitelnost v rozumnén čase) modelů pro řešení reálných úloh. Modely se primárně zaměřují na úlohy z městského prostředí, lze je tak aplikovat na problémy jako je optimalizace svozu komunálního odpadu nebo údržby silnic. Pro potřeby práce je naprogramován generátor grafů a zadání úloh.
|
host ::
RSS.