Algoritmy a datové struktury - Přehled

Digitální kartičky pokrývající základy algoritmizace, datových struktur v C++, rekurze a řadících algoritmů.

Algoritmus (matematická definice)

Předpis konečného počtu kroků, kterými je možno řešit stejnorodé úkoly.

Konečnost

Základní vlastnost algoritmu, která určuje, že postup musí mít konečný počet kroků.

Určitost (determinismus)

Vlastnost algoritmu zajišťující, že každý krok je přesně definován.

Korektnost

Vlastnost algoritmu, díky které pro korektní vstupní data získáme korektní výsledek.

Metoda shora dolů

Metoda návrhu, kdy se zadaný problém postupně dekomponuje na dílčí podproblémy a řešení.

Rekurzní algoritmus

Algoritmus, který volá sám sebe s modifikovanými parametry, dokud nenarazí na ukončení podmínkou.

Iterativní algoritmus

Algoritmus založený na opakování určitého bloku kódu (např. cykly pro třídění v poli).

Přetečení (overflow)

Stav, kdy se hodnota proměnné dostane za hranici rozsahu a velikosti definovaného datového typu.

Ukazatel (pointer)

Specifická proměnná, jejíž hodnotou je adresa místa v paměti jiné proměnné.

Referenční operátor ($\&$)

Operátor v C++ používaný k získání adresy proměnné.

Dereferenční operátor ($*$)

Operátor v C++ používaný k získání hodnoty uložené na dané adrese.

Výčtový typ (enum)

Uživatelsky definovaný typ, kde je množina prvků definována výčtem; v paměti se uchovává jako integer.

Struktura (struct)

Kontejner, který dokáže sdružit více proměnných (členů) různých datových typů do jednoho celku.

Třída (class)

Rozšířený kontejner v OOP, který zapouzdřuje data (atributy) i chování (metody) do jednoho celku.

Objekt (object)

Konkrétní instance třídy vytvořená v paměti (proměnná daného typu třídy).

Zapouzdření (Encapsulation)

Koncept OOP, který váže data a metody dohromady a chrání je před nežádoucími vnějšími vlivy.

Volání hodnotou (Call by Value)

Způsob předávání parametrů, kdy funkce pracuje pouze s kopií původní proměnné.

Volání odkazem (Call by Reference)

Způsob předávání parametrů, kdy funkce dostane adresu původní proměnné a změny se trvale projeví.

Nepřímá rekurze

Stav, kdy funkce A zavolá funkci B a ta ve svém těle následně zpětně zavolá funkci A.

Základní podmínka rekurze (Base case)

Ukončovací podmínka rekurze (triviální případ), bez které by došlo k přetečení paměti (Stack Overflow).

Zásobník (Stack)

Dynamická datová struktura fungující na principu LIFO (Last In First Out).

Fronta (Queue)

Abstraktní datový typ fungující na principu FIFO (First In First Out), otevřený na obou koncích.

Hlídka (sentinel)

Speciální prvek vložený do zřetězeného seznamu, který slouží jako zarážka a urychluje vyhledávací algoritmy.

Binární vyhledávací strom (BST)

Stromová struktura, kde pravá větev obsahuje prvky větší a levá větev prvky menší než hodnota daného uzlu.

Halda (Heap)

Vyvážený binární strom, kde pro každý uzel platí, že jeho rodič nese stejnou nebo vyšší hodnotu než on sám.

Stabilita řazení

Vlastnost algoritmu zachovávat původní relativní pořadí prvků se stejnou hodnotou.

Bubble sort

Kvadratický řadící algoritmus založený na porovnávání sousedních prvků s průměrnou časovou složitostí $\Theta(n^2)$.

Quick sort

Logaritmický řadící algoritmus typu rozděl a panuj s ideální časovou složitostí $\Theta(n \log n)$.

Heap sort

Řazení haldou, jehož časová složitost je vždy $\Theta(n \log n)$ a nezávisí na výchozím uspořádání.