Skuska 29.1.2007
- vektor
- Matfyz(ák|ačka) level I
- Příspěvky: 42
- Registrován: 7. 1. 2007 16:59
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Skuska 29.1.2007
Zadanie tu...
EDIT: prave som zistil, ze ju vidia len prihlaseni ludia, tak si plis nemyslite, ze som blby alebo tak
EDIT: prave som zistil, ze ju vidia len prihlaseni ludia, tak si plis nemyslite, ze som blby alebo tak
- Přílohy
-
- Zadanie skuskovej pisomky 29.1.2007
- out.png (1.15 MiB) Zobrazeno 6907 x
I ? Unicode
- lavor
- Matfyz(ák|ačka) level III
- Příspěvky: 121
- Registrován: 1. 2. 2005 20:39
- Typ studia: Informatika Bc.
- Login do SIS: moskj4am
- Bydliště: kolej 17.11., A1105
- Kontaktovat uživatele:
kedze som bol na tom termine a kdesi som vyhrabal zadanie, tak tu je pisomka:
Haskell:
1. K peermutaci P(prvku od 1 do n) muzeme definovat vektor inverzi I delky n,pro niz plati,ze:
Tedy napr k permutaci P={3,2,1,4} je prislusnym vektorem inverzi O={0,1,2,0}.
Sestavte funkce,ktere:
a) k dane permutaci urci prislusny vektor inverzi
b) k danemu vektoru inverzi urc prislusnu permutaci
c) k vektoru urci zda je to vektor inversi nejake postupnosti
2. Najdete komponenty v neorientovanem grafu a mosty v nich.
Prolog:
3. Permutaci prvku 1 do n muzeme reprezentovat bud jako "vektor obrazu"
jako seznam netrivialnych cyklu prislusneho zobrazeni
Sestavte predikat, ktery realizuje umocnovani permutaci reprezentovanych pomoci cyklu.
4. Sestavte predikat
ktery uspeje pokud je Formule spravne utvorena formule vyrokoveho poctu
a sdeli zda formule je nebo neni tautologii.
Tautologie je formule pravdiva nezavisle na pravdivosti vyrokovych premennych. Napiste i predikaty, ktere zajisti pouziti prislusnych spojek jako operatoru.
Haskell:
1. K peermutaci P(prvku od 1 do n) muzeme definovat vektor inverzi I delky n,pro niz plati,ze:
Kód: Vybrat vše
Oi=pocet prvku {j je mensie ako i| (Pj je vascie ako Pi)}
Sestavte funkce,ktere:
a) k dane permutaci urci prislusny vektor inverzi
b) k danemu vektoru inverzi urc prislusnu permutaci
c) k vektoru urci zda je to vektor inversi nejake postupnosti
2. Najdete komponenty v neorientovanem grafu a mosty v nich.
Prolog:
3. Permutaci prvku 1 do n muzeme reprezentovat bud jako "vektor obrazu"
Kód: Vybrat vše
[3,2,4,1,6,5,7]
Kód: Vybrat vše
c(7, [ [1,3,4] , [5,6] ] ) (trivialni cykly [2] a [7] sme vynechali)
4. Sestavte predikat
Kód: Vybrat vše
taut(+Formule)
Kód: Vybrat vše
(spojky: unarni ~ (negace), binarni: & (konjunkce), # (disjunkce), => (implikace) s obvyklymi prioritami; zavorky pro zmenu poradi vyhodnocovani; vyrokov premenne - mala pismena)
Tautologie je formule pravdiva nezavisle na pravdivosti vyrokovych premennych. Napiste i predikaty, ktere zajisti pouziti prislusnych spojek jako operatoru.
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 71
- Registrován: 28. 9. 2007 17:36
- Typ studia: Informatika Mgr.
- Login do SIS: kohoj7am
- Kontaktovat uživatele:
Re: Skuska 29.1.2007
Ahoj,
nemate prosim nekde nekdo napsane reseni te 2. ulohy na Haskell? Mysim to hledani komponent a mostu v grafu....
Delalo by se to asi pres prohledavani do hloubky z jednotlivych vrcholu, ne? Ale nejak nevim, jak pak na ty mosty...
Dik
nemate prosim nekde nekdo napsane reseni te 2. ulohy na Haskell? Mysim to hledani komponent a mostu v grafu....
Delalo by se to asi pres prohledavani do hloubky z jednotlivych vrcholu, ne? Ale nejak nevim, jak pak na ty mosty...
Dik
- kaja
- Matfyz(ák|ačka) level II
- Příspěvky: 99
- Registrován: 20. 12. 2007 00:53
- Typ studia: Informatika Bc.
- Login do SIS: bilek7am
- Bydliště: Miðgarðr
- Kontaktovat uživatele:
Re: Skuska 29.1.2007
ty komponenty jsou jednoduché, třeba průchodem do hloubky
ty mosty jsem vygooglil na webu... KSP a je to fakt
Proto si pro každý vrchol spočítáme hladinu, ve které se nachází (kořen je na hladině 0, jeho synové na hladině 1, jejich synové 2, …). Dále si pro každý vrchol v spočítáme, do jaké nejvyšší hladiny (s nejmenším číslem) vedou ryzí zpětné hrany z podstromu s kořenem v. To můžeme udělat přímo při procházení do hloubky, protože než se vrátíme z v, projdeme celý podstrom pod v. Pokud všechny zpětné hrany vedou do hladiny stejné nebo větší než té, na které je v, pak odebráním hrany vedoucí do v z jeho otce vzniknou dvě komponenty souvislosti, čili tato hrana je mostem. V opačném případě jsme nalezli kružnici, na níž tato hrana leží, takže to most být nemůže. Výjimku tvoří kořen, který žádného otce nemá a nemusíme se o něj proto starat.
http://ksp.mff.cuni.cz/tasks/18/cook2.html
ty mosty jsem vygooglil na webu... KSP a je to fakt
Proto si pro každý vrchol spočítáme hladinu, ve které se nachází (kořen je na hladině 0, jeho synové na hladině 1, jejich synové 2, …). Dále si pro každý vrchol v spočítáme, do jaké nejvyšší hladiny (s nejmenším číslem) vedou ryzí zpětné hrany z podstromu s kořenem v. To můžeme udělat přímo při procházení do hloubky, protože než se vrátíme z v, projdeme celý podstrom pod v. Pokud všechny zpětné hrany vedou do hladiny stejné nebo větší než té, na které je v, pak odebráním hrany vedoucí do v z jeho otce vzniknou dvě komponenty souvislosti, čili tato hrana je mostem. V opačném případě jsme nalezli kružnici, na níž tato hrana leží, takže to most být nemůže. Výjimku tvoří kořen, který žádného otce nemá a nemusíme se o něj proto starat.
http://ksp.mff.cuni.cz/tasks/18/cook2.html
PONIES