1) Tridy NP, Cookova veta,ukazka NP uplnosti lib. problemu
2) Nejdelsi vodorovna usecka v nekonvexnim mnohouhekniku
3) Pro retezec A zjistit, zda existuje retezec B ze B^k=A pro k>1 (proste zjistit, zda lze A dostat napsanim nejakeho retezce B k krat za sebou)
ResenI a poznamky.
1) Chtel definice P, NP, NP tezke a NP uplne, Cookovu vetu (dukaz nechtel!!), vzit si nejaky problem a dokazat ze je NP uplny z cookovy vety (vybral jsem si 3-SAT) a zformulovat a dokazat lemmatko, ktere se pri tom vyuziva (kdyz K je v NP a L je NP uplne a L->K pak i K je NP uplne).
2) Zametani roviny primkou shora dolu. Prvni jsem si vsimnul, ze pokud se nekde v mnohouhelniku vyskytuje nejdelsi usecka, tak se stejna usecka vyskytuje nekde, kde protina bod mnohouhelniku. Takze staci zametat diskretne po bodech mnohouhelnika. Jakmile jsme v nejakem miste, tak mame prurez primkou, takze projdeme vsechny usecky, zjistime, zda je usecka uvnitr mnohuhelnika a pokud ano, tak si pamatujeme tu nejdelsi z nich. Casova slozitost je O(N^2) kde N je pocet bodu mnohouhelnika.
(Kdyz jsem sel za MJem s ulohami, tak jsem mu rikal, at tuhle ani necte, bo jsem si myslel, ze je to moc pomale, ale on si to stejne precetl a rekl mi, ze neco takoveho chtel a ze NlgN reseni ani neumi :) )
3) Pripad |A| = 1 je trivialni, necht dale |A|!=1
Sestrojime KMP automat retezce A a bud Z jeho zpetna funkce. Retezec A je indexovan od 1 do |A|
K = |A| - Z[|A|]
Prochazime retezec A odzadu od i = |A| do K+1
Pokud plati A == A[Z] a zaroven i - Z == K pak pokracujeme, jinak oznamime, ze neni periodicky.
Na to MJ docela dlouho koukal, pak mi na to rekl, ze je to krasne zbesily algoritmus a ze teda funguje. Jake je "oficialni" reseni netusim. Pointa algoritmu by mela byt v tom, ze pokud je retezec periodicky po K znacich, tak zpetna funkce posledniho znaku ukazuje na posledni znak predchozi periody, takze |A| - Z[|A|] je delka periody, kterou si zjistim na zacatku. A v cyklu uz jenom overuji, zda je retezec skutecne K-periodicky. Algoritmus je linearni.
Mel jsem vsechno az na definici tridy NP, kterou jsem nedokazal zformulovat spravne, takze za 1.
Jinak, pokud by to nekoho zajimalo, tak jeste pridavam naznak reseni na ulohu, ktera byla ve druhem predterminu.
Hradlová síť, která o dvojici binárních čísel A, B zjistí, zda je první větší než druhé.
Dela se to uplne stejne, jako scitani, akorat misto funkci kostantni 1, 0 a < (prenost) budeme mit funkce kostantni 1 (pro A>B), 0 (pro A<B) a = (rovnost, ktera se bude chovat uplne stejne jako prenos). Nove funkve se chovaji uplne stejne jako ty stare pro scitani, stejne se chova i skladani funkci
Pote nam staci udelat stejne jako u scitani, akorat staci udelat jen tu prvni cast (nevim ted, jak se ji rika).
Priklad:
Kód: Vybrat vše
1001 0101
0101 0111
------------
10== ==0=
1 = = 0
1 =
1