Skuska 29.1.2007

Zadanie tu...
:arrow: EDIT: prave som zistil, ze ju vidia len prihlaseni ludia, tak si plis nemyslite, ze som blby alebo tak :wink:

Attachments:

• out.png

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..

ja sa sice nemam cim chvalit ale aspon prispejem do statistiky, nedal som to

S odrenyma usima, ale mam to. :D (Takze za 3)

Jakto, ze tu nevidim zadnou prilohu i kdyz sem prihlaseny?? Heelp :?:

Přílohy po pádu fóra zmizely v nenávratnu. Bohužel.

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:

   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"

   [3,2,4,1,6,5,7]

jako seznam netrivialnych cyklu prislusneho zobrazeni

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

   taut(+Formule)

ktery uspeje pokud je Formule spravne utvorena formule vyrokoveho poctu

(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.

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

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