|
předmět
|
KMI/AGO1 - Algoritmy 1 a KMI/ALGO Algoritmizace - ZS 2020/2021
|
|
vyučující
|
přednášející: Radim Bělohlávek,
http://belohlavek.inf.upol.cz/
cvičící: Arnošt Večerka, Tomáš Urbanec, Jiří Balun
|
|
čas a místo
|
čtvrtek 8:00 - 10:30, LP-2001 (přednáška)
|
|
studijní materiály
|
|
slajdy a další materiály
|
Budou umísťovány na této stránce.
|
|
doporučená literatura
|
Viz popis předmětu.
|
|
|
absolvování předmětu
|
Zápočet: Zápočet bude udělen vyučujícím, který vede cvičení.
Pro získání zápočtu musí student získat alespoň 60% bodů ze
zadaných úkolů (1 písemný test v druhé polovině semestru, 1 implementace algoritmu).
Zkouška: Ústní v termínech vypsaných v systému STAG.
Před zahájením zkoušky musí mít student zápočet.
Student obdrží otázky a bude mít cca 20 min na přípravu (tužka a papír).
Pak půjde k ústnímu zkoušení (cca 25 min).
Je třeba znát látku v rozsahu probíraném na přednáškách a cvičeních. Tj.:
-
Probrané pojmy (problém, algoritmus, složitost, O-notace, \dots).
Umět s pojmy pracovat.
-
Probrané algoritmy, jak pracují, umět simulovat činnost algoritmů.
-
Složitosti probraných algoritmů.
-
Porozumět jednoduchému algoritmu zapsanému v pseudokódu.
-
Zapsat v pseudokódu jednoduchý algoritmus.
|
|
1. 10. 2020
|
-
Úvodní informace o předmětu.
Slajdy str. 1-4.
-
Algoritmy, základní úvahy, popis algoritmu, pseudokód.
-
Základní instrukce pseudokódu: přiřazení, aritmetické instrukce a výrazy,
logické instrukce a výrazy, podmíněný příkaz, cyklus for, cyklus while-do, cyklus repeat-until.
-
Správnost algoritmu,
Euklidův algoritmus.
-
Slajdy str. 5-53.
|
|
8. 10. 2020
|
-
Správnost Euklidova algoritmu.
-
Složitost algoritmu, časová a paměťová,
pojem složitosti v nejhorším a průměrném případě,
příklady, typické složitosti.
-
Odvození časové složitosti jednoduchého algoritmu.
Technologický pokrok a složitost algoritmů.
-
Slajdy str. 52-82.
-
Pole.
Třídění.
-
Algoritmus Insertion Sort a jeho složitost.
-
Slajdy str. 1-15.
|
|
15. 10. 2020
|
-
Složitost algoritmu Insertion Sort.
-
Algoritmus Selection Sort a jeho složitost.
-
O-notace a asymptotický růst funkcí.
-
Slajdy str. 1-55.
|
|
22. 10. 2020
|
-
Algoritmus Bubble Sort, jeho varianty a jeho složitost.
-
Algoritmus Quick Sort a jeho složitost.
-
Algoritmus Merge Sort a jeho složitost.
-
Slajdy str. 56--86.
|
|
29. 10. 2020
|
-
Odvození složitosti algoritmu Merge Sort.
-
Algoritmus Heap Sort a jeho složitost.
-
Slajdy str. 87--103.
|
|
5. 11. 2020
|
|
|
12. 11. 2020
|
|
|
19. 11. 2020
|
-
Opakování látky. Požadavky ke zkoušce.
|
|
26. 11. 2020
|
|