alg_zkouska.md

Aktualizované okruhy ke zkoušce ALG LS 2016 (parttime)

• Časová složitost, prostorová složitost – co to je. Asymptotická notace – co to je, proč ji zavádíme. Definice symbolů O, Ω, Θ, o, ω. Příklad jednoduchého algoritmu a jeho časové a prostorové složitosti.

• Turingův stroj. Co to je (neformálně), definice (formálně). Jednoduchý příklad stroje a jeho výpočtu.

• Rekurze. Co to je, příklady typických rekurzivně zadaných problémů. Příklad vhodného a nevhodného použití rekurze k řešení nějakého problému. Rozděl a panuj – co to je, příklad. Dynamické programování – co to je, příklad.

• Pole. Co to je, základní vlastnosti. Operace nad polem proveditelné a jejich složitosti. Seznam. Co to je, základní vlastnosti. Operace nad seznamem proveditelné a jejich složitosti.

• Zásobník. Co to je, jaké umožňuje operace. Implementace polem a seznamem a složitosti zásobníkových operací při těchto implementacích. Fronta. Co to je, jaké umožňuje operace. Implementace polem a seznamem a složitosti frontových operací při těchto implementacích.

• Bubble sort a Insertion sort. Vlastnosti a popis algoritmu, složitost.

• Heapsort. Datová struktura halda a její vlastnosti. Reprezentace haldy polem. Vlastnosti a popis algoritmu, složitost.

• Merge sort. Vlastnosti a popis algoritmu, úsporné řešení přístupem zdola, složitost.

• Quicksort. Vlastnosti a popis algoritmu, složitost.

• Vyhledávání – vyhledávací datová struktura a operace, které od ní požadujeme. Vyhledávání v seznamu, poli, setříděném poli, složitosti vyhledávacích operací na těchto datových strukturách.

• Binární vyhledávací strom. Definice, vyhledávací operace nad ním. Výška binárního vyhledávacího stromu, složitosti vyhledávacích operací.

• Vyvažované binární vyhledávací stromy – proč, jak. AVL strom – definice, výška, operace insert, delete a jejich složitosti, příklady.

• B-strom. Definice, výška, operace insert, delete a jejich složitosti, příklady.