Štruktúry a organizácia údajov Nezačaté

0. Kľúčové fakty

1. Štruktúra údajov — Štruktúra je usporiadaný spôsob, ako uložiť informácie tak, aby sa v nich dalo ľahko orientovať a rýchlo niečo nájsť. Keď údaje nie sú usporiadané (napríklad rozhádzané papieriky), hľadanie trvá dlho a ľahko sa pomýlime. Vďaka štruktúre vieme každý údaj zaradiť na svoje miesto a potom ho podľa pravidla znova nájsť.

2. Postupnosť (zoznam) — Postupnosť je rad údajov uložených jeden za druhým v určitom poradí, napríklad dni v týždni, čísla od 1 do 10 alebo poradie žiakov v rade. Na poradí záleží — pondelok je vždy pred utorkom a prvý je pred druhým. Postupnosti používame všade, kde má niečo svoje pevné poradie alebo nasledovnosť.

3. Tabuľka — Tabuľka usporadúva údaje do riadkov a stĺpcov, takže každý údaj má svoju presnú polohu. V riadku býva jeden záznam (napríklad jeden žiak) a v stĺpcoch jeho vlastnosti (meno, vek, obľúbený predmet). Tabuľka je veľmi prehľadná, lebo údaj nájdeme tak, že sa pozrieme, kde sa pretína správny riadok so správnym stĺpcom.

4. Vyhľadávanie podľa kritérií — Kritérium je pravidlo alebo podmienka, podľa ktorej vyberáme len niektoré údaje, napríklad „všetci žiaci starší ako 11 rokov". Schopnosť hľadať podľa kritérií je dôležitá, lebo v reálnom živote nepotrebujeme všetky údaje naraz, ale len tie, ktoré spĺňajú našu podmienku. Práve takto fungujú aj vyhľadávače a filtre v počítačových programoch.

5. Graf (diagram) — Graf zobrazuje údaje pomocou obrázka, najčastejšie pomocou stĺpcov, čiar alebo výsekov koláča, aby sme vzťahy videli na prvý pohľad. Napríklad stĺpcový graf nám hneď ukáže, ktorý mesiac bol najteplejší, bez toho, aby sme čítali všetky čísla. Graf je výhodný, lebo náš mozog rýchlejšie pochopí obrázok než dlhý zoznam čísel.

6. Mapa — Mapa je zmenšené a usporiadané znázornenie priestoru, napríklad mesta, krajiny alebo školy, kde poloha na obrázku zodpovedá skutočnej polohe vo svete. Údaje v mape sú uložené podľa miesta, takže podľa nej vieme nájsť cestu alebo zistiť, čo sa kde nachádza. Mapa je príkladom štruktúry, kde je dôležité, kde presne sa údaj nachádza.

7. Labyrint (bludisko) — Labyrint je štruktúra ciest, v ktorej hľadáme správnu cestu od vchodu k cieľu spomedzi mnohých odbočiek a slepých uličiek. Učí nás skúšať možnosti, vracať sa späť pri zlej voľbe a postupovať systematicky, čo je základ riešenia problémov v informatike. Riešenie labyrintu sa podobá tomu, ako počítač hľadá cestu medzi viacerými možnosťami.

8. Strom rozhodnutí — Strom rozhodnutí je štruktúra, ktorá sa vetví podľa odpovedí na otázky áno/nie, a tak nás krok za krokom dovedie k záveru alebo riešeniu. Začína jednou otázkou (koreň) a každá odpoveď nás posunie na ďalšiu vetvu, až dôjdeme k výsledku (list). Používame ho napríklad pri triedení vecí, určovaní zvierat alebo rozhodovaní, čo robiť ďalej.

9. Rodokmeň (strom príbuznosti) — Rodokmeň je stromová štruktúra, ktorá zobrazuje príbuzenské vzťahy v rodine, napríklad kto sú rodičia, deti, starí rodičia a súrodenci. Vzťahy sú uložené pomocou vetiev — z rodičov vedú čiary k deťom, takže hneď vidíme, kto ku komu patrí. Rodokmeň ukazuje, že stromová štruktúra je vhodná všade, kde sa niečo vetví a má nadradené a podradené prvky.

10. Koreň, vetva a list stromu — V stromovej štruktúre je koreň úplne hore (začiatok), z neho vychádzajú vetvy a na koncoch sú listy, ktoré sa už ďalej nevetvia. Tieto pojmy nám pomáhajú presne pomenovať, kde sa v strome nachádzame a ako sú prvky navzájom prepojené. Strom je výborný na zobrazenie vzťahov typu „nadradený – podradený", napríklad priečinky v počítači obsahujú ďalšie priečinky a súbory.

11. Interpretácia vzťahov vlastnými slovami — Interpretovať znamená pozrieť sa na údaje v štruktúre a vlastnými slovami povedať, čo z nich vyplýva, napríklad „z tabuľky vidím, že najviac detí má rado matematiku". Nestačí len mať údaje uložené — dôležité je vedieť ich aj prečítať a pochopiť, čo nám hovoria. Práve interpretácia mení obyčajné údaje na užitočnú informáciu, ktorú vieme použiť.

12. Prečo organizujeme údaje — Údaje organizujeme do štruktúr preto, aby sme v nich rýchlo našli, čo potrebujeme, ľahko ich porovnávali a nestratili sa v množstve informácií. Tá istá informácia sa dá zapísať rôznymi štruktúrami a my si vyberáme tú, ktorá sa k danej úlohe najlepšie hodí — napríklad poradie zapíšeme postupnosťou, vzťahy v rodine stromom a polohu mapou. Vhodne zvolená štruktúra robí prácu s údajmi jednoduchšou a zrozumiteľnejšou.

1. Poučka

Štruktúra údajov je usporiadanie informácií tak, aby sme sa v nich ľahko orientovali a rýchlo našli to, čo potrebujeme. Údaje vieme organizovať do postupností, tabuliek, grafov, máp, labyrintov a stromov (napríklad rodokmeň alebo strom rozhodnutí). V dobre usporiadanej štruktúre vieme vyhľadať údaj podľa kritéria a vysvetliť vzťahy medzi údajmi vlastnými slovami.

2. Vysvetlenie

Predstav si, že máš veľa informácií — mená, čísla, obrázky, cesty. Keby ležali na kope, nič v nich nenájdeš. Preto ich usporiadame do nejakého tvaru:

1. Postupnosť (zoznam, rad) — údaje idú jeden za druhým v poradí (napr. dni v týždni).
2. Tabuľka — údaje sú v riadkoch a stĺpcoch; každý stĺpec má svoj nadpis (kritérium).
3. Graf — slovo má dva významy: diagram (stĺpcový, čiarový, koláčový) porovnáva množstvá a graf ako sieť ukazuje vzťahy medzi údajmi pomocou bodov (uzlov) a čiar (spojení), napríklad mapa ciest.
4. Mapa — usporiadanie podľa polohy v priestore (kde sa čo nachádza).
5. Labyrint (bludisko) — sieť ciest, kde hľadáme správnu cestu od štartu do cieľa.
6. Strom — údaje sa vetvia od jedného koreňa do viacerých vetiev; používa sa pri rodokmeni aj pri strome rozhodnutí (otázka → áno/nie → ďalší krok).

Keď chceš niečo nájsť, použiješ kritérium — pravidlo, podľa ktorého vyberáš (napr. „všetci žiaci so známkou 1“). Potom vieš vzťahy v štruktúre opísať vlastnými slovami (napr. „Jano je syn Petra“).

3. Príklady a prečo je to dôležité

Príklad 1 — vyhľadávanie v tabuľke podľa kritéria: V tabuľke sú žiaci a ich vek: Ema 10, Filip 12, Hana 11, Ivan 10. Kto spĺňa kritérium „starší ako 10 rokov“?
Kritérium = pravidlo, podľa ktorého vyberám: vek väčší ako 10.
Prejdem stĺpec vek riadok po riadku: Ema 10 nie, Filip 12 áno, Hana 11 áno, Ivan 10 nie.
Pozor: 10 nie je viac ako 10.
Kritérium spĺňajú → Filip a Hana

Príklad 2 — postupnosť: Zoraď do správnej postupnosti: obuť sa, vstať z postele, odísť do školy, naraňajkovať sa, obliecť sa.
V postupnosti záleží na poradí, každý krok musí dávať zmysel po predchádzajúcom.
Najprv vstanem, potom sa oblečiem, naraňajkujem, obujem a až potom odchádzam.
Poradie → vstať, obliecť sa, naraňajkovať sa, obuť sa, odísť do školy

Príklad 3 — čítanie rodokmeňa: V rodokmeni vedú čiary od Petra k Jánovi a Zuzke a od Jána k Lukášovi. Kým je Peter Lukášovi?
Čiara od rodiča vedie k dieťaťu: Peter je otec Jána a Zuzky.
Ján je otec Lukáša.
Peter je otec Lukášovho otca → starý otec

Príklad 4 — strom rozhodnutí: Strom rozhodnutí má otázky: „Žije vo vode?“ Ak áno, je to ryba. Ak nie: „Šteká?“ Ak áno, je to pes, inak mačka. Ktoré zviera vyjde, keď odpovieš „nie“ a „nie“?
Prvá otázka: Žije vo vode? Nie → idem na druhú vetvu.
Druhá otázka: Šteká? Nie → dostanem sa na list „mačka“.
Výsledok → mačka

Príklad 5 — výber štruktúry: Akou štruktúrou najlepšie zapíšeš a) poradie zastávok autobusu, b) kto je v rodine čí príbuzný, c) kde je v meste škola a ihrisko?
a) zastávky idú jedna za druhou → postupnosť.
b) vzťahy sa vetvia od starých rodičov k deťom → strom (rodokmeň).
c) dôležitá je poloha v priestore → mapa.
Voľba → a) postupnosť, b) strom, c) mapa

Príklad 6 — interpretácia grafu z praxe: Stĺpcový graf ukazuje počet prečítaných kníh: Ema 3, Filip 5, Hana 2. Čo z neho vyplýva vlastnými slovami?
Najvyšší stĺpec má Filip, najnižší Hana.
Filip prečítal o 3 knihy viac ako Hana: 5 − 2 = 3
Záver → najviac kníh prečítal Filip, o 3 viac ako Hana

Prečo je to dôležité: dobre usporiadané údaje šetria čas — namiesto hľadania na kope nájdeš odpoveď za pár sekúnd. Počítače, internetové vyhľadávače, knižnice aj navigácie fungujú práve vďaka šikovným štruktúram údajov. Kto vie údaje organizovať, robí menej chýb a lepšie rozumie, ako veci medzi sebou súvisia.

Precvič si

1. Ako sa volá pravidlo, podľa ktorého vyberáme údaje?
2. Ako sa volá miesto, kde začína strom (úplne hore)?
3. Ako sa volajú vodorovné rady buniek v tabuľke?
4. Ktorý deň nasleduje v postupnosti dní po štvrtku?
5. V rodokmeni je Mária mama Jany a Jana mama Tomáša. Kým je Mária Tomášovi?
6. Body žiakov: Adam 7, Beáta 9, Cyril 4, Dana 9. Kto má viac ako 8 bodov?