Fórum studentů MFF UK

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. [b]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.[/b] 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

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

Oi=pocet prvku {j je mensie ako i| (Pj je vascie ako Pi)}

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

c(7, [ [1,3,4] , [5,6] ] ) (trivialni cykly [2] a [7] sme vynechali)

taut(+Formule)

(spojky: unarni ~ (negace), binarni: & (konjunkce), # (disjunkce), => (implikace) s obvyklymi prioritami; zavorky pro zmenu poradi vyhodnocovani; vyrokov premenne - mala pismena)

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:
[code]Oi=pocet prvku {j je mensie ako i| (Pj je vascie ako Pi)}[/code]
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"
[code][3,2,4,1,6,5,7][/code]
jako seznam netrivialnych cyklu prislusneho zobrazeni
[code]c(7, [ [1,3,4] , [5,6] ] ) (trivialni cykly [2] a [7] sme vynechali)[/code]
Sestavte predikat, ktery realizuje umocnovani permutaci reprezentovanych pomoci cyklu.

4. Sestavte predikat
[code]taut(+Formule)[/code]
ktery uspeje pokud je Formule spravne utvorena formule vyrokoveho poctu
[code](spojky: unarni ~ (negace), binarni: & (konjunkce), # (disjunkce), => (implikace) s obvyklymi prioritami; zavorky pro zmenu poradi vyhodnocovani; vyrokov premenne - mala pismena)
[/code]
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.

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

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

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

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

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

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