skuska 25.1.2008

no tak dnesne zadanie:

Prolog:

1. je dan acyklicky orientovany graf a body A, B. Ulohou najit nejblizsiho prechudce obou vrcholu, kde nejblizsi znamena ze na cestach SA, SB neni vrchol, ktery by byl taky predchudcem obou vrcholu

2. Na vstupu je matice. Vasi ulohou je vydat polohu sedloveho bodu matice, pokud existruje. Kde sedlovy bod matice je min(max aij) = max(min aij) kde max aij ide cez j a min aij ide cez i

Haskell

1. je dan binarny strom, ktory ma hodnoty len v listoch, ulohou bolo previest tento strom na binarny strom, ktory ma hodnoty aj vo vnutornych uzloch. a to tak ze hodnota je minimum hodnot z jeho podstromov. uvidite datovy struktury a typy funkci

2. dostanete 2 grafy reprezentovane zoznamom susedov, zistite zda sou ekvivalnetni (nejde o ziaden izomorfizmus, vrcholy su rovnako pomenovane proste len ci su rovnake)

a ted maso Velky Priklad:
Je dany zoznam vsetkych dvojic strojovych instrukcii,u ktorych bud
a) nezalezi na poradi
b) zalezi a maju danu minimalnu vzdalenost provederi r(ij)
Procesor moze zacat v jednom cykle najviac jednu instrukciu - cize moze byt aj cyklus ked nezacne ziadna.
Ulohou je najst take poradie instrukcii abo splnovalo vsetky podmienky a aby pocet cyklov na ich spracovanie bol
co najmensi, kde najmensi sa mysly od zaciatku spracovania az dokonca.

Vysledok este neviem o 16:40 tak uvidime ...

Musím říct, že Hric hodnotí opravdu mírne. První příklad jsem měl z půlky, druhej jsem špatně pochopil zadání a udělal jsem ho až na ústním, ve čtvrtým jsem měl malou chybku a velkej příklad jsem řešil generováním všech permutací (s ořezáváním). Přesto výsledek = 1 :D

No tak ja mam za 3 a to som mal obidve male priklady z haskellu s nejakymi malyckmymi chybkami, a z prologu som mal druhy s tym ze som tam nedoriesil jednu vec takze som to pred ustnou opravoval. Velky som mal rieseny heuristikou - nie velmi vhodna reprezentavia hricovi sa moc nepacila a mal som len + predikat cely a jeden z polovice ostatne som mal okecane takze som to nemal "technicky dotiahnute" takze tak. Ako hric je na ustnej v poho som spokojny, tak s 3 som pocital.

Chcem sa opytat ako je to s reprezentaciou grafov v ulohach, pretoze v zadani tam nikde nepise ako je dany graf reprezentovany. Znamena to ze volba reprezentacie grafu je sucastou ulohy a teda si mozem zvolit lubovolnu?

Návštěvník wrote:Chcem sa opytat ako je to s reprezentaciou grafov v ulohach, pretoze v zadani tam nikde nepise ako je dany graf reprezentovany. Znamena to ze volba reprezentacie grafu je sucastou ulohy a teda si mozem zvolit lubovolnu?

vacsinou reprezentaciu danu nemas, ale nema moc rad ked mas graf ulozeny priamo v databaze.. teda aspon v mojom pripade, a podla toho co som cital na fore, tak u v minulych rokoch mu to vadievalo

no reprezentacia grafu je na tebe. napr v prvom priklade (ja som ho sice nemal) ale si to moze zvolit ze graf bude dany zoznamom predchodcov - cim sa ti zlahci uloha. a hric proti tomu nic nema je fakr na tebe ako si to zvolis - no a ako je hore uvedene priamo v databaze to asi nebude ono

Musim souhlasit, ze Hric je u zkousky dost v pohode. Sice dle meho nazoru, jak male, tak velke priklady mi prijdou nekdy dost hard a nektere jsou dost navzajem nesrovnatelne, ale popravde, Hric to hodnoti dost dobre a jak napsal nardew, tak i spravedlive. Male priklady dava opravit u ustni, a u velkeho nejak neresi, jestli to mate uplne algoritmicky optimalne. Hlavne ze mate neco, takze i generovani vsech permutaci povazuje za reseni, i kdyz to zrovna nepodporuje. :)

Ja jsem mel 3 male priklady, teoretickou otazku jsem mel tak napul a jeden priklad (ty matice) jsem nemel vubec, pac jsem nepochopil definici toho sedlovyho bodu. Velky priklad jsem mel, resil jsem ho tak, ze jsem si vybiral dalsi vhodnou instrukci, kterou muzu zpracovat (nejdriv hledam v zavislych, kdyz nic, tak v nezavislych instrukcich). Mel sice vyhrady, kdyz jsem na filtraci instrukci pouzil nekolikero setof, rikal, ze to je lepsi nez generovani permutaci, ale ze ne tak o moc. Obhajil jsem to tim, ze to za me dela Prolog :D a ne ja. Tak uz pak nic nerikal. Dotazeny do konce jsem ten velky priklad taky nemel, akorat jsem mu nastinil dotazeni, naznacil jsem mu, ze bych asi pouzil znovu setof :D Tak se pousmal, ale uz to dal neresil, pak si jen vyzadal index a ja odchazel nevericne s 1.