KMI/ALM1 a KMI/ALGO 1 – Algoritmy 1
Zápočet
Pro získání zápočtu je potřeba se účastnit cvičení (online) a odevzdat následující úkoly na email jiri.balun01@upol.cz do 20.12.2020. Jako předmět emailu uveďte "ALGO1_úkol" a do přílohy dejte zdrojové soubory, které pojmenujte ve formátu prijmeni_jmeno1.c pro první úkol a prijmeni_jmeno2.c pro druhý úkol (odevzdávejte pouze soubory s příponou .py).
- Implementujte v jazyce python algoritmy Insertion-sort, Quick-sort a Heap-sort a vypište následující vyplněné tabulky pro pole náhodných hodnot (v rozsahu 0 až 1000) o velikosti 10, 100, 1000 a 10000 prvků:
Počet porovnání
Alg. \ Počet prvků 10 100 1000 10000 Insertion-sort Quick-sort Heap-sort Počet výměn
Alg. \ Počet prvků 10 100 1000 10000 Insertion-sort Quick-sort Heap-sort poznámka: pro náhodné číslo v pythonu lze použít funkci randint z modulu random. V níže uvedeném příkladu se tato funkce nejprve importuje (import je potřeba uvést na začátku zdrojového kódu), následně ji použijeme s hodnotami 0 a 1000 (výsledkem je náhodné číslo od 0 do 1000) a tuto hodnotu vypíšeme pomocí funkce print.
from random import randint print(randint(0,1000))
- Implmentujte v jazyce python algoritmy pro následující problémy. Do komentáře k funkci ještě napište časovou složitost vašeho řešení v nejhorším případě (oboustrannou mez) a jednou větou ji zdůvodněte:
- V poli je uloženo n čísel. Napište v funkci, která vrátí True, jsou-li všechna čísla vzájemně různá (žádné číslo se v poli nevyskytuje vícekrát), False v opačném případě.
- Pro zadané čísla A a B vypište posloupnost, která začne číslem A a následující prvky se sníží vždy o hodnotu B. Pokud by následující prvek měl být menší než 0, začne posloupnost růst o hodnotu B. Algoritmus končí, když vypíše podruhé hodnotu A. Například pro vstup A=10, B=3 algoritmus vypíše: 10,7,4,1,4,7,10). Navrhněte iterativní (cykly) i rekurzivní algoritmus.
Vizualizace třídících algoritmů
- Insertion Sort
- Selection Sort
- Bubble Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Counting Sort
- Radix Sort
- Bucket Sort
Procvičení procesu algoritmizace
- iBot – jednoduchá hra
- základy pseudokódu (autor: RNDr. Arnošt Večerka)
- project Euler – obsáhlá sbírka pokročilých úloh, která je užitečná pokud se budete někdy během studia nudit (většina úloh je opravdu složitá, takže je doporučuji řešit až pozdějších fázích studia)
Seznam cvičení
-
opakování základních pojmů: množiny, posloupnosti a funkce
- vlastnosti posloupností – rostoucí/klesající, omezenost
- aritmetická posloupnost – příklady, vzorec pro n-tý člen a součet prních n členů
- geometrická posloupnost – příklady, vzorec pro n-tý člen a součet prních n členů
- vlastnosti funkcí – rostoucí/klesající, omezenost, sudá/lichá, prostá
- elementární funkce a jejich vlastnosti – lineární, kvadratická, kubická, exponenciální
-
opakování základních pojmů a základy pseudokódu
- elementární funkce a jejich vlastnosti – logaritmická, druhá odmocnina, faktoriál a inverzní funkce
- základy pseudokódu – příkazy přiřazení, větvení, cykly a funkce, viz dokument základy pseudokódu (autor: RNDr. Arnošt Večerka)
- pseudokódy funkcí – signum, absolutní hodnota, modulo, faktoriál a spočítejPole (funkce pro sečetení všech hodnot v poli)
-
časová složitost algoritmu, odkaz na video
- pojem časové složitosti – v nejhorším případě a v průměrném případě
- časová složitost algoritmů – funkce Swap, JeNovýRok2000, JeNeklesající a NejvětšíMocninaDvojky
- 1. úkol – zamyslete se nad složitostí algoritmu pro splnitelnost logické formule, která má k výrokových symbolů
- 2. úkol – nasimulujte si algoritmus Insertion-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
-
Asymptotické meze a selection sort, odkaz na video
- definice asymtotických mezí – horní, dolní a oboustranná mez
- příklady použití asymptotických mezí – na příklady algoritmu JeNeklesající z minul0ho zvičení
- Selection-sort – demonstrace algoritmu
- 1. úkol – podívejte se na video základy pythonu: video
- 2. úkol – nasimulujte si algoritmus Selection-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
- 3. úkol – zamyslete se v jakém vztahu jsou jednotlivé asymptotické meze elementárních funckí n, n2, n3, loga n, n loga n, 2n a n!
- 4. úkol – vyzkoušejte si online interpret pythonu a zkuste v něm implementovat algoritmus je_neklesajici (oveří, že hodnoty v poli jsou neklesající) a pokud se vám bude dařit, pak zkuste insertion-sort
-
Ostré asymptotické meze a nejhorší a nejlepší/nejhorší případy, odkaz na video
- definice ostrých asymtotických mezí – horní a dolní ostrá mez a příklady použití
- nejlepší/nejhorší případy vstupních dat – algoritmy insertion-sort, selection-sort a bubble-sort
- 1. úkol – nasimulujte si algoritmus bubble-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
- 2. úkol – rozhodněte, které vztahy platí: 2n² ∈ ω(n²), 2ⁿ ∈ o(n!), log₈(n) ∈ ω(log₂(n))
- 3. úkol – zkuste v pythonu implementovat algoritmus bubble-sort a jeho variantu, která si pamatuje místo poslední výměny
-
Rekurze, odkaz na video
- rekurzivní funkce faktoriál – rozdíl oproti iterativnímu řešení
- quicksort – časová složitost v nejlepším a nejhorším případě
- výpočet Fibonacciho čísla – výpočet horní meze
- 1. úkol – nasimulujte si algoritmus quick-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
- 2. úkol – vyřešte složitost rekurzivní funkce faktoriálu (pomocí rekurentní rovnice)
- 3. úkol – nalezněte dolní mez rekurzivní funkce pro výpočet Fibonacciho čísla (podle videa)
- 4. úkol – napište pseudokód rekurzivního algoritmu JeNeklesající a zkuste jej implementovat
-
Merge-Sort a Counting-Sort, odkaz na video
- Merge-Sort – idea algoritmu a jeho časová složitost
- Counting-Sort – idea algoritmu a jeho časová složitost
- 1. úkol – nasimulujte si algoritmus merge-sort krok po kroku (podle pseudokódu) pro nějaké malé pole a zkuste jej imlementovat
- 2. úkol – nasimulujte si algoritmus counting-sort krok po kroku (podle pseudokódu) pro nějaké malé pole a zkuste jej imlementovat
-
Heap-Sort, odkaz na video
- Heap-Sort – idea algoritmu a jeho časová složitost
- 1. úkol – nasimulujte si algoritmus heap-sort krok po kroku (podle pseudokódu) pro nějaké malé pole (třeba příklad z videa)
- 2. úkol – Popřemýšlejte, jestli by šlo (a případně jak) navrhnout algoritmus obdobný heap sortu, který by místo max haldy využival min haldu (tj hodnota rodiče je menší rovna hodnotám potomků).
-
Radix-sort a Bucket-sort, odkaz na video
- Stabilní třídění – popis vlastnosti
- Radix-Sort – idea algoritmu a jeho časová složitost
- Bucket-Sort – idea algoritmu a jeho časová složitost
- 1. úkol – nasimulujte si algoritmus radix-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
- 2. úkol – nasimulujte si algoritmus bucket-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
- 3. úkol – Popřemýšlejte, které z dosud představených třídících algoritmů jsou stabilní
-
Master theorem, odkaz na video
- Master theorem – znění, příklady
- Pořádkové statistiky – idea algoritmu a příklad
- 1. úkol – nachystejte si dotazy na poslední cvičení v zápočtové týdnu (k čemukoliv co jsme probírali v průběhu semestru)