Original title: Kombinatorické úlohy o mincích
Translated title: Combinatorial problems with coins
Authors: Hamáček, Jan ; Slavík, Antonín (advisor) ; Fiala, Jiří (referee)
Document type: Master’s theses
Year: 2016
Language: cze
Abstract: 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
Keywords: coin system; Frobenius number; greedy algorithm; minimal representation; problems with coins; representability; representation count; Frobeniovo číslo; hladový algoritmus; minimální reprezentace; počet reprezentací; reprezentovatelnost; systémy mincí; úlohy o mincích

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/83103

Permalink: http://www.nusl.cz/ntk/nusl-352752


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses