od Lado » 11. 6. 2009 21:14
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
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