Zkouska 30.1.2006

[Eubie]

Takze, dnesnimi lehkymi ukoly byly nasledujici:
1/ Mame acyklickej graf a v nem dva vrcholy A a B. Predikat ma najit nejblizsi spolecnej vrchol S takovej, ze S je predchudcem Acka i Bcka na to nejblizsi, tj zadnej vrchol na ceste SA a SB neni spolecnym vrcholem A a B.

2/ Najdete sedlovy bod matice (presnou definici SB matice uz nevim, tak si ji najdete).

3/ Pro binarni (ne nutne vyhledavaci) strom kterej ma data jen v listech vytvorte predikat, tkerej ten strom prevede na strom s daty i v uzlech, kde hodnota v uzlu je minimum hodnoty obou podstromu (takze neco jako Halda).

4/ Drsna vec tykajici se stringu..aspon pulka z nas to nepochopila, takze to sem nemuzu reprodukovat, ale dalo se to lehce resit strucnyma seznamama (teda pokud to mam dobre:)).

Tezky priklad:
Neorientovany graf je triangulvoatelny, pokud vsechny cykly delky >= 4 maji aspon jednu uhlopricku. Nas predikat ma z grafu kterej dostane udelat triangulovatelnej graf pridavanim hran, ale pridavat se smi pouze pokud musime (na tabuli bylo, ze nechceme kliku) - jinak by to logicky slo doplnit na uplnej graf a ten je urcite triangulovatelnej.

Behem cele pisemky profesor Hric neco opravoval a tvaril se zasmusile, pochvili zase vesele, jindy vrtel hlavou, jindy si opiral hlavu o stolecek v zapalu premysleni..sranda se divat:)

[Návštěvník]

2/ Najdete sedlovy bod matice (presnou definici SB matice uz nevim, tak si ji najdete).

A to mi Hric pri pisemce rekne, co to je ten sedlovej bod? Slysim to poprvy v zivote.

[Kuba]

Jen pro uplnost, rika Hric, jak je ten graf datove reprezentovan, nebo si to kazdy muze urcit sam?

Je to napr seznam dvojic (vrchol-seznam nasledniku)?
Matice sousednosti?

A jeste dotaz, jak se resi ta 1?

[Eubie]

Co je sedlovej bod nadefinoval, je to něco jako max (přes sloupce) min (přes řádky) a[i,j] = min (přes sloupce) max (přes řádky) a[i,j].

Graf je reprezentovanej jak si kdo vybere, standardní reprezentací v Prologu, jak, to je jedno.

Ad jak se řeší jedna: nevim, myslel sem, že to mam dobře ale neměl sem to.

Ad "je jedno jak je to složitý": napsal sem ten těžkej uplně krásně prologově, všude samej members a vypliv by všechny možnosti. Když to Hric viděl, uznal mi ho, ale měl remcy jako že je to moc složitý, takže mi za 3 úspěšný příklady malý a jeden velkej dal za dvě, což už sem viděl i horší písemky, který byly ohodnocený stejně/líp.

[Leli]

A jak se mela resit ta 4ka? Hledaly se cykly a kdyz se nasel, tak si pridal hranu? Dik

[Eubie]

Zdar.
Moje řešení bylo takový:
1/ najdi cykly
2/ vyber delsi nez 3
3/ vyber ty bez uhlopricky
4/ member konkretni cyklus z 3/
5/ najdi hrany, ktery by tvorily uhlopricku tohohle konkretniho cyklu
6/ member jednu hranu z 5/
7/ obohat E o tuhle hranu a pust na obohacenej graf.
...dokud 3/ neda prazndej seznam.

[krystof]

A jak se mela resit ta 4ka? Hledaly se cykly a kdyz se nasel, tak si pridal hranu? Dik

jen tak me napada, kdyz si v tom grafu nasel 2-souvisle komponentyt, tak ty musely byt doplnene na uplne grafy, anebo sem moc ozraty a neco mi unika???

[Eubie]

Nějak mi uniká souvislost mezi 2-souvislostí a tím zadáním:)

[Kuba]

3/ Pro binarni (ne nutne vyhledavaci) strom kterej ma data jen v listech vytvorte predikat, tkerej ten strom prevede na strom s daty i v uzlech, kde hodnota v uzlu je minimum hodnoty obou podstromu (takze neco jako Halda).

A toto? Jak se to (algoritmicky, v Haskellu) vlastne dela?

[Eubie]

data Tree1 a= Leaf1 a | Branch1 (Tree1 a) (Tree1 a)
data Tree2 a = Leaf2 a | Branch2 (Tree2 a) a (Tree2 a)

preved::(Tree1 a) -> (Tree2 a)

preved (Leaf1 a) = (Leaf2 a)
preved (Branch1 T1 T2) = ( Branch2 (preved T1) (minimum T1 T2) (preved T2))

kde
minimum::(Tree1 a)->(Tree1 a)-> a
minimum T1 T2 = min (minimum2 T1) (minimum2 T2)

kde
minimum2 (Leaf1 a) = a
minimum (Branch1 T1 T2) = minimum T1 T2

[krystof]

Nějak mi uniká souvislost mezi 2-souvislostí a tím zadáním:)

teda kua myslel jsem ten tezky priklad....

[Eubie]

To rozumim, ale nevidim souvislosti ani mezi dvousouvislostí a zadáním těžkýho příkladu.

[krystof]

To rozumim, ale nevidim souvislosti ani mezi dvousouvislostí a zadáním těžkýho příkladu.

no, kdyz mas 2souvisly kraf, tak kazde dva vrcholy lezi na nejakem cyklu, ne? No a kdyz je delsi nez 3, tak musi mit nejakou pricku a (tady je jen muj dukazem nepodporeny, ale silny, dojem ) z toho by mel byt jakousi indukci uplny.
naopak kdyz mas v grafu most spojujici dve 2souvisle konponenty, tak v zadnem cyklu neni, tudiz zustava tak, jak byl...

[Kuba]

data Tree1 a= Leaf1 a | Branch1 (Tree1 a) (Tree1 a)
data Tree2 a = Leaf2 a | Branch2 (Tree2 a) a (Tree2 a)

preved::(Tree1 a) -> (Tree2 a)

preved (Leaf1 a) = (Leaf2 a)
preved (Branch1 T1 T2) = ( Branch2 (preved T1) (minimum T1 T2) (preved T2))

kde
minimum::(Tree1 a)->(Tree1 a)-> a
minimum T1 T2 = min (minimum2 T1) (minimum2 T2)

kde
minimum2 (Leaf1 a) = a
minimum (Branch1 T1 T2) = minimum T1 T2

A nebudou tam pak ty prvky co jsou minima vickrat? Napriklad jednou v tom "preved T2" a jednou v "minimum T1 T2"?

[hippies]

A nebudou tam pak ty prvky co jsou minima vickrat? Napriklad jednou v tom "preved T2" a jednou v "minimum T1 T2"?

No proč ne, vždyť už v zadání je, že není nutně vyhledávací. Například absolutní (rozuměj globální) minimum bude na celé cestě od kořene až k sobě.