Zkouška - 13.12.2019 Hubička

Pokračování přednášky TIN060 Algoritmy a datové struktury I
spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Zkouška - 13.12.2019 Hubička

Příspěvek od spidoosho »

1. Popsat Goldbergův algoritmus, správnost + časová složitost [10 bodů]

2. Navrhněte hradlovou síť, která porovná dvě n-bitová čísla. (log n) [5 bodů]

3. Navrhněte algoritmus, který pokruje šachovnici s dírami dominem (2x1), aby žádné domino nečouhalo ze šachovnice nebo z děr. (průvodce 329/4) [5 bodů]

(BONUS) 4. Navrhněte dynamickou datovou strukturu, která po změne jednotlivých znaků v textu řekne, jestli obsahuje jehlu.
ZabudolSomHeslo

Re: Zkouška - 13.12.2019 Hubička

Příspěvek od ZabudolSomHeslo »

1. Popísať Dinica - algoritmus, čas, pamäť, stačila mu intuícia
2. Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 2 P ? Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 4 NP ?
3. Nájsť v texte najdlhšie fibonacciho slovo

Bonusovku som ani nečítal, možno by mohol niekto doplniť.
Remi

Re: Zkouška - 13.12.2019 Hubička

Příspěvek od Remi »

Bonusovka byla pro obě skupiny zhruba stejná.
Odpovědět

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