6.2.2012 SW systémy/Počítačová grafika

[macekt]

Na počítačovou grafiku jsme byli jen tři studenti a naše komise byla: Josef Pelikán, Jiří Žára a Tomáš Dvořák. První dva zkoušeli ty odborný předměty, T.Dvořák zkoušel datovky a základy složitosti a vyčíslitelnosti. Na začátku nám rozdali všech pět témat, dali nám 45 minut na přípravu a pak se u nás střídali a zkoušeli.

Datovky a složitost
Dostal jsem 1) dynamické programování a 2) univerzální hashování. Mí dva kolegové dostali myslim NP úplnost, B-stromy, Fibonacciho haldy a asi něco s ČRF.

Ke každýmu tématu jsem si připravil cca stránku informací, když mě pak T. Dvořák zkoušel, tak seděl u mě, procházeli jsme to a šťoural se v tom.

1) U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).

2) K tomu univ. hashování jsem napsal definici, definici c-univerzálního systému, konstrukci systému s důkazem c-univerzality (podle skript Koubka) a bez důkazu složitost operací. Tohle se mu sice líbilo, ale pak začal víc rozebírat tu složitost počtu operací a tam jsem už nic moc kloudnýho do kupy nedal. Nechtěl to dokázat, ale nějak interpretovat, a to se mi nedařilo. Zasekl jsem se u definice očekávané délky řetězce a snažil jsem se tu diskuzi stočit jinam, protože tady o tom jsem věděl kulový. Nakonec jsme to nechali být a ještě mě taky dostal otázkou, kdy se vybírá ten náhodnej index hashovací funkce. Já jsem si myslel, že se vybírá pro každý prvek nová, ale není to tak, protože bych pak nevěděl, kterou funkci jsem pro každej prvek použil. Prý se teda volí index jednou předtím, než přijdou data a pokud se ukáže, že vybraná funkce není dobrá, tak se potom může vybrat nová a tabulka celá přehashovat.

Grafika
Dostal jsem 3) Dekonvoluce - inverzní a Wienerův filtr, 4) Rozptylování, palety, 5) Radiozita.

3) Napsal jsem to podle materiálů k DZO s Flusserem, definice problému dekonvoluce, jak to vypadá ve Fourierovském spektru, ty filtry a pak taky formulace problému ve variačním počtu pomocí minimalizace funkcionálu. Byli spokojený, tady myslím neměli ani žádný otázky.

4) Popsal jsem náhodný rozptylování, pak pomocí půltónovacích matic a metody distribuce chyby. To bylo OK. Pak přišly palety, tak jsem řekl proč se vůbec používají, že jsou nějaký pevný (5-6-5, 3-3-2 apod.) a pak jsem se vrhnul na konstrukci palety pro daný obrázek. To jsem tak nějak nastínil, jak na to, ale Žára se tady v tom začal hrabat do detailu. Jak přesně fungujou ty algoritmy, s jakou složitostí apod. No, nakonec jsem to po mírném postrkování nějak dal dokupy, akorát mě teda dostal na otázce: Který z těch půltónovacích algoritmů lze použít pro barevný obrázek s paletou? Tipnul jsem ty matice, ale je to distribuce chyby.

5) Vyšel jsem od zobrazovací rovnice a odvodil jsem z ní tu soustavu rovnic pro radiozity plošek. Pak pár vět o tom, jak se dá řešit (je diagonálně dominantní -> lze iteračně, takže Jacobi, SOR apod.). Taky jsem řekl, které odrazy to simuluje a že to není úplný řešení ZR. Ptali se, jak ty spočítaný výsledky nakonec zobrazím. Tak jsem říkal buď ray-tracingem nebo rasterizací těch plošek. Ray-tracingem jsem je malinko zaskočil, ale operativně jsem dovysvětlil, že tím tu radiozitu vylepším, že zvládne i lesklé odrazy před difůzníma, takže OK. Pak se ptali na stínování těch plošek, jak se to vlastně dělá - ze soustavy vypadnou radiozity ploch, z těch musím spočítat hodnoty na vrcholech (nějak zprůměrovat okolní plošky) a z těch se pak počítají ty výsledný hodnoty interpolací na povrchu plošek. Poslední dotaz mířil na progresivní radiozitu, ale o té jsem moc nevěděl (hlavní, co chtěli slyšet, a neslyšeli , bylo, že jedna iterace odpovídá jednomu odrazu světla a počtem iterací snadno omezit délku výpočtu a je to hodně rychlé).

Celkově to bylo docela v pohodě, T.Dvořák je hodný, sem tam pomůže, rozhodně se nesnaží trápit nebo se v něčem extrémně šťourat. J. Pelikán je taky v pohodě, moc se na nic neptá. J.Žára se ptá celkem dost, chvilkama mi přišel nepříjemný, ale rozhodně pořád v mezích korektnosti.

[Návštěvník]

Ja sem dostal nasledujici otazky
1) Algoritmicky nerozhodnutelne problemy
Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS
U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved.
Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.

2) B-stromy
Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko )
Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost )
Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka )

3) Metody odstranovani sumu (Digitalni zpracovani obrazu)
Tohle zkousel Pelikan, Zara jen sedel vedela pozoroval.
Popsal sem kratce modely sumu ( Gamma, Exp, Gauss, Impulzni )
Nasledoval konvolucni fitr, frekvencni low pass filtr (+vztah mezi nimi : tedy konvolucni teorem + FFT ), medianovy filtr, filtrace pomoci waveletu, anizotropni filtr ( viz flusserovi slidy ...detekce hran a pak rozmazani mimo tyto hrany. Pelikan se tvaril spokojene nakonec se zeptal jestli vim jak funguje odstranovani sumu pomoci rotacniho okenka ...to sem vubec netusil co to ma byt, tak dodal ze to pry uci Hlavac na svoji prednasce ale ze je to jen takovy detail a tim to skoncilo.

4) Interkativita ve VRML
Tady to prevzal Zara ( bohuzel, Pelikan je imhho o dost mirnejsi, Zara v tom celkem rejpe )
Senzory, Manipulatory, EventIn, EventOut, Route To, Interpolatory.
Pak se ptal na strukturu uzlu Collision (chtel vedet jaky atributy tam jsou a jak se pouzivaji...tady sem zacinal tapat protoze do takovych detailu sem to neumel.
Posledni otazka jak ve vrml implementovat teleportaci avatara kdyz se stiskne napriklad tlacitko ...to sem navrhl par moznosti, zadna se mu prilis nelibila ( respektiva zadna by pry nebyla realizovatelna ve VRML )
Spravna odpoved byl udajne uzel Anchor.
Tim to nastesti skoncilo ( mam pocit ze cim dyl by se ptal tim horsi celkovej dojem bych zanechal )

5) Komprese PNG a GIF
Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara
Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu )
...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi
Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech
Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim.

Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor)
No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu