• Pokročilí

Čítaš stránku, ktorá je stará. Údaje a linky nemusia byť aktuálne.

Starú verziu stránky nájdeš na https://www.ksp.sk/osp20/urovne/pokrocili/pokrocili-stara-stranka/

V kategórii pokročilí ti pomôžeme preniknúť do sveta algoritmov a dátových štruktúr. Algoritmy sú informatické recepty na riešenie problémov. Problémy v informatike sa čas podozrivo podobajú na problémy z reálneho sveta -- budeme napríklad riešiť, ako utriediť zoznam čísel, ako hľadať najkratšie cesty v cestnej sieti, a mnoho iného. Dátové štruktúry sú informatické recepty na to, ako ukladať dáta v našich programoch tak, aby sme s nimi vedeli efektívne narábat. Jedna z dátových štruktúr, ktorá už vám je zrejme dobre známa, je pole (list), ktoré slúži na ukladanie dát, napríklad čísel, v pamäti za sebou.

Teraz stojíš na prahu poznania tých najznámejších algoritmov a dátových štruktúr. Aby sme ti bádanie uľahčili, zoradili sme ich do rôznych "levelov". Vyššie levely môžu využívať poznatky z tých nižších. Odporúčame ti preto začať v leveli 1 :)

Takmer každá téma obsahuje aj úlohy na precvičenie. Silne ti odporúčame si tieto úlohy pri pozeraní prednášok a textov preriešiť.

Predtým, než sa do toho pustíš, prihlás sa na náš Discord, kde sa dozvieš všetky novinky o OŠP a nájdeš tam aj super ľudí, ktorí ti radi poradia s prípadnými problémami a navedú na riešenie úloh.

Level 1

Prefixové súčty (Prefix sums)

Prefixové súčty slúžia na to, aby sme vedeli rýchlo zistiť súčet ľubovoľného podúseku poľa. Pomáhajú nám preto efektívne odpovedať na otázky typu: "Aký je súčet v poli X od indexu 3 po index 10?"

Časová zložitosť (Time complexity)

V informatike sa rýchlosť algoritmov typicky nemeria klasickým časom, pretože niektoré počítače sú oveľa rýchlejšie ako iné. Namiesto toho sa rýchlosť meria v počte inštrukcií, ktoré algoritmus vykoná v závislosti od veľkosti vstupu. Výhoda je v tom, že počet krokov zostáva rádovo rovnaký bez ohľadu na to, na akom stroji algoritmus beží.

Práca s reťazcami (String manipulation)

Základná práca s reťazcami zahŕňa napríklad porovnanie reťazcov, tvorbu podreťazcov či zmenu niektorých znakov. Práve posledná operácia, zmena znaku, nás v Pythone môže trochu zaskočiť. Reťazce v Pythone sa po vytvorení nedajú zmeniť, sú tzv. immutable. Preto ak chceme meniť znaky nejakého reťazca retazec, musíme ho najskôr premeniť napríklad na list jednotlivých znakov pomocou list(retazec). Z listu znakov znaky môžeme reťazec vybudovať naspäť pomocou ''.join(znaky).

Reprezentácia grafov (Representing graphs)

Grafmi v informatike myslíme úplne iné grafy ako tie, s ktorými ste sa stretli na základnej alebo strednej škole, vykreslujúce napríklad priebeh funckií. Grafy v algoritmoch budú jednoducho krúžky spojené čiarkami :) Môžu sa hodiť napríklad pri zisťovaní najkratších ciest medzi mestami, kde krúžky budú mestá, a čiarky cesty.

Množina a asociatívne pole (Set and Map)

Zjednodušene povedané, množina (anglicky set) je vrece, do ktorého môžeme vhadzovať čísla, vyberať ich a zisťovať, či sa vo vreci nachádzajú. Ako takéto vrece by mohlo poslúžiť pole (list). Nevýhodou poľa však je, že buď majú niektoré z uvedených operácií časovú zložitosť $O(n)$ ($n$ je počet prvkov) alebo veľkú pamäťovú zložitosť. Existujú ale aj šikovnejšie spôsoby ako reprezentovať množinu, napríklad pomocou tzv. vyvažovaných binárnych stromov alebo pomocou hešovacích tabuliek. V C++ sa tieto dátové štruktúry nazývajú set, resp. unordered_set. V Pythone štandardne nie sú, ale môžeme tam nájsť asociatívne pole (inak aj slovník alebo mapa). Ide o množinu popísanú vyššie, pri ktorej si navyše pri každom prvku (kľúči, key) pamätáme aj nejakú hodnotu (value). V C++ sú asociatívne polia nazývane map alebo tiež unordered_map, v Pythone dict.

Fronta a zásobník (Queue and stack)

Fronta je dátová štruktúra simulujúca klasickú frontu v obchode, kde predavač/ka obslúži prvého zákazníka v rade, pričom noví zákazníci sa postavia vždy na koniec. Zásobník zase simuluje hŕbu tanierov, z ktorých berieme vrchný, ale aj nový vkladáme navrch.

Level 2

Rekurzia (Recursion)

Zamysleli ste sa niekedy nad tým, čo sa stane, keď funkcia zavolá vo svojom tele samú seba? Vznikne rekurzia :) V informatike je to mocný nástroj, ktorý je využívaný v mnoho algoritmoch, napríklad pri prehľadávaní do hľbky (DFS) či triedenie zlievaním (merge sort).

Triedenie (Sorting)

V programoch veľmi často potrebujeme prvky utriediť, teda zoradiť ich zostupne alebo vzostupne. Napríklad čísla podľa veľkosti, reťazce lexikografiky (abecedne), atď. Existuje celé spektrum algoritmov, od "kvadratických" (s časovou zložitosťou $O(n^2)$), ako napríklad bublinkové triedenie (bubble sort) až po tie efektívne s časovou zložitosťou $O(n \log n)$, napríklad triedenie zlievaním (merge sort).

Pozor: V nasledovných úlohách nie je cieľom použiť knižničné triediace algoritmy, napríklad sort() v C++ a Pythone. Práve naopak, ide o to vyskúšať si naimplementovať vlastný sort() :)

Rýchle umocňovanie (Exponentiating by squaring)

Ak chceme vypočítať $a^b$, môžeme spraviť for-cyklus od 1 po $b$ a postupne prinásobovať $a$. Časová zložitosť takéhoto prístupu je $O(b)$. Existuje však aj rýchlejší spôsob, ktorý má časovú zložitosť $O(\log n)$ :)

Predstavte si, že do jedného z vrcholov grafu začneme pumpovať vodu, ktorá sa začne propagovať grafom. Ak na chvíľu pozabudneme na princípy hydrodynamiky, bude platiť, že voda sa dostane do každého miesta grafu tou najkratšou cestou. Pritom sa rozteká do každého smeru, do šírky. Toto je základná myšlienka prehľadávania do šírky, ktoré slúži okrem veľa iného napríklad aj na hľadanie najkratších ciest v neohodnotenom grafe.

Prvočíselnosť a Eratotenovo sito (Primality and Sieve of Eratosthenes)

Prvočisla sú čísla, ktoré sú deliteľné iba $1$ a sami sebou. V tejto časti sa dozviete, ako rýchlo overiť, či je zadané číslo prvočíslo. Tiež zájdeme do histórie, ukážeme si algoritmus na hľadanie prvočísel v zadanom intervale. Jeho vznik sa pripisuje matematikovi Eratosthenovi, ktorý žil ešte pred našim letopočtom. Asi vtedy netušil, že raz bude jeho algoritmus patriť do povinnej výbavy akýchsi informatikov.

Úvod do geometrie

Ako zistiť či sa dve úsečky pretínajú? Aký je obvod daného telesa? Alebo ako vlastne také geometrické útvary reprezentovať v pamäti? To všetko a ešte trochu viac sa dozvieš v tejto kapitole. Podstatné pojmy sú: skalárny súčin (dot product), vektorový súčin (cross product), obsah (surface area), a obvod (perimeter).

Čas poslednej úpravy: 7. október 2022 23:07