Zkouška 15.01.2016 - Mareš

Pokračování přednášky TIN060 Algoritmy a datové struktury I
_Honza_

Zkouška 15.01.2016 - Mareš

Příspěvek od _Honza_ »

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:
1) Zjistit, jak rychle běží Goldbergův algoritmus na síti s jednotkovými kapacitami
2) Napsat komparátorovou třídící síť.
3) 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í)"


https://cs.wikipedia.org/wiki/Probl%C3% ... %ADk%C5%AF
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“