Název: Kombinatorické úlohy o mincích
Překlad názvu: Combinatorial problems with coins
Autoři: Hamáček, Jan ; Slavík, Antonín (vedoucí práce) ; Fiala, Jiří (oponent)
Typ dokumentu: Diplomové práce
Rok: 2016
Jazyk: cze
Abstrakt: Práce se zabývá otázkami reprezentace zvolené částky pomocí libovolného množství mincí předep- saného typu. V první kapitole odvozujeme vzorce pro počet nereprezentovatelných částek a hodnotu největší nereprezentovatelné částky pro dvoumincové systémy. Dále ukazujeme grafový algoritmus pro výpočet Frobeniova čísla a d·kaz NP-úplnosti rozhodovacího problému reprezentovatelnosti zvolené částky v systému s více mincemi. V druhé kapitole se zabýváme výpočtem počtu reprezentací částky zvláš' v systémech o dvou nebo více mincích. Ve třetí kapitole se věnujeme otázce, zda lze ve zvoleném systému mincí použít hladový algoritmus pro nalezení reprezentace částky pomocí nejmenšího možného množství mincí. Poslední kapitola obsahuje sbírku řešených logických úloh o mincích. 1
Klíčová slova: Frobeniovo číslo; hladový algoritmus; minimální reprezentace; počet reprezentací; reprezentovatelnost; systémy mincí; úlohy o mincích; coin system; Frobenius number; greedy algorithm; minimal representation; problems with coins; representability; representation count

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/83103

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-352752


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce