Organizácia údajov do štruktúr Nezačaté

0. Kľúčové fakty

1. Štruktúra údajov — Štruktúra je usporiadanie údajov podľa nejakého pravidla tak, aby sa v nich dalo ľahko orientovať a vyhľadávať. Keď údaje nie sú usporiadané (napríklad rozhádzané papiere), hľadanie je pomalé a zdĺhavé. Vďaka štruktúre vieme rýchlo nájsť presne tú informáciu, ktorú potrebujeme, podľa zvoleného kritéria.

2. Tabuľka — Tabuľka organizuje údaje do riadkov a stĺpcov, kde každý stĺpec má svoj nadpis (napr. Meno, Vek, Známka). Jeden riadok obvykle predstavuje jeden záznam (napr. jedného žiaka) a jeho hodnoty v jednotlivých stĺpcoch. Tabuľka je výborná na porovnávanie údajov a na vyhľadávanie podľa kritérií — napríklad „nájdi všetkých žiakov s vekom 12 rokov".

3. Vyhľadávanie podľa kritérií — Kritérium je podmienka, ktorú musí údaj spĺňať, aby sme ho vybrali (napr. „cena nižšia ako 5 €" alebo „farba = červená"). V štruktúre vieme zadať jedno alebo viac kritérií naraz a systém nám vyberie len vyhovujúce záznamy. Práve preto sa údaje organizujú — aby filtrovanie a hľadanie bolo rýchle a presné.

4. Triedenie (zoradenie) — Triedenie znamená usporiadanie záznamov podľa zvolenej vlastnosti, napríklad podľa abecedy, od najmenšieho po najväčšie čísla alebo podľa dátumu. Zoradené údaje sa hľadajú oveľa rýchlejšie ako neusporiadané — preto je v slovníku abeceda a v telefónnom zozname mená podľa abecedy. Triedenie môže byť vzostupné (od najmenšieho) alebo zostupné (od najväčšieho).

5. Postupnosť (zoznam) — Postupnosť je rad údajov usporiadaných za sebou v určitom poradí, kde záleží na tom, čo je prvé, druhé, tretie atď. Príkladom je poradie krokov v recepte, zoznam úloh na deň alebo postupnosť čísel 2, 4, 6, 8. Na rozdiel od tabuľky postupnosť zdôrazňuje hlavne poradie prvkov.

6. Graf (diagram) — Graf je obrázkové znázornenie údajov, ktoré nám pomáha rýchlo pochopiť vzťahy a veľkosti bez čítania čísel. Stĺpcový graf porovnáva hodnoty pomocou výšky stĺpcov, koláčový graf ukazuje, akú časť z celku tvoria jednotlivé časti, a čiarový graf zobrazuje zmenu hodnoty v čase. Graf vzniká z tabuľky údajov a slúži na ich názornú interpretáciu.

7. Grafová štruktúra (sieť) — Grafová štruktúra sa skladá z vrcholov (bodov) a hrán (spojení medzi nimi), ktoré ukazujú, čo je s čím prepojené. Príkladmi sú mapa miest spojených cestami, labyrint s chodbami alebo sieť kamarátov na sociálnej sieti. V takejto štruktúre hľadáme napríklad cestu z jedného bodu do druhého alebo najkratšie spojenie.

8. Mapa a labyrint — Mapa a labyrint sú typické grafové štruktúry, v ktorých sa pohybujeme po spojeniach (cestách, chodbách) medzi miestami. V labyrinte hľadáme cestu od vchodu k východu a niektoré chodby môžu byť slepé. Učia nás premýšľať o tom, ako sú miesta poprepájané a ako sa dostať z miesta A do miesta B.

9. Stromová štruktúra — Strom je štruktúra, ktorá sa vetví od jedného začiatku (koreňa) do viacerých vetiev a listov, podobne ako naozajstný strom obrátený naopak. Každá vetva sa môže ďalej deliť na menšie vetvy, ale neexistujú v nej kruhy — z koreňa vedie ku každému prvku len jedna cesta. Príkladom je usporiadanie priečinkov v počítači, kde hlavný priečinok obsahuje podpriečinky.

10. Rodokmeň — Rodokmeň je stromová štruktúra, ktorá zobrazuje rodinné vzťahy — predkov a potomkov — pomocou vetiev. Hore sú najstarší členovia rodiny (prarodičia) a smerom nadol pribúdajú deti a vnúčatá. Ukazuje, kto je čí rodič, súrodenec alebo potomok, a pekne znázorňuje, ako stromová štruktúra zachytáva vzťahy.

11. Strom rozhodnutí — Strom rozhodnutia je stromová štruktúra, ktorá pomáha vybrať správnu možnosť pomocou postupných otázok s odpoveďami áno/nie. Pri každej otázke sa cesta rozvetví a podľa odpovede pokračujeme ďalej, až kým neprídeme k výsledku. Používa sa napríklad v hrách na uhádnutie zvieraťa alebo pri rozhodovaní „čo si oblečiem podľa počasia".

12. Interpretácia údajov — Interpretovať údaje znamená prečítať štruktúru a vyvodiť z nej zmysel — povedať, čo nám tabuľka alebo graf vlastne hovorí. Napríklad z grafu teploty zistíme, ktorý deň bol najteplejší, alebo z tabuľky vyčítame, kto mal najlepšiu známku. Samotné údaje sú len čísla a slová; ich hodnota vznikne, až keď z nich vieme správne čítať a robiť závery.

13. Vrchol, hrana, koreň a list — Sú to základné pojmy štruktúr: vrchol (uzol) je jeden bod s údajom, hrana je spojenie medzi dvoma vrcholmi, koreň je začiatočný vrchol stromu a list je koncový vrchol bez ďalšieho vetvenia. Pomocou týchto pojmov vieme presne opísať, ako je štruktúra postavená. Rozdiel medzi grafom a stromom je práve v tom, či sa cesty môžu vracať a tvoriť kruhy (graf) alebo nie (strom).

1. Poučka

Údaje sú jednotlivé fakty (čísla, slová, mená). Aby sme sa v nich vyznali a vedeli rýchlo nájsť, čo hľadáme, usporiadame ich do štruktúry. Najčastejšie štruktúry sú: - Tabuľka — údaje v riadkoch a stĺpcoch, - Postupnosť (zoznam) — údaje za sebou v určitom poradí, - Graf — body (vrcholy) pospájané čiarami (hranami); patrí sem mapa, labyrint, sieť, - Strom — graf, ktorý sa vetví z jedného koreňa a nikdy sa nevracia do kruhu; patrí sem rodokmeň a strom rozhodnutí.

V dobre usporiadanej štruktúre vieme vyhľadať informáciu podľa kritéria (napr. „nájdi všetkých s vekom nad 12") a interpretovať údaje (prečítať, čo nám hovoria).

2. Vysvetlenie

Predstav si neusporiadanú kopu papierikov s menami a známkami — hľadať v nej je zdĺhavé. Keď tie isté údaje zapíšeš inak, hneď sa v nich vyznáš:

1. Vyber správnu štruktúru podľa toho, aké údaje máš. - Veľa rovnakých záznamov s viacerými údajmi → tabuľka. - Údaje, kde záleží na poradí (kroky, dni) → postupnosť. - Veci pospájané cestami či vzťahmi → graf (mapa miest, sieť kamarátov). - Vzťahy typu „nadradený – podradený" alebo vetvenie → strom (rodokmeň, rozhodovanie).
2. Doplň údaje na svoje miesta (do buniek tabuľky, na vrcholy grafu…).
3. Vyhľadávaj podľa kritéria — prejdi štruktúru a vyber len to, čo spĺňa podmienku.
4. Interpretuj — povedz, čo z údajov vyplýva (kto je najstarší, ktorá cesta je najkratšia).

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

Príklad 1 — vyhľadanie v tabuľke podľa dvoch kritérií: Tabuľka (Meno, Vek, Šport): Lea 12 plávanie, Tomáš 11 futbal, Nina 12 futbal, Marek 13 hokej. Kto spĺňa kritériá „vek 12“ a zároveň „šport futbal“?
Prvé kritérium „vek 12“ spĺňajú Lea a Nina.
Z nich druhé kritérium „futbal“ spĺňa len Nina.
Musia platiť obe kritériá naraz → Nina

Príklad 2 — triedenie: Zoraď tých istých žiakov podľa veku zostupne (od najstaršieho).
Zostupne znamená od najväčšieho čísla po najmenšie.
13 Marek, 12 Lea a Nina, 11 Tomáš; rovnaký vek zoradíme podľa abecedy.
Poradie → Marek, Lea, Nina, Tomáš

Príklad 3 — mapa ako graf, najkratšia cesta: Mestá A, B, C, D sú vrcholy, cesty sú hrany: A–B 5 km, B–D 4 km, A–C 3 km, C–D 8 km. Ktorá cesta z A do D je najkratšia?
Z A do D vedú dve cesty: cez B alebo cez C.
Cez B: 5 + 4 = 9 km.
Cez C: 3 + 8 = 11 km.
Kratšia je cesta cez B → A, B, D s dĺžkou 9 km

Príklad 4 — strom priečinkov: Priečinok Dokumenty obsahuje priečinky Škola a Fotky, priečinok Škola obsahuje priečinok Matematika. Čo je koreň a čo sú listy?
Koreň je začiatočný vrchol, z ktorého sa všetko vetví: Dokumenty.
Listy sú koncové vrcholy bez ďalšieho vetvenia: Matematika a Fotky.
Škola je vnútorný vrchol (má pod sebou ďalší priečinok).
Výsledok → koreň Dokumenty, listy Matematika a Fotky

Príklad 5 — strom rozhodnutí: Hádame zviera. Otázka 1: Má perie? Ak áno, je to vták. Ak nie, otázka 2: Žije vo vode? Ak áno, je to ryba, ak nie, cicavec. Na otázky odpovedáme nie a áno. Aké zviera vyjde?
Otázka 1: odpoveď nie, ideme do vetvy „nie“.
Otázka 2: odpoveď áno, ideme do vetvy „áno“.
Prišli sme do listu stromu → ryba

Príklad 6 — z praxe, interpretácia grafu: Stĺpcový graf ukazuje počet kníh požičaných v školskej knižnici: pondelok 2, utorok 5, streda 1, štvrtok 4. Ktorý deň bol najrušnejší a koľko kníh sa požičalo spolu?
Najvyšší stĺpec patrí utorku (5 kníh).
Spolu: 2 + 5 + 1 + 4 = 12.
Interpretácia → utorok, spolu 12 kníh

Prečo je to dôležité: Dobre usporiadané údaje sa rýchlo prehľadávajú a ľahko čítajú. Presne takto fungujú telefónne kontakty, internetové vyhľadávače, GPS navigácia aj databázy v školách a obchodoch. Kto vie údaje organizovať, ten v nich nájde odpoveď za sekundy namiesto hodín.

Precvič si

1. Ako sa volá spojenie dvoch vrcholov v grafe?
2. Ako sa volá koncový vrchol stromu, z ktorého už nič nevedie?
3. Doplň ďalší člen postupnosti 5, 10, 15, …
4. Ktorý graf ukáže, akú časť z celku tvorí každá časť?
5. Z tabuľky Jana 11, Peter 13, Eva 12 vyber všetkých s vekom menej ako 12.
6. Môže sa v strome vyskytnúť kruh (cesta, ktorá sa vráti na začiatok)?