|
předmět
|
KMI/ALGO1 - Algoritmy 1 a KMI/ALGO Algoritmizace - ZS 2022/2023
|
|
vyučující
|
přednášející: Radim Bělohlávek,
http://belohlavek.inf.upol.cz/
cvičící: Arnošt Večerka, Tomáš Urbanec, Eliška Foltasová
|
|
č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.
|
|
22. 9. 2022
|
-
Ú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.
-
Slajdy str. 5-44.
|
|
29. 9. 2022
|
-
Algoritmus pro hledání nejkratší cesty a důkaz jeho nesprávnosti.
-
Euklidův algoritmus a jeho správnost.
-
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. 45-71.
|
|
6. 10. 2022
|
-
Pole.
Třídění.
-
Algoritmus Insertion Sort a jeho složitost.
-
Algoritmus Selection Sort a jeho složitost.
-
Slajdy str. 1-27.
-
O-notace a asymptotický růst funkcí.
Slajdy str. 28-46.
|
|
13. 10. 2022
|
-
Algoritmus Bubble Sort, jeho varianty a jeho složitost.
-
Algoritmus Quick Sort a jeho složitost.
-
Slajdy str. 46-76.
|
|
20. 10. 2022
|
|
|
27. 10. 2022
|
|
|
3. 11. 2022
|
|
|
10. 11. 2022
|
-
Výzkum na katedře informatiky
-
Těžké problémy a NP-úplnost.
|
|
24. 11. 2022
|
|