KMI/ALGO – Algoritmizace

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 "ALGO_ú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).

1. 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))

2. 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:
   1. 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ě.
   2. 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í

1. 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í


2. 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)


3. č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


4. 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 minulého zvičení
   • Selection-sort – demonstrace algoritmu
   
   
   • 1. úkol – nasimulujte si algoritmus Selection-sort krok po kroku (podle pseudokódu) pro nějaké malé pole
   • 2. úkol – zamyslete se v jakém vztahu jsou jednotlivé asymptotické meze elementárních funckí n, n², n³, log_a n, n log_a n, 2ⁿ a n!
   • 3. úkol – zkuste v pythonu implementovat algoritmy insertion-sort, selection-sort a funkci je neklesajici (oveří, že hodnoty v poli jsou neklesající)


5. 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


6. 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


7. 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


8. 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ů).


9. 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í


10. 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)