Zkouška - Mareš 14.1.2019

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Joffrey
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 26. 5. 2018 14:00
Typ studia: Informatika Bc.

Zkouška - Mareš 14.1.2019

Příspěvek od Joffrey »

1/Goldberg: algoritmus, invarianty, lemmata. Mares potom kazdemu vybere jedno lemma na dokazani
2/Najit co nejdelsi prefix retezce, ktery je zaroven jeho suffixem (tj. pro slovo ABCXYZABC tomu bude odpovidat retezec "ABC"), neboli co nejdelsi zacatek slova, ktery se nachazi take na jeho konci
3/Dokazte, ze Nezavisla mnozina je NP-uplny problem i za podminky deg(v)=<4

Reseni:
2/ Sestrojit KMP automat a nahlednout na zpetnou hranu vedouci z posledniho stavu
3/Prevest 3,3-SAT na Nezavislou mnozinu
Odpovědět

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