Matfyz Wiki
Tohle byl předtermín, a byli jsme v jeho kabinetě a na chodbě, takže každý dostal něco jiného.
Já měl:
Zjistit, jak rychle běží Goldbergův algoritmus na síti s jednotkovými kapacitami
Napsat komparátorovou třídící síť.
Vymyslet pseudopolynomiální algoritmus řešící problém dvou loupežníků.
"Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist ( oceněné věci) mezi 2 loupežníky, aby dostali oba věci ve stejné hodnotě.
Praktický příklad:
Mějme zadáno N čísel. Otázka zní: lze rozdělit zadaná čísla do dvou skupin tak, aby součet čísel v obou skupinách byl stejný (tj. aby se dva loupežníci mohli spravedlivě rozdělit o kořist N oceněných věcí)"