Algoritmické řešení úlohy lineárního programování v rovině
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ě...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Čeština |
| Vydáno: |
2011
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/323609/prif_b/ |
| Shrnutí: | 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. 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. |
|---|---|
| Popis jednotky: | Vedoucí práce: Martin Čadek |
| Fyzický popis: | 46 l. + CD |