|
|
Přeurčené soustavy intervalových lineárních rovnic
Horáček, Jaroslav ; Hladík, Milan (vedoucí práce)
Tato práce se zabývá přeurčenými soustavami intervalových lineárních rovnic. První část se skládá z úvodu do intervalové aritmetiky a intervalové lineární algebry a základní teorie intervalových lineárních systémů. Ve druhé části jsou popsány různé metody řešení přeurčených intervalových lineárních systémů. Řešením přeurčeného intervalového systému chápeme sjednocení všech řešení všech podsystémů. Jsou zde diskutovány známé i naše varianty algoritmů. Představíme naši vlastní metodu podčtverců. Všechny zmíněné metody jsou implementovány do jednoho toolboxu pro Matlab. Metody jsou otestovány na řešitelných a neřešitelných přeurčených systémech. Pro řeši- telné systémy testujeme obálku řešení, čas a speciální vlastnosti metod. Pro neřešitelné systémy testujeme detekci neřešitelnosti. Na konci této práce po- skytneme základní úvod do systému Intlab. 1
|
|
|
Metody na výpočet optimálních hodnot intervalového lineárního programování
Král, Ondřej ; Hladík, Milan (vedoucí práce) ; Novotná, Jana (oponent)
Tato práce pojednává o problému hledání intervalu, ve kterém se m·žou nacházet optimální hodnoty účelové funkce intervalového lineárního programu, takzvaný rozsah optimální hodnoty (optimal value range). ešení toho pro- blému m·že být v určitých případech redukováno na řešení několika lineárních program·, obecně se ale jedná o těžký problém. Po seznámení s intervalovou aritmetikou a rozšířením lineárního programování na intervalové si zavedeme d·ležité množiny a jejich vlastnosti, B-stabilitu a další podproblémy s tím souvi- sející. Rozšíříme pojem B-stability na generalizované intervalové lineární progra- mování a budeme se věnovat metodám na výpočet rozsahu optimálních hodnot a jejich numerickému porovnání na náhodných soustavách. Cílem bude dané me- tody naimplementovat pomocí MATLAB/INTLAB a na základě provedených test· vytvořit jedinou funkci, která bude problém řešit, pokud možno efektivně. 1
|
|
|
Pole hodnot intervalové matice
Ivičič, Michal ; Hladík, Milan (vedoucí práce) ; Tichý, Petr (oponent)
Pole hodnot matice je množina komplexních čísel, která zapouzdřuje vlastní čísla ma- tice. Používá se například k odhadu maticové normy. V práci se zabýváme polem hodnot intervalové matice. V teoretické části vyšetřujeme jeho vlastnosti. Dokazujeme například, že je NP-těžké zjistit, zda daný bod do pole hodnot patří. Na příkladu ukazujeme, že pole hodnot intervalové matice není nutně konvexní. Popisujeme také dva algoritmy na vy- kreslení konvexního obalu pole hodnot. Oba se kvůli velké časové složitosti hodí jen pro matice malých rozměrů. Uvádíme tak i polynomiální algoritmus na vykreslení horního od- hadu pole hodnot intervalové matice. V praktické části algoritmy implementujeme jako funkce v jazyce Matlab. 1
|
|
|
Interval linear and nonlinear systems
Horáček, Jaroslav ; Hladík, Milan (vedoucí práce) ; Garloff, Jürgen (oponent) ; Ratschan, Stefan (oponent)
Nejprve představíme základní aspekty intervalové analýzy, role intervalů a jejich aplikace. Poté popíšeme různé třídy intervalových matic a popíšeme je- jich vztahy. Tato látka představuje základ pro jednotící téma celé práce - řešení intervalových lineárních soustav. Představíme a porovnáme několik metod pro řešení čtvercových a přeurčených intervalových soustav. Pro čtvercové soustavy představíme novou shaving me- todu, pro přeurčené soustavy představíme nové schéma podčtverců. Diskutujeme detekci neřešitelnosti a řešitelnosti soustav a porovnáme několik polynomiálních podmínek. Dokážeme, že dvě nejsilnější podmínky jsou ekvivalentní za určitého předpokladu. Řešení intervalových lineárních soustav je poté použito řešení ostat- ních problémů v této práci. Zabýváme se výpočtem obálky determinantu intervalových matic. Dokážeme NP-těžkost relativní i absolutní aproximace. Navrhneme novou metodu založenou na řešení čtvercových intervalových soustav a Kramerově pravidlu. Charakterizu- jeme rozličné třídy matic, u kterých lze spočítat meze determinantu v polynomi- álním čase. Řešení soustav rovnic je též použito k výpočtu lineární a nelineární regrese pomocí nejmenších čtverců. Ta je poté aplikována na reálná medicínská data z analýzy plicních funkcí. Výsledky produkují několik potenciálně klinicky významných...
|
|
|
Monge property for interval matrices
Černý, Martin ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Tato práce je prvním průzkumem oblasti intervalových matic s Mongeovou vlastností. Zabývá se charakterizacemi a vlastnostmi dvojice tříd matic - třídy intervalových silně Mongeových matic a třídy intervalových slabě Mongeových matic. V práci je představeno několik metod na rozpoznávání a rekonstrukci těchto matic a následně prozkoumána jejich aplikace v problémech kombina- torické optimalizace a v problému související s výpočetní geometrií.
|
|
|
Přeurčené soustavy intervalových lineárních rovnic
Horáček, Jaroslav ; Hladík, Milan (vedoucí práce)
Tato práce se zabývá přeurčenými soustavami intervalových lineárních rovnic. První část se skládá z úvodu do intervalové aritmetiky a intervalové lineární algebry a základní teorie intervalových lineárních systémů. Ve druhé části jsou popsány různé metody řešení přeurčených intervalových lineárních systémů. Řešením přeurčeného intervalového systému chápeme sjednocení všech řešení všech podsystémů. Jsou zde diskutovány známé i naše varianty algoritmů. Představíme naši vlastní metodu podčtverců. Všechny zmíněné metody jsou implementovány do jednoho toolboxu pro Matlab. Metody jsou otestovány na řešitelných a neřešitelných přeurčených systémech. Pro řeši- telné systémy testujeme obálku řešení, čas a speciální vlastnosti metod. Pro neřešitelné systémy testujeme detekci neřešitelnosti. Na konci této práce po- skytneme základní úvod do systému Intlab. 1
|
|
|
Computational Bounded Rationality
Černý, Jakub ; Loebl, Martin (vedoucí práce) ; Hladík, Milan (oponent)
Tato závěrečná práce formalizuje model omezené racionality hráčů v sekvenčních hrách nazvaný herní schémata. Ve zkoumaném modelu jsou strategie reprezentované strukturou skládající se z konečného automatu a dvou výpočetních funkcí. Zatímco konečný automat reprezentuje hráčovu strukturovanou pamět', výpočetní funkce reprezentují jeho schopnost efek- tivně abstrahovat danou hru. Schémata jsou realizacemi čistých strategií a mohou být hráčem implementovány za účelem hraní sekvenční hry. Práce ukazuje jak zkonstruovat korektně hrající schéma pro jakoukoli strategii v jakékoli sekvenční hře s vícero hráči a jak určit jeho složitost. Dokazuje, že ekvilibrium vždy existuje a jeho výpočet je PPAD-těžký. Navíc práce defin- uje třídu efektivně reprezentovatelných strategií, pomocí které lze spočítat MAXPAY-EFCE v polynomiálním čase. 1
|
|
|
Determinanty intervalových matic
Matějka, Josef ; Horáček, Jaroslav (vedoucí práce) ; Hladík, Milan (oponent)
Tato práce se zabývá determinanty intervalových matic. Po úvodu do inter- valové aritmetiky se práce věnuje složitosti výpočtu těsné obálky intervalových determinantů, ukazuje v jaké složitostní třídě se tento problém nachází, dále pak složitosti aproximace daného problému, aproximaci jak s relativní tak i s absolutní chybou. Další kapitolou jsou různá předpodmínění matice, která mohou vést k těsnějším výsledkům. Po té, co rozebereme předpodmiňovaní matic představíme několik metod pro výpočet determinatnu, počínaje Gaussovou eliminací a vyu- žíváním Cramerova pravidla konče. Též se zastavíme i u speciálních tříd matic, jakými jsou symetrické, tridiagonální a Toeplitzovské matice. Nakonec předve- dené metody otestujeme. 1
|
|
|
Evaluation of interval polynomials
Firment, Roman ; Hladík, Milan (vedoucí práce) ; Hartman, David (oponent)
V práci sa zaoberáme nájdením obálky oboru hodnôt reálneho a intervalového polynómu o jednej premennej nad intervalom. Prezentujeme funkčné formy pre re- álne polynómy, ktoré následne implementujeme v prostredí Matlab používajúceho intervalovú aritmetiku toolboxu INTLAB. Tie nám umožňujú efektívne spočítať obálku polynómu. V teoretickej časti je taktiež predstavený prevod umožňujúci použiť ľubovoľnú formu počítajúcu obálku reálneho polynómu na výpočet obálky intervalového polynómu. Súčasťou práce je aj numerické porovnanie jednotlivých metód. Na základe toho sú navrhnuté dve globálne funkcie riešiace náš prob- lém aplikujúce niektorú z foriem. Užívateľ má možnosť nepriamo ovplyvniť voľbu formy nepovinným parametrom špecifikujúci stratégiu výpočtu, ktorá definuje rýchlosť výpočtu a veľkosť výsledného nadhodnocovania.
|
|
|
The optimal solution set of interval linear programming problems
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Určení množiny všech optimálních řešení lineárního programu s intervalovými daty je jedním z hlavních problémů intervalové optimalizace. Prezentujeme dvě metody založené na dualitě v lineárním programovaní, které jsou využívány k aproximaci optimální množiny. Dále je také navržena dekompoziční metoda založená na komplementaritě omezujících podmínek. Tato metoda poskytuje přesný popis optimální množiny pro problémy s pevnou maticí koeficientů. Druhá část práce se zabývá topologickými a geometrickými vlastnostmi optimální množiny. V této části zkoumáme postačující podmínky pro uzavřenost, omezenost, souvislost a konvexitu. Navíc je dokázáno, že testování omezenosti je co-NP-těžké pro problémy s omezeními ve formě nerovností a volnými proměnnými. Silnější výsledky jsou odvozeny pro některé speciální třídy intervalových lineárních programů, například programy s pevnou maticí koeficientů. Dále studujeme efekt transformací běžně používaných v lineárním programování na intervalové problémy, což umožňuje přímé zobecnění některých výsledků na různé typy intervalových lineárních programů. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.