Odkazy na kapitoly k ověřování najdete na úvodní stránce. Tyto vzdělávací materiály jsou alfa verzí určenou k ověřování ve školním roce 2018/2019 v rámci projektu CZ.02.3.68/0.0/0.0/16_036/0005322 Podpora rozvíjení informatického myšlení.


Grafy

Z Informatika pro každého
Přejít na: navigace, hledání
Informace · Algoritmus
ikona boxu
Grafy, grafy a grafy

Hned na začátku si vyjasněme, že grafy v informatice se liší od grafů funkcí v matematice i od grafů v tabulkových procesorech. Budeš tedy muset rozlišovat různé významy slova graf podle kontextu stejně, jako to děláš s ostatními souzvučnými slovy.

ikona boxu
Proč nezvolit jiný pojem?

Nabízí se otázka, proč pracujeme s pojmem, který už studenti znají v jiném významu. Mohli bychom mluvit např. o sítích či schématech. Ovšem v okamžiku, kdy by studenti přišli do kontaktu se světem mimo školu, byli by opět zmatení a s ostatními lidmi by si nerozuměli. Co víc, měli by potíže i se snahou použít jiné studijní materiály, které se samozřejmě drží standardní terminologie. Z těchto důvodů jsme se rozhodli vystavit studenty dalšímu významu pojmu graf a umožnit jim samostatně ty významy rozlišovat.

Tím spíš je nutno sledovat, jestli právě zmatený student nepracuje s jiným významem grafu, občas se to stává.

Co má společného Kréta, vyhledávání na GoogleSpolečnost Google podpořila vznik této učebnice - děkujeme!, evoluce, hledání prvočinitelů, městská hromadná doprava, větné rozbory či origami? Všechny nějak souvisí s grafy.

ikona boxu
Souvislosti

Pro úplnost:

  • Z Kréty studenti znají labyrint, tedy bludiště, tedy graf.
  • Relevanci stránky Google určije mimo jiné podle dalších stránek, které na ni odkazují, pracuje tedy s grafem odkazů mezi stránkami.
  • Evoluční vývoj druhů pro přehlednost znázorňujeme pomocí stromů, tedy grafů.
  • Jeden z postupů hledání prvočinitelů číslo postupně rozkládá na jednotlivé dělitele a ty dále dělí (dokud to jde). Abychom se v tom neztratili, zakreslujeme dílčí rozklady jako větvení stromu, na jehož listech potom najdeme prvočinitele.
  • Plány městské hromadné dopravy jsou klasickým příkladem grafů.
  • Při navrhování nového origami tvůrce nejprve hledá strukturu výsledného objektu, totiž jednotlivá větvení a jejich větvení — tedy strom.

Uvedený odstavec má nicméně podnítit zvědavost, není nutné hned tady prozradit, co je graf vlastně zač.

I když o nich zatím možná nemáš tušení, jsou grafy jednoduchým, užitečným a velmi mocným nástrojem pro řešení široké škály různých problémů. Právě proto se staly nedílnou součástí výbavy každého informatika. Uplatnění ale najdou skoro všude, kde záleží na vzájemných vztazích mezi nějakými objekty. Takže skoro všude.

Obsah

ikona boxu
Doporučený průběh

Cílem této části učebnice je základní seznámení s grafy. Studenti by je měli umět rozpoznat v běžných situacích a usnadnit si tak např. odvozování jednoduchých závěrů o daném problému. Kromě toho samozřejmě grafy bohatě využijeme v dalších částech učebnice, zejména v části o stavových prostorechTODO: odkaz. V té se také budeme věnovat systematickému procházení grafů.

Na grafech studenty zároveň seznamujeme s modelováním. Modely k řešení problémů i školních úloh již samozřejmě dávno používají. Zpravidla si toho ovšem nejsou vědomi, stejně jako souvisejících úskalí.

Nejdřív studenti na připravených úlohách zjistí, že na intuitivní úrovni už s grafy pracují. Jejich existující znalosti následně strukturujeme. Abychom mohli zpracovávat velké grafy (a grafy v počítači), potřebujeme grafy zapsat pomocí posloupností znaků, nikoliv jako obrázky. To je tedy dalším krokem. Zároveň u toho opakujeme učivo o informaci.

S tímto základem je možné začít zkoumat nějaký konkrétní problém a odvodit např. obecný postup řešení. Nám se osvědčily eulerovské grafy (jednotažky), ale vybrat lze i jiné základní téma, např. stromy a jejich vlastnosti, kostry (a minimální kostry) atp.

Závěrečná kapitola o isomorfismu grafů je pro některé žáky zprvu obtížná, nakonec ale látku pochopí. Samotný isomorfismus grafů jako takový vlastně není tak zásadní (umožňuje to ale precizně popsat, v jakém smyslu v grafu „nezáleží na nakreslení“). Smyslem kapitoly je ukázat, že pojem „stejnosti“ může být složitější, než se na první pohled zdá, na čem závisí a že stojí za bližší prozkoumání. Rozeznávání v nějakém smyslu stejných, ekvivalentních či isomorfních struktur se v informatice objevuje v mnoha různých souvislostech.

Do grafů jsme zařadili i dvě doplňující kapitoly. Myšlenkové mapy jsou aplikací grafů a užitečným nástrojem, který by studenti měli znát (a pokud je znají, není problém kapitolu projít velmi rychle, nebo ji zcela přeskočit). Regulární grafy jsou příležitostí k systematickému zkoumání abstraktní struktury a hledání zákonitostí. Je to dobrá průprava, ale další kapitoly na tom přímo nezávisí.

TODO:

pretest !!!

Kapitoly

  1. Myšlenkové mapy
  2. Úvod
  3. Zapisování grafů
  4. Regulární grafy
  5. Jednotažky
  6. Které grafy jsou stejné?

Tučně uvedené kapitoly tvoří základní jádro. Kapitola Myšlenkové mapy s grafy úzce souvisí a lze ji pojmout jako velmi jemný úvod a ukázku jedné z aplikací grafů. Nejužitečnější ale bude pro ty, kdo se s myšlenkovými mapami dosud nesetkali. V kapitole Regulární grafy podrobněji zkoumáme strukturu grafů jako takových, takže jde o poněkud abstraktnější a teoretičtější práci. Zkoumání regulárních grafů usnadní porozumění následujícím dvěma kapitolám, lze jej nicméně přeskočit.

TODO:

Rozšiřující kapitoly

???

Hlavní otázky

TODO: opravdu? promysli, až budeš hotov

  1. Co je v informatice graf?
    1. Z čeho se grafy skládají?
    2. Jaké druhy grafů rozlišujeme?
    3. Které jsou základní a zajímavé vlastnosti grafů?
  2. Co můžeme pomocí grafů reprezentovat?
  3. Jaké můžeme s pomocí grafů řešit problémy?
  4. Jak grafy kreslit, jak je zapisovat?

TODO:

Další témata

Těchto témat se v nějaké souvislosti dotkneme.

  • Model, abstrakce
  • Rozhodovací stromy
  • Dvojková soustava
  • Efektivita
  • Rekurze

Pojmy

--- to možná spíš pro učitele?

  • Komunikace, data, zpráva, (de)kódování, komunikační kanál, interpretace, zpětná vazba
  • Informace, znalost, neurčitost, pravděpodobnost
  • Strom, kořen, podstrom, list, výška stromu, logaritmus
  • Množství informace, (ne)závislé zprávy, bit, bajt, kilobajt