Zkouška 22.1. Hubička

Pokračování přednášky TIN060 Algoritmy a datové struktury I
666
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 23. 1. 2020 00:59
Typ studia: Informatika Bc.

Zkouška 22.1. Hubička

Příspěvek od 666 »

1. Definujte P, NP třídu problémů, definujte NP-úplné problémy, napište Cookovu větu(bez důkazu), příklad a důkaz NP-úplného problému (s využitím Cookovy věty).
2. Sestavte hradlovou síť, která pro 2 n-bitová čísla rozhodne, které je větší.
3. Permanent matice se počítá jako determinant matice, ale všechny jeho členy jsou kladné. Jak zjistit, jestli pro zadanou nula jedničkovou matici je permanent rovný nule.
Dobrá víla

Re: Zkouška 22.1. Hubička

Příspěvek od Dobrá víla »

Řešení dvojky už tu myslím někde je, tak aspoň něco k trojce.

Byl to úkol na nalezení dokonalého párování. Stačí si uvědomit ze je nutné najít jedinou permutaci pozic prvků, kde ani na jedné nebude nula.
Tedy jedna partita budou řádky matice, druhá sloupce, a každý řádek napojíme na ty sloupce, kde jsou v něm nenulové hodnoty. Pak už stačí v tomto grafu najít párování, pokud existuje tak je permanent nenulový.
Odpovědět

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