Analýza systémů. Strukturovaná analýza informačních systémů Teorie grafu Ing. Dagmar Létavková, Ph.D

Analýza systémů Strukturovaná analýza informačních systémů Teorie grafu Ing. Dagmar Létavková, Ph.D.

STRUKTUROVANÁ ANALÝZA A NÁVRH IS … hlavní zdroje ŘEPA, V.: Vývojové trendy metodik vývoje IS – výzva BPR. Praha, VŠE – katedra informačních technologií. Dostupné z WWW. < http://nb.vse.cz/~repa/veda/EurOpen99%20Paper.pdf > ŘEPA, Václav. Analýza a návrh informačních systémů. Praha : Ekopress, 1999. ISBN 8086119-13-0. S. 403. (česky)

Oficiální stránky Smart Draw Communicate Visually. Dostupné z WWW. < http://www.smartdraw.com > Štíbal, M.: Strukturovaná analýza informačních systémů. Bakalářská práce. Brno 2008, Masyrykova univerzita, fakulta informatiky. Dostupné z WWW. < http://is.muni.cz/th/172681/fi_b/bc.pdf >

DEMARCO, Tom. Structured Analysis and System Specification. New York : Yourdon Press, 1979. ISBN 978-0138543808. S. 352. (anglicky) YOURDON, Edward. Structured Design: Fundamentals of a Discipline of Computer Program and Systems Design. New York : Yourdon Press, 1979. ISBN 978-0138544713. S. 473. (anglicky)

PAGE-JONES, Meilir. Practical Guide to Structured Systems Design. New York : Yourdon Press, 1988. ISBN 978-8120314825. S. 384. (anglicky) YOURDON, Edward. Modern Structured Analysis. New York : Yourdon Press, 1988. ISBN 978-0135986240. S. 688. (anglicky)

STRUKTUROVANÁ ANALÝZA A NÁVRH IS

Metody strukturované systémové analýzy a návrhu představují ne příliš rozsáhlý soubor vzájemně se doplňujících metod založených na relativně jednoduchých a jasně specifikovaných principech. Důsledné uplatňování takovýchto principů sice neposkytuje uživateli na první pohled příliš mnoho volnosti, avšak vede ke tvorbě konzistentních modelů. V neposlední řadě jejich nespornou výhodou je existence ověřených a propracovaných prostředků počítačové podpory, které tyto metody implementují. Ačkoliv s příchodem objektově orientovaných metod na počátku 90. let se další vývoj metod strukturované systémové analýzy a návrhu více méně zastavil, díky všem výše zmíněných aspektům si dodnes uchovávají přední pozici v oblasti analýzy a návrhu jak softwarových, tak především nesoftwarových systémů.

STRUKTUROVANÁ ANALÝZA IS … funkce systému

Metoda analýzy funkční struktury je jednou ze základních metod strukturované analýzy používaná především k popisu struktury systému. Jedná se o metodu grafickou, která slouží k zachycení hierarchické dekompozice systému na subsystémy a prvky pomocí stromových diagramů. Hierarchické stromové uspořádání vyjádřené vzájemnými vazbami prvků zachycuje vztah nadřazenosti a podřízenosti prvků a vztah sounáležitosti podřízených prvků patřících k jednomu prvku nadřazenému. Listové položky hierarchického stromového diagramu představují elementární prvky systému, tedy prvky s ohledem na daný účel tvorby modelu dále nedekomponované. Pro plně popsanou strukturu systému tvořenou souborem listových položek je možno s využitím principů grafického zápisu algoritmů podle Jacksona v jisté míře popsat jejich algoritmický obsah.


Diagram funkční struktury obsahuje zdánlivě velmi málo informace o analyzovaném systému, neboť zachycuje pouze hierarchickou nadřazenost a podřízenost prvků a postihuje pouze jejich základní souvislosti. Zcela mimo oblast zájmu této metody stojí vzájemné informační vazby jednotlivých prvků systému. Jednoduchost a přehlednost takto získaného popisu funkční struktury systému vytváří z této metody vhodný nástroj pro první, orientační představu o analyzovaném systému. Ve srovnání s dále zmíněnou metodou informačních toků na menší ploše zachycuje a zobrazuje větší část analyzovaného systému.


Funkční diagram

Systém

Prvek 1

Subsystém 2

Prvek 21

Prvek 2

Prvek 22

Metoda analýzy funkční struktury může být využita samostatně, častěji však jako vhodný doplněk metody informačních toků.

STRUKTUROVANÁ ANALÝZA IS … informační toky

Metoda informačních toků vyjadřuje formou hierarchicky uspořádaných síťových diagramů dekompozici systému na subsystémy a prvky a současně zachycuje informační vazby mezi těmito prvky. Na vrcholu této hierarchie stojí tzv. kontextový diagram, který vyjadřuje začlenění systému do souvislostí okolního světa. Kontextový diagram se dále rozkládá na Data Flow Diagramy (DFD). Nejjemnější rozlišovací úroveň pak v případě využití CASE Studia představují minispecifikace s podrobným popisem funkce systému. V popisu metody analýzy funkční struktury systému byla zmíněna případná vazba na metodu informačních toků, jsou-li obě metody v rámci analýzy uplatňovány. Jednotlivé diagramy informačních toků jsou vázány k prvkům – uzlům hierarchické stromové funkční struktury a podrobněji popisují jednu úroveň jedné větve.

STRUKTUROVANÁ ANALÝZA IS … informační toky V základním členění lze prvky rozdělit na prvky aktivní a pasivní. Základními aktivními prvky jsou funkční prvky neboli funkce, prvky zajišťující transformaci vstupní informace na výstupní. Aktivní prvky lze dále rozlišovat na prvky příslušné k popisovanému systému a prvky, které lze považovat vzhledem k popisovanému systému za vnější. Tyto vnější prvky jsou součástí definice vazeb popisovaného systému na okolní svět. Jejich vnitřní aktivita není předmětem studia systému, jejich funkce je dána a není úkolem návrhu systému je vytvářet nebo měnit. Představují adekvátní model okolí popisované systému a jsou vzhledem k základnímu předpokladu obecné teorie systémů na uzavřenost systému jeho nezbytnou součástí. Není nutné, ale může být účelné, od základních funkčních prvků odlišit prvky systému, které sice náležejí k vnitřním prvkům systému, ale které nejsou bezprostřední součástí právě studované části a patří ostatním částem systému. Pasivní prvky představují paměti. Jedná se o prvky, které jsou schopny uchovat uloženou informaci. V případě softwarově orientovaných systémů mohou být realizovány například soubory nebo databázemi, v oblasti nesoftwarových systémů například protokoly, seznamy nebo záznamovými knihami.


Prvek 1

Subsystém 2

Systém

Prvek 1

Prvek 3

Subsystém 2

Prvek 2 Prvek 1

Prvek 21

Prvek 3

Prvek 22 Prvek 22 Prvek 21

Paměť

Informační toky


Metoda informačních toků podle DeMarca je sama o sobě efektivně využitelná pro jednodušší systémy, neboť umožňuje jednoúrovňové zobrazení prvků systému a jejich vazeb. Ward-Mellorova metoda rozšiřuje standardní metodu informačních toků o řídicí funkce a řídicí toky a doplňuje ji tak o možnost hrubého popisu chování systému spočívajícího v zachycení sekvence vykonání ucelených a relativně samostatných činností. Je-li to z hlediska pochopení funkčnosti systému nezbytné, lze k řídicím funkcím připojit stavový diagram. Tento přístup však s sebou přináší nutnost násilného oddělování informačních a řídicích toků již od prvních kroků analýzy. Vyjádření řídicích toků je zřetelným přechodem od popisu struktury systému k popisu jeho chování a dochází tedy k prolínání popisu kvalitativních a kvantitativních vlastností systému. Poznámka: u analýzy běžných informačních systémů nezařazujeme řídící procesy a řídící datové toky, není-li to nezbytně nutné !!!

STRUKTUROVANÁ ANALÝZA IS … struktura dat

Jedním z prostředků datové analýzy je popis datových struktur. Analýza datových struktur umožňuje pomocí hierarchických stromových diagramů postupné rozčlenění informačních toků nebo paměťových prvků. Všechny prvky tohoto diagramu představují obecně chápané bloky informace – datové položky. Na analýzu struktury dat bezprostředně navazuje detailní datová analýza, která je prostředkem k podrobnému popisu elementárních datových položek – listových prvků hierarchického stromového diagramu. Detailní datová analýza umožňuje přiřadit každé elementární položce datové struktury datový element, který určuje formu uložení informace. Pro datové elementy je možno specifikovat například typ, rozsah nebo výčet možných hodnot.


Prvek 1

Prvek 3

Prvek 22 Prvek 21

Paměť

Informační tok 2122 Datové pole 1 Datová položka 11

Datová položka 2

Datová položka 12

Paměť

Datová položka 1

Datové pole 2

Datová položka 21

Datová položka 22


ER model – model entit a jejich vzájemných vztahů je speciální, avšak velmi rozšířenou metodou datové analýzy. Je vhodný pro analýzu systému v případě, kdy složitost systému spočívá spíše ve složitosti struktury dat než ve složitosti jeho funkčních složek. Nachází uplatnění ve specializované aplikační oblasti nazývané hromadné zpracování dat. ER model zachycuje formou síťového grafu objekty reálného světa a vztahy mezi nimi. Množiny objektů reálného světa mající shodné vlastnosti se nazývají entitami, vztahy mezi nimi pak relacemi. Entity mohou být blíže specifikovány množinou atributů, které mají shodný význam jako datové elementy užívané při detailní datové analýze. Relace mezi entitami jsou specifikovány kardinalitou a těsností vazby. ER modely se využívají pro tvorbu modelů dat na logické neboli konceptuální úrovni, tedy modelů dat nezávislých na jejich fyzické realizaci prostřednictvím specifického databázového systému.

STRUKTUROVANÁ ANALÝZA IS … popis chování systému

Popis chování systému je v obecném slova smyslu jeho algoritmizací. Z tohoto faktu vychází názor, že popis chování systému, zejména pak softwarově orientovaného, je předmětem jeho návrhu a obsahem vlastního programového řešení. Algoritmus chování je však v určitých případech nutné nebo účelné podrobněji popsat již ve fázi analýzy. Metody popisu chování umožňují ve fázi analýzy zachytit algoritmickou složku systému, avšak abstrahují od konkrétního způsobu realizace, který je předmětem fáze návrhu. Metody popisu chování jsou obvykle velmi příbuzné metodám užívaným při tvorbě programů, neboť jde v obou případech o popis algoritmů.


Klasickým grafickým prostředkem zápisu algoritmu je vývojový diagram. Díky své jednoduchosti získal oblibu v nejrůznějších oblastech, které daly vzniknout jeho různým modifikacím. Nejjednodušší varianta zachycuje základní strukturu algoritmu pomocí vzájemně propojených elementů představovaných bloky a podmínkami. Detailní specifikace algoritmu je obsahem příslušných elementů a je vyjádřena formalizovaným jazykem.

vývojový diagram

Z AKCE 1

podmínka

-

+ AKCE 2

K

AKCE 3

STRUKTUROVANÁ ANALÝZA IS … popis chování systému Metoda stavových diagramů je grafická metoda popisu chování použitelná pro vyjádření jednodušších algoritmů nebo pro popis algoritmů na hrubé úrovni. Systém je popsán síťovým grafem, jehož uzly znázorňují stav systému a hrany naznačují možné přechody mezi stavy s vyjádřením podmínek přechodu a akcí s přechodem spojených. Akce a stavy systému pouze symbolicky označují funkce a jejich účinky. Algoritmickou náplň akcí je však nutné popsat s využitím jiných prostředků. P

Stav 1

stavový diagram

U2 (P2) A2

Událost 1 (Podmínka 1) Akce 1

Stav 2

U4 (P4) A4

U3 (P3) A3

Stav 3

U5 (P5) A5

U6 (P6) A6

K

K

STRUKTUROVANÁ ANALÝZA IS … popis chování systému Mezi metody, které podporují a dodržují zásady strukturovaného programování patří metoda grafického zápisu algoritmů podle Jacksona, označovaná jako Jacksonovy diagramy. Základní struktura algoritmu je popsána hierarchickým stromovým diagramem, detailní specifikace je obsahem příslušných elementů a je vyjádřena formalizovaným jazykem. Jacksonův diagram

if AKCE 1

while

Podmín.1

Podmín.2

AKCE 2

AKCE 3

AKCE 4


Metoda sekvenčních funkčních grafů představuje grafickou metodu popisu chování systému vyhovující nejobecnějším nárokům na popis algoritmu. Základy metody jsou postaveny na principech Petriho sítí. Původně byla metoda vyvinuta pro detailní zachycení RT vlastností systémů, tedy pro popis algoritmů, které kladou velké nároky na vzájemnou i časovou synchronizaci. Se značným časovým zpožděním se tato metoda dostala do povědomí i jako jedna z analytických metod pro popis chování systému. Metoda funkčních kroků a přechodů byla poprvé uveřejněna v roce 1977 pod názvem GRAFCET (Graphe Fonctionnel de Commande Etape-Transition). V současné době se však s touto metodou lze setkat častěji pod názvem SFC (Sequential Function Chart).


Uzlem síťového grafu není stav systému, ale krok algoritmu, respektive akce s daným krokem spojená. Přechod z kroku do kroku je vázán podmínkou přechodu a aktivitou kroků této podmínce bezprostředně předcházejících. Síťový graf tedy zachycuje základní strukturu algoritmu, detailní popis je pak obsahem akcí spojených s dílčími kroky. Ačkoliv detailní algoritmický popis není povinnou součástí analýzy metodou sekvenčních funkčních grafů a lze v případě potřeby zůstat na úrovni kvalitativního popisu, není tato metoda vhodným nástrojem pro vlastní analýzu systému, respektive pro její počáteční fázi. Velmi dobře však může navazovat na metodu informačních toků nebo na popis hierarchické funkční struktury.

Metoda sekvenčních funkčních grafů


Přechod od analýzy k detailnímu návrhu je v případě sekvenčních diagramů přímý a tedy vysoce efektivní.

Akce 1

K1

Podmínka 1

K2

A2 P2

K3

A3

K4

P3

A4 P4

K5

P5

A5 P6

K7

A7

A9 P9

K2

A6 P7

A8

Sekvenční funkční graf

P8

K9

K8

K6

STRUKTUROVANÁ ANALÝZA A NÁVRH IS

V rámci této prezentace se podrobněji budeme zabývat analýzou 1. struktury dat v podobě: • ERD • Detailního popisu datových struktur v podobě datového slovníku 2. analýzou funkce v podobě: • Kontextového diagramu • DFD • CDFD • Rozšíření o STD • Detailního popisu v podobě minispecifikací

Praktické příklady jsou realizovány v prostředí CASE Studia 2.

DATA FLOW DIAGRAM – DIAGRAM DATOVÝCH TOKŮ – DFD

Je základním nástrojem konceptuálního funkčního modelu. Popisuje z jakých procesů a jejich návazností se realita skládá a potažmo i jaké procesy budou tvořit IS. V DFD se používají základní prvky: • proces; • datový tok (Data Flow); • datový sklad (Data Store); • terminátor. DFD slouží ke znázornění toku a transformace dat, a to bez ohledu na fyzickou realizaci!!! Neslouží k zaznamenání časového hlediska, typů uživatelů, toků materiálů či dokumentů, podmínek, cyklů, frekvence …


PROCES

DATOVÝ SKLAD

GRAFICKÉ ZNAČENÍ PRVKŮ DFD

TERMINÁTOR

DATOVÝ TOK


PROCES – vyjadřuje transformaci dat. Popisuje transformaci vstupů na výstupy, tj. změnu reprezentace, změnu hodnot, změnu stavu, vznik nových hodnot …

PRAVIDLA KONZISTERNCE PROCESŮ: • • • • •

musí mít jednoznačné číslo, které reprezentuje hierarchii rozkladu; musí mít jednoznačný, stručný a výstižný název; nepopisují žádné inicializační ani závěrečné funkce; neznázorňují cykly; neznázorňují časovou posloupnost.


ŘÍDÍCÍ PROCES – vyjadřuje algoritmus vzájemných časových návazností procesů v určité části systému. Nezpracovává data, používá se k popisu real-time charakteristik aplikace. Pro běžné informační systémy se nezpracovává.

PRAVIDLA KONZISTENCE ŘÍDÍCÍCH PROCESŮ: • • • •

neznázorňují transformaci dat; znázorňují řídící procedury a jejich časovou posloupnost; používají se výhradně k popisu real-time složek systémů; musí mít doprovodné diagramy STD.


DATOVÝ TOK – vyjadřuje jakoukoliv formu přesunu dat, spojuje ostatní složky DFD.

PRAVIDLA KONZISTENCE DATOVÝCH TOKŮ: • datový tok musí mít výstižné jméno; • mohou existovat duplicitní dat. toky, ale pouze tehdy, když mají stejnou strukturu; • datové toky vyjadřují JEN skutečnost, že data se „přesunují“ a to bez ohledu na způsob přesunu; • každý datový sklad musí mít min 1 tok dovnitř a 1 tok ven; • každý proces musí mít min 1 tok dovnitř a 1 tok ven; • datový sklad může být propojen pouze s procesem; • terminátor může být propojen pouze s procesem.

POZNÁMKY: • pokud datový tok spojuje datový sklad, nemusí mít název, je-li jeho obsah dán obsahem datového skladu (tj. přenáší celou strukturu skladu); • datový tok může být obousměrný; • většinou operace EDIT v sobě zahrnuje také operaci DELETE, INSERT i všechny požadavky na přesun vstupních formulářů.


TERMINÁTOR – vyjadřuje vnější entitu, s níž popisovaný systém komunikuje, tzn. objekty, které nejsou součástí popisovaného systému, ale jeho podstatného okolí.

PRAVIDLA KONZISTENCE TERMINÁTORŮ: • terminátor musí mít jednoznačný název v rámci kontextového diagramu; • duplicitně se vyskytuje na nižších úrovních; • všichni terminátoři i „jejich“ datové toky vznikají v kontextovém diagramu.


DATOVÝ SKLAD – vyjadřuje jakoukoli formu uložení dat Používá se všude tam, kde při přesunu dat mezi procesy existuje časové zpoždění, může být implementován různě, konkrétní forma uložení nemusí představovat pouze databázi (nezapomínejme, že se pohybujeme stále na konceptuální úrovni, tedy o způsobu budoucí implementace není ještě rozhodnuto).

PRAVIDLA KONZISTENCE DATOVÝCH SKLADŮ: • • •

• •

datový sklad musí mít výstižný název; může se vyskytovat duplicitně, pokud se jedná o sklad s totožnou strukturou; je to pasivní prvek, vyjadřuje pouze uložení, ne transformaci dat; pokud data uložíme, musíme je také použít (pro každý sklad musí existovat datový tok do/ze skladu); datový sklad se v DFD objevuje až v případě potřeby, tj. až když jsou viditelné toky, které do skladu zapisují nebo z něj čtou.

KONTEXTOVÝ DIAGRAM … příklad

REALIZOVÁNO V PROSTŘEDÍ CASE STUDIA 2

DATA FLOW DIAGRAM … příklad DFD 1. úrovně

REALIZOVÁNO V PROSTŘEDÍ CASE STUDIA 2


HIERARCHIE DFD – představuje postupný rozklad systému směrem shora dolů, směrem k nejpodrobnějšímu pohledu Aby byl DFD přehledný, je třeba najít kompromis mezi úplností a podrobností popisu.

HIERARCHIE DFD ZAHRNUJE: • kontextový diagram (nejvyšší, nejméně podrobná rozlišovací úroveň); • první úroveň DFD; • několik středních rozlišovacích úrovní (dle potřeby, může i chybět); • nejnižší úroveň (popisující elementární funkce spolu s minispecifikací).


PRAVIDLA KONZISTENCE KONTEXTOVÉHO DIAGRAMU: • • •

vymezuje popisovaný systém v rámci jeho podstatného okolí, reprezentuje hranice systému; obsahuje pouze 1 proces, jež představuje popisovaný systém; obsahuje všechny terminátory spolu s „jejich“ datovými toky

PRAVIDLA KONZISTENCE NEJNIŽŠÍ ÚROVNĚ: • úroveň podrobnosti je dána analytikem dle potřeb; • elementární funkce představují jediné procesy, jež se budou fyzicky realizovat, všechny ostatní procesy jsou pouze jejich agregací sloužící výhradně ke zvýšení přehlednosti; • všechny elementární funkce musí být zahrnuty v DFD – rozdělení na automatickou a ruční část je záležitostí následné technologické úrovně návrhu IS; • elementární funkce mají výstižný a jednoznačný název; • elementární funkce mají doprovodnou minispecifikaci;


POZNÁMKY KE KONSTRUKCI DFD: • rozkládat je možno procesy, toky a sklady. Rozkládat není možno terminátory a toky spojené s terminátorem (ale je možná duplicita); • je nutno důsledně dbát na hierarchické číslování procesů; • je nutno dodržovat hierarchickou konzistenci DFD (tj. stejné názvy u duplicit); • DFD musí být srozumitelný jak pro analytika tak pro uživatele.


TVORBA DFD - POSTUP: 1. 2.

3. 4. 5. 6. 7.

kontextový diagram - uvědomíme si hranice systému; DFD 1. úrovně – rozdělíme systém na základní procesy, uvědomíme si vzájemnou komunikaci procesů; DFD nižší úrovně – podle potřeby pro velmi rozsáhlé systémy; DFD nejnižší úrovně – sestrojíme pomocí techniky analýza událostí; je-li nejnižší DFD příliš rozsáhlý, přidáme další rozlišovací meziúroveň; zkontrolujeme hierarchickou konzistenci, názvy, číslování; vytvoříme minispecifikaci pro všechny elementární funkce – je lépe dělat paralelně se zakreslením elementárních funkcí do DFD, protože nám to pomáhá si uvědomovat mnohé skutečnosti včas.

Poznámka: v rámci kontroly bezrozpornosti ERD, DFD, DD a minispecifikace je často nutné zpětně upravovat jednotlivé modely.


TECHNIKA ANALÝZY UDÁLOSTÍ - POSTUP: 1. 2. 3. 4. 5. 6. 7.

pro každou událost vytvoř proces; každý proces výstižně a jednoznačně pojmenuj; ke každému procesu doplň vstupy, které ke své činnosti potřebuje; ke každému procesu doplň výstupy, které produkuje; zakresli DFD; zkontroluj konzistenci vzhledem k vyšším úrovním; v případě potřeby vytvoř meziúroveň.

Nezapomínej, že PROCES představuje transformaci dat, tzn. musí mít vstupní i výstupní datový tok. Je výhodné paralelně s vykreslením DFD zapisovat prvotní minispecifikaci.

PŘÍKLAD ANALÝZY UDÁLOSTÍ – PROCES EVIDENCE KNIH

POTŘEBUJE VSTUPY Zavedení knihy Dodejka Struktura katalogu Zrušení knihy Pžd zrušení Info knihovní fond Info struktura Výpis info Info struktura Info titul Info výtisk PROCES

PRODUKUJE VÝSTUPY Ins titul Dlt titul Dlt výtisk Struktura katalogu Info knihovní fond

CONTROL DATA FLOW DIAGRAM … CDFD

Pokud je v diagramu datových toků třeba vyjádřit časovou posloupnost procesů, tak rozšiřujeme DFD o řídící procesy a řídící toky. Po rozšíření vznikne diagram datových toků s řízením (CDFD – control data flow diagram). Řídící proces zajišťuje pouze časovou posloupnost ostatních procesů. Řídící procesy komunikují s ostatními procesy pomocí speciálních řídících toků, tzv. vstupních a výstupních signálů (graficky znázorněno přerušovanou čarou). Vstupní signály informují řídící proces o splnění sledované události během transformace. Výstupními signály naopak dává řídící proces pokyny transformačním procesům. Každý řídící proces znázorněný na CDFD by měl být specifikován pomocí stavově přechodového diagramu (STD).

CONTROL DATA FLOW DIAGRAM … CDFD

Zakreslení řídících procesů a řídících toků (přerušovaná čára) do funkčních diagramů a jejich rozepsání v podobě stavového diagramu.

STATE TRANSITION DIAGRAM … STD

STD musí existovat pro každý řídící proces zobrazený v CDFD. Slouží jako specifikace řídících procesů a skládá se ze stavů a přechodů mezi nimi. Stav je zobrazen jako obdélník s názvem a přechod je znázorněn šipkou s popisem. Popis přechodu je rozdělen čarou na podmínku a akci. Podmínkou se rozumí událost ve vnějším okolí, kterou systém detekuje. Akce je reakce na splněnou podmínku. Pokud dojde ke splnění podmínky, tak nastává změna stavu, po které se provede akce. Každý STD má jeden počáteční a minimálně jeden koncový stav. Počáteční stav poznáme tak, že na něj ukazuje šipka. Koncové stavy jsou ty, ze kterých nevedou žádné přechody. Složité STD je vhodné kvůli zvýšení přehlednosti dekomponovat.

STATE TRANSITION DIAGRAM … STD

Pravidla tvorby STD: • identifikovat všechny možné stavy systému a zakreslit je na STD; • najít všechny přechody mezi stavy a začít je zakreslovat systematicky od počátečního stavu do koncového stavu; • prověřit konzistenci a hierarchii STD; • prověřit konzistenci STD oproti jiným modelům systému.

vztah mezi CDFD a STD

STD

CDFD

Minispecifikace Minispecifikace je detailní popis procesu, upřesňuje, jak probíhá uvnitř procesu transformace vstupů na výstupy. Každá elementární funkce (tj.proces na nejnižší rozlišovací úrovni DFD) musí povinně mít definovanou minispecifikaci. A naopak, ke každé minispecifikaci musí existovat elementární fce. Její konkrétní podoba je různá: běžný jazyk, strukturovaný jazyk, strukturní diagram, formální zápis algoritmu…

PRAVIDLA TVORBY MINISPECIFIKACE: • 1 minispecifikace pro 1 elementární funkci • Vyjadřuje POSTUP transformace vstupů na výstupy • Nevyjadřuje ZPŮSOB IMPLEMENTACE transformace • nesmí popisovat to, co je již popsáno v datovém slovníku, protože duplicita vždy představuje riziko nekonzistence • musí být srozumitelná analytikovi i uživateli • popis by měl být strukturovaný

Strukturní diagramy Představují jednu z možností zápisu minispecifikace. Jejich vzhled vychází ze „Jackson Structured Programming“. Jsou univerzální, lze je použít jak k popisu struktury algoritmu, tak k popisu struktury dat. Pomáhají nám uvědomit si souvislosti mezi uspořádáním dat a uspořádáním procesů. Využívají se rovněž k popisu dat v datovém slovníku (DD). Čtou se shora dolů a zleva doprava. Představují stromový graf, kde rozklad prvku do podřízených prvků může být typu: • Sekvence • Selekce (značka kolečka) • Iterace (značka hvězdičky)

PŘÍKLAD MINISPECIFIKACE V PODOBĚ STRUKTURNÍHO DIAGRAMU zaplacení

Kontrola čtenáře Samostatné placení

Kontrola průkazu

Potvrzení zaplacení

Kontrola dluhů

Dokud nejsou všechny dluhy vyřízeny

Kontrola požadavku

vyřízení

Příjem peněz

Vymazání dluhů

STRUKTUROVANÝ JAZYK Pro vyjádření minispecifikace lze použít k popisu elementárních procesů slova přirozeného jazyka , jež vychází z vyšších programovacích jazyků. Rozhodovací struktury - platí-li podmínka, provedou se příkazy 1, v opačném případě příkazy 2. IF podmínka THEN příkazy 1 ELSE příkazy 2 END

základní konstrukce strukturovaného jazyka

Přepínač - postupně se vyhodnocují podmínky podmínka n a provedou se ty příkazy, pro které je podmínka platná. SELECT CASE CASE 1 podmínka 1 příkazy 1 CASE 2 podmínka 2 příkazy 2 ..... OTHERWISE příkazy j END


Cyklus s předem definovaným počtem průchodů Po vyčerpání počtu počet průchodů se struktura ukončí. FOR počet DO příkazy těla NEXT


Cyklus s podmínkou na počátku V případě, že při prvním vyhodnocení podmínky cyklus zjistí její neplatnost, tělo cyklu se nevykoná a struktura se ukončí. WHILE podmínka DO příkazy těla END


Cyklus s podmínkou na konci

Oproti předcházející struktuře se příkazy těla provedou minimálně jednou i přesto, že podmínka není platná. REPEAT příkazy těla UNTIL podmínka


Příklad minispecifikace zapsané strukturovaným jazykem

PROCESS zaplacení BEGIN kontrola čtenáře IF samostatné placení THEN kontrola průkazu, ELSE kontrola požadavku kontrola čtenáře END; kontrola dluhů REPEAT vyřízení SEQ příjem peněz; vymazání dluhů vyřízení END UNTIL (dokud nejsou všechny dluhy vyřízeny); potvrzení o zaplacení END.

PROCESS zaplacení BEGIN kontrola čtenáře IF Porovnání minispecifikace samostatné placení zapsané strukturovaným jazykem THEN kontrola průkazu, ELSE kontrola požadavku a grafickou formou kontrola čtenáře END; strukturovaných diagramů kontrola dluhů REPEAT vyřízení SEQ příjem peněz; vymazání dluhů vyřízení END UNTIL (dokud nejsou všechny dluhy vyřízeny); potvrzení o zaplacení zaplacení END.

Kontrola čtenáře Samostatné placení

Kontrola průkazu


Kontrola dluhů

Kontrola požadavku

vyřízení Příjem peněz


Vymazání dluhů

DATOVÝ SLOVNÍK – DATA DICTIONARY - DD

Představuje místo centrálního popisu datových struktur. V DFD se data realizují v podobě datových skladů a datových toků, v ERD mají podobu entit, jejich záznamů a vazeb. Jedná se však o tutéž realitu, proto je nutné zajistit konzistenci všech modelů včetně konzistence různých rozlišovacích úrovní. Hlavním styčným bodem modelů (DFD, ERD, STD, Structure Chart…) a současně jediným místem popisu datových struktur je datový slovník. Je důležité zamezit duplicitě popisu datových struktur, protože duplicita vždy představuje potenciální zdroj rozporných popisů. Po vytvoření datového slovníku se následně kontroluje spolupráce modelů, a to právě prostřednictvím DD.


Pro přehlednost je vhodné DD rozdělit na následující části: 1. Datové toky 2. Datové sklady 3. Datové prvky 4. Číselníky Do DD je možno začlenit také minispecifikace procesů, pakliže nejsou součástí elementárních funkcí. Nesmíme dopustit duplicitu minispecifikací, protože duplicity jsou možným zdrojem nekonzistence.


Poznámky ke konstrukci datového slovníku Datový tok může obsahovat jen části struktury datových skladů, jejich kombinace i nově vzniklé prvky. Datový prvek je nejmenší - dále nedělitelná - významová jednotka dat. U relačních databází je touto jednotkou položka záznamu. Navržení správné struktury dat je jednou z nejdůležitějších činností při návrhu IS. Pro jednotný a srozumitelný návrh musí existovat jednotný vyjadřovací prostředek. Vhodné jsou struktury z vyšších programovacích jazyků.


Symboly vhodné pro popis datových struktur

údaj je složen (rovná se) logické spojené (and) opakování obsahu v závorkách obsah závorek obsahuje výčet možností (odděleny "|") ( ) parametr může ale nemusí existovat *...* komentář @ označení klíčového prvku (primárního klíče) = + {} []

Jazyk Data Dictionary Jméno = (titul) + křestní:_jméno + příjmení Titul = [pan│paní│slečna│Dr. │Prof. │Ing.] Křestní_jméno = {písmeno} * a je možná poznámka*

Jméno

Diagram datové struktury

Křestní jméno

Písmeno

Titul

Pan

Paní

Slečna

Dr.

Prof.

Příjmení

Písmeno

Ing.


Pro definování datových toků nebo skladů se uvádí: • identifikátor • struktura (obsahující substruktury a názvy položek, případně označení položky představující klíč symbolem @) • Popis (možno uvést i popisy vazeb na okolní prvky DFD)


Pro definování datových prvků se uvádí: • identifikátor • popis - představuje verbální popis prvku a jeho použití. • délka - uvádí potřebný počet znaků. • typ - udává základní typ prvku (N=číselný, C=textový, D=datum, L=logický) • interval přípustných hodnot – nepovinný, uvádí se buď formou intervalu nebo výčtem.

Poznámka: pokud uvažujete s pozdějším generováním SQL skriptů, musíte definovat atributy se všemi detaily !!!

DATOVÝ SLOVNÍK … příklad popisu datových toků

Datový tok: ADRESA=NÁZEV+ULICE+ČÍSLO_DOMU+PSČ+MĚSTO+ STÁT Popis: Adresa osoby nebo firmy. Datový tok: DODAVATEL=ADRESA Popis: Jméno nebo název firmy a přesná adresa dodavatele zboží. Datový tok: OBJEDNÁVKA=DODAVATEL+{ZBOŽÍ}+ODBĚRATEL+DATUM Popis: Základní údaje dokumentu, kterým ODBĚRATEL objednává specifikované zboží Datový tok: OBJEDNÁVKA_A=OBJEDNÁVKA Popis: Akceptovaná objednávka - bude dodavatelem vyřízena kladně.

DATOVÝ SLOVNÍK … příklad popisu datových skladů

Sklad: STUDENT= @RODNÉČISLO + PŘÍ.JMENI + JMÉNO + MÍSTONAROZENÍ + OKRESNAROZENÍ Popis: Základní osobní údaje studenta. Sklad: ZÁKAZNIK=INTČÍSLO + ADRESA + (BANKSPOJENÍ)+ @IČO Popis: Seznam zákazníků firmy. Sklad: ZBOŽÍ =KÓDOZNAČENÍ+NÁZEVZBOŽÍ+CENA+MNOŽSTVÍ

DATOVÝ SLOVNÍK … příklad popisu datových prvků

Datový prvek CENA Typ: N Délka: 30 Popis: Cena prodávaného zboží. Interval: 150 - 3000 Kč. Datový prvek: DÉLKA Typ: N Délka: 5 Datový prvek: PROFESE Typ: N Délka: 2 Popis: Údaj označující profesi, ve které je pracovník vyučen. Interval: viz dále interní číselník PROFESE

DATOVÝ SLOVNÍK … příklad popisu datových prvků

Datový prvek: RODNÉ.ČÍSLO Typ: AN Délka: 11 Popis: Rodné číslo osoby, dle celostátního číselníku. Datový prvek: STAV Typ: A Délka: 1 Popis: Údaj definující rodinný stav. ["s"|"S"] - svobodný(á) ["r"|"R"] - rozvedený(á) ["v"|"V"] - vdaná ["ž"|"Ž"] - ženatý Interval: ["s"|"S"|"r"|"R"|"v"|"V"|"ž"|"Ž"]

DATOVÝ SLOVNÍK … příklad číselníku

Číselník: PROFESE Struktura: XX - kde X je číslice O div 9 Obsah: 01 - dělník 02 - soustružník 03 - frézař 04 - svářeč atd. Příkladem číselníku mohou být české státní normy, poštovní směrovací čísla, kódová označení surovin …

KONZISTENCE MODELŮ Základním rysem strukturované analýzy je oddělení popisu funkcí systému (DFD) a struktury systému (ERD). Tato skutečnost při analýze způsobuje mnohé nesnáze, protože nás nutí paralelně pracovat se dvěma různými modely. Zároveň je nezbytné hlídat bezpozpornost těchto modelů. Protože oba modely popisují tytéž datové struktury vyjádřené odlišnou formou, zaměřuje se kontrola konzistence modelů na kontrolu datových struktur. • • • •

Centrem popisu dat je DD, proto je právě DD logickým východiskem při kontrole konzistence. Pokud při analýze tvoříme taky STD, Structure Chart, či jiné typy diagramů, musejí i ty projít kontrolou konzistence. Bezrozpornost modelů musíme dodržovat nejen mezi různými typy modelů, ale také na různých rozlišovacích úrovních (hierarchická konzistence). Navíc je potřeba hlídat spolupráci modelů nejen na konceptuální úrovni, ale i na úrovni technologické a implementační (není probíráno v rámci předmětu Systémová analýza).

Hierarchická konzistence Kontrolujeme všude tam, kde se modely hierarchicky rozkládají na různé rozlišovací hladiny. Týká se hlavně DFD. V ERD jsou jakékoliv duplicity nepřípustné, tento typ modelu neobsahuje hierarchii!!! U DFD je nutné se zvýšenou pozorností kontrolovat zejména datové toky a sklady, které mají větší než pouze lokální platnost v jediném diagramu. Protože toky i sklady se mohou také rozkládat, je účelné tento rozklad zaznamenat v rámci DD. Konzistence hierarchie

Pravidla konzistence mezi DFD a DD Kontroluje definované datové struktury v DFD • Každý tok i sklad musí být definován v DD • Každý prvek a sklad definovaný DD musí být použit v DFD.

Pravidla konzistence mezi DD a DFD&minispecifikací Kontrolují požadavek nutného použití každého prvku (struktury) definovaného v DD. • Každý datový prvek v DD musí být použit v minispecifikaci, nebo v DFD, nebo při popisu jiného datového prvku.

Pravidla konzistence mezi DFD a minispecifikací Kontroluje vztahy mezi rozlišovacími úrovněmi v rámci DFD. • Každý elementární proces (tj. proces na nejnižší úrovni, jež není dále dekomponován) musí mít svou minispecifikaci a naopak ke každé minispecifikaci musí existovat elementární proces. • Každému výstupnímu/vstupnímu datovému toku z procesu v DFD musí v minispecifikaci odpovídat příslušná operace zápisu/čtení dat.

Pravidla konzistence mezi minispecifikací a DFD&DD

Kontroluje, zda všechny datové prvky použité v minispecifikaci mají „vyšší“ význam. Tedy každý odkaz na data musí představovat: 1. Data tvořící rozhraní elementární funkce, tj. vstupní/výstupní tok (nebo jeho část) příslušného procesu, nebo kontaktovaný sklad 2. Nebo data lokálního významu, jež mají význam pouze pro popisovaný algoritmus (lokální proměnné) 3. Nebo pomocné struktury, jejímž cílem je zjednodušit složitější algoritmus rozdělením zpracování v čase)

Každý odkaz na data v minispecifikaci musí představovat buď: • název datového toku/skladu spojeného s procesem, nebo • lokální data popisovaného procesu, nebo • název komponenty datového toku/skladu spojeného s procesem (pak musí být komponenta uvedená v DD)

Pravidla konzistence mezi DFD a STD Kontrolují velmi problémovou existenci řídících procesů a dat ve funkčním modelu. • Každý řídící proces v DFD musí mít svůj STD • Každá podmínka v STD odpovídá vstupnímu řídícímu toku v DFD a naopak • Každá akce v STD odpovídá výstupnímu řídícímu toku v DFD a naopak.

Pravidla konzistence mezi ERD a DFD&minispecifikací

Představují základ integrace datového a funkčního modelu • Každému datovému skladu v DFD musí v ERD odpovídat entita nebo vztah nebo kombinace obojího. • Datové prvky v DD popisují jak data v DFD, tak data v ERD • Minispecifikace musí obsahovat operace CREATE a DELETE pro každý objekt a vztah uvedený v ERD. • Datové elementy (atributy) každého objektu v ERD musí být nastaveny některým procesem v DFD a také některým použity.

Pravidla konzistence mezi ERD a DFD

• Datový sklad na DFD musí odpovídat entitní množině na ERD a naopak. • Jména entitních množin na ERD a jména datových skladů na DFD si musí odpovídat. • Položky v datovém slovníku musí být aplikovatelné současně na DFD i ERD. • Musí existovat procesy, které přiřadí hodnoty každému datovému elementu, který je atributem na ERD. • Rovněž musí existovat procesy, které tyto hodnoty čtou.

VYPRACOVANÝ PŘÍKLAD NA STRUKTUROVANOU ANALÝZU (návrh struktury i funkce budoucího systému) Navrhni IS pro zabezpečení chodu jednoduché knihovny. Požadavky na IS:  Evidence titulů  Evidence čtenářů  Podpora výpůjček jednotlivých výtisků

Pro tento IS je prvotní DB, proto budeme postupovat v následujících krocích:         

Hrubý ERD Podrobný ERD Kontrola normalizačních pravidel Kontextový diagram DFD pro jednotlivé rozlišovací úrovně Předběžná kontrola konzistence DFD – ERD Minispecifikace DD Kontrola konzistence

Prvotní návrh ERD

ERD včetně klíčových položek a atributů

NORMALIZACE – 1.NF Aby byla relace v 1.NF, musí obsahovat pouze atomické, tj. dále nedělitelné atributy

NAKLADATELSTVÍ ULICE_ČP MĚSTO PSČ NOVÁ TABULKA

AUTOR_1 AUTOR_2 AUTOR_3

ULICE_ČP MĚSTO PSČ NOVÁ TABULKA

REGÁL POZICE

NORMALIZACE – 1.NF

VÝSLEDEK Není účelné rozdělovat tabulky

Normaliza ce … 2.NF Aby relace byla ve 2.NF, musí být již v 1.NF a každý její atribut musí být závislý na CELÉM primárním klíči Žádná tabulka nemá složený PK – 2.NF je splněna

KLÍČ KLÍČ KLÍČ KLÍČ

KLÍČ KLÍČ

KLÍČ

KLÍČ KLÍČ

KLÍČ KLÍČ

Normalizace … 3.NF Aby relace byla ve 3.NF, musí být již ve 2.NF a jednotlivé atributy musí být závislé POUZE na PK a ne na jiném atributu.

NOVÁ TABULKA

VYPOČÍTANÁ POLOŽKA !!!

NOVÁ TABULKA

NORMALIZACE – 3.NF

výsledný relační datový model

Zjednodušení – 1 PSČ odpovídá jen 1 „město“

Vypočítaná položka nutno zvážit její přítomnost!

Pokud budeme chtít pomocí CASE nástrojů automaticky generovat SQL skripty, musíme ihned na začátku zadávání ERD vybrat DB implementační prostředí a posléze zadat relační datový model se všemi podrobnostmi:

• • • • • • • • •

Klíče primární, cizí, složené, alternativní … Pravidla referenční integrity Datové typy + délky Vstupní masky Omezení rozsahu hodnot Ověřovací pravidla Opravné texty Formáty zobrazení V datovém slovníku je uveden přesný popis seznamů a číselníků pro vstup dat

ERD … DEFINICE ATRIBUTŮ

Implementační prostředí CASE Studio 2

ERD … DEFINICE PRIMÁRNÍHO KLÍČE Označení klíčového atributu

Primární klíče jsou často automaticky generované atributy typu celočíselných proměnných


ERD … DEFINICE ATRIBUTŮ

CASE Studio 2 umožňuje zadat formáty, masky, ověřovací pravidla, implicitní hodnoty, povinnost členství, možnost duplicitních a nulových hodnot …

Je vhodné využívat karty POPIS a POZNÁMKY kvůli udržení přehlednosti


ERD … TYP RELACE

entita na straně dítě nepovinné členství

entita na straně rodič povinné členství

Typ vazby … IDENTIFIKAČNÍ nutno nastavit referenční integritu Implementační prostředí CASE Studio 2

ERD … PARCIALITA RELACE identifikační vazba je znázorněna plnou čarou

nepovinné členství je znázorněno prázdným kolečkem

identifikační relace má povinné členství na straně rodič


ERD … REFERENČNÍ INTEGRITA

Referenční integrita určuje co se stane, když změníte anebo zrušíte klíč, pomocí něhož je realizována vazba mezi tabulkami

Nastavuje se zvlášť pro stranu rodič a pro stranu dítě


ERD … REFERENČNÍ INTEGRITA • None – referenční integritu nebude kontrolovat DB stroj, proto musíme zajistit její hlídání v nadstavbovém informačním systému • Restrict – editace (zrušení) klíče je zablokováno • Cascade – při editaci (zrušení) klíče se změna promítne automaticky do celé kaskády záznamů v podřízených tabulkách • Set null - při editaci (zrušení) klíče se automaticky v podřízených tabulkách nastaví klíč na hodnotu 0 • Set default - při editaci (zrušení) klíče se automaticky v podřízených tabulkách nastaví klíč na předem definovanou hodnotu


DFD … KONTEXTOVÝ DIAGRAM CÍL: vymezit podstatné okolí systému.


DFD … 1. ÚROVEŇ CÍL: rozdělit analyzovaný systém na hlavní podsystémy.


Analýza událostí pro proces EVIDENCE KNIH POTŘEBUJE VSTUPY Zavedení knihy Dodejka Struktura katalogu Zrušení knihy Pžd zrušení Info knihovní fond Info struktura Výpis info Info struktura Info titul Info výtisk PROCES

PRODUKUJE VÝSTUPY Ins titul Dlt titul Dlt výtisk

Struktura katalogu Info knihovní fond

Pomůže nám v definici nejnižší úrovně DFD Procesu EVIDENCE ČTENÁŘŮ

DFD … 2. ÚROVEŇ (nejnižší)

Procesy na nejnižší úrovni se jako jediné z celé hierarchie DFD budou fyzicky realizovat Implementační prostředí CASE Studio 2

Analýza událostí pro proces EVIDENCE ČTENÁŘŮ PROCES Zavedení čtenáře Zrušení čtenáře

Editace čtenáře

POTŘEBUJE VSTUPY Data čtenář

PRODUKUJE VÝSTUPY Ins čtenář průkazka Dlt čtenář

Průkazka Info čtenář Výpis výpůjčka Data čtenář Edt čtenář Průkazka Info čtenář

Pomůže nám v definici nejnižší úrovně DFD procesu EVIDENCE KNIH

DFD … 2. ÚROVEŇ (nejnižší)


PROCES Vypůjčení výtisku SPRÁVA VYPŮJČEK Zaplacení

Vydání upomínky Vrácení výtisku

POTŘEBUJE VSTUPY Průkaz Info výpůjčka PŽD výtisk Info výtisk Průkaz PŽD zaplac. upomínky Info výpůjčka PŽD zaplacení penále Info výpůjčka Info čtenář Průkaz Info výpůjčka

Zrušení výtisku

PŽD zrušení výtisku

informace

PŽD výpis knih. fond PŽD výpis výpůjčka info výpůjčka info titul/výtisk info struktura

PRODUKUJE VÝSTUPY EDT výpůjčka EDT výtisk PŽD zaplacení upomínky Info výpůjčka EDT výpůjčka Potvrzení zaplacení

EDT výpůjčka upomínka PŽD zaplac. upomínky EDT výpůjčka EDT výtisk Potvrzení vrácení PŽD zrušení výtisku PŽD zaplacení penále EDT výtisk Výpis knihovní fond Výpis výpůjčka

Rozklad procesu SPRÁVA VÝPŮJČEK


Minispecifikace procesu ZAPLACENÍ Proces zaplacení se spustí, pokud přijde požadavek na zaplacení upomínky, anebo požadavek na zaplacení penále při ztrátě/poškození výtisku. Upomínky se generují automaticky, čtenář může chtít pouze zaplatit upomínku, anebo si zároveň půjčit další knihy. Upomínku/penále je nutno zaplatit vždy jako celek najednou. Po zaplacení čtenář dostane potvrzení o zaplacení.

1.

2. 3. 4.

Buď kontrola průkazu PRŮKAZ (T.čtenář – P.zaplacení) anebo PŽD ZAPLACENÍ UPOMÍNKY (P.vypůjčení výtisku – P.zaplacení) anebo PŽD ZAPLACENÍ PENÁLE (P.zrušení výtisku – P.zaplacení) Kontrola všech dluhů INFO VÝPŮJČKA (D.S.výpůjčka – P.zaplacení) – poznámka: chybí atribut k zaznamenání penále – nutno dodělat!!! Po fyzickém zaplacení změnit status výpůjčky na „vyřízeno“ EDT VÝPŮJČKA (P.zaplacení – D.S.výpůjčka) Vytisknout potvrzení o zaplacení dluhů POTVRZENÍ ZAPLACENÍ (P.zaplacení – D.S.čtenář)

Tento způsob není příliš vhodný – slouží jako prvotní minispecifikace

Minispecifikace procesu ZAPLACENÍ zaplacení

Kontrola čtenáře


Samostatné placení

Kontrola průkazu

STRUKTURNÍ DIAGRAM


Kontrola dluhů

Kontrola požadavku

vyřízení

Příjem peněz

Vymazání dluhů

Minispecifikace procesu ZAPLACENÍ PROCESS zaplacení BEGIN kontrola čtenáře IF samostatné placení THEN kontrola průkazu, ELSE kontrola požadavku kontrola čtenáře END; kontrola dluhů REPEAT vyřízení SEQ příjem peněz; vymazání dluhů vyřízení END UNTIL (dokud nejsou všechny dluhy vyřízeny); potvrzení o zaplacení END.

STRUKTUROVANÝ JAZYK

Minispecifikace procesu VYDÁNÍ UPOMÍNKY Upomínky se generují automaticky, na začátku pracovního dne se zkontrolují výpůjčky a potřebné upomínky se automaticky zašlou čtenářům. 1. Kontrola všech výpůjček INFO VÝPŮJČKA (D.S.výpůjčka – P.vydání upomínky) 2. Načtení údajů o čtenáři pro vybrané výpůjčky INFO ČTENÁŘ (D.S.čtenář – P.vydání výpůjčky) 3. Generování upomínek 4. Odeslání upomínek čtenářům UPOMÍNKA (P.vydání upomínky – T.čtenář)

Tento způsob není příliš vhodný – slouží jako prvotní minispecifikace

Minispecifikace procesu VYDÁNÍ UPOMÍNKY Vydání upomínky Kontrola výpůjčky

Dokud nejsou všechny výpůjčky zkontrolovány

Vypršela doba výpůjčky

Upomínka

Kontrola čtenáře

STRUKTURNÍ DIAGRAM

Generování upomínky

Odeslání upomínky

Zápis ve výpůjčce

Minispecifikace procesu VYDÁNÍ UPOMÍNKY

PROCESS vydání upomínky; BEGIN kontrola výpůjčky REPEAT IF vypršela doba výpůjčky THEN upomínka SEQ kontrola čtenáře; generování upomínky; odeslání upomínky; zápis ve výpůjčce upomínka END END; UNTIL všechny výpůjčky zkontrolovány END.

STRUKTUROVANÝ JAZYK

Minispecifikace procesu PŮJČENÍ VÝTISKU Čtenář předloží čtenářský průkaz, obsluha ho zkontroluje a vyhledá čtenářovy upomínky + seznam půjčených knih. V případě upomínky bude požadovat její zaplacení, teprve potom zkontroluje, zda požadované tituly jsou momentálně k dispozici, zaeviduje novou výpůjčku a čtenářovi předá půjčené knihy včetně jejich seznamu s daty půjčení /vrácení. 1. 2. 3. 4. 5. 6.

Kontrola průkazu PRŮKAZ (T.čtenář – P.vypůjčení výtisku) Kontrola výpůjček/dluhů INFO VÝPŮJČKA (D.S.výpůjčka – P.vypůjčení výtisku) Pokud je upomínka, pak aktivovat zaplacení PŽD ZAPLACENÍ UPOMÍNKY (P.vypůjčení výtisku-P.zaplacení) Kontrola požadovaných knih PŽD VÝTISK (T.čtenář-P.vypůjčení výtisku) + INFO VÝTISK (D.S.výtisk – P.vypůjčení výtisku) Pokud jsou výtisky na místě, pak ( změnit status výtisků na „půjčeno“ EDT VÝTISK (P.vypůjčení výtisku – D.S.výtisk) a založit novou výpůjčku EDT VÝPŮJČKA (P.vypůjčení výtisku – D.S.výpůjčka)) Vytisknout seznam všech, tzn. také předešlých vypůjčených knih VÝPIS VÝPŮJČKA (P.vypůjčení výtisku – T.čtenář)

Tento způsob není příliš vhodný – slouží jako prvotní minispecifikace.

PROJEKTOVÝ STROM

ERD – návrh struktury

Kontextový diagram – vymezení podstatného okolí systému

DFD - postupný rozklad na různé rozlišovací úrovni


Stavební prvky ERD a DFD • • • • •

Entita Identifikační relace Neidentifikační relace Relace N:M Informativní relace

• • • •

Datový sklad Terminátor Proces Datový tok

•

Hierarchický rozklad DFD


PRINCIP TŘÍ ARCHITEKTUR PŘI ANALÝZE A NÁVRHU IS

Každá ze tří úrovní definuje specifickou architekturu. Každá architektura má svou specifickou logiku a specifický předmět zájmu (obsah, technologii a implementační specifika). Pro metody to znamená: • pro každou úroveň návrhu mít specifický jazyk a techniky návrhu; • pro každý přechod z jedné úrovně do následující mít specifické techniky přechodu . Příklady nástrojů a technik různých metod pro činnosti na konceptuální a technologické úrovni uvádí následující tabulka.

Základní rozpory při strukturovaném přístupu k analýze a návrhu IS

Přehled CASE nástrojů na trhu

CASE (computer aided software engineering) nástroje jsou aplikace nebo sady aplikací používané pro podporu vývoje softwarových produktů ve všech jeho stádiích. Jde o velkou skupinu různých typů nástrojů podporujících jednotlivé procesy, které jsou součástí vývoje software od nástrojů pro řízení vývojových projektů a skupin, analýzu podnikových procesů či nástrojů pro analýzy rizik po samotné programovací nástroje, nástroje pro testování aplikací a konfigurační nástroje.

Hlavní dělení Case nástrojů je dělení na základě • podporovaných činností v životním cyklu informačních systémů. • stupně integrace nástrojů

Dělení CASE podle podporovaných činností:

• Upper CASE nástroje podporují strategické plánování a návrh informačních systémů po konceptuální úroveň. Do této skupiny patří mimo jiné nástroje pro analýzu podnikových procesů, pro tvorbu modelů datové struktury či chování systému. • Lower CASE nástroje jsou zaměřeny na činnosti na úrovni fyzického návrhu a implementace, jako jsou programování, ladění, testování, integrace komponent, údržba a aktualizace.

Dělení CASE podle stupně integrace: • Jednotlivé nástroje (tools) - nástroje pro podporu jednotlivých činností v rámci vývoje software. • Skupiny nástrojů zaměřené na konkrétní část vývojového cyklu (workbenches) - sady nástrojů podporující konkrétní etapu vývoje software. Obvykle jsou dále děleny podle podporované etapy vývoje software na • nástroje pro modelování a plánování obchodních procesů • nástroje pro analýzu a návrh systémů • nástroje pro návrh a vizualizaci uživatelského rozhraní • programovací nástroje • nástroje pro testování a kontrolu • nástroje pro údržbu a reverzní inženýrství • nástroje pro konfigurační managementn • nástroje pro řízení projektů • CASE prostředí (environments) - ucelené sady nástrojů podporující velkou část životního cyklu software.


Přestože všechny etapy životního cyklu software je možné spravovat či podporovat různými CASE nástroji, obecně jsou pod pojmem CASE nástroje vnímány především nástroje pro analýzu a návrh informačních systémů a tvorbu modelů datové struktury a chování systému. CASE nástroje dostupné na trhu se dají rozdělit do tří základních skupin.

Přehled CASE nástrojů na trhu 1. Skupina - aplikace určené pro jiný typ úloh, ve kterých jsou některé modely strukturované analýzy vhodným doplňkem k hlavní funkci Zde patří především CASE nástroje s podporou UML a nástroje specializované na analýzu, správu a návrh databází. V UML nástrojích je často možnost tvorby ERD diagramů pro vizualizaci struktury databáze a v některých případech i DFD. V aplikacích pro správu, analýzu a návrh databází je ERD diagram základním vizualizačním nástrojem, ostatní modely strukturované analýzy v nich ale nejsou vůbec podporovány.


2. Skupina - obecné editory diagramů, ve kterých jsou k dispozici i sady obrazců vhodných pro tvorbu diagramů strukturované analýzy obsahují obvykle velkou škálu sad obrazců pro tvorbu různých typů diagramů. Některé z nich umožňují nejen tvorbu více modelů strukturované analýzy, ale pro jednotlivé modely jsou k dispozici obrazce podle více různých notací konkrétního diagramu. Nevýhodou těchto nástrojů je absence kontroly správnosti modelů.

Přehled CASE nástrojů na trhu 3. Skupina - aplikace specializované na podporu strukturované analýzy a návrhu informačních systémů Specializované aplikace obsahují kompletní sadu nástrojů pro tvorbu modelů a kontrolují správnost modelů nejen na úrovni jednotlivých modelů, ale i integritu celého popisu systému. Stručný přehled je uveden na následující stránce. V tabulce chybí nástroj CASE Studio, který byl použit při zpracování praktické části této prezentace. CASE Studio 2 již není na trhu. Jeho nástupce, Toad Data Modeler, neumožňuje tvorbu Data Flow Diagramů, specializuje se pouze na návrh struktury databáze pomocí ERD.

Přehled CASE nástrojů na trhu výrobce

produkt

www adresa

podporované modely stručný popis AQUAFOLD

Aqua Data Studio

http://www.aquafold.com/

ERD nástroj pro analýzu, vývoj a správu databází. ERD slouží pro vizualizaci zkoumaných, spravovaných a navrhovaných databází CHANGE VISION

Astah professional

http://astah.net

ERD, DFD umožňuje tvorbu UML modelů i DFD a ERD. Hlídá správnost jednotlivých modelů, nikoliv vztahy mezi jednotlivými modely

DBDEVELOPER Solutions

dBConstructor

http://www.dbconstructor.com/overview/

ERD nástroj pro analýzu, vývoj a správu databází. ERD slouží pro vizualizaci zkoumaných, spravovaných a navrhovaných databází komunitní projekt

Dia

https://wiki.gnome.org/Apps/Dia

ERD, DFD nástroj inspirovaný aplikací Microsoft Visio. Kromě jiných diagramů a grafů umožňuje tvorbu DFD a ERD. Chybí jakákoliv kontrola správnosti diagramů.

EDRAWSOFT

Edraw Max

http://www.edrawsoft.com/EDrawMax.php

ERD, DFD editor diagramů. Kromě jiného umí několik notací DFD, ERD, UML diagramy, kontrola správnosti chybí SPARX SYSTEMS

Enterprise Architect

http://www.sparxsystems.com.au/

ERD, DFD "UML Modeling and Lifecycle Tool Suite" - Sada nástrojů pro UML modelování a správu životního cyklu SW. Z nástrojů strukturované analýzy podporuje ERD a DFD, kontrola na úrovni jednotlivých modelů

Přehled CASE nástrojů na trhu výrobce

produkt

podporované modely GRANDITE

stručný popis Open ModelSphere

ERD, DFD

SMARTDRAW, LLC

http://www.modelsphere.org/open_modelsphere.html

umožňuje tvorbu UML modelů i DFD a ERD. Kontrola jednotlivých modelů chybí

SmartDraw

DFD, ERD

www adresa

http://www.smartdraw.com/product/

editor diagramů. Kromě jiného umí DFD, ERD, UML diagramy. Kontrola správnosti chybí

DELL

Toad Data Modeler

ERD

SELECT BS

nástroj pro modelování a návrh databází. Nástupce Case Studia, ze kterého byl odebrán DFD a dále vylepšen byl ERD Select Yourdon

ERD, DFD, STD, Structure Chart

MICROSOFT

http://www.selectbs.com

specializovaný nástroj analýzu a návrh IS s použitím Yourdonovy metody. Kontroluje správnost jednotlivých modelů i konzistenci celého popisu systému pomocí DD

Visio ERD, DFD

http://www.quest.com/toad-data-modeler/

http://office.microsoft.com/cs-cz/visio

editor diagramů. Kromě jiného umí DFD, ERD, UML diagramy. Kontrola správnosti chybí

VISUAL PARADIGM INT

ERD, DFD

Visual Paradigm for UML

http://www.visual-paradigm.com/

umožňuje tvorbu UML modelů i DFD a ERD. Hlídá správnost jednotlivých modelů

ASTAH PROFESSIONAL … ERD

ASTAH PROFESSIONAL … DFD

ASTAH PROFESSIONAL … funkčnost Podporované diagramy: • UML2.x • Mind Map • ER Diagram • Flowchart • CRUD • Data Flow Diagram (DFD) • Requirement Table • Requirement Diagram • State Transition Table • State Transition Path • DSM • Inconsistency Check

ASTAH PROFESSIONAL … funkčnost Jazyky, API, Plug-ins: • Java Modeling, Export • Java Reverse • C# Modeling, Export • C# Reverse • C++ Modeling, Export • C++ Reverse • PHP Export • Getting/Editing models by using API • Plug-ins

ASTAH PROFESSIONAL … funkčnost Konverze mezi diagramy: • Convert UML models to Mind Map Topics, ER, DFD models and vice versa • Convert ER models and DFD models and vice versa • Convert Flowchart models to UML models Vstupy / výstupy: • Printing, Print options, Print Preview • Exporting to JPEG, PNG, EMF, SVG files • Exporting to RTF Documents • Exporting HTML • Exporting CSV • Database Reverse Engineering • Exporting Entity Definition Report • SQL Export • XML Input/Output • Tagged Value • Astah Publish Compatible • XMI Import

PŘÍPADOVÁ STUDIE firmy poskytující outsourcingové služby v oblasti IT

Zpracováno v rámci bakalářské práce v roce 2014 Analýza a návrh části IS při společnosti George Engineering, a.s. Student: Vožeh Petr Vedoucí práce: Létavková Dagmar Plný text této práce je uložen v repozitáři Dspace na Vysoké škole báňské - Technické univerzitě Ostrava

ZADÁNÍ PŘÍPADOVÉ STUDIE

Cílem zde prezentovaného příkladu je navrhnout informační systém pro správu požadavků pro jistou menší outsourcingovou společnost. Úkolem navrhovaného systému je zabezpečit evidenci a zpracování požadavků zákazníků společnosti, evidenci událostí týkajících se požadavků, evidenci výkazů práce technického týmu a přípravu fakturace víceprací. Společnost působí v oblasti outsourcingu IT, specializuje se na cloudové služby a hosting informačních systémů klientů. Na své IT infrastruktuře provozuje informační systémy klientů. Rozsah služeb poskytovaných klientům kolísá od hostování a správy jednotlivých aplikací po hosting kompletní aplikační infrastruktury klienta včetně poštovních, databázových a souborových serverů. Navrhovaný informační systém bude jedním z modulů informačního systému společnosti, který je nyní vyvíjen interním vývojovým oddělením. Agenda správy požadavků, kterou navrhovaný modul řeší, je v současné době řešena v komerčním systému dodávaném jedním z partnerů společnosti.

ZADÁNÍ PŘÍPADOVÉ STUDIE

MODULY ANALYZOVANÉHO INFORMAČNÍHO SYSTÉMU • • • •

modul pro správu životního cyklu požadavků; modul pro správu SLA katalogu; modul pro správu řešitelů; modul výkaznictví.

CÍL ANALÝZY • detailně analyzovat a navrhnout modul pro správu životního cyklu požadavku; • analyzovat návaznosti na ostatní moduly systému; • navrhnout strukturu uložení dat; • zajistit normalizaci datových struktur do 3-tí normální formy.

POSTUP ŘEŠENÍ – první fáze (funkční analýza)

• analýza podstatného okolí systému (vymezení všech terminátorů a všech datových toků, jimiž systém komunikuje s okolím); • konstrukce kontextového diagramu; • rozdělení systému do základních funkčních modulů; • konstrukce 1-ní úrovně DFD; • detailní analýza životního cyklu požadavku; • konstrukce nejnižší úrovně DFD; • dle potřeby začlenit meziúroveň DFD kvůli zvýšení přehlednosti diagramů; • kontrola všech funkčních diagramů podle pravidel konzistence požadovaných u DFD; • detailní analýza procesů nejnižší úrovně; • zápis minispecifikací.

POSTUP ŘEŠENÍ – druhá fáze (datová analýza)

• analýza hrubé datové struktury; • normalizace dat do 3-tí NF, konstrukce hrubého entitně relačního diagramu; • detailní návrh jednotlivých atributů včetně návrhu zajištění referenční integrity a business pravidel; • konstrukce detailního ERD; • konstrukce datového slovníků – popis tabulek, klíčů, atributů; • konstrukce datového slovníků – popis datových toků.

POZNÁMKA: • první a druhou fázi analýzy IS je možné provádět dle potřeby paralelně anebo v opačném pořadí; • Spolu s rozkladem do detailnějších pohledů se doporučuje zapisovat názvy všech užitých datových toků/prvků a průběžně kontrolovat názvosloví.

POSTUP ŘEŠENÍ – třetí fáze (zajištění konzistence)

• kontrola konzistence mezi datovou analýzou (ERD) a funkční analýzou (DFD) s využitím datového slovníku (DD); • kontrole podléhají rovněž minispecifikace ve vztahu k datovému slovníku; • úprava případných nesrovnalostí; • závěrečná kontrola/úprava všech diagramů.

KONTEXTOVÝ DIAGRAM …………. VYMEZENÍ OKOLÍ SYSTÉMU 0-tá úroveň rozkladu

Zpracováno v CASE Studiu 2

POPIS TERMINÁTORŮ Zadavatel - osoba, která požádá společnost o provedení nějaké činnosti, většinou pomoc při řešení nějakého problému. Obvykle jde o zaměstnance společnosti George Engineering, zaměstnance zákazníka společnosti či partnera zákazníka. • zadání požadavků • přístup k informacím o stavu řešení požadavku • na vyžádání doplnění informací nutných k řešení požadavku • akceptace řešení • na vyžádání autorizace zadání zadavatele Účetní • získání podkladů pro fakturaci za uplynulé fakturační období Řešitel - osoby přímo se podílející na řešení jednotlivých požadavků, v rámci technického týmu jednotliví technici, v rámci vývojového oddělení analytici, architekti řešení a vývojáři, v rámci obchodního oddělení jednotliví obchodníci a podobně. • záznamy o postupu řešení požadavku • přesun požadavku na vyšší úroveň podpory • vkládání výkazů práce • žádosti o doplnění informací zadavatelem • žádost o konzultaci a poskytování konzultací ostatním řešitelům

POPIS TERMINÁTORŮ

Supervizor - člen řešitelského týmu oprávněný v případě potřeby zasáhnout do standardního průběhu požadavku firmou. • přidělení požadavků „mimo pořadí“ • změna parametrů požadavků (priorita, stav, řešitel) • převod požadavku na jiný útvar Vedení • kontrola stavu požadavků, událostí a prací • vytváření reportů výkazů práce Ostatní moduly informačního systému společnosti Navrhovaný informační systém sdílí některá data s ostatními systémy společnosti. Z nich čerpá informace o firmách zákazníků a jejich kontaktních osobách, řešitelích požadavků a odděleních společnosti.

CELKOVÝ POHLED NA SYSTÉM - DFD

1-ní úroveň rozkladu


U každého požadavku jsou zaznamenávány události:

• automaticky generované události – automaticky jsou zaznamenávány všechny změny stavu požadavku, změny řešitele apod.; • dodatečná komunikace se zadavatelem – záznamy o proběhlé komunikaci či přímo kopie komunikace mezi techniky a zadavatelem; • interní komunikace týkající se požadavku; • informace o provedené práci - výkazy práce s uvedeným počátkem a koncem práce, celkovou dobou trvání a časem pro fakturaci (čas pro fakturaci klientovi se může lišit od celkové doby práce v případě, že doba řešení požadavku nepřesáhne minimální fakturovanou dobu nebo v případě, kdy problém byl způsoben (zcela nebo zčásti) chybou, jejíž odstranění musí společnost zajistit na své náklady).

ŽIVOTNÍ CYKLUS POŽADAVKU START

PŘÍJEM POŽADAVKU

PŘIDĚLENÍ TECHNIKOVI

ZPRACOVÁNÍ POŽADAVKU

UKONČENÍ POŽADAVKU

AKCEPTACE ŘEŠENÍ

KONEC

ŽIVOTNÍ CYKLUS POŽADAVKU - DFD 2-há úroveň rozkladu


PŘÍJEM POŽADAVKU – STANDARDNÍ POSTUP Pracovník helpdesku příjme telefonicky nebo elektronickou poštou požadavek zákazníka. Zkontroluje, jestli je zadavatel oprávněn požadavky zadávat. Ověření sestává ze 3 kroků: • kontrola firmy – je v DB zákazníků? • kontrola firmy – není na blacklistu? • kontrola osoby – je osoba oprávněna zadávat požadavky jménem příslušné firmy? Při neúspěšné kontrole je předána zamítavá odpověď s určením důvodu nepřijetí. Při úspěšné kontrole zapíše pracovník helpdesku základní údaje o požadavku (firma, osoba, název požadavku, popis problému) do IS. Poté ze SLA katalogu určí SLA kategorii, podle které doplní nejzazší termín dokončení požadavku. Zákazníkovi je předána informace o přijetí požadavku a nejzazším termínu dokončení. Stav požadavku je nastaven na „Přijatý“.

PŘÍJEM POŽADAVKU – NESTANDARDNÍ POSTUP

• požadavek automaticky vygenerovaný na základě časové události ze seznamu naplánovaných požadavků; • interní požadavek – může zadat jakýkoliv zaměstnanec společnosti, požadavek je pak považován za autorizovaný; • do budoucna přibude možnost generování požadavků klientem přes webové rozhraní helpdesku. Vzhledem k nutnosti přihlášení, které budou mít možnost provést pouze autorizované osoby, budou takto zadané požadavky považovány automaticky za autorizované.

PŘÍJEM POŽADAVKU - DFD 3-tí úroveň rozkladu



Při prvním zpracování řešitel mění stav požadavku na „Rozpracovaný“ a dále mohou nastat následující situace:

 řešitel požadavek vyřeší – v tom případě ho označí jako „Vyřešený;“  řešitel si vyžadá od zadavatele doplňující informace nutné k řešení požadavku – v takovém případě je požadavek označen jako „Odložený“ a na dobu, dokud nejsou informace doplněny, je přerušena doba pro plnění SLA. Zákazník je o přerušení práce na požadavku informován elektronickou poštou;  řešitel si vyžádá pomoc vyššího stupně technické podpory – požadavek je předán zpět do zásobníku a změní se u něj požadavek na stupeň podpory. Požadavek je následně automaticky předán řešiteli vyššího stupně podpory. Mění se odpovědný řešitel i aktuální řešitel;


 řešitel si vyžádá konzultaci konkrétního člena řešitelského týmu. V takovém případě přímo změní aktuálního řešitele. Po skončení konzultace druhý řešitel zapíše výkaz práce a vrací ho zpět. Po dobu konzultace se stav požadavku mění na „konzultace;“  řešitel přeruší práci na řešení požadavku kvůli čekání na jinou událost (dokončení běžící úlohy, konzultace se subdodavatelem apod.) – v takovém případě požadavek označí jako „Čekající;“  řešitel v rámci řešení požadavku zjistí, že požadavek nelze splnit (např. v případě, že omezená funkčnost služby je způsobená třetí stranou (nefunkční připojení k internetu na straně zadavatele apod), zákazník nemá potřebné licence SW apod.) – v tom případě požadavek označí jako „Nevyřešený.“

ZPRACOVÁNÍ POŽADAVKU - DFD 3-tí úroveň rozkladu


UKONČENÍ POŽADAVKU

K ukončení prací na řešení požadavku dochází v následujících případech: • požadavek je řešitelem označen jako „Vyřešený“ nebo „Nevyřešený.“ • dojde ke zrušení požadavku ze strany zákazníka. Požadavek je označen jako „Stornovaný.“ • požadavek je ve stavu „Odložený“ a čeká na doplňující informace od klienta po dobu delší než je trojnásobek doby pro vyřešení požadavku dle SLA. V takovém případě je označen jako „Stornovaný.“ • Ve všech těchto případech je zadavateli odeslána zpráva o ukončení práce na požadavku a žádost o akceptaci řešení. Zpráva obsahuje informace o době odpracované při řešení požadavku a v případě požadavku „Nevyřešeného“ doporučení dalšího postupu klienta pro řešení problému. • Po odeslání zprávy je požadavek označen jako „Dokončený.“

AKCEPTACE POŽADAVKU Součástí zprávy o ukončení práce na požadavku odeslané zadavateli je žádost o akceptaci řešení. Pokud zadavatel neodpoví do 3 pracovních dnů, je požadavek považován za „Akceptovaný.“ • V případě, že zadavatel odpoví a akceptuje přijaté řešení, označí pracovník helpdesku, který odpovědi přijímá, požadavek jako „Akceptovaný.“ • Pokud zadavatel odmítne zvolené řešení a informuje o tom technickou podporu poté, kdy byl požadavek označen jako „Akceptovaný,“ je vytvořen nový požadavek a začíná znovu běžet lhůta pro vyřešení požadavku dle SLA. • V případě, že zadavatel nesouhlasí se zvoleným řešením požadavku a své stanovisko předá před tím, než je požadavek označen za akceptovaný, je požadavek označen jako „Reklamace“ a předán supervizorovi. Lhůta pro vyřešení požadavku dle SLA pokračuje dále, do celkové doby řešení požadavku se nezapočítává doba, od okamžiku, kdy byla zadavateli odeslána informace o vyřešení požadavku do okamžiku, kdy byla doručena na helpdesk informace o odmítnutí řešení. • Supervizor zkontroluje zvolené řešení a důvod pro jeho odmítnutí. V případě, že identifikuje chybu v řešení požadavku, předá ho zpět řešiteli, který požadavek zpracovával, k dořešení. Pokud v řešení chybu neidentifikuje, předá ho řešiteli na vyšším stupni podpory pro určení jiného způsobu řešení.

DFD ……………………………………. UKONČENÍ POŽADAVKU 3-tí úroveň rozkladu


DFD ……………………………….... UKONČENÍ POŽADAVKU 2-há úroveň rozkladu


PRŮBĚH POŽADAVKU

Minispecifikace procesu 1.1.2.2 Práce na požadavku

• Proces po přihlášení řešitele načte z paměti Pozadavky všechny požadavky, kde přihlášený řešitel vystupuje jako aktuální řešitel. Seřadí je podle priority a seznam předá řešiteli. • Poté, co řešitel vybere konkrétní požadavek z dodaného seznamu, načte události týkající se požadavku z paměti Udalosti a předá je řešiteli. • Po dokončení práce řešitel předá procesu informace o provedné práci spolu s informacemi o novém stavu požadavku, případně upřesňujícími informacemi pro další činnosti. • Proces zapíše informace o provedených pracech do pamětí Udalosti a VykazyPrace a dále postupuje podle určeného nového stavu požadavku. • V případě, že nový stav je „Vyřešený“ nebo „Nevyřešený“, zapíše změnu stavu do paměti Pozadavky, informace o události do paměti Udalosti (informace o změně stavu a detaily k řešení, případně důvod, proč nebyl požadavek vyřešen), vymaže aktuálního řešitele a předá požadavek k ukončení procesu Ukonceni pozadavku. • Pokud je nový stav „Konzultace“, provede v paměti Pozadavky změnu stavu požadavku a aktuálního řešitele na osobu, s kterou bude stávající řešitel konzultovat, a do paměti Udalosti zapíše záznam o provedené změně stavu s komentářem ke konzultaci.

Minispecifikace procesu 1.1.2.2 Práce na požadavku

• V případě, že nový stav je LevelUp, provede proces výmaz aktuálního řešitele i odpovědného řešitele v paměti Pozadavky a zároveň zvýší úroveň podpory potřebnou pro řešení požadavku o jeden stupeň. Tím se požadavek přesune do fronty nepřidělených požadavků a při nejbližší příležitosti bude přidělen řešiteli zajišťujícímu vyšší úroveň podpory. Nakonec proces provede záznam o provedené akci do paměti Udalosti. • Pokud je nový stav „Odložený“, je požadavek předán procesu Doplneni informaci, který na základě předaných informací zajistí žádost zadavateli o dodání doplňujících informací a po jejich dodání přepočítá termín řešení. • Pokud je nový stav „Čeká“, provede proces pouze změnu stavu v paměti Pozadavky a záznam o provedené změně do tabulky Udalosti. • V případě, že všechny požadavky řešitele jsou ve stavu „Čeká“, je odeslána žádost o přidělení nového požadavku procesu Prideleni pozadavku resiteli. • Občas se stane, že zadavatel zruší požadavek v průběhu jeho zpracování. V takovém případě proces načte od řešitele informace o právě prováděné činnosti, zapíše je do pamětí Udalosti a VykazyPrace, změní stav požadavku na „Stornovaný“, vymaže aktuálního řešitele a po zápisu informací o provedené akci do paměti Udalosti ho předá k ukončení procesu Ukonceni pozadavku.

Minispecifikace procesu 1.1.2.2 Práce na požadavku FOR EVERY resitel DO "načti vsechny POZ – pozadavek z Pozadavky , kde aktualni resitel = prihlaseny resitel" "serad podle priority" "pošli seznam pozadavku do Resitel " "načti vybrany pozadavek od Resitel" "načti vsechny UD – udalost, kde UDA_pozadavek = vybrany pozadavek" "pošli detail pozadavku do Resitel" "načti pozadavek - aktivita od Resitel" "zapiš UD - udalost do Udalosti (vykaz prace)" "zapiš VYK – vykaz prace do Vykazy prace" DO CASE { POZ_novystav = Vyreseny { "zapiš POZ – zmena stavu do Pozadavky (Vyřešený)" "zapiš POZ – zmena osob do Pozadavky (vymaz aktualni resitel)" "zapiš UD - udalost do Udalosti (zmena stavu)" "pošli predani k ukončení do Ukonceni pozadavku" } POZ_novystav = Konzultace { "zapiš POZ – zmena stavu do Pozadavky (Konzultace)" "zapiš POZ – zmena osob do Pozadavky (aktualni resitel -> OSO_new)" "zapiš UD - udalost do Udalosti (zmena stavu)" } POZ_novystav = Odlozeny { "pošli predani k doplneni do Doplneni informaci" } POZ_novystav = LevelUp { "zapiš POZ – zmena stavu do Pozadavky (LevelUp)" "zapiš POZ – zmena osob do Pozadavky (vymaz aktualni resitel)"

Minispecifikace procesu 1.1.2.2 Práce na požadavku "zapiš POZ – zmena stupne podpory do Pozadavky (uroven + 1)" "zapiš UD - udalost do Udalosti (LevelUp, zmena stavu)" } POZ_novystav = Ceka { "zapiš POZ – zmena stavu do Pozadavky (Čeká)" "zapiš UD - udalost do Udalosti (zmena stavu)" } POZ_novystav = Nevyreseny { "zapiš POZ – zmena stavu do Pozadavky (Nevyřešený)" "zapiš POZ – zmena osob do Pozadavky (výmaz aktualni resitel)" "zapiš UD - udalost do Udalosti (zmena stavu)" "pošli predani k ukonceni do Ukonceni pozadavku" } } IF vsechny pozadavky resitele vykazuji stav "Čeká" THEN {"pošli zadost o prirazeni pozadavku procesu Prideleni pozadavku resiteli"} ELSE nic } FOR EVERY zruseni pozadavku DO { "načti pozadavek – aktivita od Resitel" "zapiš UD - udalost do Udalosti (vykaz prace)" "zapiš VYK – vykaz prace do Vykazy prace" "zapiš POZ – zmena stavu do Pozadavky (Storno)" "zapiš POZ – zmena osob do Pozadavky (výmaz aktualni resitel)" "zapiš UD - udalost do Udalosti (zmena stavu)" "pošli predani k ukonceni do Ukonceni pozadavku" }

RELAČNÍ DATOVÝ MODEL

RDM … tabulka Pozadavek

Tabulka Pozadavek je propojena s dalšími tabulkami. Obsahuje základní informace o samotném požadavku zákazníka, stavu jeho řešení a nejdůležitějších termínech.

Pozadavek POZ_ID

Celé číslo

POZ_cislo

Text (9)

POZ_nazev

Text (128)

POZ_popis

Text (4096)

POZ_priorita

Celé číslo

POZ_start

Datum a čas

POZ_termin

Datum a čas

POZ_cyklicky

Bit

POZ_cyklus

integer

FK

SLS_ID

Celé číslo

FK

SPO_ID

Celé číslo

FK

STP_ID

Celé číslo

FK

FIR_ID

Celé číslo

PK

RDM … definice tabulky Pozadavek

• atribut POZ_ID – primární klíč tabulky, automatické číslo generované systémem • atribut POZ_cislo – číslo požadavku používané při komunikaci o požadavku, jedinečný řetězec ve tvaru POZ###### (POZ + 6 číslic) • atribut POZ_nazev – krátký název požadavku vystihující řešený problém • atribut POZ popis – úplný text zadání požadavku • atribut POZ_priorita – číslo od 1 do 10. Určuje pořadí řešení jednotlivých požadavků. Priorita se automaticky zvyšuje, jak se blíží termín řešení požadavku. Kromě toho může být „manuálně“ změněna supervizorem. • atribut POZ_start – termín zahájení řešení požadavku, používá se u požadavků s odloženým startem (dlouhodobě plánovaných nebo periodických) • atribut POZ_termin – termín dokončení řešení požadavku podle smlouvy se zákazníkem. Je určen termínem přijetí požadavku a úrovní SLA služby, které se týká

RDM … definice tabulky Pozadavek

• atribut POZ_cyklicky – určuje, zda po dokončení požadavku bude okamžitě vygenerován nový požadavek se stejným zadáním s odloženým startem. • atribut POZ_cyklus – určuje délku cyklu v dnech pro cyklické požadavky. • atribut SLS_ID – primární klíč tabulky Sluzba. Zajišťuje vazbu na službu z katalogu služeb, které se požadavek týká a tím určuje úroveň SLA a tedy termíny, lteré je potřeba při řešení dodržet • atribut SPO_ID – primární klíč tabulky Stav_pozadavku – číselníku stavů, kterých může požadavek během řešení nabývat • atribut STP_ID – primární klíč tabulky Stupen_podpory – určuje aktuální požadavky na úroveň znalostí řešitele požadavku. • atribut FIR_ID – primární klíč tabulky Firma. Odkazuje na zákazníka, pro kterého je požadavek zpracováván.

RDM … definice tabulky Stav_pozadavku

Tato tabulka obsahuje číselník stavů, kterými může požadavek během svého řešení procházet.

Stav_pozadavku PK SPO_ID SPO_stav

Celé číslo Text (16)

SPO_popis

Text (128)

Jedinečný, nenulový jedinečný

• atribut SPO_ID – primární klíč, automatické číslo generované systémem • atribut SPO_stav – názvy jednotlivých stavů požadavku. • atribut SPO_popis – krátký popis, co stav znamená, v jaké situaci k němu dochází

RDM … definice tabulky Vazba_Poz_Oso

Jde o vazební tabulku řešící vztah M:N mezi tabulkami Pozadavek a Osoba. Vazba_Poz_Oso PFK

POZ_ID

Celé číslo

nenulový

PFK

VPO_ID

Celé číslo

nenulový

FK

OSO_ID

Celé číslo

nenulový

Primární klíč této tabulky je tvořen dvěma cizími klíči – primárními klíči tabulek Pozadavek a Typ_Vazba_Poz_Oso, což je číselník rolí osob, které jsou u požadavku evidovány (zadavatel, aktuální a odpovědný řešitel, autorizovaná osoba zákazníka). Poslední atribut odkazuje na konkrétní osobu z tabulky Osoba.

DATOVÝ SLOVNÍK - datové toky k procesu Práce na požadavku

datový tok: SEZNAM POZADAVKU = { POZ_cislo + POZ_nazev + POZ_popis + POZ_priorita + POZ_termin + POZ_stav } popis: seznam požadavků technika datový tok: VYBRANY POZADAVEK = POZ_cislo popis: požadavek vybraný ke zpracování ze seznamu požadavků technika datový tok: DETAIL POZADAVKU = POZ_cislo + POZ_nazev + POZ_popis + POZ_priorita + POZ_termin + POZ_stav + { UD udalost} popis: detail požadavku vybraného ke zpracování včetně informací o předchozích událostech vázaných k požadavku datový tok: UD - UDALOST = UDA_nazev + UDA_popis + UDA_casudalosti + UDA_caszapsani + UDA_pozadavek + UDA_osoba + UDA_typudalosti popis: komplet záznam do/z paměti Udalosti

DATOVÝ SLOVNÍK - datové sklady k procesu Práce na požadavku

paměť: Pozadavky = @POZ_ID + POZ_cislo + POZ_nazev + POZ_popis + POZ_start + POZ_priorita + POZ_termin + POZ_firma + POZ_stupenpodpory + POZ_stav + POZ_zadavatel + POZ_sluzba + POZ_cyklicky + POZ_autorizoval + POZ_odporesitel + POZ_aktualresitel popis: paměť pro uložení základních informací o požadavku, v ERD odpovídají tabulky Pozadavek, Vazba_Poz_Oso, Stav_pozadavku paměť: Udalosti = @UDA_ID + UDA_nazev + UDA_popis + UDA_casudalosti + UDA_caszapsani + UDA_pozadavek + UDA_osoba + UDA_typudalosti popis: paměť pro uložení událostí vázaných k požadavkům nebo výkazům práce mimo požadavky. V ERD odpovídá tabulka Udalost a Typ_udalosti

DATOVÝ SLOVNÍK - datové prvky k procesu Práce na požadavku Datový prvek POZ_aktualresitel, typ: C, délka 8 popis: identifikace aktuálního řešitele Struktura: {[abeceda|cislice]} Datový prvek POZ_autorizoval, typ: C, délka 8 popis: identifikace osoby, která požadavek autorizovala Struktura: {[abeceda|cislice]} Datový prvek POZ_cas_autorizace, typ: D popis: čas autorizace požadavku pro výpočet termínu řešení Struktura: [datum a čas] Datový prvek POZ_cislo, typ: C, délka 9 popis: číslo požadavku Struktura: "POZ"+ {[cislice]}

Datový prvek POZ_firma, typ: C, délka 16 popis: zkrácený název firmy Struktura: {[abeceda|cislice]} Datový prvek POZ_nazev, typ: C, délka 128 popis: název požadavku Struktura: {[abeceda|cislice|specialni_znaky]} Datový prvek POZ_odporesitel, typ: C, délka 8 popis: identifikace osoby odpovědného řešitele Struktura: {[abeceda|cislice]}

pouze část datových prvků

ZÁKLADNÍ ALGORITMY Z TEORIE GRAFU literatura Systémová analýza. VŠB-TU Ostrava. Fakulta hornicko-geologická. Dostupné online: < http://rubin.vsb.cz/course/view.php?id=39 > Teorie grafu. Dostupné online: < http://teorie-grafu.cz/ > Hliněný, P.: Základy teorie grafu. Masyrykova univerzita, Fakulta informatiky. Dostupné online: < http://is.muni.cz/do/1499/el/estud/fi/js10/grafy/Grafy-text10.pdf > Teorie grafu. Matematika pro inženýry 21. století. Dostupné online: < http://mi21.vsb.cz/modul/teorie-grafu > Šeda, M.: Teorie grafu. VUT Brno, Fakulta strojního inženýrství. Dostupné online: < http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf >

PREZENTACE GRAFU ve formě matic Grafy je možné jednoznačně popsat algebraicky v maticové formě. Tento popis je nutný pro početní operace na grafech. Mějme graf G = (U, H, R) s množinou uzlů U = {u1, u2, ….,um} a množinou hran H = {h1, h2, …., hn}. • Incidenční matice Incidenční matice udává vztah mezi uzly a hranami grafu, a to ve smyslu zda hrana s uzlem inciduje či nikoliv. • Matice sousednosti Matice sousednosti popisuje provázanost vrcholů hranami, a to ve smyslu počtu hran. Maticí sousednosti rozumíme čtvercovou matici S = [sij] typu (m,m), jejíž prvek sij je roven počtu hran spojující uzly ui, uj.

INCIDENČNÍ MATICE Incidenční maticí rozumíme matici A = [aij] typu (m,n) pro kterou platí: a) u neorientovaného grafu Je-li prvek aij = 1, pak hrana s uzlem grafu inciduje, Je-li prvek aij = 0, pak hrana s uzlem grafu neinciduje. b) u orientovaného grafu Vstupní uzel incidence = 1 Koncový uzel incidence = -1

V incidenční matici vždy jeden sloupec odpovídá jedné hraně, proto v 1 sloupci musíme mít právě dvě 1 u neorientovaného grafu, anebo jedenkrát +1 a jedenkrát -1 u grafu orientovaného.

INCIDENČNÍ MATICE … graf neorientovaný k-tá hrana

i-tý prvek

VAZBY Index i

yk

UZLY Index j Xi

1

j-tý prvek

Xj

1

vazba mezi prvkem i a prvkem j

INCIDENČNÍ MATICE … graf orientovaný k-tá hrana

i-tý prvek

VAZBY Index i

yk

UZLY Index j Xi

+1

j-tý prvek

Xj

-1

vazba z prvku i do prvku j

MATICE SOUSEDNOSTI

Matice sousednosti je čtvercová matice, jednotlivé řádky a sloupce odpovídají jednotlivým uzlům v grafu. Její prvky sij jsou dány předpisem: a) u neorientovaného grafu sij = 1, jestliže uzly ui a uj jsou sousední sij = 0, jestliže uzly ui a uj nejsou sousední b) u orientovaného grafu sij = n, jestliže je hrana z uzlu ui do uzlu uj, kde n je roven počtu hran sij = 0, jestliže není hrana z uzlu ui do uzlu uj

MATICE SOUSEDNOSTI Xi

Index j

Index i

i-tý prvek

j-tý prvek

vazba mezi prvkem i a prvkem j Xj

y ji

Matice sousednosti popisuje, které prvky spolu sousedí Obsahuje pouze 0 a 1 (číslo větší než 1 indikuje násobnou vazbu) 1 … vazba existuje 0 … vazba neexistuje (0 často vynecháváme kvůli přehlednosti)

MATICE SOUSEDNOSTI neorientovaný graf Xi

Xi

Xj

1 1

1

1

1

vazba mezi prvkem j a prvkem i

vazba mezi prvkem i a prvkem j

1 1 Xj

1

1

1

Neorientovaný graf má vždy matici sousednosti souměrnou podle hlavní diagonály, protože každá vazba se v ní zobrazí 2x

MATICE SOUSEDNOSTI orientovaný graf Xi

0 0 0 0 0 nulový řádek 0 indikuje 0 koncový prvek 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

1 na diagonále indikuje smyčku

1 pod hlavní diagonálou indikuje zpětnou vazbu Xj

nulový sloupec indikuje počáteční prvek

Zpětná vazba vždy představuje nebezpečí zacyklení a je nutno ji prověřit. Zpětná vazba v matici existuje pouze tehdy, pokud se žádnou matematicou úpravou neumíme 1 pod hlavní diagonálou zbavit.

MATICE SOUSEDNOSTI orientovaný graf S1

Xi

Řádková suma ukazuje počet hran vedoucích z prvku x j

1-ní mocnina matice sousednosti zobrazuje Xj 0 0 0 0 0 1 0 1 1 0 0 1 4 jednohranové cesty

Celková suma řádkových sum ukazuje celkový počet hran v systému

1 0 0 5 2 0 0 12

Složitost systému = suma prvků + suma hran + suma cest


B

2-há mocnina matice sousednosti zobrazuje Xj dvouhranové cesty

2

A

Z

A

B X

Dvě dvouhranové cesty z prvku A do prvku B


R

následníci prvku x j třetí generace jsou v řádku

Xj 0 0 0 0 0 1 0 1 1 0 0 1 4

4

A

C

Z

A

R X

B

následníci prvku x j třetí generace jsou celkem 4

z prvku A do prvku R se lze dostat čtyřmi trojhranovými cestami


A

R

následníci prvku A třetí generace

2 0 3 1 0 0 0 0 0 1 0 1 1 0 0 1 4 0 4 předchůdci 0 prvku R třetí 0 generace 0 0 0

MATICE SOUSEDNOSTI předchůdci a následníci Předchůdci - jsou prvky systému, které mohou představovat možný zdroj poruch v systému. Ovlivňují svým působením následující prvky. Míra vlivu souvisí s číslem generací konkrétních předchůdců. Čím vyšší číslo generace, tím víc bude vliv předchůdců slábnout. Speciálním případem při hledání předchůdců je nalezení hraničních prvků – vstupní prvky systému. • Např. ve větrné síti hlubinného dolu lze identifikovat možné zdroje výronu metanu při identifikaci zvýšené koncentrace metanu v určitém uzlu. Následníci - jsou prvky systému, které jsou ovlivňovány, řízeny daným prvkem, jsou na něm závislé, mohou být postiženy jeho poruchou. Míra postižení je dána číslem generace následníka. • Např. u distribuční sítě pitné vody lze identifikovat, do kterých uzlů se bude šířit znečištění při poruše v daném uzlu.

MATICE SOUSEDNOSTI

D

J

J

B E

A

H C

F I

Systém obsahuje celkem:

3 ZPĚTNÉ VAZBY 14 HRAN 10 PRVKŮ 0 SMYČEK

MATICE SOUSEDNOSTI D

G

J

B E

A

H C

F I

z prvku F se lze dostat do prvku H celkem 2 různými dvouhranovými cestami

Složitost systému = 10+14+ 14+17+16+11+4 = 86 Nejdelší cesta má délku 65 hran

Matice sousednosti různých mocnin

ÚLOHA O CESTÁCH V úlohách o cestách v systému se studují cesty mezi prvky systémů a vyšetřují se jejich vlastnosti, např. délka cest, jejich počet, apod. Řešení těchto úloh má význam zejména pro poznání souvislostí v systémech, pro posuzování složitosti a vlastností systémů a pro hodnocení různých alternativních struktur systémů. Cesta je tah, v němž se každý uzel vyskytuje nejvýše jednou. Jinak řečeno cesta je sled, v němž se žádná hrana ani uzel nevyskytuje více než jednou. Délku cesty uvažujeme jako počet hran. Mezi úlohy o cestách patří zejména: • nalezení všech cest v systému, příp. mezi dvěma prvky systému • nalezení nejkratší (nejdelší) cesty • výpočet složitosti systému • zjištění počtu n-hranových cest mezi dvěma prvky systému • předchůdci a následovníci • vyhledání trasy cest mezi dvěma prvky systému

ZPĚTNÝ ALGORITMUS

K vyhledání trasy cest mezi dvěma prvky systému existují dva typy algoritmů lišících se směrem postupu: • dopředný algoritmus • zpětný algoritmus Zde si popíšeme zpětný algoritmus, který se užívá např. k prohledávání stavového prostoru v umělé inteligenci. Umožní nám vyhledat všechny trasy z jednoho předem určeného prvku do jiného určeného prvku o zadané délce trasy (délka je zde chápána jako počet hran).

ZPĚTNÝ ALGORITMUS – zadání úlohy D

G

B E

A

H C

F I

ZADÁNÍ ÚLOHY: Najděte pomocí matic sousednosti všechny 5-ti hranové cesty z prvku A do prvku J

J Tyto cesty jsou celkem 4

ZPĚTNÝ ALGORITMUS

A

?

?

?

?

prvky G; H

prvky G; H; J

A

J

?

?

?

G

J průnik v prvcích G; H

A

?

?

?

H

J

ZPĚTNÝ ALGORITMUS

A

?

?

?

G

J prvky D

prvky D;E;G; H; I

průnik v prvku D

A

?

?

D

G

J

ZPĚTNÝ ALGORITMUS

A

?

?

D

G

J prvky B

prvky B;D;E;F

průnik v prvku B

A

?

B

D

G

J

ZPĚTNÝ ALGORITMUS

A

?

B

prvky B;C

D

G

J

prvky A;C

Cesta č.1 průnik v prvku C

A

C

B

D

G

J

ZPĚTNÝ ALGORITMUS

A

?

?

?

H

J prvky E;F;I

prvky D;E;G; H; I

průnik v prvcích E;I

A

?

?

E

H

J

A

?

?

I

H

J

ZPĚTNÝ ALGORITMUS

A

?

?

E

H

J prvky B;F

prvky B;D;E;F

průnik v prvcích B;F

A

?

B

E

H

J

A

?

F

E

H

J

ZPĚTNÝ ALGORITMUS

A

?

B

prvky B;C

E

H

J

prvky A;C


A

C

B

E

H

J

ZPĚTNÝ ALGORITMUS

A

?

F

prvky B;C

E

H

J

prvky C


A

C

F

E

H

J

ZPĚTNÝ ALGORITMUS

A

?

?

I

H

J prvky F

prvky B;D;E;F

průnik v prvku F

A

?

F

I

H

J

ZPĚTNÝ ALGORITMUS

A

?

F

prvky B;C

I

H

J

prvky C


A

C

F

I

H

J

ZPĚTNÝ ALGORITMUS - výsledek

A

C

B

D

G

J

A

C

B

E

H

J

A

C

F

I

H

J

A

C

F

E

H

J

D

G J

B E

A

H C

F I

celkem čtyři 5-ti hranové cesty z prvku A do prvku J

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH Jedná se o zjištění minimální (nejkratší) vzdálenosti z počátečního uzlu do všech ostatních uzlů. Algoritmus se liší podle toho, jedná-li se o graf: • ohodnocený • neohodnocený, • orientovaný • neorientovaný. Využití je ve všech úlohách, kde je cílem nalézt nejkratší cestu z uzlu A do uzlu B. Součástí zadání je struktura grafu včetně hodnotícího kritéria a vyjasnění, který z uzlů budeme brát jako počátek cesty. U ohodnoceného grafu je minimální cesta uvažována z hlediska hodnoty kritéria (např. čas potřebný k překonání vzdálenosti, spotřeba nafty, převýšení, náklady …)

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf neohodnocený a neorientovaný

V této jednodušší úloze je nejkratší vzdálenost hápána jako minimální počet hran (kroků), ležících mezi uzlem 1 a uzlem i. Algoritmus: 1) výchozí uzel ohodnoť vzdáleností d1 = 0 (vzdálenost uzlu sama od sebe) 2) i = 0 3) vyhledej všechny hrany, jejichž jeden koncový uzel je ohodnocen hodnotou i a druhý ještě není ohodnocen; pokud taková hrana neexistuje, pak konec algoritmu 4) i = i + 1 5) přiřaď k neohodnoceným uzlům hran zjištěných v kroku 3) hodnotu i 6) návrt na krok 3)


Máme systém znázorněný jednoduchým, konečným a souvislým grafem s jedním výchozím uzlem. Hodnota každé hrany je 1 měrná jednotka.


2

3

1

4

2

0

3 1

4

2

3 5 Nejdelší cesta v systému (vzhledem k zadanému počátku) má 5 hran. Délka cesty je uvedena v přímo v uzlech.

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný Pro ohodnocený graf používáme dvoustupňový algoritmus, ve kterém je úvodní fáze prakticky totožná jako u neohodnoceného jenom s tím rozdílem, že místo jednotek sčítáme skutečné délky hran. Tím získáme tzv. dočasné ohodnocení. Druhá fáze vede k postupné minimalizaci ohodnocení a tedy konečnému ohodnocení. Algoritmus pak vypadá takto: Dočasné ohodnocení 1) d1 = 0 2) vyhledej všechny hrany, jejichž jeden koncový uzel je ohodnocen a druhý nikoliv, pokud taková hrana již existuje, pokračuj krokem 5) 3) u každého neohodnoceného následníka uj, spojeného s ohodnoceným předchůdcem ui hranou hm  H, proveď dj = di + fm (fm – délka hrany) , 4) návrat na krok 2);

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný Konečné ohodnocení 5) vyhledej hranu hm spojující uzly ui, uj , pro kterou platí, di – dj > fm (rozdíl vzdálenosti je větší než ohodnocení hrany). Pokud taková hrana neexistuje, algoritmus končí. 6) pokud platí, že dj > di, potom vzdálenost dj spočítáme dj = di + fm (vzorec platí i opačně, tedy di = dj – fm) 7) návrat na krok 5). Technika iterace daná kroky 5) až 7) spočívá v postupném vyhledávání takových hran, pro které je rozdíl ohodnocení jejich koncových uzlů větší než délka hrany. V tom případě se zruší větší ohodnocení krajního uzlu hrany a nahradí se součtem ohodnocení uzlů v celém systému až v okamžiku, kdy ve struktuře hran není jediná, jejíž ohodnocení by splňovalo nerovnost danou krokem 5) algoritmu.

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný

2

3 8

2

1 4

10

6

2 1

2 2

1 6

5 5

Máme systém znázorněný jednoduchým, konečným, souvislým a ohodnoceným grafem s jedním výchozím uzlem. Hodnota každé hrany je 1 měrná jednotka.

3

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný

3

8

8

2

11

1

2

2 15

2

2

7

16

1 6

5 5 Toto je výsledek počáteční fáze (může se lišit u každého z vás)

23

1

2

4

10

6

9 0

13

3

12

19

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný |23-10|=13 > 1  opravuji 10+2=12 |9-13|=4 > 2  opravuji 9+2=11 |11-6|=5 > 3  opravuji 6+3=9 |2-8|=6 > 4  opravuji 2+4=6 3

8

8 6

11 9

1

4

2

7 7

2 15 9

16 10

1 6

5 5

Opravná fáze

23 12

1

2 2

2 2

13 11 10

6

9 7 0 0

2

3

12 12

19 13

|19-10|=9 > 3  opravuji 10+3=13

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a neorientovaný 3 8

6

9

1

2

12

2 9

2 5 5

Toto je celkový výsledek, vidíme minimální vzdálenosti jednotlivých uzlů od počátku

10

1

7

2

10

1

2

4

11

6

7 0

2

12

6 3 13

ÚLOHA O MINIMÁLNÍCH VZDÁLENOSTECH graf ohodnocený a orientovaný DANTZIGŮV ALGORITMUS

Podstata Dantzigova algoritmu spočívá v postupném hledání nejkratších cest z počátku do ostatních uzlů grafu v pořadí jejich rostoucí (nejkratší) délky až po nalezení nejkratší cesty do koncového uzlu. Rozlišujeme tzv. prozkoumané a neprozkoumané uzly, kde prozkoumané jsou ty, které jsou již jakoby připojené na cestě. Poznámka: Nemusíme jít přes všechny uzly!

DANTZIGŮV ALGORITMUS

Obecný krok Dantzigova algoritmu: Pro každý prozkoumaný uzel, který je

bezprostředním předchůdcem alespoň jednoho neprozkoumaného uzlu, vypočteme součet: a) známe nejkratší vzdálenosti prozkoumaného

uzlu; b) vzdálenosti prozkoumaného uzlu k jeho nejbližšímu neprozkoumanému následníku, provedeme součty a vybereme nejkratší z těchto součtů. Poznámka: Nesmíme se vracet zpět, tedy k uzlům, které jsme tzv. prozkoumali.


(A)+d(AB) 0+2 (A)+d(AE) 0+3 = min 2 = B (A)+d(AC) 0+4 Tj. uzel B je zřejmě nejbližší uzlu A.


2. krok: Prozkoumávané uzly jsou A,B; jejich bezprostřední neprozkoumaní Následníci jsou uzly E, C, D. Vypočteme minimum. (A)+d(AE) (A)+d(AC) (B)+d(BD)

0+3 0+4 = min 3 = E, D 2+1

Uzly E a D jsou další nejbližší k uzlu A.


3. krok: Prozkoumané uzly jsou A, B, D, E; jejich bezprostřední neprozkoumaní následníci jsou uzly C, F, G, H. (A)+d(AC) (D)+d(DG) (E)+d(EF) (E)+d(EH) (E)+d(EG)

0+4 3+5 3+1 = min 4 = C, F, H 3+1 3+2

Uzly C, F, H jsou další nejbližší k uzlu A.


4. krok: Prozkoumané uzly jsou nyní uzly A, B, C, D, E, F, H; jejich bezprostřední neprozkoumaní následníci jsou uzly G a I. (D)+d(DG) (E)+d(EG) (H)+d(HI) (H)+d(HG)

3+3 3+2 = min 5 = G 4+4 4+4

Uzel G je další nejbližší.


5. krok: Jediným neprozkoumaným uzlem je nyní uzel I. (G)+d(GI) 5+2 (H)+d(HI) 4+4 = min 7 = I Vzhledem k tomu, že se jedná o koncový uzel hledané nejkratší cesty, výpočet je tím ukončen. Posloupnost hran nalezení nejkratší cesty z A do I identifikujeme zpětným postupem od uzlu I prostudováním výsledků. Jedná se o cestu A g E g G g I.

ÚLOHA O MINIMÁLNÍ KOSTŘE

Úlohu o hledání minimální kostry grafu lze aplikovat na problém optimálního spojení míst u technických a ekonomických úloh, např. při hledání nejlevnějšího propojení dané oblast telefonním kabelem, dopravní sítě, elektrické sítě, plynovod, apod. Algoritmus hledání kostry grafu j využitelný např. v krizových situacích. Příkladem může být krizová situace, při níž dojde k částečnému nebo úplnému zneprůchodnění dopravních komunikací (sněhová kalamita, zasypání, zatopení apod.).

KOSTRA GRAFU

V každém souvislém hranově neorientovaném grafu G = (U,H,R) lze nalézt nejméně jeden jeho podgraf se stromovitou strukturou, který se označuje jako kostra grafu. Pro všechny kostry Gk  G přitom platí, že počet jejich vrcholů je stejný jako u grafu G, počet jejich hran je potom o jednotku menší než počet jejich vrcholů. Počet koster m úplného grafu G o n vrcholech, tj. takového, kde každé dva vrcholy jsou vzájemné propojeny hranou, se určí vzorcem: m = nn-2

n-počet vrcholů

KOSTRA GRAFU Toto je ÚPLNÝ GRAF spojení každý s každým

A

B

C

D

A

B

A

B

C

D

C

D

A

B

A

B

C

D

C

D

počet možných koster = nn-2 = 42 = 16

kostra je pokaždé jiná

KOSTRA GRAFU

Kostra má vždy strukturu stromu, tj. neobsahuje cykly.

Celkový přehled o všech možných kostrách pro úplný graf se čtyřmi uzly.

KOSTRA GRAFU

Každý neorientovaný graf, který představuje systém s oboustrannou vzájemnou interakcí sousedních prvků, obsahuje řadu koster i v případě, že není úplný. Vlastnost úplnosti grafu G bývá v praxi často nahrazena požadavkem jeho souvislosti. Např. při návrhu dopravní sítě není z technických důvodů možné přímé spojení mezi každými dvěma místy. Využití úlohy o minimální kostře je např. při hledání možného spojení mezi jednotlivými místy v obslužné síti.

původní graf (neúplný)

jedna z jeho možných koster

ÚLOHA O MINIMÁLNÍ KOSTŘE Otázka vyhledávání koster ve struktuře vazeb v systému má svůj význam, jestliže tyto systémové vazby jsou nějakým způsobem kvantifikovány a můžeme je tedy považovat za ohodnocené hrany. Z technických, či ekonomických důvodů můžeme požadovat vyhledávání takové sítě vazeb v systému, která nám zaručí: • vzájemnou dosažitelnost každých dvou prvků systému přímou, nebo zprostředkovanou vazbou; • minimalizaci součtu ohodnocení vyhledaných vazeb (hran).

Úloha vede na určení minimální kostry, tj. takové, pro kterou platí, že suma ohodnocení všech jejich hran je ze všech možných koster minimální. I tato minimální kostra musí být souvislá, v grafu systému nesmí vzniknout kružnice ani se vyskytovat izolované vrcholy.


Postup k nalezení minimální kostry: Je dán neorientovaný graf G = (U,H,R) s nezáporným ohodnocením hran. Máme nalézt takovou kostru G1 = (U, H1, R1), která je Minimální. 1. krok: zvolíme si libovolný uzel grafu G a spojíme jej s nejbližším uzlem (z hlediska minimálního ohodnocení hrany).

2. krok: nalezneme dosud tzv. nepřipojený uzel, který je nejblíže k některému z již „připojených“ uzlů a spojíme jej s ním. Tento krok opakujeme tak dlouho, dokud nebudou propojeny všechny uzly.


2

3 8

2

1 4

10

6

2 1

2 2

1 6

5 5

počáteční prvek si volíme sami, je to libovolný prvek

3


2

3 8

2

1 4

10

6

2 1

2 2

1 6

5 5

toto je minimální kostra , minimálních koster může být více než jedna

3

velikost této kostry je: 2+4+1+3+2+2+2+5+1 +1+3=26

HAMILTONSKÉ CESTY V GRAFECH

U hamiltonovských grafů hledáme uzavřenou cestu, tj. kružnici, která obsahuje všechny uzly grafu. V praxi lze pro grafy s malým počtem uzlů vyhledávat hamiltonovské cesty pomocí algoritmu založeného na aplikaci logického rozhodovacího stromu. Princip je založen na neustálém větvení stromu, kde uzlem větvení je uzel grafu, ve kterém se zrovna nacházíme a větve vedou na všechny jeho následovníky. Přitom postupně vylučujeme ty větve, které vedou na uzel, který se již vyskytl v předchozí úrovni. Nelze-li mezi následovníky nalézt žádný uzel, který se dosud nevyskytl na trase, je nutno zkoušet další větvení.

HAMILTONSKÉ CESTY V GRAFECH

Kružnici nazveme hamiltonovskou, jestliže obsahuje všechny uzly grafu. Graf G nazveme hamiltonovským, pokud v něm existuje hamiltonovská kružnice. Čím více má graf při daném počtu uzlů hran, tím větší je naděje, že bud hamiltonovský. Nejjednodušší situace je u úplných grafů. Úplný graf (s alespoň třemi uzly) je vždy hamiltonovský, protože každý uzel v něm sousedí s každým uzlem. Při sestavení hamiltonovské kružnice lze vyjít z libovolného uzlu a sestavovat cestu postupným přidáváním dalších a dalších uzlů a po vyčerpání všech uzlů ji nakonec uzavřít v kružnici spojením koncového uzlu cesty s počátečním uzlem cesty.

ÚLOHA OBCHODNÍHO CESTUJÍCÍHO

S hamiltonovskou kružnicí souvisí úloha obchodního cestujícího. Jejím cílem je najít nejkratší trasu pro obchodního cestujícího, který vyjíždí z určitého místa, má navštívit jistá obchodní místa (každé však pouze jednou) a nakonec se má vrátit na původní místo, odkud vyjel. Vyjádříme-li tuto úlohu grafem, pak uzly v něm reprezentují výchozí místo a místa, která má obchodní cestující navštívit. Dále každé dva uzly v grafu jsou spojeny hranou, která je ohodnocena vzdáleností, kterou je zapotřebí urazit, abychom se dostali z místa reprezentovaného jedním z těchto uzlů do místa, jež reprezentuje druhý z uzlů.

ÚLOHA OBCHODNÍHO CESTUJÍCÍHO

Úloha je zadána jednoduchým, neorientovaným, souvislým, konečným a hranově ohodnoceným grafem. Cílem této úlohy je najít tu hamiltonovskou kružnici, jejíž délka, která je vyjádřena součtem ohodnocení hran v ní, je nejmenší ze všech hamiltonovských kružnic v grafu. Tato hamiltonovská kružnice je zároveň i nejkratší trasou pro obchodního cestujícího a je tedy řešením úlohy obchodního cestujícího.

ÚLOHA OBCHODNÍHO CESTUJÍCÍHO Navrhněte takovou trasu s výjezdem i návratem do bodu A, aby se mohlo provést prohledání všech bodu a na žádný se nešlo vícekrát.

Uzel, který už byl, se v cestě nesmí vyskytnout. Větev, která takový uzel obsahuje, dále nerozvíjíme. Některé cesty jsou slepé, neboť se nelze vrátit do výchozího uzlu.

ÚLOHA OBCHODNÍHO CESTUJÍCÍHO 1. část řešení

ÚLOHA OBCHODNÍHO CESTUJÍCÍHO 2. část řešení

V grafu existuje 8 hamiltonovský cest, polovina z nich je však tvořena pouze inverzí pořadí hran (protisměrem). Nejkratší cesta [A, D, B, C, E, G, F, A] je délky 17,9 jednotek.

EULEROVSKÉ CESTY

Eulerovské cesty je možno vyhledávat v systémech, které je možno znázornit souvislým, hranově orientovaným i neorientovaným grafem. V praxi se tato úloha nazývá „jednotažky“, nebo-li „cesta kropícího vozu“. Je to jedna ze základních a historicky prvních úloh z teorie grafů, jejíž matematický základ položil německý matematik Euler roku 1736 v úloze „sedmi mostů“. Využití např. pro hledání trasy, jak na jeden zátah uklidit všechny komunikace. U eulerovských grafů hledáme uzavřený tah, který obsahuje všechny hrany.

EULEROVSKÉ CESTY Eulerovská cesta je takový sled uzlů a hran, obsahujících všechny hrany náležejících do H, ale každou pouze jednou. Na rozdíl od hamiltonovkých cest, je tato úloha snadno algoritmizovatelná a matematická formulace nutných a postačujících podmínek pro rozhodnutí, zda graf obsahuje eulerovskou cestu je jednoduchá. EULEROVSKÉ CESTY

uzavřené orientované

neorientované

typy Eulerovských cest

otevřené orientované

neorientované

EULEROVSKÉ CESTY … cesta UZAVŘENÁ Orientovaná cesta Aby bylo možno uzlem projet, musí každý uzel splňovat podmínku: počet vstupních hran = počtu výstupních hran

Neorientovaná cesta Aby bylo možno uzlem projet, musí každý uzel splňovat podmínku: počet hran incidujících y uzlem je sudý

EULEROVSKÉ CESTY … cesta otevřená ORIENTOVANÁ Vstupní uzel cesty Aby bylo možno v uzlu začít a popřípadě uzlem projet, musí vstupní uzel splňovat podmínku: počet vstupních hran = počtu výstupních hran + 1 Ostatní uzly Aby bylo možno uzlem projet, musí každý uzel splňovat podmínku: počet vstupních hran = počtu výstupních hran

Výstupní uzel cesty Aby bylo možno v uzlu skončit a popřípadě uzlem projet, musí výstupní uzel splňovat podmínku: počet vstupních hran = počtu výstupních hran - 1

EULEROVSKÉ CESTY … cesta otevřená NEORIENTOVANÁ

Vstupní a výstupní uzel cesty Aby bylo možno v uzlu začít (skončit) a popřípadě uzlem projet, musí vstupní (výstupní) uzel splňovat podmínku: počet incidujících hran je lichý Ostatní uzly Aby bylo možno uzlem projet, musí každý uzel splňovat podmínku: počet incidujících hran je sudý

EULEROVSKÉ CESTY … příklad

Zjistěte zda v grafu existuje Eulerovská cesta, a pokud ano, jaká je. Odůvodněte.


lichý počet incidujících hran – hraniční uzel

lichý počet incidujících hran – hraniční uzel

ŘEŠENÍ: Jde o otevřenou a neorientovanou eulerovskou cestu. Dva uzly mají lichý stupeň, ostatní mají stupeň sudý.


Zjistěte, zda v grafu existuje Eulerovská cesta, a pokud ano, jaká je. Odůvodněte.


Řešení: Jde o uzavřenou a neorientovanou eulerovskou cestu, neboť u všech uzlů se počet vstupů rovná počtu výstupů.

ÚLOHA O CYKLECH

Existence zpětné vazby (cyklu) ve struktuře systému je závažným jevem, který v určitých případech představuje pozitivní – žádoucí vlastnost systému, v určitých případech negativní – nežádoucí vlastnost systému. Typickým příkladem systémů patřící do první skupiny případů, jsou kybernetické systémy. Zpětná vazba je zde považována za jeden ze základních principů řízení. Příkladem nežádoucí existence zpětné vazby (cyklu) je systém, v němž díky nevhodnému uspořádání může dojít k (nekonečnému) zacyklení procesů. Jiným případem je situace označovaná jako „smrtelné objetí“ („dead lock“). Je to cyklus, v němž spotřeba času nenarůstá, resp. v němž prvky, které se cyklu zúčastňují, realizují své funkce ve stejném čase. Příkladem může být ucpání křižovatky, ze které nemůže nikdo vyjet.

ÚLOHA O CYKLECH

Teorie grafů poskytuje základní pojem uzavřeného sledu, na němž lze systémovou interpretaci cyklu a zpětné vazby založit. V případě, že sled obsahuje pouze jednu hranu, tj. hranu spojující uzel se sebou samým, pak se takový uzavřený sled nazývá smyčkou.

Sledované charakteristiky cyklu Pokud analyzujeme systém, tak v prvé řadě se snažíme identifikovat zpětné vazby. V případě nálezu cyklu v systému nás zajímá:

• Délka cyklu (kolika hranový cyklus je) • Časová charakteristika (za jak dlouho se cyklus zrealizuje) • Které prvky jsou účastníky cyklu a zda se tyto prvky neúčastní ve více cyklech najednou. Poznámka: Je-li cyklů více najednou, říkáme jim shluky nebo klubka.

ÚLOHA O CYKLECH Pojem zpětná vazba budeme chápat jako obecný případ vzájemné návaznosti mezi dvěma prvky bez ohledu na její délku. K analýze zpětných vazeb opět používáme matici sousednosti S a její mocniny. Možnou existenci cyklu (kromě smyčky) ve struktuře signalizuje nenulová hodnota koeficientu v matici S1 pod hlavní diagonálou. Jestliže není možné žádným způsobem uspořádat matici S1 na trojúhelníkovou (záměnou řádků a odpovídající změnou sloupců), pak je jisté, že v grafu existuje smyčka. Kolika hranový cyklus v systému existuje se dozvíme z vyšších mocnin matice sousednosti, z rozboru prvků vyskytujících se na hlavní diagonále.

ÚLOHA O CYKLECH

5 7

2

6 1

3

4

8

9

V SYSTÉMU JSOU 4 ZPĚTNÉ VAZBY

Zpětná vazba představuje nebezpečí vzniku cyklu a zacyklení. Proto se musí zpětné vazby prověřit !!!

10

ÚLOHA O CYKLECH

Ve třetí mocnině matice sousednosti jsou uvedeny 3-hranové cykly. Možné prvky: Prvek 2 … 2x Prvek 3 … 2x Prvek 5 … 1x Prvek 6 … 3x Prvek 9 … 1x

Na hlavní diagonále jsou uvedeny prvky, které mohou (ale nemusí) být účastny v cyklech. Konkrétní průběh cyklů není v S vidět !!! Je nutné vycházet z grafu !!!

ÚLOHA O CYKLECH … 3-hranové cykly Možné prvky: Prvek 2 … 2x Prvek 3 … 2x Prvek 5 … 1x Prvek 6 … 3x Prvek 9 … 1x

5 7

2

6 3

1

8

4

9

10

5 6

2

3 6

3

9

2 6

ÚLOHA O CYKLECH … 4-hranové cykly

Možné prvky: Prvek 1 Prvek 2 Prvek 3 … 2x Prvek 4 Prvek 6 Prvek 8 Prvek 9

3 9

6

1

8

4

2 3

ÚLOHA O CYKLECH … 5-hranové cykly Možné prvky: Prvek 1 … 2x Prvek 2 … 2x Prvek 3 … 1x Prvek 4 … 2x Prvek 5 … 1x Prvek 6 … 2x

2

1

2

1

5

3 4

6

4

6

ÚLOHA O CYKLECH … 6-hranové cykly Možné prvky: Prvek 2 … 6x Prvek 3 … 6x Prvek 5 … 3x Prvek 6 … 9x Prvek 9 … 3x

9

Toto jsou pouze některé z cyklů

6

3

5

6

9

2 6

3

6

3

5

6

3

6

2

2

2

Analýza systémů. Strukturovaná analýza informačních systémů Teorie grafu Ing. Dagmar Létavková, Ph.D

Recommend Documents