Paralelne algoritmy

Uživatelský avatar
nytram
Matfyz(ák|ačka) level II
Příspěvky: 68
Registrován: 4. 1. 2005 15:54
Typ studia: Informatika Bc.
Bydliště: da B-9'th floor
Kontaktovat uživatele:

Paralelne algoritmy

Příspěvek od nytram »

Zdravim.

Moze niekto napisat svoje dojmy a priebeh skusky z paralelnych algoritmov (predn. F. Mraz) ?
Quod Erat Demonstrandum.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Paralelne algoritmy

Příspěvek od hippies »

Lidi projde na 2 pruchody - nejprv ti da jednu otazku co se delalo (napr. ssk, nebo opt. trideni) pri durhem pruchodu se podiva co mas a podle toho ti da komplikovanou ulohu, kde mas neco sam vymyslet (najdi vsechny mosty/artikulace v grafu, ...) tam mu staci kdyz reknes neco jako ze to udelas pomoci toho a toho algoritmu (treba ssk), ale misto toho a toho tam budes delat to a to.

jinak jako na vsech jeho zkouskach - hodnoti to ferove a rozhodne te nechce videt znova;) ..

vzdali jsme to dva, nejak se trefil do jedine otazky, kde jsem vubec netusil - opt. trideni (nejak jsem to za ten jeden den nestihnul)
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Lado
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Re: Paralelne algoritmy

Příspěvek od Lado »

Pridavam moje dojmy a pojmy. Skusku som mal uz 9.6., ale bol som lenivy tu ihned nieco napisat :)

Skuska bola naplanovana na 9:30, no prednasajuci akosi zaspal - meskal cca 15 minut. Hned potom sme isli dnu ( bolo nas 5 ). Mal pripravene papieriky s otazkami. Boli dve farby - jedna na teoreticku otazku ( algoritmus, ktory sme robili na prednaske, popripade nejaka teoria ) a jedna za prakticku cast ( vymysliet nejaky algoritmus ). Co ma trochu sklamalo, bolo, ze som si tie otazky sam nemohol vybrat, ale dal mi ich on. Na druhej strane, necital ich, vybral ich nahodne. Co bolo dobre, tak potom prisiel ku kazdemu a prebral otazky - ci chapeme zadanie a vieme, co od nas chce - mne to dost pomohlo.

Ako teoreticku som mal P-uplnost + dokaz, ze Gen je P-uplny. Prakticka bola spocitat pocet artikulacii v grafe.
Priebeh skusky:
Ked som mal vypracovane otazky, tak som sa ozval, pan doktor ku mne prisiel a cital si najprv teoreticku otazku. Mal som to neprehladne, ale to mu nevadilo. Co ma potesilo, tak privital moj slovny vyklad k citaniu. Dava si nacas, s prvou otazkou sme stravili snad 15 minut a to som tam prakticky vsetko mal, len som mu to ukazoval a on sa obcas opytal doplnujucu otazku. Trochu ma zaskocil otazkou, nech mu dokazem, ze next() sa da NC-transformovat. Na slajdoch ten dokaz nemal, ani ho snad nehovoril na prednaske, takze sm to musel vymysliet, ale nakoniec to nebol taky problem.

Prakticka otazka - artikulacia je vrchol, ktory, ked odtrhnem, tak sa zmeni pocet komponent grafu. To som nevedel, tak som sa ho hned pri rozdavani prikladov opytal. Tak prvy nastrel ( trvalo to asi 15 sekund ) bol, ze pre kazdy vrchol spravim graf bez neho a potom na kazdom novom grafe spocitam pocet komponent a porovnam s originalnym grafom. Tam, kde sa pocet komponent zmenil, bude artikulacia. Casova zlozitost bola O(log n), ale procesorova P( n^3/(logN)^2 ). Na to mi povedal, ze by rad nizsi pocet procesorov, dokonca mi naznacil, ako funguje seriovy algoritmus a povedal, ze by chcel optimalny paralelny algoritmus. Tak som sa snazil :) Nebolo to az take tazke, trochu som zrecykloval par algoritmov a bolo to. Nakoniec mi dal bez vahania (!) jednotku. Sam som bol prekvapeny :)

Celkovo to bola velmi prijemna skuska, skusajuci je velmi mily, pozorny, da cas na vypracovanie, kludne aj prepracovanie celeho algortimu ( napr. v mojom pripade ). Samozrejem, to, ze je mily, nic nehovori o narocnosti skusky. Pre tych, ktori nechodili na prednasky, to moze byt narocnejsie, pretoze na slajdoch ma par chyb a hlavne je tam par veci preskocenych - len povie, ze nieco plati, ale nedokaze to a potom sa na to na skuske pyta. Takze odporucam nad danymi vecami pri uceni trochu premyslat, nechat zabehnut myslienky aj dalej a vrati sa to v podobe uspesne absolvovanej skusky.

Ja osobne som skoncil po cca hodine, ale to som bol prvy. Neskor som stretol kolegu, ktory "uz" z nej isiel a to bolo asi po dva a pol hodine s tym, ze tam este jeden z piatich ostal. Takze to asi zaberie viac casu - ako vravim, neponahla sa, ale je to prospesne pre oboch - pre skusajuceho aj skusaneho.

Snad vycerpavajuci popis, ak nie, rad doplnim :D
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“