Hlavne menu We are sorry, but magazine AMMO is suspended. Here is just read-only access to the articles archive. Some features are removed because they were outdated, pointless in read-only (voting and pools), or it was missused by spammers (comments) etc. Now the webpages aren't maintained so when something will get broken most probably it won't be fixed at all. If you liked our magazine then please make donation with paypal so we can pay for traffic on this server.

TOP Výuka
01 Maľované krížovky 103 bodov
02 OpenGL, lákadlo 38 bodov
03 MySQL (+ použitie Visual C++ a PHP) 28 bodov
04 OpenGL, časť 1 21 bodov
05 Huffmanove kódovanie 19 bodov
06 Pascal, časť 1 18 bodov
07 Ako tlačiť s HP 16 bodov
08 Základy HTML časť 2 16 bodov
09 Základy HTML časť 3 13 bodov
10 Hry pre nenáročných + zdrojáky 10 bodov
11 OpenGL, úvod 8 bodov
12 Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0 7 bodov
13 OpenGL – Intermezzo 1 7 bodov
14 OpenGL povinná literatúra 6 bodov
15 Základy HTML časť 1 6 bodov
Najnovsie clanky
Kvalitné služby podľa skúseností iných - TopSlužby.sk
LOTR - Dve veže - Parodia - Scénka 2. časť
Neverwinter nights
Children Of Bodom-Hatebreeder
Kult Duny - 6. časť (Bonus)
Kult Duny - 5. časť (Filmy, Hry)
Dobré ráno. (morc certa, hora incerta...)
Kult Duny - 4. časť (Knihy 2/2)
Stretnutie Spoločenstva Tolkiena
GRAVE DIGGER – Knights Of The Cross
Kult Duny - 3. časť (Knihy 1/2)
Kult Duny - 2. časť (Pojmy)
Kult Duny - 1. časť (Úvod)
LOTR - Dve veže - Parodia - Scénka
Jackass
Vsetky clanky
Airsoft - Specnaz [4 clanky]
Básne [6 clankov]
Fantázia [4 clanky]
Filmy a DVD [51 clankov]
Hardware [10 clankov]
Hry [170 clankov]
Hry, návody [6 clankov]
Hudba [8 clankov]
Internet [7 clankov]
Knihy [6 clankov]
O AMME [4 clanky]
Pandemonium [10 clankov]
Poviedky [14 clankov]
Programy [18 clankov]
Rôzne [8 clankov]
Technické [3 clanky]
Úvahy [8 clankov]
Výuka [50 clankov]
Ako tlačiť s HP
Fake2
Faktúrka
Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0
Fract
HLSaver
Hry pre nenáročných + zdrojáky
Huffmanove kódovanie
IPicture2 & aggresiveoptimize.h
Maľované krížovky
MySQL (+ použitie Visual C++ a PHP)
OpenGL - GLWnd
OpenGL AMMO Saver
OpenGL povinná literatúra
OpenGL – Intermezzo 1
OpenGL, časť 10
OpenGL, časť 11
OpenGL, časť 12
OpenGL, časť 13
OpenGL, časť 14
OpenGL, časť 15
OpenGL, časť 16
OpenGL, časť 17
OpenGL, časť 18
OpenGL, časť 7
OpenGL, časť 8
OpenGL, časť 9
Opengl – Cloth Simulation
RenameR
SkinMagic
WinSocket Communication via VC++
Údajové štruktúry
viac...
Zábava [5 clankov]
Zdravie [15 clankov]
Celkovy pocet clankov: 407
Algoritmy v grafoch 
Výuka | Dna 29.5.2002 | Johny | 6 znamok, priemer 2.33 | 9195 videni | 1004 WAP videni

Pred pár dňami som bol na skúške z teórie grafov a nedopadla podľa očakávaní. Začalo sa to dobre, pozerali sme algoritmy, o ktorých tu budem písať, ale potom pri definíciách to už bolo horšie. Ale verím tomu, že Vás presné definície od slova do slova nebudú až tak zaujímať, ale ak si spomeniem, tak skúsim napísať aj nejakú od slova do slova.

O čo vlastne ide ? Väčšina ľudí si predstaví pod grafom, nejakú cikcakatú čiaru, ktorá je akože grafom funkcie. Aj ja som si niečo také predstavoval, ale skutočnosť je iná. Takže povedzme si, čo je to graf.

Graf G je usporiadaná dvojica množín V,H, kde množina V je neprázdna a množina H je množina neusporiadaných dvojíc typu u,v, kde u aj v patrí do V a u je rôzne od v.

Toľko hovorí definícia. Máte v tom jasno ? A teraz to poviem mojou „učebnicovou“ definíciou.
Graf je matematický popis nejakých objektov, ktoré existujú a sú nejakým spôsobom spojené. Množina V je množinou všetkých objektov, a množina H určuje pre každú dvojicu, ktorá tam je, že práve medzi týmito dvoma objektmi existuje spôsob spojenia. Množina V alebo tiež množina Vrcholov a množina H ako množina hrán.
Príklad: Množina V sú mestá, napríklad na Slovensku a množina H sú cesty, ktoré existujú medzi mestami
Napríklad: V=Zvolen, B.Bystrica, Bratislava, Košice
A množina H by bola (Zvolen,B.Bystrica), (Bratislava,B.Bystrica), (B.Bystrica, Košice)
Teda medzi Zvolen a Bystricou existuje hrana, to znamená, že sa dá priamo dostať z jedného vrcholu do druhého, lebo medzi nimi existuje hrana.
Existuje hrana medzi Zvolenom a Košicami ? Nie, žiadna taká dvojica Zvolen, Košice sa v množine hrán nevyskytuje.
A mohla by byť hrana Zvolen, Zvolen ? Nie, v grafe nič také neexistuje.

Ďalej si povieme, čo v grafe znamená cesta. Cesta je taká postupnosť vrcholov a hrán, že sa v nej žiadna hrana ani vrchol neopakuje. Kedy existuje v grafe cesta ? Predstavte si to ako reálnu situáciu. Chcete ísť z Bratislavy do Košíc. Dostanete sa tam priamou hranou ? Nie, žiadna taká hrana neexistuje. Ale existuje hrana z Bratislavy do Bystrice a odtiaľ do Košíc. Opakuje sa tam nejaká hrana 2 krát ? Nie, takže je to cesta.

Sled je hocijáka postupnosť vrcholov a hrán, môže sa tam opakovať hocičo. Príklad sledu : (Zvolen), (Zvolen,Bystrica), Bystrica, (Bystrica,Kosice), Kosice, (Kosice,Bystrica), Bystrica
To v zátvorkách sú hrany a bez zátvoriek sú vrcholy.
Vrchol, hrana, vrchol, hrana, vrchol...

Ale vždy keď idete do nejaké vrcholu, tak môžete vyberať len takú hranu, ktorá ku tomu vrcholu vedie.
Napr. Zvolen, (Košice, Bystrica) nie je sled. Predstavte si to takto: sme vo Zvolene, poďme z Košíc do Bystrice. A ako ? Je to trochu proti logike.
Takisto ako, keby sme pri ceste chceli ísť cez to isté miesto 2 krát. Prečo ? Chceme ísť niekam a nie niekadiaľ. Potom by to už bol sled.

Existuje ešte aj pojem ťah, ale bez toho sa zaobídeme.

Tarry. Súvislosť grafu. Graf je súvislý, keď sa dá z každého miesta dostať do každého. Ak sa to nedá, tak potom tam existujú nejaké izolované časti, ktoré nech robia čokoľvek nikdy sa nedostanú ku inej izolovanej časti. Takýmto častiam sa hovorí komponent grafu.

Dijkstra. Najkratšia cesta. Hrany sú ohodnotené napr. dĺžkou. Teda sme vo vrchole X, chceme ísť do Y a máme nájsť najkratšiu cestu, teda poradie vrcholov, ako treba ísť, aby sme išli najkratšou cestou.

Floyd. To isté ako Dijkstra, ale s tým rozdielom, že zistí najkratšie cesty pre všetky vrcholy ku všetkým vrcholom. Výsledkom je matica, ktorá hovorí ako ďaleko je od ktorého ku ktorému.

Kruskal. Najlacnejšia kostra. Kostra je niečo, čo predstavuje podgraf, ktorý obsahuje všetky vrcholy a spája všetky vrcholy do jedného komponentu s minimálnym počtom hrán.
Príklad: Máme v kancelárii 50 počítačov, chceme ich všetky spojiť do LAN, a chceme to urobiť tak, aby sme minuli, čo najmenej kábla. Predpokladáme, že ich chceme spájať káblom a nie rádiovo ;o). Vieme, že niektoré počítače sa dajú spojiť priamo a vieme ako ďaleko sú od seba. Nie je podmienkou, aby sa každý počítač dal spojiť s každým, stačí, aby sa dal spojiť aspoň s jedným. Vytvorením kostry zistíme, ktoré počítače treba pospájať s ktorými, aby sme dosiahli, čo najlacnejšiu LAN.

Labyrintový algoritmus. Chceme nakresliť niečo jedným ťahom. Vieme, že tam existujú miesta, ktoré treba spojiť a vieme, ktoré môžeme spojiť a ktoré nemôžeme. Teda vieme vrcholy a hrany. Tento program nám napíše v akom poradí treba spájať vrcholy, aby sme dosiahli nakreslenie celého jedným ťahom.

CPM. Metóda časového plánovania. Asi nemá veľké využitie pri bežných algoritmoch. Ide o to, že máte definované činnosti, viete koľko trvajú a ktoré činnosti musia byť ukončené, aby tieto mohli začať. Napr. stavba domu, najprv treba vykopať základy, postaviť steny a až potom môžeme stavať strechu. A tento algoritmus zistí, v akom čase môže, ktorá činnosť začať, kedy musí skončiť, aby projekt skončil v čo najkratšom čase a akú majú jednotlivé činnosti časovú rezervu. Zistí celkový čas trvania projektu a kritickú cestu, teda poradie činnosti, ktoré určia celkové trvanie projektu.

Niektoré tieto algoritmy majú aj reálne využitie,... teda všetky majú reálne využitie, určite sa nejaké nájde, ale osobne za najužitočnejšie považujem algoritmus o najkratšej ceste. A asi najneužitočnejší pre Vás je CPM.

Dá sa to použiť v nejakých hrách, kde má panáčik niekam ísť a musí si nájsť cestu cez terén. Napr. stratégie ako Command and Conquer.

Úlohy, ktoré sa dajú previesť na úlohy téorie grafov je strašne veľa, všetko, čo sa dá reprezentovať ako množina vrcholov a hrán, prípadne ešte nejaká informácia naviac je úlohou z teórie grafov.

Koho to zaujalo natoľko, že by chcel vedieť viac, tomu odporúčam kúpiť si skriptá, alebo mu predám svoje ;o). Alebo si ich môže požičať od hocikoho, kto chodí na FRI.

Na záver ešte vtip nášho prednášajúceho: “Má to 800 gúľ a hučí to ako Niagara. Čo je to ? Alexandrovskij“

Všetky algoritmy v Pascale môžete stiahnuť tu:
http://www.softsklad.host.sk/grafy.zip

Ak sa chystáte na FRI, tak Vám to určite pomôže. A niektoré verzie skrípt sú aj v elektronickej podobe na stránke http://frcatel.fri.utc.sk ,nájdite odkaz na Stránku Stanislava Palúcha a tam už nájdete skriptá.




Najnovsie clanky od tohto redaktora
Podobne clanky