Bankovní institut vysoká škola Praha Katedra informatiky a kvantitativních metod
Úlohy systémové analýzy Diplomová práce
Autor:
Bc. Štěpán Jalovec Informační technologie a management
Vedoucí práce:
Praha
Ing. Vladimír Beneš, Ph.D.
Duben 2015
Prohlášení: Prohlašuji, ţe jsem diplomovou práci zpracoval samostatně a v seznamu uvedl veškerou pouţitou literaturu. Svým podpisem stvrzuji, ţe odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámen se skutečností, ţe se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze elektronických vysokoškolských prací.
V Praze dne
Poděkování Rád bych poděkoval svému vedoucímu diplomové práce, Ing. Vladimíru Benešovi, Ph.D. za jeho cenné rady a odborné vedení mé práce a mé rodině za její podporu.
Anotace Podmínkou pro správné pochopení přednášené problematiky je kvalitní studijní materiál. Základem studijního materiálu je studijní opora. Tato práce si klade za cíl seznámit s problematikou vytváření studijní opory a nabídnout aplikační program pro úpravy jiţ vytvořené studijní opory.
Klíčová slova: Typologie, piktogram, studijní opora, programovací jazyk
Anotation The condition for a proper understanding of what is teaching is quality study materials. The basis of the study material is study support. This thesis aims to familiarize students with the issue of creating learning support and offers application software for editing already created study materials.
Key words: Typology, pictogram, study support, programming language
Obsah Úvod ........................................................................................................................................... 9 1
Studijní opora ................................................................................................................... 10
2
Struktura studijní opory .................................................................................................... 11 2.1
2.1.1
První etapa .......................................................................................................... 12
2.1.2
Druhá etapa ......................................................................................................... 12
2.1.3
Třetí etapa ........................................................................................................... 12
2.2
3
4
5
Standardní postup tvorby studijního textu ................................................................. 12
Rozdělení studia studijní opory ................................................................................. 13
2.2.1
Rozpoznání obsahu a rozsahu opory .................................................................. 13
2.2.2
Vlastní otázky k problematice ............................................................................ 14
2.2.3
Čtení ................................................................................................................... 14
2.2.4
Ujasnění přednesené části ................................................................................... 14
2.2.5
Opakování........................................................................................................... 14
Typografie ........................................................................................................................ 15 3.1
Historie typografie ..................................................................................................... 15
3.2
Mikrotypografie ......................................................................................................... 15
3.3
Makrotypografie ........................................................................................................ 16
Piktogramy ....................................................................................................................... 16 4.1
Historie piktogramů ................................................................................................... 16
4.2
Dnešní piktogramy ..................................................................................................... 16
4.3
Edukační význam ....................................................................................................... 17
4.4
Pouţité piktogramy .................................................................................................... 19
Popis funkcí aplikace ........................................................................................................ 20 5.1
Analýza jednotlivých funkcí ...................................................................................... 20
5.2
Scénář pouţití aplikace .............................................................................................. 20
5.3
Modelové znázornění pouţití aplikace ...................................................................... 20 5
6
5.3.1
Sekvenční diagram ............................................................................................. 21
5.3.2
Diagram aktivit ................................................................................................... 21
Popis postupu výběru programovacího jazyka ................................................................. 23 6.1
6.1.1
C++ ..................................................................................................................... 23
6.1.2
PHP ..................................................................................................................... 23
6.1.3
Java ..................................................................................................................... 24
6.1.4
C# ....................................................................................................................... 24
6.2
Problémy jednotlivých uvaţovaných programovacích jazyků .................................. 24
6.2.1
Nevýhody C++ ................................................................................................... 24
6.2.2
Nevýhody PHP ................................................................................................... 25
6.2.3
Nevýhody Java ................................................................................................... 25
6.2.4
Nevýhody C# ...................................................................................................... 25
6.3
Výhody jednotlivých programovacích jazyků ........................................................... 26
6.3.1
Výhody C++ ....................................................................................................... 26
6.3.2
Výhody PHP ....................................................................................................... 26
6.3.3
Výhody Java ....................................................................................................... 26
6.3.4
Výhody C#.......................................................................................................... 27
6.4 7
Jaké jazyky byly zvaţovány? ..................................................................................... 23
Pouţitý programovací jazyk ...................................................................................... 27
Popis vývoje programu ..................................................................................................... 28 7.1
Mnoţina pouţitých řídících znaků ............................................................................. 28
8
Vloţený kód programu ..................................................................................................... 29
9
Vysvětlení kódu programu ............................................................................................... 32 9.1
Knihovny programu ................................................................................................... 32
9.2
Třídy........................................................................................................................... 32
9.3
Hlavní funkce ............................................................................................................. 33
9.3.1
Otevření dokumentu ........................................................................................... 33 6
10
9.3.2
Nahrazení řídícího znaku piktogramem ............................................................. 33
9.3.3
Uloţení dokumentu ............................................................................................ 33
Učební text pouţitý jako příklad pro vytvoření studijní opory ....................................... 34 10.1
Systémová analýza ................................................................................................. 34
10.1.1
Úlohy v systému ................................................................................................. 35
10.1.2
Úlohy o systému ................................................................................................. 35
10.1.3
Úlohy na systém ................................................................................................. 35
10.2
Úloha o cestách ...................................................................................................... 37
10.3
Úlohy o hledání nejkratší cesty v grafu.................................................................. 38
10.3.1
Dijkstrův algoritmus ........................................................................................... 38
10.3.2
Floyd - Warshallův algoritmus ........................................................................... 41
10.4
Hledání minimální kostry grafu ............................................................................. 44
10.4.1
Borůvkův algoritmus .......................................................................................... 45
10.4.2
Kruskalův algoritmus ......................................................................................... 47
10.4.3
Jarníkův algoritmus ............................................................................................ 50 Hledání cesty „Bloudění v bludišti“ ....................................................................... 52
10.6
Eulerovský tah ........................................................................................................ 52
10.7
Úloha obchodního cestujícího ................................................................................ 53
11
10.5
10.7.1
Problém obchodního cestujícího ........................................................................ 54
10.7.2
Pošťákův problém............................................................................................... 54
10.7.3
Problém kropicího vozu ..................................................................................... 54
Výsledek po překladu ....................................................................................................... 55 11.1
Systémová analýza ................................................................................................. 55
11.1.1
Úlohy v systému ................................................................................................. 56
11.1.2
Úlohy o systému ................................................................................................. 56
11.1.3
Úlohy na systém ................................................................................................. 57
11.2
Úloha o cestách ...................................................................................................... 59 7
11.3
Úlohy o hledání nejkratší cesty v grafu.................................................................. 60
11.3.1
Dijkstrův algoritmus ........................................................................................... 60
11.3.2
Floyd - Warshallův algoritmus ........................................................................... 62
11.4
Hledání minimální kostry grafu ............................................................................. 65
11.4.1
Borůvkův algoritmus .......................................................................................... 67
11.4.2
Kruskalův algoritmus ......................................................................................... 70
11.4.3
Jarníkův algoritmus ............................................................................................ 72
11.5
Hledání cesty „Bloudění v bludišti“ ....................................................................... 74
11.6
Eulerovský tah ........................................................................................................ 74
11.7
Úloha obchodního cestujícího ................................................................................ 76
11.7.1
Problém obchodního cestujícího ........................................................................ 76
11.7.2
Pošťákův problém............................................................................................... 77
11.7.3
Problém kropicího vozu ..................................................................................... 77
Závěr ......................................................................................................................................... 78 Zdroje ....................................................................................................................................... 79 Seznam obrázků, diagramů a tabulek ....................................................................................... 82
8
Úvod Tato diplomová práce si klade za cíl seznámit s problematikou studijní opory, vytvořit a popsat aplikační software, který by měl usnadnit práci pedagogů při vzdělávání. Vytvořit kvalitní výukový materiál je jedna strana mince, druhou je její prezentace - způsob, jakým je předávána studentům, posluchačům. První část diplomové práce je věnována teoretické části studijní opory. Diplomová práce je v této části rozdělena do kapitol, které se postupně věnují typografii, piktogramům a obecné teorii o vytváření studijní opory. Ve druhé části diplomové práce je popsán proces výběru programovacího jazyka, ve kterém je vypracována praktická část této diplomové práce. Budou vysvětleny důvody, které vedly k výběru pouţitého jazyka a okolnosti, překáţky a problémy, které bylo potřeba překonat před samotným vývojem aplikace. Ve třetí části diplomové práce bude popsán pracovní postup vytvoření programové aplikace. Na konci této části diplomové práce bude vloţen kód programu praktické části diplomové práce a bude vysvětlen a popsán. Součástí této části je také seznam pouţitých řídících znaků. Poslední část práce bude obsahovat ukázkový text studijní opory před a po pouţití konverze aplikačním programem vytvořeným v rámci této diplomové práce.
9
1 Studijní opora Nejenom učebnice, ale i naučné publikace pouţívají k lepšímu rozdělení svého obsahu různé grafické značky, fonty písma, podbarvení textu a další pomůcky. Pouţití těchto pomůcek (značek) v textu pomáhá k lepší orientaci a lepšímu pochopení struktury obsahu. Výhodou při studiu je rozdělení textu do pevně dané struktury, která je dodrţována v celé délce textu. Cílem uţití těchto dvou pomůcek, značek a strukturnímu rozdělení textu, je vytvořit takový textový materiál, který bude srozumitelný, bude přehledný a bude poskytovat zpětnou vazbu čtenáři. Kdyţ mluvíme o zpětné vazbě, můţe vyvstat otázka, co je myšleno zpětnou vazbou. Zpětná vazba je určitá sebekontrola. Kontrola čtenářem získaných znalostí při studiu daného učebního materiálu. Tato zpětná vazba je nápomocná v případech, kdy na probranou látku přímo navazuje látka v další kapitole/kapitolách. Bez dostatečných znalostí pak můţe mít student problémy s pochopením další látky. Za příklad je moţné vzít si učebnici matematiky. Na konci kaţdé kapitoly je seznam otázek týkajících se teoretické částky látky, které by měl student zodpovědět a několik příkladů k praktickému ověření získaných znalostí. Pro kontrolu správnosti je pro kaţdý příklad přiloţen klíč ke správnému řešení. Základní otázkou, při pouţívání grafického rozdělení textu pomocí značek, je určení kolik druhů značek pouţívat. Stylů textu a značek by mělo být takové mnoţství, aby si je čtenář dokázal jednoduše zapamatovat a následně je pouţíval v průběhu četby studijní opory automaticky. Podmínkou je, aby výskyt – četnost pouţití nerušila kontinuitu sdělovaných informací. Stejnou otázku jsem si poloţil, kdyţ jsem přemýšlel kolik druhů různých značek pouţít v praktické části této diplomové práci. Bylo potřeba si uvědomit, jak bude vypadat a co bude obsahovat text, ke kterému se budou značky doplňovat. Při pouţívání grafických značek je důleţitý jejich vzhled. Při prvním pohledu na pouţitou značku musí být jasné, co daný symbol představuje. Pokud pro kontrolní otázky pro ověření znalostí studenta na konci kapitoly pouţijeme symbol otazníku, musí být na první pohled jasné, o jaký symbol se jedná. Současně by symboly neměly být vzájemně zaměnitelné. Docházelo by tak zbytečně k matení studenta.
10
2 Struktura studijní opory Studijní opora nebo také studijní text je didakticky strukturovaný text, který má za cíl v maximální moţné míře usnadnit studium látky. Učivo je ve studijní opoře rovnoměrně rozloţeno a na konci kaţdé určité části kapitoly jsou vloţeny zpětnovazební prvky. Tyto zpětnovazební prvky mají za cíl prověřit znalost a pochopení učiva a schopnost znalosti pouţívat. Jako příklad lze uvést studijní oporu pro předmět matematika, kde na konci kaţdé kapitoly je několik příkladů ke spočítání, které prakticky ukazují principy popsané v předcházející, výkladové části materiálu. Struktura studijní opory je pevně daná. Text je graficky členěn, dělí se na určité části s vlastním zaměřením a bývá doplněn piktogramy. Studijní opora a učebnice se od sebe liší. Funkcí učebnice je doplnit prezenční výuku. Studijní opora pokládá základy pro další vzdělávání v oblasti, především ve formě samostudia. Text studijní opory je jasný, rozdělen do krátkých vět a odstavců. Uţití cizích slov je výjimečné. Oproti tomu text učebnice je nepřerušován, jazyk textu bývá sloţitý a často jsou pouţita cizí slova. Učebnice pouţívají grafiku jako doplněk k textu. Ve studijní opoře je grafika velice důleţitá, dá se říci klíčová a kromě zmíněných piktogramů se pouţívají i různé fonty textu, ohraničení, podbarvení atd. Cílem je rozlišit text tak, aby při pouţívání bylo na první pohled jasné, čeho se daná část textu týká. Velikým rozdílem mezi studijní oporou a učebnicí je mimo jiné v předpokladu motivace studenta. U učebnice se motivace předpokládá, kdeţto studijní opora by měla vyvolat zájem o látku a zájem o další studium. Učebnice neobsahují na rozdíl od učební opory, jak bylo popsáno na začátku této části, zpětnou vazbu. Neobsahují kontrolní otázky na probranou látku, praktické příklady apod. Kapitola studijní opory se nejčastěji dělí takto: Vymezení studijních cílů Uvedení do problematiky (pouţití klíčových slov) Vlastní text Příklady Shrnutí Cvičení, otázky, testy, … Klíč k řešení úkolů a příkladů 11
2.1 Standardní postup tvorby studijního textu Studijní text se zpravidla vytváří ve třech etapách v závislosti na osobě, která ji tvoří.
2.1.1 První etapa Většinou odborník pro danou oblast napíše souvislý nepřerušený text podle předem stanoveného zadání. Dále vytvoří příklady, grafiku a na konec textu zařadí závěrečné shrnutí, otázky a cvičení. Odborník garantuje odbornou úroveň předkládaného studijního textu.
2.1.2 Druhá etapa Ve druhé fázi je na osobě metodika, aby text posoudil z hlediska pouţité metodiky a zda text splňuje didaktické principy. Metodik posoudí zda text splňuje pravidla zadané metodiky a plní funkce nutné pro studium a samostudium.
2.1.3 Třetí etapa V poslední etapě grafik upraví text do jednotné a systematické úpravy. Text by po této etapě mel být přehledný a měl by vzhledově odpovídat ostatním studijním textům.
Didaktické principy: Text musí zohledňovat úroveň vstupních znalostí. Struktura text musí být logická a musí být jednotná v celém studijním textu. V úvodu kaţdé kapitoly jsou formulovány konkrétní dílčí cíle. Kaţdá kapitola musí dodrţovat jednotnou strukturu. Text by měl být rozdělen na krátké odstavce. Věty by neměly být příliš dlouhé. Studijní text by neměl obsahovat příliš cizích slov. Do textu by měly být zahrnuty schémata, přehledy, tabulky a jejich vztahů ke studijnímu textu. Studijní text se člení na kapitoly. Kapitoly se dále rozdělují na studijní cíle a vlastní látku. Studijní cíle musí být jasně formulované. Měly by obsahovat popis toho, co by měl student po prostudování příslušné kapitoly znát, umět nebo schopen vykonat. Vlastní látka ke studiu by měla splňovat určité zásady. Text by měl být rozčleněn do krátkých odstavců s tím, ţe kaţdý odstavec by se měl věnovat pouze jedné konkrétní myšlence. Věty 12
by neměly být dlouhé, pokud moţno, mělo by se jednat spíše o kratší věty. Věty by neměly být spojeny v obsáhlá souvětí. Cizí slova by se měla pouţívat v nejnutnějších případech. Upřednostňovat by se měla slova obvyklá a obecně známá. Při pouţití cizího slova nebo odborného termínu je potřeba dané slovo hned vysvětlit, i opakovaně. Všechny ucelené části by měly být rozděleny do kapitol. Kapitoly by měly být opatřeny nadpisem. Pokud se jedná o delší kapitolu, měla by být pro větší přehlednost rozdělena do označených podkapitol. U označení kapitol a podkapitol je doporučeno pro lepší přehlednost pouţít číslování kapitol. Pro vlastní text je moţné pouţít libovolné formátování. Je nutné mít stále na paměti dodrţování stejného způsobu formátování v celém textu. Pro studijní text je přínosné pouţívat ilustrace. Je potřeba, při výběru ilustrací, obrázků nebo náčrtků myslet na vypovídající hodnotu dané ilustrace. Jednoduché náčrty nemusí vypadat v textu zajímavě, ale v mnohých případech kvalitní náčrt poslouţí k pochopení látky lépe. Kaţdá kapitola by měla na svém konci obsahovat shrnutí obsahu z probírané kapitoly. V shrnutí by měly být zopakovány klíčové body. V rámci shrnutí by měly být studentovi poloţeny kontrolní otázky, případně úloha k vyřešení (dle charakteru látky).
2.2 Rozdělení studia studijní opory Pro správné pouţívání studijní opory je potřeba zmínit také pohled z druhé strany, tedy z pohledu studenta. Studium opory lze rozdělit na 5 úseků: 1. Rozpoznání obsahu a rozsahu opory. 2. Vlastní otázky k problematice. 3. Čtení. 4. Ujasnění přednesené části. 5. Opakování.
2.2.1 Rozpoznání obsahu a rozsahu opory K tomuto slouţí dobře strukturovaný text opory, pouţitý jazyk a jeho odborná úroveň. Jak bylo uvedeno výše, je vhodné pouţívání jednoduchých vět a vyhýbat se dlouhým, košatým souvětím. 13
2.2.2 Vlastní otázky k problematice Při psaní studijní opory a popisu problematiky je potřeba se vţít do role studenta a představit si, jaké otázky si sám pokládá. Opora by takové otázky měla předpokládat a odpověď na ně. Forma odpovědi je volná. Můţe se jednat o prostý text, grafiku nebo příklad.
2.2.3 Čtení Jak bylo popsáno výše: výsledkem uţití správné úrovně odborného jazyka, cizích slov a skladby vět by měla být studijní opora, která se dobře čte a je srozumitelná. Student by se neměl ztrácet v textu z důvodu délky souvětí nebo přílišného pouţití cizích nebo odborných termínů.
2.2.4 Ujasnění přednesené části Člověk můţe zpracovat informaci čtyřmi způsoby: vědět, rozumět, aplikovat, rozvinout. První způsob je samotný proces získání informace. Nejčastěji se informace získávají čtením nebo poslechem. Porozumění informaci znamená, ţe člověk dokáţe získanou vědomost vysvětlit jiné osobě. Aplikací je myšleno umět pouţít získané znalostí v praxi. Posledním způsobem je rozvinutí znalostí v souvislosti s jinými myšlenkami, zkušenostmi a znalostmi, kterými daná osoba, a nebo osoby disponují.
2.2.5 Opakování Pro naučení se novým znalostem je dobré opakování probrané látky, postupů nebo termínů. Pokud se studijní opora v textu vrací k jiţ probrané látce je příhodné zopakovat stěţejní informace (například jména, pracovní postup) neţ pouţít strohý odkaz na danou část studijní opory (ten by ale také neměl chybět).
14
3 Typografie Typografie je umělecko-technický obor zabývající se tiskovým písmem. Další členění oboru je dle oblasti, kterou zabývá.
3.1 Historie typografie První zmínky o typografii (z dnešního pohledu) pocházejí z Mezopotámie, kdy pro vytvoření textu z klínového písma byla pouţita rákosová pisátka. Babyloňané pouţívali k vytlačování obrázkového písma do hlíny tzv. pečetní válečky Způsob zaznamenávání a vytváření textů se vyvíjel aţ do doby, kdy byl vymyšlen systém pohyblivé litery. Jedná se o princip, kdy je kaţdé písmeno vytlačováno do tiskového podkladu za pomocí jedné tiskařské litery. Ze začátku byly litery ve starověké Číně hliněné nebo dřevěné. Problémem hliněných a dřevěných liter bylo (relativně) rychlé opotřebení. Začaly se proto pouţívat litery z vypálené hlíny, tedy keramické nebo porcelánové. Kovové litery se začaly pouţívat v Koreji. V Číně na to navázala výroba bronzových tiskařských liter. Přibliţně ve stejné době jako ve východní Asii došlo i v Evropě k vynálezu pohyblivé litery a to německým zlatníkem Johannesem Gutenbergem. Gutenberg pouţil jako materiál pro výrobu liter slitinu z olova (přesně to byla slitina z cínu, olova a antimonu) tak kvalitní, ţe vydrţely do dnešní doby a lze je stále pouţívat. Zajímavostí můţe být, ţe první kniha, kterou Johannes Gutenberg na svém knihtisku vytisknul, byla v letech 1454 Bible1.
3.2 Mikrotypografie Mikrotypografie pracuje na uspořádání textu, například psaní mezer a písmem samotným. Navrhuje a tvoří vzhled písma, typografii písmen, čísel a dalších znaků. Úkolem mikrotypografie je zvýšení estetické kvality sazby. Mikrotypografie pracuje s následujícími technikami: Úpravy šířky znaků a mezer. Optimalizace mezislovních mezer. Zúţení nebo roztaţení znakových mezer.
1
Tzv. Gutenbergova 42řádková bible. Zdroj: http://text.nkp.cz/o-knihovne/zakladni-informace/klementinskanej/gutenbergovy-tisky
15
Techniky mikrotypografie se uplatňují především při zarovnání textu do bloku. O mikrotypografii hovoříme také ve spojitosti s uměleckým písmem.
3.3 Makrotypografie Makrotypografie se zaměřuje na sloţení textu jako celku. Zabývá se celkovým dojmem ze sazby, vzhledu textu. Současně se klade důraz na funkci a estetiku textu. Stará se o to, aby text byl dobře čitelný ve vztahu k rozmístění odstavců, ilustracím, piktogramům a dalším textem.
4 Piktogramy Piktogram je grafický znak znázorňující pojem nebo sdělení obrazově2. Jsou to maximálně zjednodušená zobrazení předmětů nebo činností. Cílem piktogramů je univerzální nástroj pro komunikaci bez pouţití slov nebo jazyka.
4.1 Historie piktogramů Člověk začal pouţívat piktogramy uţ od pravěku, kdy na stěny jeskyně kreslil obrázky – piktogramy mamutů, lidí a pouţíval tyto nástěnné malby např. jako plán útoku při lovu. Piktogramy se postupem času vyvíjely. Přibývaly nové symboly, jejich mnoţství narůstalo a začaly zobrazovat stále větší část kaţdodenního ţivota člověka. Z piktogramů se vývojem v čase stalo první obrázkové písmo. Obrázkové písmo pouţívali např. Egypťané nebo Sumerové. Některé kmeny v Africe, Jiţní Americe nebo Oceánii pouţívají obrázkové písmo i dnes.
4.2 Dnešní piktogramy Piktogramy, z pohledu dnešního pouţívání a chápání, začaly být pouţívány přibliţně v období druhé světové války na mapách londýnských příměstských ţeleznic. Piktogramy na této mapě nesly informace ohledně zařízení, která se nacházela v prostorách nádraţí nebo v jeho blízkosti3. Piktogramy se dnes pouţívají zcela běţně. Slouţí jako schematické, reprezentační znamení – symbol nebo návod.
2 3
Zdroj: http://slovnik-cizich-slov.abz.cz/web.php/slovo/piktogram Zdroje: http://www.steamindex.com/library/dow.htm a http://en.wikipedia.org/wiki/Transit_map
16
Pro svůj jednoznačný význam přesahují piktogramy hranice států a pouţívají se celosvětově. Nejčastěji se s nimi lze setkat v dopravě jako s dopravním značením, v turistice jako značení cest nebo označení tábořišť, při označení budov jako je nemocnice nebo letiště nebo oblastní vědy. Piktogramy se pouţívají také v uţivatelských příručkách nebo v oděvním průmyslu. V poslední době je velice oblíbené při statistických šetřeních nebo při jiných kvantitativních měřeních pouţívat piktogramy jako vyjádření zjištěného mnoţství. Součástí takového zobrazení je klíč (legenda), který vysvětluje, jaké mnoţství kaţdý jeden piktogram představuje. Podmínkou je, aby všechny piktogramy byly stejně veliké. Je dovoleno zobrazit pouze část piktogramu k vyjádření dílčího mnoţství. Například pokud by piktogram jedné poštovní obálky znázornil 10 odeslaných dopisů, pro vyjádření 15 odeslaných dopisů by se pouţil jeden a půl piktogramu, viz ukázka:
Den
Počet dopisů
Den
Pondělí
20
Pondělí
Úterý
5
Úterý
Počet dopisů
= 10 dopisů
Důvody pouţití piktogramů jsou lepší orientace, větší přehlednost a rychlejší práce. Z jednoho celkového pohledu lze okamţitě vyčíst rozdíly. Pro některá šetření se toto znázornění pouţívá ke zvýšení atraktivnosti prezentace výsledků. Za obdobu tohoto postupu můţeme povaţovat tzv. „koláčové grafy“.
4.3 Edukační význam Pouţívání piktogramů v textu se zařazuje do oboru alternativní a augmentativní komunikace4. Tento způsob komunikace se pouţívá při komunikaci s lidmi, kteří trpí závaţnými poruchami řeči, jazyk a psaní. Při tomto způsobu komunikace mají piktogramy za úkol podporovat komunikační schopnosti postiţené osoby a v některých případech nahrazovat mluvenou řeč. Piktogramy se také pouţívají při práci s mentálně postiţenými lidmi a dětmi.
4
Více: http://slovnik-cizich-slov.abz.cz/web.php/slovo/augmentativni-komunikace
17
Obrázek 1: Příklad pouţití piktogramu jako míry mnoţství
Zdroj: http://en.wikipedia.org/wiki/Pictogram#/media/File:Titanic_casualties.svg
18
4.4 Použité piktogramy Pro tuto diplomovou práci bylo vybráno celkem 8 různých piktogramů pro text studijní opory.
T
C Cíle kapitoly
Test
P
Č Čas k nastudování
Příklad
D L
S Doplňková literatura
Shrnutí
D
V Definice
Výuka - studijní text
19
5 Popis funkcí aplikace Před tím, neţ popíšu postup výběru programovacího jazyka, budu se v této kapitole věnovat popisu funkcí vytvořené aplikace.
5.1 Analýza jednotlivých funkcí Aplikace má tři základní funkce: Načte uţivatelem vybraný soubor. Nahradí řídící znak5 za piktogram. Uloţí výsledek procesu do nového souboru.
5.2 Scénář použití aplikace Aplikace má pouze jednu uţivatelskou funkci a tou je načtení určitého souboru pro úpravu textu. Při spuštění je uţivatel vyzván k určení souboru obsahující text pro úpravu. Určení je prováděno vypsáním adresy v počítači, kde se soubor nachází. Poté je vyzván k určení cílové adresy, kam se má upravený soubor uloţit. Adresa musí obsahovat také jméno souboru a jeho koncovku. Program rozlišuje typy dokumentu s koncovkou docx a doc. Lze tedy určit v jakém formátu má být soubor uloţen. Následuje automatický proces, kdy aplikace čte celý dokument a hledá předem dané textové řetězce (string6) - řídící znaky, které nahrazuje k nim přiřazenými piktogramy (viz kapitola 4.4). Po dokončení procesu nahrazení řídících znaků příslušným piktogramem se objeví informační zpráva pro uţivatele a soubor s doplněnými piktogramy se uloţí na uţivatelem určené místo s poţadovaným jménem a v poţadovaném formátu.
5.3 Modelové znázornění použití aplikace Dále budou znázorněny různé scénáře, sekvence a aktivity aplikace v jednotlivých UML diagramech. Pro vytvoření diagramů byl pouţit program StarUML.
5 6
Řídícím znakem je myšlen speciální textový řetězec, který je pro potřeby aplikace pro jednotlivé piktogramy předem jasně definován. Definice: Textový řetězec (string) je v programování název datového typu slouţícího k uloţení konečné posloupnosti znaků.
20
5.3.1 Sekvenční diagram Následuje sekvenční diagram pouţití aplikace. Celou sekvenci začíná aktér „Uţivatel“, který je po zapnutí aplikace vyzván k určení souboru pro provedení úpravy. Po vybrání souboru aplikace převede řídící znaky na piktogramy a uloţí soubor. Uţivateli je zobrazena informační zpráva o dokončení procesu.
Obrázek 2: Sekvenční diagram pouţití aplikace
Zdroj: Vlastní
5.3.2 Diagram aktivit Následující diagram aktivit popisuje stav dokumentu, určeného pro úpravu. V prvním stavu je dokument vytvořen a uţivatel do něj vloţí předem známé řídící znaky. Následně jej uţivatel po výzvě vybere a aplikace sis jej nahraje. Tato nahraný soubor přečte a
21
všechny nalezené řídící znaky vymění za připravené piktogramy. Poté celý soubor uloţí jako nový dokument.
Obrázek 3: Diagram stavu dokumentu
Zdroj: Vlastní
22
6 Popis postupu výběru programovacího jazyka V následujících kapitolách popíši, jak jsem postupoval při výběru programovacího jazyka pro vytvoření aplikace pro praktickou část této diplomové práce. V samostatných kapitolách budou popsány samotné programovací jazyky, jejich obecné nedostatky a přednosti. U některých jazyků budou popsány problémy, které bylo potřeba překonat při vytváření programu.
6.1 Jaké jazyky byly zvažovány? Pečlivě jsem vybíral programovací jazyk, ve kterém je nakonec aplikace naprogramována. Kaţdá jednotlivá kapitola je věnována jednomu určitému programovacímu jazyku. Pořadí kapitol odpovídá pořadí, ve které byly jednotlivé jazyky zvaţovány a prakticky vyzkoušeny pro realizaci aplikace.
6.1.1 C++ Jako první jazyk jsem k vytvoření aplikace pro praktickou část diplomové práce zvolil jazyk C++. Pro tento jazyk jsem se rozhodl z důvodu vlastního studia tohoto jazyka. C++ je volně šiřitelný a pouţitelný programovací jazyk odvozený od jazyka C. Od roku 1998 je spravován a udrţován komisí organizace ISO7. Pracuje s nativním kódem počítače, proto se obecně povaţuje za nejrychlejší programovací jazyk. Od programátora očekává absolutní znalost jazyku a chování počítačů. Na oplátku umoţňuje obrovskou kontrolu nad průběhem programu a vyuţití paměti počítače. Umoţňuje strukturní, procedurální i objektově orientované programování. Vzhledem k otevřenosti jazyka a široké škále kompilátorů8 je moţné, prakticky bez rozdílu, pracovat a pouţívat jazyk C++ téměř na všech platformách.
6.1.2 PHP Druhou moţností byl jazyk PHP9. Jazyk PHP vznikl původně pro vytváření internetových stránek. Odtud i původní název jazyka. V dnešní době lze PHP vyuţít i pro tvorbu aplikací. Stejně jako C++ je jazyk PHP volně šiřitelný jazyk, spravovaný organizací PHP Group.
7 8 9
ISO (International Organization for Standardization), jedná se o organizaci spravující mezinárodní standardy v různých oblastech lidské činnosti. více: http://www.iso.org/iso/home/about.htm Téţ překladač, je softwarový nástroj pouţívaný pro vývoj softwaru. Původně z anglického Personal Home Page
23
Obliba jazyku PHP velice rychle roste. Na začátku roku 2013 byl jazyk PHP na 240 miliónech internetových stránek a 2,1 miliónů webových serverů10.
6.1.3 Java Java je objektově orientovaný jazyk vyvinutý společností Sun Microsystems. Jedná se o nejpouţívanější programovací jazyk současnosti11. S jazykem Java se setkáváme i v běţném ţivotě. Mobilní telefony, Blue-Ray přehrávače i televize pouţívají jazyk Java při svém provozu.
6.1.4 C# Je programovací jazyk vyvinutý společností Microsoft společně s platformou .NET. Jde o víceúrovňový objektově orientovaný jazyk zaloţený na jazycích C++ a Java. Pomocí jazyka C# lze vytvářet desktopové aplikace, konzolové aplikace, vytvářet webové stránky, databázové programy a software pro mobilní zařízení jako jsou chytré telefony a tablety. Oproti jazyku C++ jsou některé funkce a metody omezené, například v jazyce C# neexistuje vícenásobná dědičnost, jazyk je bezpečnější a povaţuje se za snadněji naučitelný (oproti C++).
6.2 Problémy jednotlivých uvažovaných programovacích jazyků Před vyjmenováním specifických problémů při pouţití jednotlivých jazyků je potřeba si vyjmenovat omezení a specifikace k aplikaci: Zdrojový dokument musí být dokument Word nebo RTF12. Formát upraveného dokumentu musí být dokument Word nebo dokument PDF. Za řídícím znakem musí být vloţena mezera.
6.2.1 Nevýhody C++ Při pouţití jazyka C++ bylo potřeba vyřešit několik zásadních a několik menších problémů.
10
Zdroj: http://news.netcraft.com/archives/2013/01/31/php-just-grows-grows.html Zdroj: http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html 12 Z anglického Rich Text Format. Jedná se o dokumenty obsahující kresby, komentáře, vloţené fonty nebo některé formáty obrázků 11
24
Jeden z problémů, které bylo potřeba vyřešit, bylo pouţívání české diakritiky. Česká diakritika není standardně v C++ podporována. Bylo potřeba najít takovou knihovnu, která umoţní uţivatelsky zadané hodnoty přijmout s českou diakritikou a pouţívat ji. Tento nedostatek jazyka C++ byl nakonec vyřešen knihovnou
. Zásadním problémem a důvodem pro odstoupení od jazyka C++ pro vytvoření aplikace bylo nedostatečné zpracování formátu textu. Během procesu záměny řídících znaků docházelo k rozpadu formátování textu. Dalším problémem bylo čtení obrázků z původního dokumentu. Obrázky v textu nezpůsobovaly ţádné chyby při čtení, ale aplikace je při čtení ignorovala. To mělo za následek, ţe v upraveném dokumentu se ţádný z obrázků nevyskytoval.
6.2.2 Nevýhody PHP Pouţitím jazyka PHP a příslušné knihovny odpadl problém s načítáním obrázků z dokumentu. Nicméně se znovu objevil problém s českou diakritikou, který se v kombinaci s knihovnou na čtení dokumentu nepodařilo odstranit. Nedostatkem pro pouţití jazyka PHP je nutnost pouţití serveru, na kterém je aplikace uloţena a ze kterého se spouští. K aplikaci se pak přistupuje skrz internetový prohlíţeč. Pro práci s aplikací je tedy nutné, aby byl uţivatel připojen do místní sítě, ve které se server s nainstalovanou aplikací nachází. Druhou variantou je připojení se k serveru přes internet.
6.2.3 Nevýhody Java Při analýze řešení aplikace byl předpoklad, ţe vzhledem k různé velikosti nahrávaného textu bude program dynamicky alokovat potřebnou paměť. Při pouţití jazyku Java je tento předpoklad nerealizovatelný. Jazyk Java nemá nástroje pro práci s pamětí a tak bylo potřeba dobře zváţit, kolik paměti bude potřeba. Z toho vyplývá, ţe při pouţití programu vytvořeného v jazyce Java se automaticky alokuje největší moţné mnoţství paměti, které je nadefinováno v programu.
6.2.4 Nevýhody C# Jazyk C# je závislý na .NET framework od společnosti Microsoft. Cokoliv, co není součástí .NET Framework, je velice obtíţné implementovat. Tato podmínka velice stěţuje vývoj programů v tomto jazyce a omezuje vývoj na platformu Windows.
25
Jazyk C# je oproti jazyku C++ pomalejší13.
6.3 Výhody jednotlivých programovacích jazyků Kaţdý programovací jazyk má svoje obecné výhody a nevýhody. V následující kapitole se pokusím vypsat ty výhody, které mají nějaký vztah k řešené úloze vytvoření aplikace pro přípravu textu studijní opory.
6.3.1 Výhody C++ Zásadní výhodou jazyka C++ oproti ostatním uvaţovaným jazykům je moţnost dynamicky alokovat paměť a tak celý program zrychlit a současně sníţit náročnost programu. Nespornou výhodou práce s C++ je, ţe výsledkem kompilace kódu je běţně spustitelný program. Ke spuštění programu pak není potřeba připojení k internetu, ani ţádných dalších jiných programů nebo zvláštních postupů. Ze všech uvaţovaných variant se jedná o nejrychlejší programovací jazyk.
6.3.2 Výhody PHP Výhodou vyuţití PHP bylo univerzálnost pouţití aplikace. Aplikace by byla uloţena na serveru a přístup k ní by byl skrze internetový prohlíţeč. Díky tomu by byla aplikace bez problému přístupná pro velký počet různých operačních systémů a současně, by bylo moţné s ní pracovat i na mobilních zařízeních, jako jsou tablety nebo chytré telefony.
6.3.3 Výhody Java Java je navrţena tak, aby bylo snadné se ji naučit, pouţívat, psát, kompilovat a ladit neţ jiné programovací jazyky. Java je objektově orientovaný jazyk. To umoţňuje vytvářet modulární programy a objekty. Jednou z největších výhod je jeho schopnost snadno přecházet mezi platformami počítačů. Moţnost spustit stejný program na mnoha různých systémech je rozhodující pro webové aplikace. Java má bezpečnost jako součást svého designu. Překladač a vývojová prostředí obsahují automatické nástroje pro kontrolu kódu a jeho struktury.
13
Zdroj: https://chiafong6799.wordpress.com/2006/07/11/advantages-and-disadvantages-of-c-as-compared-to-c/
26
Jazyk Java je spolehlivý. Kompilátory jazyka Java jsou schopny detekovat moţné problémy ještě před spuštěním programu. Java umoţňuje vykonávat více úloh v rámci jednoho programu současně.
6.3.4 Výhody C# Díky převzatým prvkům z jazyku Java a syntaxi z jazyku C++ lze vytvářet téměř bezchybné programy. Velikou výhodou jazyka C# je jeho bezpečnost. Uţ při kompilaci kódu programu je předem vyhodnocováno riziko a chyby, které se můţou vyskytnout při pouţívání programu. Údrţba kódu je mnohem snazší neţ u jazyka C++. Jazyk C# můţe být vyuţit pro tvorbu široké škály aplikací, od jednoduchých ovládacích prvků po sloţité webové sluţby nebo pro vyuţití v robotice.
6.4 Použitý programovací jazyk Na základě poznatků, výhod a nevýhod jednotlivých programovacích jazyků jsem se rozhodl pro vytvoření programu pouţít jazyk C# a to zejména z důvodů: Nativní podpora diakritiky a české latinky. Nástroje pro práci s ostatními programy společnosti Microsoft. Volně staţitelné oficiální vývojové prostředí.
27
7 Popis vývoje programu Před samotným vývojem programu bylo potřeba vybrat takový programovací jazyk, který dokáţe pracovat s dokumenty. Tedy je otevřít, upravit a následně uloţit jako nový soubor. Výhody a nevýhody uvaţovaných programovacích jazyků jsou vypsány v předchozích kapitolách.
7.1 Množina použitých řídících znaků Obsahem této kapitoly je seznam pouţitých řídících znaků společně s piktogramem, který reprezentují. Při vytváření řídících znaků bylo cílem vytvořit jednoduše zapamatovatelný řetězec, který by co nejlépe odpovídal piktogramu, který zastupuje.
Tabulka 1: Přehled piktogramů a řídících znaků Piktogram
Řídící znak
Piktogram
Řídící znak
C
@C
T
@T
Č
@Č
P
@P
D L
@L
S
@S
D
@D
V
@V
Zdroj: Vlastní
28
8 Vložený kód programu V této kapitole se věnuji popisu kódu programu pro úpravu vzoru studijní opory. Kód je vloţen bez úpravy formátování přímo z vývojového prostředí. Je zachováno rozloţení a struktura kódu vývojového prostředí Microsoft Visual Express Studio 2013. using System; using System.Drawing.Imaging; using System.Text.RegularExpressions; using Aspose.Words; using Aspose.Words.Drawing; namespace Uprava_textu {
public class ObrazekT : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\T.png"); Console.WriteLine("Nahrazuji piktogram T"); e.Replacement = ""; return ReplaceAction.Replace; } } public class ObrazekC : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\C.png"); Console.WriteLine("Nahrazuji piktogram C"); e.Replacement = ""; return ReplaceAction.Replace; } } public class ObrazekCC : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\CC.png"); Console.WriteLine("Nahrazuji piktogram Č"); e.Replacement = ""; return ReplaceAction.Replace;
29
} } public class ObrazekD : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\D.png"); Console.WriteLine("Nahrazuji piktogram D"); e.Replacement = ""; return ReplaceAction.Replace; } } public class ObrazekL : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\L.png"); Console.WriteLine("Nahrazuji piktogram L"); e.Replacement = ""; return ReplaceAction.Replace; } } public class ObrazekP : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\P.png"); Console.WriteLine("Nahrazuji piktogram P"); e.Replacement = ""; return ReplaceAction.Replace; } } public class ObrazekS : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\S.png"); Console.WriteLine("Nahrazuji piktogram S"); e.Replacement = ""; return ReplaceAction.Replace; } }
30
public class ObrazekV : IReplacingCallback { ReplaceAction IReplacingCallback.Replacing(ReplacingArgs e) { DocumentBuilder builder = new DocumentBuilder((Document)e.MatchNode.Document); builder.MoveTo(e.MatchNode); Shape img = builder.InsertImage(@"C:\TIHS\Piktogramy\V.png"); Console.WriteLine("Nahrazuji piktogram V"); e.Replacement = ""; return ReplaceAction.Replace; } } class Program { static void Main(string[] args) { string zdroj; string cil; Console.WriteLine("\r\nPROSÍM, ZKONTROLUJTE, ZDA JE PROGRAM UMÍSTĚN NA SPRÁVNÉM MÍSTĚ\r\n\r\n"); //dotaz na umístění zdrojového souboru Console.WriteLine("Zadejte jméno souboru a adresu, kde se nachází"); zdroj = Console.ReadLine(); Console.WriteLine("Soubor se nachází: {0}\r\n", zdroj); //dotaz na cíl uložení Console.WriteLine("Zadejte adresu, jmméno a koncovku (podle té se dokument uloží) dokumentu, který chcete uložit"); cil = Console.ReadLine(); Console.WriteLine("Adresa, kde bude soubor uložen je: {0}", cil); Document doc = new Document(@zdroj); doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new doc.Range.Replace(new
Regex(@"@T"), Regex(@"@C"), Regex(@"@Č"), Regex(@"@D"), Regex(@"@L"), Regex(@"@P"), Regex(@"@S"), Regex(@"@V"),
new new new new new new new new
ObrazekT(), false); ObrazekC(), false); ObrazekCC(), false); ObrazekD(), false); ObrazekL(), false); ObrazekP(), false); ObrazekS(), false); ObrazekV(), false);
doc.Save(@cil); Console.WriteLine("\r\nÚprava byla dokončena, soubor byl uložen na adrese, kterou jste zadali"); Console.WriteLine("\r\nProgram ukončíte stisknutím libovolné klávesy"); Console.ReadKey(); } } }
31
9 Vysvětlení kódu programu Kód programu pro úpravu textu lze rozdělit na tři části. Kaţdé části bude v této kapitole věnována vlastní podkapitola.
9.1 Knihovny programu Na začátku kódu programu jsou pomocí příkazu using připraveny k zahrnutí specifické knihovny nezbytně nutné pro správné fungování programu. První tři knihovny jsou standardní knihovny jazyka C#. Knihovna System.Drawing.Imaging je potřebná pro zpracování obrázků. Jejich načtení, přečtení a ukládání. Knihovna System.Text.RegularExpression je nezbytně nutná pro fungování metody Regex. Funkce Regex (více viz níţe). V pořadí čtvrtá a pátá knihovna je zákaznická komerční knihovna vytvoření společností Aspose. Knihovny je moţné zakoupit ve formě časového certifikátu umoţňujícího pouţívání knihovnu po dobu jednoho nebo dvou let nebo pouţít jako trial verzi po omezenou dobu zdroj? Pro potřeby diplomové práce byla vyuţita moţnosti trial verze knihovny. Knihovna Aspose.Word obsahuje metody pro úpravy dokumentů Word ze sady Microsoft Office – otevírání, úprava obsahu a uloţení do dokumentu typu Word. Knihovna Aspose.Word.Drawing je pouţita pro nahrazování řídícího znaku vlastním obrázkem, mimo obsah dokumentu.
9.2 Třídy Pro nahrazení kaţdého jednotlivého řídícího znaku obrázkem je pro daný řídící znak pouţita vlastní třída. Pro kaţdý obrázek je určena jedna třída, která je v hlavní funkci programu cíleně volána. Z knihovny Aspose.Words se v kaţdé třídě volá metoda IReplacingCallback, která obsahuje dvě funkce: ReplaceAction ReplacingArgs Funkcí ReplaceAction se jakýkoliv řetězec nahradí libovolnou entitou. V tomto případě se obrázkem (který je volán ze sloţky v počítači) nahrazuje prázdná mnoţina. Toto nahrazení je pouze uvnitř třídy, neplatí pro celý program! 32
Funkce ReplacingArgs poskytuje data pro operaci výměny jedné entity za jinou. Kombinací výše zvýšených funkcí je výstupem třídy obrázek, který bude nahrazovat řetězec určený v hlavní funkci programu.
9.3 Hlavní funkce Hlavní funkci lze rozdělit na tři části: Otevření dokumentu. Nahrazení řídících znaků obrázkem. Uloţení obsahu jako nový dokument.
9.3.1 Otevření dokumentu Dokument je otevírán třídou Document z knihovny Aspose.Word. Uţivatel zadá adresu, kde se jeho dokument nachází včetně jména a koncovky dokumentu, který chce načíst. Program rozlišuje koncovky dokumentu Word doc a docx.
9.3.2 Nahrazení řídícího znaku piktogramem Pro kaţdý řídící znak je vytvořeno volání dané třídy, vyuţívající třídu Regex. Třída Regex je standardní třídou14 jazyka C#. Třída Regex hledá určený textový řetězec, který následně nahrazuje parametrem. V tomto případě, je za parametr nastavena uţivatelská třída z kapitoly 9.2 Celý proces pak funguje následovně: Program prochází text dokumentu, a kdyţ narazí na předem definovaný řetězec, nahradí jej pomocí třídy Regex danou třídou, která na místo řetězce vloţí určený obrázek. Pro kaţdý řídící znak je připravena jedna funkce s třídou Regex a k tomu přiřazená třída. Pokud bychom chtěli přidat nový řídící znak, stačí přidat řádek kódu v odpovídající části hlavní funkce programu a vytvořit k tomu další třídu.
9.3.3 Uložení dokumentu Uţivatel aplikace je při pouţití vyzván k zadání cílového adresáře, kam se má dokument uloţit. Program rozlišuje zadanou koncovku a podle té ukládá dokument Word buď s koncovkou doc nebo docx. 14
Zdroj: https://msdn.microsoft.com/cs-cz/library/system.text.regularexpressions.regex%28v=vs.110%29.aspx
33
10 Učební text použitý jako příklad pro vytvoření studijní opory Celá tato kapitola obsahuje text jako příklad vzoru studijní opory před provedením automatizované úpravy textu. Text obsahuje řídící znaky, které budou při pouţití programu z kapitoly 8 vyměněny za piktogramy uvedené dříve. Upravený text, obohacený o piktogramy, je vloţen za následujícím vzorem studijní opory.
10.1 Systémová analýza @C Po prostudování kapitoly by měl student znát: Co je to systémová analýza. Jakými oblastmi se systémová analýza zabývá. Základní dělení úloh systémové analýzy a jejich význam. Třídy úloh systémové analýzy a čím se zabývají. @Č Čas k nastudování: 60 minut
@D „Systémová analýza je soubor úloh a metod jejich řešení formulovaný na identifikovaném objektu, jejichţ cílem je zjištění nebo zabezpečování systémových vlastností sledovaného objektu.“15 @V Úlohy systémové analýzy vycházejí z poznatků obecné teorie systémů. Oblasti, kterými se systémová analýza zabývá, jsou: vnitřní struktury systému, prvky systému a funkce systému. Sleduje také vazby mezi samotným systémem a jeho okolím. Zabývá se také zdokonalováním algoritmizaci procesů nebo racionalizaci struktur algoritmů v systému a dalším. Systémová analýza se zabývá systémy, i mimo oblast informatiky. 15
Zdroj: https://is.bivs.cz/el/6110/zima2012/M101SME/um/5_Systemova_analyza_a_synteza.pdf
34
Úlohy systémové analýzy se dělí do třech základních kategorií dle pohledu na systém a to na: Úlohy v systému. Úlohy na systému. Úlohy o systému.
10.1.1
Úlohy v systému
Řešení úloh je totoţné s řešením jednotlivých funkcí. O řešení se starají specialisté oblastí, do kterých daná funkce patří. Například pro finance je to účetní, u personálního oddělení je to řízení lidských zdrojů. Tento typ úloh nepatří do skupiny úloh systémové analýzy.
10.1.2
Úlohy o systému
Úlohy o systému se zabývají chováním systému jako součástí jiného, většího systému a vztahů systému s jeho nejbliţším okolím. Se systémem pracuje jako se součástí vyššího celku - většího systému. Při takovém pohledu jsou pak jednotlivé niţší systémy prvky (komponenty) vyššího systému. Tento vyšší systém pak můţe být jako prvek opět součástí jiného vyššího systém, atd. Změnou míry podrobnosti s jakou je pracováno při práci s úlohami o systému se mohou tyto úlohy změnit na úlohy na systém. Míra podrobnosti se označuje pojmem rozlišovací úroveň.
10.1.3
Úlohy na systém
Tyto úlohy systémové analýzy zkoumají současně části systému a systému jako celku, včetně vztahů mezi nimi. Úlohy dále zjišťují soudrţnost částí systému ve vztahu k celému systému. Zkoumají důsledky jedné funkce (nebo algoritmu či výpočtu) na ostatní funkce nebo celý systém. Úlohy na systém jsou součástí systémové analýzy. Rozdělení tříd úloh na systému podle určitého postupu řešení: Úlohy o stanovení soudrţnosti částí a celku. 35
Kapacitní úlohy. Strukturní úlohy. Úlohy o stanovení cíle a klasifikace cílů. Kromě vypsaných tříd úloh existují ještě další úlohy, například: úlohy o kontaminaci a imunitě (takové úlohy zkoumají rychlost a způsob rozšiřování například nákazy virusového onemocnění), etice, chování dekompozici (jedná se atypické úlohy systémové analýzy, které zkoumají rozkládání systému na jednotlivé prvky systému).
10.1.3.1
Stanovení soudržnosti částí a celku
Při těchto úlohách se zkoumá spolupráce mezi jednotlivými částmi - prvky systému. V případě výskytu konfliktů v systému se hledá původ problému a současně také jeho řešení. Úlohy se také zabývají zajištění společného rozhraní, zkoumání rozvíjejícího se nebo degenerujícího systému.
10.1.3.2
Kapacitní úlohy
Řešeny jsou úlohy sdílení zdrojů a kapacit. Tyto úlohy se řeší v rámci oboru lineárního programování (někdy také jako operační výzkum). Mezi typické úlohy patří úlohy na výkonnost objemu výrobních linek s různou kapacitou nebo tzv. směšovací úlohy, kdy je úkolem z jednotlivých látek vytvořit podle zadaného schématu směs (odtud směšovací úlohy), například čajová směs. Podobné jsou tzv. kompletační úlohy, které jsou o něco sloţitější neţ směšovací úlohy. Princip kompletačních úloh spočívá v předem známém schématu sloţení kompletu, počtu potřebných komponent a jejich vlastnostech (např. délka). Zadání – cíl úloh je pak sloţení co největšího počtu kompletů z dodaných komponent, sloţení kompletů s nejmenším odpadem při zpracování komponent, atd.
36
10.1.3.3
Strukturní úlohy
Tyto úlohy sledují a analyzují potencionální moţnosti dané systémové struktury a zjišťují důsledky strukturních změn na chování. Zabývají se jednak jednotlivými prvky systému a také celým systémem. Strukturní úlohy se dále dělí podle specifikace oblasti, které se věnují. Více o nich dále.
10.1.3.4
Stanovení cíle a klasifikace cílů
Jedná se o nejsloţitější úlohy systémové analýzy. Vzhledem ke své sloţitosti se dále dělí podle různých kritérií. Kritéria je moţné navzájem kombinovat a vytvářet tak další, nová kritéria. Pouţívaná kritéria jsou např. kritérium pouţitých zdrojů, kritérium druhů cílů a jejich klasifikaci. @T Jak byste definovali systémovou analýzu? Vyjmenujte hlavní kategorie systémové analýzy. Které úlohy nepatří do systémové analýzy. Vyjmenujte alespoň 3 třídy úloh systémové analýzy. Vyberte si jednu libovolnou třídu úloh a podrobněji ji popište.
Pro potřeby studijní opory bude třída strukturních úloh rozčleněna na typy: O cestách. O předchůdcích a následnících. O zpětných vazbách. Identifikace specifických prvků a vazeb. O tocích v sítích. O dekompozici, integraci a úpravách struktury. O cílech.
@V
10.2 Úloha o cestách Některé zdroje uvádějí tento typ strukturních úloh jako samostatnou třídu úloh, tedy na stejné „úrovni“ dělení úloh systémové analýzy jako strukturní úlohy. 37
Základní dělení úloh o cestách je následující: Nejkratší cesty v grafu. Hledání minimální kostry grafu. Hledání cesty „Bloudění v bludišti“. Další, podrobnější členění: Eulerův tah. Úloha obchodního cestujícího.
@C Po prostudování kapitoly by měl student umět: Popsat rozdíl mezi Dijkstrovým algoritmem a Floyd-Warshallovým algoritmem. Pouţít oba popsané algoritmy na příkladech.
@Č Čas k nastudování: 120 minut
@V
10.3 Úlohy o hledání nejkratší cesty v grafu S tímto typem úloh se celkem často setkáváme v běţném ţivotě. Pouţívají se pro hledání nejkratší cesty v navigacích, ať pro cyklistiku, automobily nebo pro pěší. Ve všech těchto zařízeních se pro nalezení nejkratší cesty pouţívá Dijkstrův algoritmus. Dalším algoritmem, který se také pouţívá pro hledání nejkratší cesty v grafu, je Floyd - Warshallův algoritmus.
10.3.1
Dijkstrův algoritmus
Jedná se o nejrychlejší známý algoritmus pro nalezení nejkratší cesty v grafu16, který byl poprvé popsán nizozemským informatikem a matematikem jménem Edsger Dijkstra. Tento algoritmus se pro svou vlastnost najít nejkratší trasu v co nejrychlejším času pouţívá v navigacích. Předpokladem pro správné fungování algoritmu je nezáporná hodnota kaţdé 16
Zdroj: http://www.algoritmy.net/article/5108/Dijkstruv-algoritmus
38
hrany grafu. Hrana grafu by také neměla mít nulovou hodnotu - z logiky funkce grafu by se pak vrcholy grafu, které mají od sebe nulovou vzdálenost, překrývaly na souřadnicích. Záporná hodnota hrany je pak pro určení trasy – cesty nelogická a nepouţitelná. Záporná vzdálenost neexistuje. Algoritmus pracuje na principu fronty, ve které jsou uloţeny vrcholy grafu podle vzdálenosti od výchozího vrcholu. Algoritmus v kaţdém kroku vybere z fronty jeden vrchol, který je podle váhy hrany nejblíţe k uţ vybranému vrcholu nebo soustavě vrcholů a zařadí jej mezi zpracované. Následně do fronty doplní všechny potomky nově přidaného vrcholu. Pokud se některý z potomků ve frontě nachází, ověří, zdali není blíţe k výchozímu vrcholu. Pro všechny potomky se porovnává vzdálenost mezi nově zařazeným potomkem a součtem vzdáleností zpracovávaného bodu a potomku, který je byl zařazen ve frontě jako nezpracovaný. Pokud se při porovnání zjistí, ţe nezpracovaný potomek má menší vzdálenost neţ nově přiřazený, označí se jeho předek za zpracovaný a nastaví se nová vzdálenost, vyuţívající právě nově přiřazené spojení vrcholu a potomka. Pokud se takto projdou všechny potomky, algoritmus vybere z fronty další vrchol a celý proces opakuje. @P Obrázek 4: Nalezení nejkratší cesty
Zdroj: Vlastní
10.3.1.1
Popis postupu algoritmu na příkladu
V grafu XY je výchozím vrcholem A. Cílovým vrcholem je vrchol F. V prvním kroku algoritmu se do fronty zařadí vrcholy B, C, D. Algoritmus porovná váhy vrcholů B, C, D a vybere tu hranu s nejniţší váhou. Jinými slovy, nejkratší cestu. V obrázku XY je nejkratší hrana s hodnotou 6 spojující body A a B. Po přidání vrcholu B do soustavy vrcholů doplní 39
algoritmus potomky bodu B do fronty. Při přidávání potomků dojde k porovnání, zda není některý z potomků zařazen do fronty jako jeden z vrcholů, který byl porovnáván s předkem porovnávaného potomka. V případě obrázku XY jde o potomka vrchol C, který byl původně porovnáván společně se svým předkem - vrcholem B. Při tomto kroku dojde k porovnání vzdálenosti součtu hran potřebných pro spojení vrcholů A, B, C a váhy hrany spojující A, C. Jak je patrně z obrázku XY, vzdálenost mezi vrcholy A, C je kratší, neţ spojení přes vrcholy A, B, C. Hodnota váhy hrany vrcholů A, C je 10, zatímco součet hran spojující vrcholy A, B, C je 12. Po tomto kroku se vyřadí cesta A, B, C z algoritmu a je nahrazena novou cestou A, C. Algoritmus se přesune do bodu C a do fronty se zařadí jediný potomek a to vrchol F. Algoritmus se přesune do vrcholu F a tím se dostal do cílového vrcholu. Pro ověření správnosti vybrané cesty se provede algoritmus znovu, tentokrát se za výchozí vrchol pouţije původně cílový vrchol F a za cílový vrchol původní výchozí vrchol A. Postup algoritmu pro ověření nalezené cesty je shodný s postupem hledání nejkratší cesty. Algoritmus pouţije vrchol F za výchozí. Ze skupiny moţných vrcholů (C, D, E) vybere nejbliţší vrchol a to vrchol D. Do fronty zařadí jediného potomka vrchol A, který je současně cílovým vrcholem. Protoţe se kontrolní cesta neshoduje s nejkratší cestou, provede algoritmus k určení nejkratší cesty porovnání součtu vah (vzdáleností) pouţitých hran grafu. Pro cestu s pouţitím vrcholů A, C, F je hodnota cesty 15. Hodnota cesty A, D, F je 14. Kontrolní cesta A, D, F je kratší a bude určena jako nejkratší cesta v grafu XY pro spojení výchozího vrcholu A a cílového vrcholu F. Po konečném určení nejkratší cesty se algoritmus ukončí. V případě, ţe je nalezeno více nejkratších cest, algoritmus vybere tu, která obsahuje méně uzlů. Navigace při hledání nejkratší cesty postupuje stejně, váha hrany grafu je vzdálenost (délka cesty – silnice) mezi určenými vrcholy (dopravními křiţovatkami) v grafu (mapě). V případě hledání nejrychlejší cesty se za váhu hrany pouţije například čas, který je potřeba pro překonání daného úseku cesty. Navigace během cesty počítá s dodrţováním maximální povolené rychlosti.
40
10.3.2
Floyd - Warshallův algoritmus
Algoritmus slouţí k nalezení nejkratších cest mezi všemi dvojicemi vrcholů grafu. Předpokládá se, ţe graf neobsahuje hrany se zápornou délkou. Pro určení nejkratší cesty se pouţívá matematický postup, při kterém se v kaţdém kroku algoritmu přepočítá matice. Tato matice je matematickým obrazem grafu, pro který se hledá nejkratší cesta. Stejně jako u D algoritmu platí, ţe v případě, kdy existuje více nejkratších cest, vybere algoritmus cestu s menším počtem vrcholů. Postup algoritmu s pouţitím matice je následující: Kaţdý vrchol grafu se očísluje od 1 do n v libovolném pořadí. Vytvoří se matice o rozměrech n x n, kde n je nejvyšší hodnota z očíslovaných vrcholů grafu. Na kaţdou pozici na diagonále matice se vloţí hodnota nula (0). Pro kaţdé dva přímo spojené vrcholy i, j se na souřadnice matice i, j zapíše váha spojující hrany z grafu. Pořadí vrcholů a tedy souřadnici v matici určuje směr hrany. V případě, ţe pro danou souřadnici i, j neexistují přímo spojené dva vrcholy grafu, zapíše se při vytvoření matice na tuto souřadnici nekonečno (∞). Na příkladu níţe lze vidět pouţití Floydova - Warshallova algoritmu v kroku, kdy jsou všechny vrcholy grafu očíslovány a je vytvořena počáteční matice s vyplněnými hodnotami.
41
@P Obrázek 5: Znázornění pouţití Floyd - Warshallova algoritmu na grafu v prvním kroku.
Zdroj: Vlastni
Matice má na diagonále hodnoty nula (0). Pro všechny napřímo spojené vrcholy grafu je v matici na dané pozici doplněna hodnota. Pro výchozí matici uveďme příklad na vrcholech 3 a 4. Podle směru hrany mezi těmito napřímo propojenými vrcholy určíme pořadí, a tím i souřadnici v matici, jako 4, 3. V matici pak na této souřadnici nalezeme hodnotu 4, coţ odpovídá váze hrany mezi vrcholy 3 a 4. Pro vrcholy, které nejsou přímo spojeny jednou hranou, byla na dané souřadnice doplněna hodnota nekonečno (∞). V dalších krocích algoritmu se hodnoty nekonečna postupně přepočítávají. Hodnota na těchto pozicích se určí jako součet hran potřebných ke spojení vrcholy na souřadnici i, j matice pomocí prostředníků. Prostředník je spojovací vrchol, který je připojen k oběma vrcholům i a j. Při pouţití prostředníků se musí dodrţovat směr propojovacích hran, není moţné „jít v protisměru“.
42
Pouţitá propojovací cesta by měla mít následující vlastnosti: Pokud se vyskytuje více moţných cest, vybere se ta, která je nejkratší. Pokud existuje více neţ jedna nejkratší cesta, pouţije se ta, která v sobě obsahuje nejmenší počet vrcholů.
Při dodrţení popsaných pravidel vypadá postup pro pouţitý příklad takto:
@P Obrázek 6: Kroky výpočtu matice Floyd - Warshallova algoritmu
Zdroj: http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus s vlastní úpravou
Ve 4. kroku výpočtu je pro vrcholy 1 a 5 v matici hodnota 14. Hodnota 14 není nejkratší cesta při pouţití prostředníka. V následujícím kroku výpočtu (5.) je pro souřadnici 1,5 pouţit jiný prostředník a hodnota cesty se přepočítá a do matice se zapsala nová hodnota 3. Tato hodnota je skutečně nejmenší a zůstane nezměněná aţ do konce algoritmu. @T Kde se můţeme běţně setkat s Dijkstrovým algoritmem? V čem spočívá jeho výhoda? Jaký je rozdíl mezi Dijkstrovým algoritmem a Floyd – Warshallovým algoritmem? Zkuste vyřešit příklady uvedené u kaţdého algoritmu. 43
10.4 Hledání minimální kostry grafu @C Po prostudování kapitoly by měl student umět: Co je to kostra grafu. Jaká musí kostra grafu splňovat pravidla. @Č Čas k nastupování: 20 minut. @V Kostra grafu je pojem z oblasti disciplíny teorie grafů. Kostrou grafu je myšlen libovolný podgraf, který pomocí hran spojuje všechny vrcholy grafu. Podmínkou je, ţe tento podgraf neobsahuje ţádnou kruţnici. Kruţnice je uzavřený tvar podgrafu. Kruţnice se určí tak, ţe při postupném projití celého podgrafu lze spojit všechny vrcholy podgrafu bez toho, aby se nějaký vrchol prošel víc neţ jednou a zároveň se začíná a končí v jednom a tom samém vrcholu.
@P Obrázek 7: Různé kostry grafu
Zdroj: http://teorie-grafu.cz/zakladni-pojmy/kostra-grafu.php s vlastní úpravou
44
Úkolem hledání minimální kostry grafu je nalézt takový podgraf, který splňuje následující pravidla: Spojuje všechny body vrchol. Součet vah jednotlivých hran pouţitých k propojení vybraných vrcholů je nejmenší. Řešení ve formě podgrafu neobsahuje kruţnici. Pro řešení úloh o minimální kostře grafu se pouţívají tři algoritmy Borůvkův, Kruskalův a Jarníkův.
@T Jaký geometrický tvar nesmí mít kostra grafu?
10.4.1
Borůvkův algoritmus
@C Po prostudování kapitoly by měl student: Znát předpoklady pro správné pouţití Borůvkova algoritmu. Umět pouţít Borůvkuv algoritmus. @Č Čas k nastudování: 60 minut @V Borůvkův algoritmus byl vymyšlen matematikem Otakarem Borůvkou za účelem trasování elektrické sítě na Moravě17. Borůvkův algoritmus hledá nejmenší kostru grafu. Pro správnou funkčnost Borůvkova algoritmu je nezbytně nutné, aby se hodnoty hran grafu neopakovaly.
17
Zdroj: http://www.algoritmy.net/article/1396/Boruvkuv-algoritmus
45
Postup algoritmu pro nalezení nejmenší kostry grafu se rozděluje na dvě fáze: V první fázi se kaţdý vrchol v grafu propojí s alespoň jedním jiným vrcholem grafu. Ve druhé fázi se podgrafy vytvořené v první fázi algoritmu propojují navzájem. 10.4.1.1
První fáze algoritmu
Začne se s hranou o nejmenší váze a pomocí této hrany se propojí dva přímo spojené vrcholy. V dalším kroku se pouţije další, nepouţitá hrana, která má nejmenší váhu hrany. Opět se spojí dva vrcholy grafu. V této fázi je dovoleno pomocí hrany spojit jeden vrchol s jiţ existujícím podgrafem. Není dovoleno takto spojovat dva podgrafy. Ve chvíli, kdy jiţ není moţné spojit dva samostatné vrcholy nebo připojit jeden vrchol k podgrafu a další kroky by byly v rozporu s pravidlem výše, první fáze končí a začíná druhá fáze. 10.4.1.2
Druhá fáze algoritmu
Ve druhé fázi se postupně pomocí hran s nejmenší vahou propojí vytvořené podgrafy do jednoho podgrafu. Výsledný koncový podgraf musí splňovat podmínky: Součet vah hran ve výsledném podgrafu musí být co nejmenší. Byly pouţity pouze nezbytně nutné hrany grafu.
V následujícím grafickém příkladu odpovídá první a druhý krok první fázi algoritmu. Třetí a čtvrtý krok pak patří do druhé fáze. Výsledkem je kostra grafu s celkovou vahou 67.
46
@P Obrázek 8: Příklad pouţití Borůvkova algoritmu
Zdroj: http://www.algoritmy.net/article/1396/Boruvkuv-algoritmus s vlastní úpravou
@T Mohou se váhy (hodnoty) hran v grafu pro pouţití Borůvkova algoritmu opakovat a proč? Na uvedeném příkladu si sami vyzkoušejte postup řešení Borůvkova algoritmu.
10.4.2
Kruskalův algoritmus
@C Po prostudování kapitoly by měl student: Pochopit postup algoritmu při řešení úloh systémové analýzy. Umět pouţít Kruskalův algoritmus pro vyřešení úlohy. 47
@Č Čas k nastudování: 20 minut @D Cílem Kruskalova algoritmu je spojit propojit všechny vrcholy v grafu do jednoho celku podgrafu. Podle české Wikipedie vychází Kruskalův algoritmus z Borůvkova algoritmu. @V Algoritmus spojuje vrcholy grafu pomocí hran. Algoritmus pracuje v zásadě pouze s hranami. Vrcholy se propojují tak dlouho, dokud nejsou všechny spojeny. Pro grafy velkého rozsahu je potřeba pouţívat informační technologie. Pro postup algoritmu je nutné mít všechny hrany grafu ohodnoceny. Výchozím místem v grafu je hrana spojující dva vrcholy o nejmenší váze. Dále se postupuje k další dvojici vrcholů, které jsou znovu spojeny volnou hranou s nejniţší vahou. V případě, ţe by pouţití hrany vznikla kruţnice podgrafu, tato hrana se vynechá a pouţije se další v pořadí podle váhy hrany. Tímto způsobem algoritmus postupuje, dokud nejsou spojeny všechny vrcholy grafu. Postup je znázorněn na příkladu:
48
@P Obrázek 9: Příklad pouţití Kruskalova algoritmu
Zdroj: Vlastní
Hodnota podgrafu je rovna součtu pouţitých hran, v tomto případě je to hodnota 4. Hrana s vahou 3 není potřeba pouţít - všechny vrcholy grafu jsou propojeny. Navíc by pouţitím hrany s vahou 3 došlo k vytvoření kruţnice podgrafu, coţ je v rozporu se zásadami algoritmu. @T Jakých hodnot můţou hrany grafu nabývat? Zkuste vytvořit jednoduchý graf a pouţijte na něm Kruskalův algoritmus.
49
@V
10.4.3
Jarníkův algoritmus
Stejně jako předchozí dva algoritmy i tento hledá nejmenší kostru grafu. Algoritmus byl vymyšlen matematikem Vojtěchem Jarníkem v roce 1930 a znovuobjeven americkým matematikem Robertem Primem v roce 1957. Můţeme se setkat také s pojmenováním Primův algoritmus nebo Prim - Jarníkův algoritmus. Jarníkův algoritmus je velice podobný Dijkstrovu algoritmu. Některé zdroje uvádějí, ţe se jedná o stejný algoritmus18 a došlo pouze k jeho znovuobjevení. Algoritmus hledá nejkratší cestu v grafu s cílem spojit všechny vrcholy grafu s co nejmenší vahou kostry. Algoritmus vychází s libovolného vrcholu a udrţuje si seznam jiţ objevených vrcholů a jejich vzdáleností od propojené části grafu. V kaţdém kroku algoritmu se připojí ten z uzlů, mezi nímţ a jiţ vytvořeným kompletem je hrana s nejmenší vahou. Při připojení nového vrcholu se sousední vrcholy označí za objevené. Pokud byla nalezena výhodnější hrana pro jejich připojení, dojde k přepojení soustavy kostry grafu. V okamţiku propojení všech vrcholů je algoritmus ukončen. Na následujícím příkladu je v 8 krocích ukázán postup pro spojení. Konečná váha kostry grafu je 39.
18
Zdroj: http://www.algoritmy.net/article/1393/Jarnik-Primuv-algoritmus
50
@P Obrázek 10: Postup pouţití algoritmu
Zdroj: http://cs.wikipedia.org/wiki/Jarn%C3%ADk%C5%AFv_algoritmus s vlastní úpravou
51
@T K jakému jinému algoritmu je Jarníkův algoritmus přirovnáván?
@V
10.5 Hledání cesty „Bloudění v bludišti“ Tento algoritmus je často spojován s hledáním cesty ven z bludiště. Pouţívá se pro grafy, kde nejsou předem známy všechny vrcholy a hrany grafu. Graf je „objeven“ během průběhu algoritmu. Hledání cesty v grafu funguje na principu lokální informace. Kaţdý průchod (pouţití hrany jako cesty) se zaznamenává, včetně směru cesty. Dále se zaznamenává z jakého směru byl objeven nový vrchol a jakým směrem byl na jiné hraně opuštěn. Kaţdý průchod vrcholem je zaznamenáván. Pokud graf není otevřen na dvou místech, bude po skončení algoritmus projita kaţdá hrana dvakrát a to v obou směrech. Nikdy nebude jedna hrana projita ve stejném směru dvakrát. Pokud existuje výstup, východ z bludiště, bude po určitém počtu kroků algoritmu nalezen.
10.6 Eulerovský tah @C Po prostudování kapitoly by měl student: Umět poznat úlohy Eurelova tahu. Umět rozeznat otevřený a uzavřený algoritmus Eulerova tahu. Umět pouţít úlohy typu Eulerův tah. @Č Čas k nastudování: 60 minut
52
@V Někdy označován jako Eulerův tah. Jedná se o způsob propojení grafu za následujících podmínek: 1. Musí být spojen kaţdý vrchol. 2. Musí být pouţita kaţdá hrana. 3. Ţádná z hran nesmí být pouţita více neţ jednou. 4. Vrcholy mohou být projity vícekrát. Rozlišuje se tzv. uzavřený a otevřený Eulerův tah. Pro uzavřený Eulerův tah platí, ţe výchozí vrchol je také koncovým vrcholem. Začátek a konec tahu je tedy v jednom a tom samém vrcholu grafu. Otevřený Eulerův tah takovou podmínku nemá. Pro jeho správné dokončení stačí dodrţet 4 podmínky vyjmenované výše. Výchozí a koncový vrchol můţe být různý. Běţně se s Eulerovým tahem setkáme v podobě tzv. „jednotaţek“ nebo „jedním tahem“. Úkolem je obkreslit předem známý graf (obrazec) jedním tahem bez toho, aby se tuţka zvedla z papíru.
@P Obrázek 11: Nejznámější obrazce pro úlohy Eulerova tahu
Zdroj: Vlastní
@V
10.7 Úloha obchodního cestujícího Existuje několik variant úloh obchodního cestujícího. V zásadě se jedná o úlohy Eulerova tahu s pozměněnými podmínkami. Základní úlohy tohoto typu jsou: 53
•
Problém obchodního cestujícího
•
Pošťákův problém
•
Problém kropicího vozu
10.7.1
Problém obchodního cestujícího
Jedná se o úlohu kombinatorické optimalizace s cílem najít nejkratší cestu v zadaném grafu. Patří mezi uzavřené Eulerovské tahy. Výchozí a koncový vrchol pro řešení úlohy je stejný. Celý graf by měl mít tvar kruţnice, která spojuje všechny vrcholy grafu. Úloha obchodního cestujícího je základní úlohou lineárního programování.
10.7.2
Pošťákův problém
Někdy pojmenována jako úloha pošťáka. Pro řešení úlohy není potřeba podmínky číslo 3 ze seznamu podmínek o úlohách Eulerova tahu. Hranu grafu je tedy moţné pouţít vícekrát. Stále platí, ţe konečná cesta musí být nejkratší ze všech moţných.
10.7.3
Problém kropicího vozu
Tyto úlohy jsou si velice blízké s úlohami pošťáka a někdy se obě úlohy povaţují za jednu a tu samou. Cílem řešení úloh kropicího vozu je nalézt tzv. sled. Sled je posloupnost navazujících hran, kde se hrany i vrcholy mohou opakovat.
54
11 Výsledek po překladu V následující kapitole je zobrazen výsledek úpravy studijní opory po pouţití programu z kapitoly 8. Všechny řídící znaky byly nahrazeny odpovídajícími piktogramy při zachování struktury textu, obsahu, vloţených diagramů a obrázků.
11.1 Systémová analýza
Po prostudování kapitoly by měl student znát: Co je to systémová analýza. Jakými oblastmi se systémová analýza zabývá. Základní dělení úloh systémové analýzy a jejich význam. Třídy úloh systémové analýzy a čím se zabývají.
Čas k nastudování: 60 minut
„Systémová analýza je soubor úloh a metod jejich řešení formulovaný na identifikovaném objektu, jejichţ cílem je zjištění nebo zabezpečování systémových vlastností sledovaného objektu.“
55
Úlohy systémové analýzy vycházejí z poznatků obecné teorie systémů. Oblasti, kterými se systémová analýza zabývá, jsou: vnitřní struktury systému, prvky systému a funkce systému. Sleduje také vazby mezi samotným systémem a jeho okolím. Zabývá se také zdokonalováním algoritmizaci procesů nebo racionalizaci struktur algoritmů v systému a dalším. Systémová analýza se zabývá systémy, i mimo oblast informatiky.
Úlohy systémové analýzy se dělí do třech základních kategorií dle pohledu na systém a to na: Úlohy v systému. Úlohy na systému. Úlohy o systému.
11.1.1
Úlohy v systému
Řešení úloh je totoţné s řešením jednotlivých funkcí. O řešení se starají specialisté oblastí, do kterých daná funkce patří. Například pro finance je to účetní, u personálního oddělení je to řízení lidských zdrojů. Tento typ úloh nepatří do skupiny úloh systémové analýzy.
11.1.2
Úlohy o systému
Úlohy o systému se zabývají chováním systému jako součástí jiného, většího systému a vztahů systému s jeho nejbliţším okolím. Se systémem pracuje jako se součástí vyššího celku - většího systému. Při takovém pohledu jsou pak jednotlivé niţší systémy prvky (komponenty) vyššího systému. Tento vyšší systém pak můţe být jako prvek opět součástí jiného vyššího systém, atd. Změnou míry podrobnosti s jakou je pracováno při práci s úlohami o systému se mohou tyto úlohy změnit na úlohy na systém. Míra podrobnosti se označuje pojmem rozlišovací úroveň.
56
11.1.3
Úlohy na systém
Tyto úlohy systémové analýzy zkoumají současně části systému a systému jako celku, včetně vztahů mezi nimi. Úlohy dále zjišťují soudrţnost částí systému ve vztahu k celému systému. Zkoumají důsledky jedné funkce (nebo algoritmu či výpočtu) na ostatní funkce nebo celý systém. Úlohy na systém jsou součástí systémové analýzy. Rozdělení tříd úloh na systému podle určitého postupu řešení: Úlohy o stanovení soudrţnosti částí a celku Kapacitní úlohy Strukturní úlohy Úlohy o stanovení cíle a klasifikace cílů Kromě vypsaných tříd úloh existují ještě další úlohy, například: úlohy o kontaminaci a imunitě (takové úlohy zkoumají rychlost a způsob rozšiřování například nákazy virusového onemocnění), etice, chování dekompozici (jedná se atypické úlohy systémové analýzy, které zkoumají rozkládání systému na jednotlivé prvky systému).
11.1.3.1
Stanovení soudržnosti částí a celku
Při těchto úlohách se zkoumá spolupráce mezi jednotlivými částmi - prvky systému. V případě výskytu konfliktů v systému se hledá původ problému a současně také jeho řešení. Úlohy se také zabývají zajištění společného rozhraní, zkoumání rozvíjejícího se nebo degenerujícího systému.
11.1.3.2
Kapacitní úlohy
Řešeny jsou úlohy sdílení zdrojů a kapacit. Tyto úlohy se řeší v rámci oboru lineárního programování (někdy také jako operační výzkum). Mezi typické úlohy patří úlohy 57
na výkonnost objemu výrobních linek s různou kapacitou nebo tzv. směšovací úlohy, kdy je úkolem z jednotlivých látek vytvořit podle zadaného schématu směs (odtud směšovací úlohy), například čajová směs. Podobné jsou tzv. kompletační úlohy, které jsou o něco sloţitější neţ směšovací úlohy. Princip kompletačních úloh spočívá v předem známém schématu sloţení kompletu, počtu potřebných komponent a jejich vlastnostech (např. délka). Zadání – cíl úloh je pak sloţení co největšího počtu kompletů z dodaných komponent, sloţení kompletů s nejmenším odpadem při zpracování komponent, atd.
11.1.3.3
Strukturní úlohy
Tyto úlohy sledují a analyzují potencionální moţnosti dané systémové struktury a zjišťují důsledky strukturních změn na chování. Zabývají se jednak jednotlivými prvky systému a také celým systémem. Strukturní úlohy se dále dělí podle specifikace oblasti, které se věnují. Více o nich dále.
11.1.3.4
Stanovení cíle a klasifikace cílů
Jedná se o nejsloţitější úlohy systémové analýzy. Vzhledem ke své sloţitosti se dále dělí podle různých kritérií. Kritéria je moţné navzájem kombinovat a vytvářet tak další, nová kritéria. Pouţívaná kritéria jsou např. kritérium pouţitých zdrojů, kritérium druhů cílů a jejich klasifikaci.
Jak byste definovali systémovou analýzu? Vyjmenujte hlavní kategorie systémové analýzy. Které úlohy nepatří do systémové analýzy. Vyjmenujte alespoň 3 třídy úloh systémové analýzy. Vyberte si jednu libovolnou třídu úloh a podrobněji ji popište.
58
Pro potřeby studijní opory bude třída strukturních úloh rozčleněna na typy: O cestách. O předchůdcích a následnících. O zpětných vazbách. Identifikace specifických prvků a vazeb. O tocích v sítích. O dekompozici, integraci a úpravách struktury. O cílech.
11.2 Úloha o cestách Některé zdroje uvádějí tento typ strukturních úloh jako samostatnou třídu úloh, tedy na stejné „úrovni“ dělení úloh systémové analýzy jako strukturní úlohy. Základní dělení úloh o cestách je následující: Nejkratší cesty v grafu. Hledání minimální kostry grafu. Hledání cesty „Bloudění v bludišti“. Další, podrobnější členění: Eulerův tah. Úloha obchodního cestujícího.
Po prostudování kapitoly by měl student umět: Popsat rozdíl mezi Dijkstrovým algoritmem a Floyd-Warshallovým algoritmem. Pouţít oba popsané algoritmy na příkladech. 59
Čas k nastudování: 120 minut
11.3 Úlohy o hledání nejkratší cesty v grafu S tímto typem úloh se celkem často setkáváme v běţném ţivotě. Pouţívají se pro hledání nejkratší cesty v navigacích, ať pro cyklistiku, automobily nebo pro pěší. Ve všech těchto zařízeních se pro nalezení nejkratší cesty pouţívá Dijkstrův algoritmus. Dalším algoritmem, který se také pouţívá pro hledání nejkratší cesty v grafu, je Floyd - Warshallův algoritmus.
11.3.1
Dijkstrův algoritmus
Jedná se o nejrychlejší známý algoritmus pro nalezení nejkratší cesty v grafu, který byl poprvé popsán nizozemským informatikem a matematikem jménem Edsger Dijkstra. Tento algoritmus se pro svou vlastnost najít nejkratší trasu v co nejrychlejším čase pouţívá v navigacích. Předpokladem pro správné fungování algoritmu je nezáporná hodnota kaţdé hrany grafu. Hrana grafu by také neměla mít nulovou hodnotu - z logiky funkce grafu by se pak vrcholy grafu, které mají od sebe nulovou vzdálenost, překrývaly na souřadnicích. Záporná hodnota hrany je pak pro určení trasy – cesty nelogická a nepouţitelná. Záporná vzdálenost neexistuje. Algoritmus pracuje na principu fronty, ve které jsou uloţeny vrcholy grafu podle vzdálenosti od výchozího vrcholu. Algoritmus v kaţdém kroku vybere z fronty jeden vrchol, který je podle váhy hrany nejblíţe k uţ vybranému vrcholu nebo soustavě vrcholů a zařadí jej mezi zpracované. Následně do fronty doplní všechny potomky nově přidaného vrcholu. Pokud se některý z potomků ve frontě nachází, ověří, zdali není blíţe k výchozímu vrcholu. Pro všechny potomky se porovnává vzdálenost mezi nově zařazeným potomkem a součtem vzdáleností zpracovávaného bodu a potomku, který je byl zařazen ve frontě jako nezpracovaný. Pokud se při porovnání zjistí, ţe nezpracovaný potomek má menší vzdálenost 60
neţ nově přiřazený, označí se jeho předek za zpracovaný a nastaví se nová vzdálenost, vyuţívající právě nově přiřazené spojení vrcholu a potomka. Pokud se takto projdou všechny potomky, algoritmus vybere z fronty další vrchol a celý proces opakuje.
Obrázek 12: Nalezení nejkratší cesty
Zdroj: Vlastní 11.3.1.1
Popis postupu algoritmu na příkladu
V grafu XY je výchozím vrcholem A. Cílovým vrcholem je vrchol F. V prvním kroku algoritmu se do fronty zařadí vrcholy B, C, D. Algoritmus porovná váhy vrcholů B, C, D a vybere tu hranu s nejniţší váhou. Jinými slovy, nejkratší cestu. V obrázku XY je nejkratší hrana s hodnotou 6 spojující body A a B. Po přidání vrcholu B do soustavy vrcholů doplní algoritmus potomky bodu B do fronty. Při přidávání potomků dojde k porovnání, zda není některý z potomků zařazen do fronty jako jeden z vrcholů, který byl porovnáván s předkem porovnávaného potomka. V případě obrázku XY jde o potomka vrchol C, který byl původně porovnáván společně se svým předkem - vrcholem B. Při tomto kroku dojde k porovnání vzdálenosti součtu hran potřebných pro spojení vrcholů A, B, C a váhy hrany spojující A, C. Jak je patrně z obrázku XY, vzdálenost mezi vrcholy A, C je kratší, neţ spojení přes vrcholy A, B, C. Hodnota váhy hrany vrcholů A, C je 10, zatímco součet hran spojující vrcholy A, B, C je 12. Po tomto kroku se vyřadí cesta A, B, C z algoritmu a je nahrazena novou cestou A, C. Algoritmus se přesune do bodu C a do fronty se zařadí jediný potomek a to vrchol F. Algoritmus se přesune do vrcholu F a tím se dostal do cílového vrcholu. 61
Pro ověření správnosti vybrané cesty se provede algoritmus znovu, tentokrát se za výchozí vrchol pouţije původně cílový vrchol F a za cílový vrchol původní výchozí vrchol A. Postup algoritmu pro ověření nalezené cesty je shodný s postupem hledání nejkratší cesty. Algoritmus pouţije vrchol F za výchozí. Ze skupiny moţných vrcholů (C, D, E) vybere nejbliţší vrchol a to vrchol D. Do fronty zařadí jediného potomka vrchol A, který je současně cílovým vrcholem. Protoţe se kontrolní cesta neshoduje s nejkratší cestou, provede algoritmus k určení nejkratší cesty porovnání součtu vah (vzdáleností) pouţitých hran grafu. Pro cestu s pouţitím vrcholů A, C, F je hodnota cesty 15. Hodnota cesty A, D, F je 14. Kontrolní cesta A, D, F je kratší a bude určena jako nejkratší cesta v grafu XY pro spojení výchozího vrcholu A a cílového vrcholu F. Po konečném určení nejkratší cesty se algoritmus ukončí. V případě, ţe je nalezeno více nejkratších cest, algoritmus vybere tu, která obsahuje méně uzlů. Navigace při hledání nejkratší cesty postupuje stejně, váha hrany grafu je vzdálenost (délka cesty – silnice) mezi určenými vrcholy (dopravními křiţovatkami) v grafu (mapě). V případě hledání nejrychlejší cesty se za váhu hrany pouţije například čas, který je potřeba pro překonání daného úseku cesty. Navigace během cesty počítá s dodrţováním maximální povolené rychlosti.
11.3.2
Floyd - Warshallův algoritmus
Algoritmus slouţí k nalezení nejkratších cest mezi všemi dvojicemi vrcholů grafu. Předpokládá se, ţe graf neobsahuje hrany se zápornou délkou. Pro určení nejkratší cesty se pouţívá matematický postup, při kterém se v kaţdém kroku algoritmu přepočítá matice. Tato matice je matematickým obrazem grafu, pro který se hledá nejkratší cesta. Stejně jako u D algoritmu platí, ţe v případě, kdy existuje více nejkratších cest, vybere algoritmus cestu s menším počtem vrcholů. Postup algoritmu s pouţitím matice je následující: Kaţdý vrchol grafu se očísluje od 1 do n v libovolném pořadí.
62
Vytvoří se matice o rozměrech n x n, kde n je nejvyšší hodnota z očíslovaných vrcholů grafu. Na kaţdou pozici na diagonále matice se vloţí hodnota nula (0). Pro kaţdé dva přímo spojené vrcholy i, j se na souřadnice matice i, j zapíše váha spojující hrany z grafu. Pořadí vrcholů a tedy souřadnici v matici určuje směr hrany. V případě, ţe pro danou souřadnici i, j neexistují přímo spojené dva vrcholy grafu, zapíše se při vytvoření matice na tuto souřadnici nekonečno (∞). Na příkladu níţe lze vidět pouţití Floydova - Warshallova algoritmu v kroku, kdy jsou všechny vrcholy grafu očíslovány a je vytvořena počáteční matice s vyplněnými hodnotami.
Obrázek 13: Znázornění pouţití Floyd - Warshallova algoritmu na grafu v prvním kroku.
Zdroj: Vlastni
63
Matice má na diagonále hodnoty nula (0). Pro všechny napřímo spojené vrcholy grafu je v matici na dané pozici doplněna hodnota. Pro výchozí matici uveďme příklad na vrcholech 3 a 4. Podle směru hrany mezi těmito napřímo propojenými vrcholy určíme pořadí, a tím i souřadnici v matici, jako 4,3. V matici pak na této souřadnici nalezeme hodnotu 4, coţ odpovídá váze hrany mezi vrcholy 3 a 4. Pro vrcholy, které nejsou přímo spojeny jednou hranou, byla na dané souřadnice doplněna hodnota nekonečno (∞). V dalších krocích algoritmu se hodnoty nekonečna postupně přepočítávají. Hodnota na těchto pozicích se určí jako součet hran potřebných ke spojení vrcholy na souřadnici i, j matice pomocí prostředníků. Prostředník je spojovací vrchol, který je připojen k oběma vrcholům i a j. Při pouţití prostředníků se musí dodrţovat směr propojovacích hran, není moţné „jít v protisměru“. Pouţitá propojovací cesta by měla mít následující vlastnosti: Pokud se vyskytuje více moţných cest, vybere se ta, která je nejkratší. Pokud existuje více neţ jedna nejkratší cesta, pouţije se ta, která v sobě obsahuje nejmenší počet vrcholů.
Při dodrţení popsaných pravidel vypadá postup pro pouţitý příklad takto:
Obrázek 14: Kroky výpočtu matice Floyd - Warshallova algoritmu
Zdroj: http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus s vlastní úpravou 64
Ve 4. kroku výpočtu je pro vrcholy 1 a 5 v matici hodnota 14. Hodnota 14 není nejkratší cesta při pouţití prostředníka. V následujícím kroku výpočtu (5.) je pro souřadnici 1,5 pouţit jiný prostředník a hodnota cesty se přepočítá a do matice se zapsala nová hodnota 3. Tato hodnota je skutečně nejmenší a zůstane nezměněná aţ do konce algoritmu.
Kde se můţeme běţně setkat s Dijkstrovým algoritmem? V čem spočívá jeho výhoda? Jaký je rozdíl mezi Dijkstrovým algoritmem a Floyd – Warshallovým algoritmem? Zkuste vyřešit příklady uvedené u kaţdého algoritmu.
11.4 Hledání minimální kostry grafu
Po prostudování kapitoly by měl student umět: Co je to kostra grafu. Jaká musí kostra grafu splňovat pravidla.
Čas k nastupování: 20 minut.
65
Kostra grafu je pojem z oblasti disciplíny teorie grafů. Kostrou grafu je myšlen libovolný podgraf, který pomocí hran spojuje všechny vrcholy grafu. Podmínkou je, ţe tento podgraf neobsahuje ţádnou kruţnici. Kruţnice je uzavřený tvar podgrafu. Kruţnice se určí tak, ţe při postupném projití celého podgrafu lze spojit všechny vrcholy podgrafu bez toho, aby se nějaký vrchol prošel víc neţ jednou a zároveň se začíná a končí v jednom a tom samém vrcholu.
Obrázek 15: Různé kostry grafu
Zdroj: http://teorie-grafu.cz/zakladni-pojmy/kostra-grafu.php s vlastní úpravou
Úkolem hledání minimální kostry grafu je nalézt takový podgraf, který splňuje následující pravidla: Spojuje všechny body vrchol. Součet vah jednotlivých hran pouţitých k propojení vybraných vrcholů je nejmenší. Řešení ve formě podgrafu neobsahuje kruţnici.
66
Pro řešení úloh o minimální kostře grafu se pouţívají tři algoritmy Borůvkův, Kruskalův a Jarníkův.
Jaký geometrický tvar nesmí mít kostra grafu?
11.4.1
Borůvkův algoritmus
Po prostudování kapitoly by měl student: Znát předpoklady pro správné pouţití Borůvkova algoritmu. Umět pouţít Borůvkův algoritmus.
Čas k nastudování: 60 minut
Borůvkův algoritmus byl vymyšlen matematikem Otakarem Borůvkou za účelem trasování elektrické sítě na Moravě. Borůvkův algoritmus hledá nejmenší kostru grafu. Pro správnou funkčnost Borůvkova algoritmu je nezbytně nutné, aby se hodnoty hran grafu neopakovaly.
67
Postup algoritmu pro nalezení nejmenší kostry grafu se rozděluje na dvě fáze: V první fázi se kaţdý vrchol v grafu propojí s alespoň jedním jiným vrcholem grafu. Ve druhé fázi se podgrafy vytvořené v první fázi algoritmu propojují navzájem. 11.4.1.1
První fáze algoritmu
Začne se s hranou o nejmenší váze a pomocí této hrany se propojí dva přímo spojené vrcholy. V dalším kroku se pouţije další, nepouţitá hrana, která má nejmenší váhu hrany. Opět se spojí dva vrcholy grafu. V této fázi je dovoleno pomocí hrany spojit jeden vrchol s jiţ existujícím podgrafem. Není dovoleno takto spojovat dva podgrafy. Ve chvíli, kdy jiţ není moţné spojit dva samostatné vrcholy nebo připojit jeden vrchol k podgrafu a další kroky by byly v rozporu s pravidlem výše, první fáze končí a začíná druhá fáze. 11.4.1.2
Druhá fáze algoritmu
Ve druhé fázi se postupně pomocí hran s nejmenší vahou propojí vytvořené podgrafy do jednoho podgrafu. Výsledný koncový podgraf musí splňovat podmínky: Součet vah hran ve výsledném podgrafu musí být co nejmenší. Byly pouţity pouze nezbytně nutné hrany grafu.
V následujícím grafickém příkladu odpovídá první a druhý krok první fázi algoritmu. Třetí a čtvrtý krok pak patří do druhé fáze. Výsledkem je kostra grafu s celkovou vahou 67.
68
Obrázek 16: Příklad pouţití Borůvkova algoritmu
Zdroj: http://www.algoritmy.net/article/1396/Boruvkuv-algoritmus s vlastní úpravou
Mohou se váhy (hodnoty) hran v grafu pro pouţití Borůvkova algoritmu opakovat a proč? Na uvedeném příkladu si sami vyzkoušejte postup řešení Borůvkova algoritmu.
69
11.4.2
Kruskalův algoritmus
Po prostudování kapitoly by měl student: Pochopit postup algoritmu při řešení úloh systémové analýzy. Umět pouţít Kruskalův algoritmus pro vyřešení úlohy.
Čas k nastudování: 20 minut
Cílem Kruskalova algoritmu je spojit propojit všechny vrcholy v grafu do jednoho celku podgrafu. Podle české Wikipedie vychází Kruskalův algoritmus z Borůvkova algoritmu.
Algoritmus spojuje vrcholy grafu pomocí hran. Algoritmus pracuje v zásadě pouze s hranami. Vrcholy se propojují tak dlouho, dokud nejsou všechny spojeny. Pro grafy velkého rozsahu je potřeba pouţívat informační technologie. Pro postup algoritmu je nutné mít všechny hrany grafu ohodnoceny. Výchozím místem v grafu je hrana spojující dva vrcholy o nejmenší váze. Dále se postupuje k další dvojici vrcholů, které jsou znovu spojeny volnou hranou s nejniţší vahou. V případě, ţe by pouţití 70
hrany vznikla kruţnice podgrafu, tato hrana se vynechá a pouţije se další v pořadí podle váhy hrany. Tímto způsobem algoritmus postupuje, dokud nejsou spojeny všechny vrcholy grafu. Postup je znázorněn na příkladu:
Obrázek 17: Příklad pouţití Kruskalova algoritmu
Zdroj: Vlastní Hodnota podgrafu je rovna součtu pouţitých hran, v tomto případě je to hodnota 4. Hrana s vahou 3 není potřeba pouţít - všechny vrcholy grafu jsou propojeny. Navíc by pouţitím hrany s vahou 3 došlo k vytvoření kruţnice podgrafu, coţ je v rozporu se zásadami algoritmu.
Jakých hodnot můţou hrany grafu nabývat? 71
Zkuste vytvořit jednoduchý graf a pouţijte na něm Kruskalův algoritmus.
11.4.3
Jarníkův algoritmus
Stejně jako předchozí dva algoritmy i tento hledá nejmenší kostru grafu. Algoritmus byl vymyšlen matematikem Vojtěchem Jarníkem v roce 1930 a znovuobjeven americkým matematikem Robertem Primem v roce 1957. Můţeme se setkat také s pojmenováním Primův algoritmus nebo Prim - Jarníkův algoritmus. Jarníkův algoritmus je velice podobný Dijkstrovu algoritmu. Některé zdroje uvádějí, ţe se jedná o stejný algoritmus. Algoritmus hledá nejkratší cestu v grafu s cílem spojit všechny vrcholy grafu s co nejmenší vahou kostry. Algoritmus vychází s libovolného vrcholu a udrţuje si seznam jiţ objevených vrcholů a jejich vzdáleností od propojené části grafu. V kaţdém kroku algoritmu se připojí ten z uzlů, mezi nímţ a jiţ vytvořeným kompletem je hrana s nejmenší vahou. Při připojení nového vrcholu se sousední vrcholy označí za objevené. Pokud byla nalezena výhodnější hrana pro jejich připojení, dojde k přepojení soustavy kostry grafu. V okamţiku propojení všech vrcholů je algoritmus ukončen. Na následujícím příkladu je v 8 krocích ukázán postup pro spojení. Konečná váha kostry grafu je 39.
72
Obrázek 18: Postup pouţití algoritmu
Zdroj: http://cs.wikipedia.org/wiki/Jarn%C3%ADk%C5%AFv_algoritmus s vlastní úpravou
73
K jakému jinému algoritmu je Jarníkův algoritmus přirovnáván?
11.5 Hledání cesty „Bloudění v bludišti“ Tento algoritmus je často spojován s hledáním cesty ven z bludiště. Pouţívá se pro grafy, kde nejsou předem známy všechny vrcholy a hrany grafu. Graf je „objeven“ během průběhu algoritmu. Hledání cesty v grafu funguje na principu lokální informace. Kaţdý průchod (pouţití hrany jako cesty) se zaznamenává, včetně směru cesty. Dále se zaznamenává z jakého směru byl objeven nový vrchol a jakým směrem byl na jiné hraně opuštěn. Kaţdý průchod vrcholem je zaznamenáván. Pokud graf není otevřen na dvou místech, bude po skončení algoritmus projita kaţdá hrana dvakrát a to v obou směrech. Nikdy nebude jedna hrana projita ve stejném směru dvakrát. Pokud existuje výstup, východ z bludiště, bude po určitém počtu kroků algoritmu nalezen.
11.6 Eulerovský tah
Po prostudování kapitoly by měl student: Umět poznat úlohy Eurelova tahu. Umět rozeznat otevřený a uzavřený algoritmus Eulerova tahu. Umět pouţít úlohy typu Eulerův tah.
74
Čas k nastudování: 60 minut
Někdy označován jako Eulerův tah. Jedná se o způsob propojení grafu za následujících podmínek: 5. Musí být spojen kaţdý vrchol. 6. Musí být pouţita kaţdá hrana. 7. Ţádná z hran nesmí být pouţita více neţ jednou. 8. Vrcholy mohou být projity vícekrát. Rozlišuje se tzv. uzavřený a otevřený Eulerův tah. Pro uzavřený Eulerův tah platí, ţe výchozí vrchol je také koncovým vrcholem. Začátek a konec tahu je tedy v jednom a tom samém vrcholu grafu. Otevřený Eulerův tah takovou podmínku nemá. Pro jeho správné dokončení stačí dodrţet 4 podmínky vyjmenované výše. Výchozí a koncový vrchol můţe být různý. Běţně se s Eulerovým tahem setkáme v podobě tzv. „jednotaţek“ nebo „jedním tahem“. Úkolem je obkreslit předem známý graf (obrazec) jedním tahem bez toho, aby se tuţka zvedla z papíru.
75
Obrázek 19: Nejznámější obrazce pro úlohy Eulerova tahu
Zdroj: Vlastní
11.7 Úloha obchodního cestujícího Existuje několik variant úloh obchodního cestujícího. V zásadě se jedná o úlohy Eulerova tahu s pozměněnými podmínkami. Základní úlohy tohoto typu jsou: •
Problém obchodního cestujícího
•
Pošťákův problém
•
Problém kropicího vozu
11.7.1
Problém obchodního cestujícího
Jedná se o úlohu kombinatorické optimalizace s cílem najít nejkratší cestu v zadaném grafu. Patří mezi uzavřené Eulerovské tahy. Výchozí a koncový vrchol pro řešení úlohy je stejný. Celý graf by měl mít tvar kruţnice, která spojuje všechny vrcholy grafu. Úloha obchodního cestujícího je základní úlohou lineárního programování.
76
11.7.2
Pošťákův problém
Někdy pojmenována jako úloha pošťáka. Pro řešení úlohy není potřeba podmínky číslo 3 ze seznamu podmínek o úlohách Eulerova tahu. Hranu grafu je tedy moţné pouţít vícekrát. Stále platí, ţe konečná cesta musí být nejkratší ze všech moţných.
11.7.3
Problém kropicího vozu
Tyto úlohy jsou si velice blízké s úlohami pošťáka a někdy se obě úlohy povaţují za jednu a tu samou. Cílem řešení úloh kropicího vozu je nalézt tzv. sled. Sled je posloupnost navazujících hran, kde se hrany i vrcholy mohou opakovat.
77
Závěr Cílem práce je seznámit s problematikou přípravy a vzniku studijní opory, vytvořit a popsat aplikační software, který by usnadnil úpravu textů studijních opor. V první části práce byl popsán obecný postup vytváření studijní opory. Byla popsána problematická místa a etapy učení studijní opory. Současně se studijní oporou byly věnovány kapitoly také typografii a piktogramům, jako nedílným součástem studijních opor. Druhá část je věnována programovacím jazykům a vytvořené aplikaci pro úpravu textu studijních opor. V úvodu této části je popis funkcí aplikace, je vytvořen modelový příklad a analytické diagramy. Dále jsou podrobněji popsány uvaţované programovací jazyky, jejich výhody a nevýhody. Závěrem je vloţen kód programu pro úpravu textu. V poslední části diplomové práce je ukázka vytvořené studijní opory obsahující předem stanované řídící znaky. Text je vloţen ve stavu před a po pouţití programu.
78
Zdroje [1]
About ISO [online]. 2015 [cit. 2015-04-19]. Dostupné z: http://www.iso.org/iso/home/about.htm
[2]
ALBATROSS. The Features of C++ as a Language [online]. [cit. 2015-04-19]. Dostupné z: http://www.cplusplus.com/info/description/
[3]
Augmentativní komunikace [online]. [cit. 2015-04-19]. Dostupné z: http://slovnikcizich-slov.abz.cz/web.php/slovo/augmentativni-komunikace
[4]
BENEŠ, Vladimír. Systémová analýza a syntéza [online]. 2012, Bankovní institut vysoká škola [cit. 2015-04-19]. Dostupné z: https://is.bivs.cz/el/6110/zima2012/M101SME/um/5_Systemova_analyza_a_synteza.pdf
[5]
BENEŠ, Vladimír. Systémová metodologie [online]. 2012 Bankovní institut vysoká škola [cit. 2015-02-26]. Dostupné z: http://is.bivs.cz/el/6110/zima2012/M101SME/um/6_Strukturni_ulohy.txt
[6]
BENEŠ, Vladimír. Systémová metodologie [online]. 2012 Bankovní institut vysoká škola [cit. 2015-02-26]. Dostupné z: https://is.bivs.cz/auth/el/6110/zima2013/M101SME/um/Systemova_metodologie_studij ni_opora.pdf?studium=34509
[7]
BIELIK, Miloš. Seven Advantages Of Java [online]. 2011 [cit. 2015-04-20]. Dostupné z: http://bielik.blogspot.cz/2011/05/seven-advantages-of-java.html
[8]
BROWNIE. Advantages and Disadvantages of C# as compared to C++ [online]. 2006 [cit. 2015-04-19]. Dostupné z: https://chiafong6799.wordpress.com/2006/07/11/advantages-and-disadvantages-of-c-ascompared-to-c/
[9]
ČERNÝ, Jakub. Dijkstrův algoritmus [online]. 2013 [cit. 2015-02-26]. Dostupné z: http://algoritmy.eu/zga/nejkratsi-cesta/dijkstruv-algoritmus/
[10] ČERNÝ, Jakub. Eulerovský tah [online]. 2013 [cit. 2015-02-26]. Dostupné z: http://algoritmy.eu/zga/pruchod-grafu/eulerovsky-tah/ [11] DANIHELKOVÁ, PhDr. Ing. Hana. Uţitečný manuál pro začínající autory studijních opor pro kombinované studium [online]. [cit. 2015-03-12]. Dostupné z: http://www.slu.cz/fvp/cz/uo/projekty/inovace/materialy/docs/manual_pro_zacinajici_aut ory_studinich_opor_300911.pdf [12] DOW, Andrew. George Dow & son [online]. [cit. 2015-04-19]. Dostupné z: http://www.steamindex.com/library/dow.htm [13] FACULTY OF ORIENTAL STUDIES, University of Oxford. Cuneiform writing [online]. 2005 [cit. 2015-02-22]. Dostupné z: http://etcsl.orinst.ox.ac.uk/edition2/cuneiformwriting.php [14] George Dow [online]. 2015 [cit. 2015-02-26]. Dostupné z: http://en.wikipedia.org/wiki/George_Dow
79
[15] GOŠOVÁ, Mgr. Věra. METODICKÝ PORTÁL. Piktogramy [online]. 2011 [cit. 201502-26]. Dostupné z: http://wiki.rvp.cz/Knihovna/1.Pedagogicky_lexikon/P/Piktogramy [16] IDE, Andy. PHP just grows & grows [online]. 2013 [cit. 2015-04-19]. Dostupné z: http://news.netcraft.com/archives/2013/01/31/php-just-grows-grows.html [17] JIROVSKÝ, Lukáš. Teorie grafů [online]. [cit. 2015-02-26]. Dostupné z: http://teoriegrafu.cz/vybrane-problemy/minimalni-kostra.php [18] Klínové písmo [online]. 2015 [cit. 2015-02-22]. Dostupné z: http://cs.wikipedia.org/wiki/Kl%C3%ADnov%C3%A9_p%C3%ADsmo [19] KRISHNAMRAJU. Advantages VS Disadvantages of C# [online]. 2010 [cit. 2015-0420]. Dostupné z: http://krishnamraju.jimdo.com/c-sharp/advantages-and-disadvantages/ [20] Learn About Java Technology [online]. [cit. 2015-04-19]. Dostupné z: https://www.java.com/en/about [21] LEHMANN-HAUPT, Hellmut E. ENCYKLOPEDIA BRITANNICA. Johannes Gutenberg [online]. 2014 [cit. 2015-02-22]. Dostupné z: http://www.britannica.com/EBchecked/topic/249878/Johannes-Gutenberg [22] LECHENE, Robert. ENCYKLOPEDIA BRITANNICA. Printing [online]. 2014 [cit. 2015-02-22]. Dostupné z: http://www.britannica.com/EBchecked/topic/477017/printing [23] MICROSOFT. Regex – třída [online]. [cit. 2015-04-19]. Dostupné z: https://msdn.microsoft.com/cscz/library/system.text.regularexpressions.regex%28v=vs.110%29.aspx [24] MICROSOFT. Visual C# [online]. [cit. 2015-04-19]. Dostupné z: https://msdn.microsoft.com/en-us/library/kx37x362%28v=vs.110%29.aspx [25] Microtypography [online]. 2014 [cit. 2015-02-22]. Dostupné z: http://en.wikipedia.org/wiki/Microtypography [26] MIČKA, Pavel. Borůvkův algoritmus [online]. [cit. 2015-04-19]. Dostupné z: http://www.algoritmy.net/article/1396/Boruvkuv-algoritmus [27] MIČKA, Pavel. Dijkstrův algoritmus [online]. [cit. 2015-04-19]. Dostupné z: http://www.algoritmy.net/article/5108/Dijkstruv-algoritmus [28] MIČKA, Pavel. Floyd-Warshallův algoritmus [online]. [cit. 2015-02-26]. Dostupné z: http://algoritmy.eu/zga/nejkratsi-cesta/floyd-warshalluv-algoritmus/ [29] MIČKA, Pavel. Floyd-Warshallův algoritmus [online]. [cit. 2015-02-26]. Dostupné z: http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus [30] MIČKA, Pavel. Jarníkův-Primův algoritmus [online]. [cit. 2015-04-19]. Dostupné z: http://www.algoritmy.net/article/1393/Jarnik-Primuv-algoritmus [31] MIČKA, Pavel. Kruskalův algoritmus [online]. [cit. 2015-02-26]. Dostupné z: http://www.algoritmy.net/article/1417/Kruskaluv-algoritmus [32] Mikrotypografie [online]. 2014 [cit. 2015-02-22]. Dostupné z: http://cs.wikipedia.org/wiki/Mikrotypografie 80
[33] NÁRODNÍ KNIHOVNA ČESKÉ REPUBLIKY. Gutenbergovy tisky [online]. 2012 [cit. 2015-04-19]. Dostupné z: http://text.nkp.cz/o-knihovne/zakladniinformace/klementinska-nej/gutenbergovy-tisky [34] NEZVALOVA. Jak vytvářet studijní opory [online]. [cit. 2015-03-12]. Dostupné z: hkol.cz/Files/nezvalova/1.doc [35] Operations research [online]. 2015 [cit. 2015-02-26]. Dostupné z: http://en.wikipedia.org/wiki/Operations_research [36] PATEL, Kamlesh. Most Significant Advantages of Java Language [online]. [cit. 201504-20]. Dostupné z: http://www.streetdirectory.com/travel_guide/114362/programming/most_significant_ad vantages_of_java_language.html [37] SLOVNÍK CIZÍCH SLOV. Piktogram [online]. [cit. 2015-02-26]. Dostupné z: http://slovnik-cizich-slov.abz.cz/web.php/slovo/piktogram [38] Systémová analýza [online]. 2009 [cit. 2015-02-26]. Dostupné z: http://informacnisystemy.studentske.cz/2009/08/systemova-analyza.html [39] Systems analysis [online]. 2015 [cit. 2015-02-26]. Dostupné z: http://en.wikipedia.org/wiki/Systems_analysis [40] The C++ Standards Committee [online]. 2015 [cit. 2015-04-19]. Dostupné z: http://www.open-std.org/jtc1/sc22/wg21/ [41] TIOBE SOFTWARE. Java back at the top [online]. [cit. 2015-04-19]. Dostupné z: http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html [42] Titanic casualties [online]. 2015 [cit. 2015-02-26]. Dostupné z: http://upload.wikimedia.org/wikipedia/commons/6/69/Titanic_casualties.svg [43] Transit map [online]. 2015 [cit. 2015-04-19]. Dostupné z: http://en.wikipedia.org/wiki/Transit_map [44] Typografie [online]. 2015 [cit. 2015-02-22]. Dostupné z: http://cs.wikipedia.org/wiki/Typografie [45] Typography [online]. 2015 [cit. 2015-02-22]. Dostupné z: http://en.wikipedia.org/wiki/Typography [46] Úlohy na systému [online]. [cit. 2015-02-26]. Dostupné z: http://eident.telematix.cz/vyuka/05_Ulohy_na_systemu.pdf [47] VYSOKÁ ŠKOLA BAŇSKÁ. Eulerovské tahy [online]. [cit. 2015-02-26]. Dostupné z: http://books.fs.vsb.cz/SystAnal/texty/22.htm [48] Webová typografie [online]. 2012 [cit. 2015-02-22]. Dostupné z: http://wiki.knihovna.cz/index.php/Webov%C3%A1_typografie
81
Seznam obrázků a tabulek Obrázek 1: Příklad pouţití piktogramu jako míry mnoţství .................................................... 18 Obrázek 2: Sekvenční diagram pouţití aplikace ...................................................................... 21 Obrázek 3: Diagram stavu dokumentu ..................................................................................... 22 Obrázek 4: Nalezení nejkratší cesty ......................................................................................... 39 Obrázek 5: Znázornění pouţití Floyd - Warshallova algoritmu na grafu v prvním kroku. ...... 42 Obrázek 6: Kroky výpočtu matice Floyd - Warshallova algoritmu ......................................... 43 Obrázek 7: Různé kostry grafu ................................................................................................. 44 Obrázek 8: Příklad pouţití Borůvkova algoritmu..................................................................... 47 Obrázek 9: Příklad pouţití Kruskalova algoritmu .................................................................... 49 Obrázek 10: Postup pouţití algoritmu ...................................................................................... 51 Obrázek 11: Nejznámější obrazce pro úlohy Eulerova tahu .................................................... 53 Obrázek 12: Nalezení nejkratší cesty ....................................................................................... 61 Obrázek 13: Znázornění pouţití Floyd - Warshallova algoritmu na grafu v prvním kroku. .... 63 Obrázek 14: Kroky výpočtu matice Floyd - Warshallova algoritmu ....................................... 64 Obrázek 15: Různé kostry grafu ............................................................................................... 66 Obrázek 16: Příklad pouţití Borůvkova algoritmu................................................................... 69 Obrázek 17: Příklad pouţití Kruskalova algoritmu .................................................................. 71 Obrázek 18: Postup pouţití algoritmu ...................................................................................... 73 Obrázek 19: Nejznámější obrazce pro úlohy Eulerova tahu .................................................... 76
Tabulka 1: Přehled piktogramů a řídících znaků ...................................................................... 28
82
