Název: Semidefinitní programování v kombinatorické optimalizaci
Další názvy: Semidefinite programming in combinatorial optimization
Autoři: Špaček, Ondřej
Vedoucí práce/školitel: Čada Roman, Doc. Ing. Ph.D.
Oponent: Kaiser Tomáš, Prof. RNDr. DSc.
Datum vydání: 2020
Nakladatel: Západočeská univerzita v Plzni
Typ dokumentu: diplomová práce
URI: http://hdl.handle.net/11025/55395
Klíčová slova: kombinatorická optimalizace;semidefinitní programování;aproximační algoritmus;vektorové programování;shannonova kapacita grafu;lovászova theta funkce;max cut;max k-cut;kapacitní max k-cut
Klíčová slova v dalším jazyce: combinatorial optimization;semidefinite programming;vector programming;approximation algorithm;shannon capacity of the graph;lovasz theta function;max cut;max k-cut;capacited max k-cut
Abstrakt: Diplomová práce se zabývá využitím semidefinitního programování v kombinatorické optimalizaci. V první části je shrnuta teorie, která je potřebná k práci v této oblasti. V části druhé se zabýváme Shannonovou kapacitou grafu, Lovászovou $\vartheta$ funkcí a úlohou maximálního řezu. Zmíněné algoritmy jsou implementovány a testovány v programovacím jazyce Python 3.
Abstrakt v dalším jazyce: Thesis deals with semidefinite programming in combinatorial optimization. The first part is summarizes the theory needed to work in this field. In the second section we are dealing with Shannon capacity of the graph, Lovasz $\vartheta$ function, and with MAX CUT problem. The mentioned algorithms are implemented and tested in the Python 3 programming language.
Práva: Plný text práce je přístupný bez omezení
Vyskytuje se v kolekcích:Diplomové práce / Theses (KMA)

Soubory připojené k záznamu:
Soubor Popis VelikostFormát 
diplomova_prace.pdfPlný text práce1,39 MBAdobe PDFZobrazit/otevřít
PO_Spacek.pdfPosudek oponenta práce738,2 kBAdobe PDFZobrazit/otevřít
PV_Spacek.pdfPosudek vedoucího práce632,73 kBAdobe PDFZobrazit/otevřít
P_Spacek.pdfPrůběh obhajoby práce158,51 kBAdobe PDFZobrazit/otevřít
dp_ospacek.zipVŠKP - příloha1,93 MBZIPZobrazit/otevřít


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/55395

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.