Zkouska 30.1.2006
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Zkouska 30.1.2006
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:)
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:)
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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.
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.
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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.
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.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 92
- Registrován: 2. 6. 2005 22:55
- Typ studia: Informatika Mgr.
- Login do SIS: klimj4bm
- Bydliště: Praha - Dejvice
- Kontaktovat uživatele:
Re: Zkouska 30.1.2006
A toto? Jak se to (algoritmicky, v Haskellu) vlastne dela?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).
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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
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
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 18. 1. 2005 15:15
- Typ studia: Informatika Mgr.
- Bydliště: Brno / 17. Listopad
- Kontaktovat uživatele:
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.Eubie píše:To rozumim, ale nevidim souvislosti ani mezi dvousouvislostí a zadáním těžkýho příkladu.
naopak kdyz mas v grafu most spojujici dve 2souvisle konponenty, tak v zadnem cyklu neni, tudiz zustava tak, jak byl...
-
- Matfyz(ák|ačka) level II
- Příspěvky: 92
- Registrován: 2. 6. 2005 22:55
- Typ studia: Informatika Mgr.
- Login do SIS: klimj4bm
- Bydliště: Praha - Dejvice
- Kontaktovat uživatele:
A nebudou tam pak ty prvky co jsou minima vickrat? Napriklad jednou v tom "preved T2" a jednou v "minimum T1 T2"?Eubie píše: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