Zapocet 16.1.2008 14:00

Pokročilé vlastnosti jazyka C++, jejich použití pro objektové programování. Dědičnost, virtuální metody, Dynamická alokace. Šablony, generické programování, kompilační polymorfismus. Výjimky. Objektové knihovny, uživatelské kontejnery a iterátory, návrhové vzory. Nízkoúrovňové implementační techniky a konstrukce.
macekt
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 5. 11. 2006 15:26

Zapocet 16.1.2008 14:00

Příspěvek od macekt »

Zadani(zkopirovano primo ze zadani zkousejiciho) :
Kriticka cesta v grafu
-------------------------

Graf G(V,E) reprezentujici posloupnost operaci.
V = operace
E = zavislosti mezi operacemi. Tj.'e' z E, e = (v1, v2) znaci, ze operace 'v1' se
provadi pred operaci 'v2'.

Pro kazdy vrchol 'v' z V je udana doba trvani operace d_v (duration).

Algoritmus hledani kriticke cesty:
-----------------------------------
Faze 1 (najde minimalni startovni (est) a koncove (ect) casy):
1. zacneme od vrcholu, ktere nemaji predchudce:
est_v = 0
ect_v = d_v (doba trvani)
2. pro kazdy vrhol 'v' jehoz predchudci jsou zpracovani
est_v = max ect_i (i jsou vsichni predchudci)
ect_v = est_v + d_v
3. Cmax = max ect_i

Faze 2 (najde maximalni startovni (lst) a koncove (lct) casy):
1. zacneme od vrcholu, ktere nemaji zadne nasledniky
lct_v = Cmax
lst_v = Cmax - d_v
2. pro kazdy vrchol 'v' jehoz naslednici uz byli zpracovani proved:
lct_v = min lst_j (j jsou vsichni jiz zpracovani naslednici)
lst_v = lct_v - d_v

Operace, jejichz est = lst (=> nejde s nima hybat) jsou kriticke.

Kritickou cestu tvori kriticke ulohy.

Vstup:
---------------
<pocet vrcholu n = |V|>
<pocet hran e = |E|>
- prazdny radek
d_1
d_2
.
.
.
d_n
- prazdny radek
1,2
2,3
.
.
.
7,n
----------------

Vystup:
-----------
- seznam vrcholu na kriticke ceste (usporadanych vzestupne podle est).


Volani programu:
----------------
cpath <nazev_souboru>
Ukazkovy vstup:
9
9

4
9
3
3
6
8
8
12
6

1,2
3,4
2,6
4,5
5,6
5,8
6,7
8,7
8,9
...a prislusny vystup:
3 -> 4 -> 5 -> 8 -> 7
Jeste doplnil, ze muzeme predpokladat absolutni korektnost vstupu, tzn. v grafu nejsou cykly, hodnoty jsou kladne, vstupni soubor vypada presne tak, jako ten ukazkovy, ..., coz ulohu ucinilo pomerne snadnou. Byli jsme tam jenom 4, pricemz vim, ze 2 jsme to dali. Zbyli 2 nevim.
Uživatelský avatar
stnicolaus
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 22. 1. 2006 17:39
Typ studia: Informatika Bc.
Bydliště: Plzeň
Kontaktovat uživatele:

Re: Zapocet 16.1.2008 14:00

Příspěvek od stnicolaus »

Já jsem odcházel jako třetí také úspěšně. Podle mne poměrně jednoduchý příklad. :D
Odpovědět

Zpět na „PRG032 Objektově orientované programování“