Cvičeni ADS2, LS 2017/18, Ut 15:40 S6


Náhradní příklady na konci.


zadano  3.10.   31.10.  5.12		19.12
            17.10   21.11   12.12     
	1   2   3  (4)  5   6	SUM	7   SUM2  
JW	5   5	4	5   3	22 ZAP	5
VS	5	5-	5   3	18 ZAP	4
MJ	4   5	4	5-*	13+5	3m  21 ZAP:13.1.
KB	4			 4
JŠ	5   5-	4*	    3m	13+4 ZAP 2-
LT	5   4-	5-	3   3	20 ZAP	4
AK	5   4		4   3-m	16 ZAP	2m
YY/JJ	5-  4	5-	5   3m	22 ZAP
PD	4   5	4	5-  3	21 ZAP	0m
PJ	5   4	4	4   3-	20 ZAP	5-m
RCh	5-  5+		4   3-	17 ZAP	5-
JJo	5   5	5	3   3	21 ZAP
OK	5		4	 9		4priklady
MVas	5   4	5	5*  4*	14+9	5   28 ZAP:13.1.
LH	4+  3m	3	    3-m	13	1m  14	2priklady
DJ	4   4m	5	    3-m	16 ZAP	1m
MVe	5   5	5	4   3	22 ZAP
FH	5   5	4	    3m	17 ZAP	5-m
MVj	5-  5-m	3m	    3-m	16 ZAP	4m
MM	3   1	5	5m  0m	14	2	1priklad
JF	4m  5	5		14		1priklad
JJu	4m  5	5-	5   3	22 ZAP	4
ES	4m			 4
MVal		5-*	5   2-  14*	4	1priklad
Anonym		4:JS
			


Maily zpracovány 12.1.2018

Pokud odevzdavate mailem, do souboru, tj. přílohy, napište:
- ADS2
- vaše jméno
- číslo úkolu (nebo datum zadání)


Ulohy: 0-5 bodu
Celkem: 25 bodu, (po DC6 max. 25b, pozadavek 16b)
Na zapocet: 16 bodu (2/3 z moznych bodu)

-: malé minus
m: mailem
*: zapsáno dodatečně
(default datum pro SIS: 10.1.2018)


    zadano
DC1  3.10.	Aho-Corasick pro XEROX, MIX, MIXER, KOMIX
DC2 17.10.	Navrhnete algoritmus pro určení hranové k-souvislosti a určete jeho složitost 
		(v závislosti na složitosti algoritmu pro toky)
DC3 31.10	Minireferat: Blokující tok ve vrstevnaté síti v O(n^2); odevzdat za 2 týdny
DC4 21.11.	Ukazte, ze pro antisymetricky vektor V=(a_0, a_1, .. a_{n-1}), kde a_0 a a_{n/2) 
		jsou realna cisla, a a_i=a_{n-i}* jsou komplexne sdruzena cisla, vyjde FT(V) 
		jako vektor realnych cisel. (Struktura vektoru: (r,b,c,d,r',d*,c*,b*), r a r' realna,
		b,c,d komplexni) ; po opraveni
DC5  5.12. 	Obsah nekonvexního mnohoúhelníku
DC6 12.12.	Polynomiální převod HAM na SAT
		HAM: instance je graf G, otázka: "existuje v G hamiltonovská kružnice?"
DC7 19.12.	Převody mezi HAM, HAMC, HAMCuv. (Každý převod za bod, max. 5 bodů)
		HAMC: instance je graf G, otázka: "existuje v G hamiltonovská cesta?" 
		HAMCuv: instance (G,u,v): graf a dva vrcholy; 
		  otázka: "existuje v G hamiltonovská cesta z u do v?"



-------------
Pokud nemate dost bodu (v sloupci SUM), vyreste (spravne) nahradni priklady, od prvniho.
Poslete do 2.2.2018 (Patek)

Nahradni priklady, kazdy za 2 body: (cisla prikladu jsou z mojich prikladu k cvicenim)
N1 Vynasobte 11 x 13 pomoci rychle FFT v Z_17, podle prikladu 38l.
N2 Prevedte nezavislou mnozinu na SAT, priklad 55.
N3 Aho-Corasikova pro "baroko, rokoko, oko, okr, brok", priklad 1f
N4 23a, pricitani k nule a k cislu n.