Skúška 13.1

Caparzzo
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 18. 1. 2005 14:11
Typ studia: Informatika Bc.
Bydliště: Turzovka(SVK)
Kontaktovat uživatele:

Skúška 13.1

Příspěvek od Caparzzo »

Tak čo povedať...Možno som mal zase raz šťastie, že sa mi podarilo opísať čo to, takže aj keď binárne sčítanie, predsa len úspešne...Hoci piatok trinásteho, všimol som si, že dosť ľudí prešlo zo známkou v indexe, resp. na jeho papieri, keďže niektorí nemali zápočet...Tak veľa zdaru šetkým...
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

No... binarni scitani pry dost hnusny... nekolikrat pry skoncilo vyhozenim (nebyl jsem primym svedkem)... ja nastesti dostal Dinice :).
Jsem tam byl ted asi od 3... vypadalo to ze to tam bude az do (pozdniho) vecera... stravil jsem tam asi hodinu, z toho vic jak 3/4 jsem sedel a psal... pak prosel jen jeden z mych 3 papiru a zeptal se me na 2 dost nepravdepodobny veci... mou nesouvisle koktavou, ale vicemene spravnou odpoved vzal OK a nechal me projit :D.
Vypada to ze si chce overit jestli tomu clovek fakt ale fakt rozumi... takze se me ptal kolikrat max. se muze hrana vyhodit (rezerva := 0) a vratit zpet do rezidualniho grafu, taky jak se najdou hrany ktery lezi na nejkr. ceste zdroj->cil ... tyhle otazky ale budou asi dost nepredikovatelny :?
Plug 'n' Pray.
Uživatelský avatar
jaruch
Supermatfyz(ák|ačka)
Příspěvky: 376
Registrován: 5. 2. 2005 14:06
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od jaruch »

inak sa asi vykrystalizoval okruh otazok, toci furt dokola zhruba toto:
Dinitz
Goldberg
Voronoi diagram
RSA + (inverzny?) Fourier
previest dva NP-uplne problemy + Fourier
vyhladavanie v texte
scitacka
bitonicke triedenie
... mozno mi este nieco uniklo

Ja som dostal vyhladavanie v texte, napisal som mu Rabin-Karpa, Knuth-Morris-Pratta a Aha-Corasicka, zacal to citat, pri Rabin Karpovi som zabudol "mod p", tak sa ma k tomu snazil naviest nejak tak, ze "keby sme mali velke cisla, ako to napchame do pamate" a potom sa pytal, preco je lepsie mat to p vacsie a preco mensie, pri tom Knuthovi to chcel odo mna sformalizovat, ale ked tomu rozumiete, tak vas k tomu dokope... potom este chcel vediet preco je to O(n), ale to som nevedel odovodnit, tak za dva. Myslim, ze tato otazka sa celkom da.
A kombinacia NP+FFT=>4 v indexe
Tak vela stastia
Shit shit, who the fuck is shooting us?
I've got a universe to master...
Návštěvník

FFT, NP a Carry-look-ahead

Příspěvek od Návštěvník »

takze som dostal FFT a prevod jednej NP ulohy na druhu podal toho, co bolo na prednaske. som sa spyatl ci hociktorej na hociktoru a povedal, ze hej ale radsej si pozrite vsetky tri prevody. sa celkom daju niektore. ked nakreslite tie obrazky na prednaske a popisete co znamenaju a co vlastne riesi ktora NP uloha z tych dvoch a dokazete, preco je mozne tento prevod pouzit, tak snad by ste to mohli mat dobre ;)

FFT som najprv napisal pre n = 4 aby bolo vidno konkretne co sa tam deje. sa ma spytal, ci by som to vedel spravit pre vseobecne n, takze som potreboval nanovo napisat tu sumu (je to aj v Algovison dole) a ked sa to rozdeli na sude a liche stlpce, som mal dokazat, ze po rozdeleni na 4 podmatice sa dve a dve rovnaju s tym, ze som mal povedat ktore dve sa rovnaju.
tam v zasade ide, aby sme predtym zadefinovali, ze ked robite kosinovu transformaciu, ze aky vektor dostanete a preco je konecny (odburate sumy a podobne...) a ze mate nejake omega, ktore umocnene na n sa rovna 1 a potom po vas bude chciet, aby ste teda dokazali, ze v tych dvoch podmaticiach v l - tom stlpci sa na pozicii i a i + n/2 tie dve hodnoty rovnaju... cize tam dosadite do tej sumy to i + n/2 a upravujete kym sa vam tam nevycleni e na 2pi.i.j.n/2 a to potom dokazete ze to je 1 a zvysok sa vam uz bude rovnat... aspon by sa mal. ak nie, pozrite si ako je vseobecne definovane omega pomocou e

inak co tam mali carry-look-ahead tak vraj chcel dokaz toho, ze v tej scitacke je v kazdej vrstve n/2 hradiel... sa to myslim indukciou dokazuje.
Uživatelský avatar
lingvik
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 23. 1. 2006 17:44
Typ studia: Informatika Bc.
Bydliště: Valašsko
Kontaktovat uživatele:

FFT + NP -> NP

Příspěvek od lingvik »

Ta implikace je blbost. Pokud někdo povídá o FFT a neví ani, co je to ten divný znak omega, tak se potom není čemu divit. Převody mezi NP úlohami jsou jedny z jednodušších věcí (zvlášť když si člověk může vybrat). A pokud člověk danému problému rozumí, tak dokáže odpovídat na všetečné dotazy. Takže FFT + NP->NP za jedna po mírném ptaní. Algoritmy pochopte a potom se nebojte.
Odpovědět

Zpět na „2005“