Bakalářská práce

Algoritmické řešení úlohy lineárního programování v rovině

Algoritmic approach to linear programming in the plane

Jan Kovář, učo 323609
Anotace

Práce se zabývá maximalizací lineární funkce na průniku konečně mnoha polorovin. Je odvozen náhodnostní algoritmus k řešení tohoto problému, který je založen na iteračním principu postupného přidávání polorovin. Následně je analyzována jeho očekávaná časová složitost. Je dokázáno, že roste lineárně vzhledem k počtu polorovin obsažených v úloze. Součástí práce je také implementace algoritmu.

Abstract

The work deals with maximizing a linear function at the intersection of a fnite number of half-planes. A randomized algorithm solving this problem is derived. It is based on the principle of iteration, when the half-planes are progressively added. Subsequent analysis of the expected time complexity is provided. The proof that the expected running time increases linearly due to the number of half-planes contained in the problem is given. The work also includes an implementation of the algorithm.

Klíčová slova
lineární programování náhodnostní algoritmus optimalizace linear programming randomized algorithm optimization
Zadání práce
Úloha lineárního programování v rovině spočívá v nalezení maxima lineární funkce na průniku polorovin. Cílem práce je popsat a případně naprogramovat náhodnostní algoritmus pro řešení této úlohy a současně najít nějaké jeho aplikace.
Administrativní informace
Práce zkontrolována:
6. 6. 2011 08:36, doc. RNDr. Martin Čadek, CSc., učo 233
Plný text práce
1,2 MB / soubor PDF
Přílohy (2)
Jazyk práce
čeština čeština
Termín obhajoby
28. 6. 2011
Práce byla úspěšně obhájena

Vedoucí

doc. RNDr. Martin Čadek, CSc., učo 233
ÚMS Ústavy PřF MU

Oponent

Mgr. Milan Werl, Ph.D.
abs PřF MU

Literatura

  • DE BERG, Mark; Otfried CHEONG; Marc VAN KREVELD a Mark OVERMARS. Computational geometry. 3rd ed. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-77973-5.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Aplikovaná matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.