Velice zajímavý předmět, který se zabývá řešením P a NP problémů. Díky dvojici Schmidt + Kordík patřil k nejlepším
předmětům v semestru.
Úlohy
- úloha 1 - batoh 1 — řešení 0/1 problému batohu hrubou silou
- úloha 2 - kýble — heuristika řešící zobecněný problém dvou kýblů
- úloha 3 - batoh 2 — řešení 0/1 problému batohu metodou větví a hranic, dynamického programování a heuristikou podle poměru cena/hmotnost s testem nejcennější věci
- úloha 4 - experiment — hodnocení algoritmů pro řešení problému batohu
- úloha 5 - batoh 4 — simulované ochlazování (pokročilá iterativní metoda)
Semestrální práce
Vyvrcholení předmětu v podobě naprogramování pokročilé heuristiky pro problém SAT.
- SAT — řešený pomocí simulovaného ochlazování