Skuska 20. 1. 2017 - Cepek

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Jankus

Skuska 20. 1. 2017 - Cepek

Příspěvek od Jankus »

Tri otazky na dve hodiny. Potom dve hodiny opravoval a potom bola ustna, ta trvala chvilku asi 3/4 hodiny. ale bolo nas asi len 5.
Zadanie pisomky bolo rovnake, ako uz v minulosti:
1) Triediaca siet pre paralelny mergesort, ktora zotriedi 8 prvkov na vstupe. Urcit hlbku a velkost (pocet hradiel)
2) Zadane komplexne cisla z_0 az z_(n-1). ulohou vytvorit v case O(n*log^2(n)) polynom stupna n, ktory ich bude mat ako svoje korene (nulove body).
3) Mame ciernu krabicku, ktora vie v polynomialnom case urcit splnitelnost formule v CNF. Najst pre zadanu formulu splnitelne ohodnotenie s pomocou tejto krabicky v polynomialnom case (vzhadom na dlzku formule)

Nastin rieseni:
1) Neuznaval (alebo ken ciastocne) Maresov bitonicky sort, ze sice triedi spravne, ale je to iny algoritmus, nez chcel. Je treba tam napisat ten jeho (to je ten isty ako Batcherov algoritmus, ktory je zmieneny v Maresovych skriptach). Popisal som tam tu rekurzivnu proceduru a podla nej sa lahko skonstruuje ta siet. Ma hlbku 6 a 19 komparatorov (bitonicky sort ich ma viac, tusim 24?).
2) Normalne by sa dalo zostavit n polynomov tvaru (x-z_i) a prenasobit ich, ale to by zabralo kvadraticky casu. Staci si ale uvedomit, ze pri vynasobeni dvoch polynomov ostavaju rovnake korene (nove korene su zjednotenie korenov prveho a druheho nasobeneho polynomu). Takze keby sme mali dva polynomy dlzky n/2, kde kazdy by mal za korene polku zo zadanych bodov, tak ich vynasobenim ziskame polynom dlzky n, ktory ma za korene vsetky zadane cisla. Tato uvaha vedie na rekurzivny algoritmus, ked si zadane cisla rozdelim na dve polky, rekurzivne spocitam prislusne polynomy, ktore ich maju za korene a tie vynasobim. Dno rekurzie je, ze ak n=1, teda mame zadane iba 1 cislo z_0, tak vratime polynom (x-z_0), ktory ma koren presne v z_0. Nasobit vieme vdaka FFT v case O(n*log(n)), co bude teda zlozitost jednej vrstvy rekurzie. Hlbka rekurzie bude log(n), lebo cisla vzdy delime na polku. Takze dohromady ziadany cas O(n*log^2(n))
3) Jednoducho pridavame k formuli postupne klauzule tvaru: v i-tom kroku F_i = F & x_i, kde x_i je i-ta premenna pre i=0..n-1, kde n je pocet premennych (tie si mozeme priechodom formule zistit). dame otestovat krabickou, ak je splnitelna, polozime F = F_i, nastavime si u seba a_i = 1, kde a_i je hodnota hladaneho splnitelneho ohodnotienia pre premennu x_i, a pokracujeme, inac polozime F = F & ( non x_i ) a a_i = 0. Po prejdeni vsetkych premennych vratime acka.
Zlozitost je O(n*k), kde k je ta polynomialna zlozitost krabicky, ak sme na zaciatku nemuseli prechadzat formulu, ak ano, tak O(f*k), kde f je dlzka formule, kazdopadne to bude vzdy polynomialne vzhladom k f (lebo n<f). Korektnost je myslim zrejma: ak je povodna formula splnitelna (co sme mohli predpokladat), tak aspon pre 1 ohodnotenie premennej x_i bude tiez splnitelna. takze ani netreba po nastaveni na 0 znovu testovat.

na ustnej som dostal Dinicov algoritmus, ako funguje + zlozitost (korektnost nechcel) a aproximaciu TSP s trojuholnikovou nerovnostou (taku tu ze vezmem min. kostru, obidem ju prehladavanim do hlbky, ocislujem vrcholy v pre-order poradi - bude to max. 2x horsie nez optimum, je to popisane v Maresovych skriptach).
Dalsie otazky boli napr. RSA ci to carry-look-ahead scitanie.
Odpovědět

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