# Zkouska 30.1.2006

<{ForumPost(poster="Eubie", timestamp=2006-01-30 12:10:56)}>
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:)
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-01-30 12:46:08)}>

 > 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.
<{/ForumPost}>

<{ForumPost(poster="Kuba", timestamp=2006-01-30 15:42:02)}>
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?
<{/ForumPost}>

<{ForumPost(poster="Eubie", timestamp=2006-01-30 16:07:57)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Leli", timestamp=2006-01-30 17:09:30)}>
A jak se mela resit ta 4ka? Hledaly se cykly a kdyz se nasel, tak si pridal hranu? Dik
<{/ForumPost}>

<{ForumPost(poster="Eubie", timestamp=2006-01-30 21:07:22)}>
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.
<{/ForumPost}>

<{ForumPost(poster="krystof", timestamp=2006-01-31 02:07:27)}>

 > Leli wrote: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???
<{/ForumPost}>

<{ForumPost(poster="Eubie", timestamp=2006-01-31 08:35:30)}>
Nějak mi uniká souvislost mezi 2-souvislostí a tím zadáním:)
<{/ForumPost}>

<{ForumPost(poster="Kuba", timestamp=2006-01-31 11:52:51)}>

 > 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?
<{/ForumPost}>

<{ForumPost(poster="Eubie", timestamp=2006-01-31 12:06:29)}>
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
<{/ForumPost}>

<{ForumPost(poster="krystof", timestamp=2006-01-31 13:29:45)}>

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

teda kua myslel jsem ten tezky priklad....
<{/ForumPost}>

<{ForumPost(poster="Eubie", timestamp=2006-01-31 13:46:15)}>
To rozumim, ale nevidim souvislosti ani mezi dvousouvislostí a zadáním těžkýho příkladu.
<{/ForumPost}>

<{ForumPost(poster="krystof", timestamp=2006-01-31 13:56:48)}>

 > Eubie wrote: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...
<{/ForumPost}>

<{ForumPost(poster="Kuba", timestamp=2006-01-31 15:20:04)}>

 > Eubie wrote: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"?
<{/ForumPost}>

<{ForumPost(poster="hippies", timestamp=2006-02-01 20:38:17)}>

 > Kuba wrote:
 > 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ě.
<{/ForumPost}>

<{ForumPost(poster="Kuba", timestamp=2006-02-01 20:58:55)}>

 > hippies wrote:
 >  > Kuba wrote:
 >  > 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ě.

No jo, to je pravda. Dik - zvyk je zelezna kosile, ja uz o jinych nez vyhledavacich ani nepremyslim.
<{/ForumPost}>