Skuska 29.1.2007

Uživatelský avatar
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

Příspěvek od vektor »

Zadanie tu...
:arrow: EDIT: prave som zistil, ze ju vidia len prihlaseni ludia, tak si plis nemyslite, ze som blby alebo tak :wink:
Přílohy
Zadanie skuskovej pisomky 29.1.2007
Zadanie skuskovej pisomky 29.1.2007
out.png (1.15 MiB) Zobrazeno 6743 x
I ? Unicode
Návštěvník

Příspěvek od Návštěvník »

Celkem by me zajimalo, jaka byla uspesnost na tehle zkousce..? Tak se kdyztak podelte o svoje dojmy.. Ja dostal nastesti za jedna :lol:, ale jak dopadl kdokoliv jiny nevim..
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

Příspěvek od lavor »

ja sa sice nemam cim chvalit ale aspon prispejem do statistiky, nedal som to
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
Návštěvník

Příspěvek od Návštěvník »

S odrenyma usima, ale mam to. :D (Takze za 3)
Uživatelský avatar
Andreas
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 18. 1. 2006 16:47
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Andreas »

Jakto, ze tu nevidim zadnou prilohu i kdyz sem prihlaseny?? Heelp :?:
New systems generate new problems:)
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Příspěvek od gASK »

Přílohy po pádu fóra zmizely v nenávratnu. Bohužel.
When life gives you crap, make crap golems.
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

Příspěvek od lavor »

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:

Kód: Vybrat vše

Oi=pocet prvku {j je mensie ako i| (Pj je vascie ako Pi)}
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"

Kód: Vybrat vše

[3,2,4,1,6,5,7]
jako seznam netrivialnych cyklu prislusneho zobrazeni

Kód: Vybrat vše

c(7, [ [1,3,4] , [5,6] ] ) (trivialni cykly [2] a [7] sme vynechali)
Sestavte predikat, ktery realizuje umocnovani permutaci reprezentovanych pomoci cyklu.

4. Sestavte predikat

Kód: Vybrat vše

taut(+Formule)
ktery uspeje pokud je Formule spravne utvorena formule vyrokoveho poctu

Kód: Vybrat vše

(spojky: unarni ~ (negace), binarni: & (konjunkce), # (disjunkce), => (implikace) s obvyklymi prioritami; zavorky pro zmenu poradi vyhodnocovani; vyrokov premenne - mala pismena)
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.
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
HonzaK
Matfyz(ák|ačka) level II
Příspěvky: 71
Registrován: 28. 9. 2007 17:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Skuska 29.1.2007

Příspěvek od HonzaK »

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
Uživatelský avatar
kaja
Matfyz(ák|ačka) level II
Příspěvky: 99
Registrován: 20. 12. 2007 00:53
Typ studia: Informatika Bc.
Bydliště: Miðgarðr
Kontaktovat uživatele:

Re: Skuska 29.1.2007

Příspěvek od kaja »

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
PONIES
Odpovědět

Zpět na „2006“