Orientace v grafu
Byla jsem nakupovat v Brně. V Králově poli jsem najela do jiného jízdního pruhu než jsem měla, a pak jsem se nemohla dostat na původní trasu.
To se může stát. Podívejme se na to společně.
Jedná se o meziúrovňovou křižovatku. Na rozdíl od běžné křižovatky, kde musíš dávat pozor, zda jsi na hlavní nebo na vedlejší silnici a komu musíš ještě dávat přednost, na meziúrovňové křižovatce dáváš přednost jen vozidlům jedoucím po hlavní silnici. Nemůžeš se ani otočit, protože všechna vozidla jedou jedním směrem. Pokud se dobře podíváš na obrázek, šipky znázorňují směr jízdy. To znamená, že po každé části silnice musíš jet pouze daným směrem.
Schéma křižovatky je také graf. V tomto grafu je možné se pohybovat pouze určitým směrem, takový graf se nazývá orientovaný graf. Jednoduchý orientovaný graf používáš třeba při převádění jednotek. Při převádění z větších jednotek na menší násobíš,
při převádění z menších na větší naopak dělíš.
Orientovaný graf
Jednou z reálných situací je, že vztah mezi dvěma prvky není oboustranný (obousměrný). V takových situacích opatřujeme hranu v grafu šipkou, která určuje přípustný směr. Stejně jako ohodnocené grafy i orientované grafy pomáhají řešit některé problémy.
Představ si, že jsi u automatu, chceš si koupit něco na pití. Tvůj vybraný nápoj stojí 7 Kč. Máš jednokorunové a dvoukorunové mince. Automat rozpozná, která mince byla vhozená a přičte ji k tomu, co je již v automatu.
Na začátku má nulu. Na konci si vždy pamatuje součet vhozených mincí.
Zkuste pomocí grafu znázornit, co se stane, když vhazuješ do automatu mince. Pozor, automat mince nevrací!
Jednotlivé uzly znázorňují stavy, které se ukazují na displeji. Žlutě jsou označeny částky, které již stačí k vydání nápoje (tzv. koncové stavy). Pro větší názornost je cesta po vhození 1korunové mince vykreslena modře, cesta po vhození 2korunové mince pak zeleně.
Těmto speciálním grafům se odborně automaty říká.
Jak se graf změní, když můžeš použít i pětikoruny?
Konečná částka je stejná, jen je více možností, jak danou částku zaplatit.
Automaty
Na počátku se automat nachází v definovaném počátečním stavu.
Dále v
každém kroku přečte jeden symbol ze vstupu a přejde do stavu, který je
dán hodnotou, která v přechodové tabulce odpovídá aktuálnímu stavu a
přečtenému symbolu. Poté pokračuje čtením dalšího symbolu ze vstupu,
dalším přechodem až do konečné hodnoty.
Procvičování s Bobrem
Výběr správného schématu, grafu, formalizace; hledání chyby
V těchto úlohách má žák VYBRAT mezi nabízenými SPRÁVNÝ model, schéma nebo graf, který odpovídá popisované situaci. Může také hledat CHYBU v takovém schématu.
Copied from:Informatika s Bobříkem
10. úkol
Nadpis a text mezi čarami zkopíruj do pracovního sešitu.
Do sešitu vypracuj úkoly z pracovního listu.