Sylabus přednášky

• Základy analýzy algoritmů 
  • Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence, verifikace
  • Délka výpočtu, složitost algoritmu, složitost problému. Asymptotická analýza časové a prostorové složitosti, růst funkcí
• Techniky návrhů algoritmů
  • Iterativní algoritmy
  • Rekurzivní algoritmy (rozděl a panuj)
• ​Řadící algoritmy
  • Řazení rozdělováním
  • Řazení slučováním
  • Řazení haldou
  • Dolní odhad složitosti
• Fundamentální datové struktury
  • Seznamy, fronty
  • Binární halda
  • Binární vyhledávací stromy, vyvážené stromy
  • Červeno-černé stromy
  • B-stromy
  • Modifikace datových struktur
  • Hašování
• Základní grafové algoritmy
  • Reprezentace grafů
  • Procházení grafu do hloubky, zúplnění uspořádání, silně souvislé komponenty
  • Procházení grafu do šířky
  • Nejkratší cesty v grafu, Dijkstrův algoritmus, Bellmanův - Fordův algoritmus

Literatura

• ​Povinná
  • T. H. Cormen, C. E. Leiserson,  R. L. Rivest, and C. Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009.
• Doporučená
  • J. Bentley. Programming Pearls (Second Edition). ACM Press 2000.
  • G. Brassard, and P. Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996.
  • T.H. Cormen. Algorithms Unlocked. The MIT Press, 2013.
  • A. Levitin, Introduction to the Design and Analysis of Algorithms. Addison-Wesley, 2003.
  • S. Dasgupta, Ch. Papadimitriou, U. Vazirani: Algorithms. McGraw Hill, 2007.
• ​​​Doplňková
  • J. Kleinberg, and E. Tardos: Algorithm Design. Addison-Wesley, 2006.
• Sbírka příkladů pro cvičení
  • Sbírka
• Slajdy z přednášek (slajdy využívejte jako podklad k vlastním poznámkám z přednášek, nejsou samostatnou studijní literaturou)
  • Přednášky 1 + 2 (složitost, korektnost, rekurze)
  • Přednášky 3 + 4 (řazení)
  • Přednášky 5 + 6 +7 + 8 (datové struktury)
  • Přednášky 9 + 10 (průzkum grafu)
  • Přednášky 11 + 12 (nejkratší cesty)

Pro představu také zveřejňujeme zadání závěrečných praktických testů z loňského roku - viz IS adresář.

Prerekvizity

IB001 Úvod do prog. skrze C || IB111 Úvod do prog. (Python) || IB999 Vstupní test z programování

Předpokládá se, že posluchači mají znalosti v rozsahu předmětů IB001 Úvod do programování skrze C anebo IB111 Úvod do programování skrze Python a v rozsahu předmětu IB000 Matematické základy informatiky. Studenti by měli být schopni používat základní programátorské konstrukce (např. podmínky, cykly, funkce, základní datové typy) a znát několik základních algoritmů. Kromě toho se předpokládá znalost základních matematických konstruktů v rozsahu IB000. Součástí hodnocení předmětu je závěrečný praktický test, realizovaný v jazyce C nebo Python.

Výuka předmětu je realizována jako dvouhodinová přednáška a dvouhodinové cvičení každý týden, navíc bude možné navštívit pravidelné konzultace k implementaci domácích úkolů v programovacím jazyku.

Přednášky

V rámci přednášky budou představeny základní koncepty algoritmizace a vhodné typy datových struktur. Přednáška probíhá v místnosti D3 a je přenášena do místnosti D1.

Cvičení

Na začátku každého cvičení studenti řeší krátký ISový seminární odpovědník (max 5 minut) pro připomenutí základních pojmů z přednášky (projděte si i pojmy v úvodu příslušné kapitoly sbírky příkladů pro cvičení). Získání stanoveného počtu bodů ze seminárních odpovědníků za semestr je nutnou podmínkou absolvování předmětu, proto je nutné na cvičení chodit, chodit včas a znát odpřednášenou látku z minulého týdne. Odpovědník na prvním cvičení se bude věnovat znalostem organizačních pokynů k předmětu. Není dovoleno využívat při vyplňování studijní materiály ani vyplňovat odpovědník vzdáleně, tj. pokud nejste fyzicky přítomni na cvičení. Pokud nemáte zařízení (notebook, chytrý telefon), na kterém můžete odpovědník v ISu vyplnit, dostanete tištěnou verzi, která bude následně scanována. Informujte včas svého cvičícího, pokud budete potřebovat tištěný odpovědník.

Po odpovědníku následuje procvičení učiva na příkladech. Na rozdíl od loňského roku nebudeme programovat na počítačích. Předmět není zaměřen primárně na programování, a proto si na cvičeních vystačíme s pseudokódem. Programování je bráno jako prostředek k hlubšímu pochopení probíraných algoritmů a datových struktur a budou na něj zaměřeny domácí úkoly. Na konci cvičení bude stručně představen domácí úkol, který mají studenti odevzdat do konce následujícího týdne.

Účast na cvičeních je povinná a eviduje se pomocí odpovědníků. V případě omluvené absence doporučujeme navštívit dle možností cvičení v jiný den daného týdne. Zeptejte se však emailem cvičícího, jestli má volno. Pokud student nemůže navštívit jiné cvičení, otevře mu cvičící na začátku následujícího cvičení i starý odpovědník. Všechna cvičení začnou již v prvním týdnu výuky, i ta v pondělí před přednáškou. Ve státní svátky, tj. v pátek 25. března a v pondělí 28. března, cvičení odpadnou - studenti navštíví libovolné cvičení v jiný den daného týdne, případně požádají o otevření odpovědníku na následujícím cvičení.

Do cvičení K21 ve čtvrtek 16:00-17:50 B204 se nepřihlašujte, jedná se o termín konzultací.

Domácí úkoly

Vypracování domácích úkolů není povinné, ale vřele doporučené. Studentům odevzdávajícím domácí úkoly bude snížena hranice pro absolvování u implementační části zkoušky a hlavně se při řešení hodně naučí, takže budou na implementační část zkoušky lépe připraveni.

Zhruba v půlce semestru (ve čtvrtek 31. března) bude speciální domácí úkol, který bude simulovat implementační část zkoušky. Ve večerních hodinách (ve 20:00) bude zveřejněno zadání, jehož řešení budete muset odevzdat do ISu do dvou hodin, tj. do 22:00. Tento úkol bude výjimečný i tím, že ho cvičící opraví a na dalším cvičení se studenty probere nejčastější chyby.

Každé úterý od 10:00 do 12:00 v A420 (Peter Benčík), středu od 12:00 do 14:00 v A420 (Jan Koniarik) a čtvrtek od 16:00 do 18:00 v B204 (Tomáš Novotný) budou probíhat konzultace k domácím úkolům. Pokud máte problém s dokončením implementace příkladů ze cvičení, neváhejte přijít a zeptat se přítomného pedagoga. Velmi vítaná bude i diskuze mezi studenty. Jde o konzultace, pedagog nemá připravený program, zodpovídá dotazy. Studenti přichází s konkrétními dotazy po tom, co sami vyzkoušeli daný problém vyřešit, tj. nepřišli si jen poslechnout rady, jak to udělat, až si k tomu někdy sednou. Pokud jsou termíny konzultací z nějakého důvodu nevyhovující, můžete to konzultovat v diskuzním fóru předmětu. Z toho důvodu se termíny mohou v průběhu semestru měnit.

Seminární odpovědníky

Na začátku každého cvičení studenti řeší krátký ISový odpovědník (max 5 minut), za který lze získat maximálně 2 body. Za špatnou odpověď dostanete záporné body, takže netipujte. Za cvičení se do celkového součtu započítá jen nezáporná hodnota, takže nemůže být horší špatně vyplněný test než absence na cvičení. Při vyplňování odpovědníku není dovoleno využívat studijní materiály ani vyplňovat odpovědník vzdáleně, tj. pokud nejste fyzicky přítomni na cvičení. Za takovéto chování dostanete za daný odpovědník do celkového součtu -5 bodů a získáte osobní zkušenost s řízením před disciplinární komisí.

Pro méně chápavé a právní zástupce:
Je vhodné výsledky průběžně ukládat. Když dokončím odpovídání, potvrdím uložení a pro jistotu si hned prohlédnu odpovědi. V případě problémů okamžitě kontaktuji cvičícího. Studijním materiálem se rozumí i tato osnova. Při vyplňování odpovědníku je student zkoušen, proto nedělá on ani jeho počítač činnosti nesouvisející se zkoušením. Zejména si neprohlíží jiné dokumenty papírové ani elektronické, nestahuje nic ze sítě, nemá otevřená jiná okna v počítači (ani vedlejší tab prohlížeče se slajdy, ani slajdy lokálně stažené v PDF prohlížeči, ani Facebookový chat s kamarádem). Nebaví se s nikým z okolí, neukazuje mu svůj monitor, nedívá se do jeho monitoru. Všechno toto může být vyhodnoceno jako pokus o podvádění. Nebudeme zjišťovat, jestli otevřené PDF je otevřené na nerelevantní stránce, nebude procházet soukromou komunikaci s kamarádem, že se opravdu týkala večerního piva a ve zprávě není zakódována nápověda, nebudeme přihlížet k tomu, že je odpověď špatně, a tak přece nemohla být ze slajdů opsaná...

Nutnou podmínkou pro účast na závěrečné zkoušce je zisk alespoň poloviny z celkového počtu bodů za seminární odpovědníky. Celkový počet bodů za seminární odpovědníky je 26 (13 týdnů výuky), tj. pro úspěšné absolvování předmětu je nutné získat alespoň 13 bodů. V případě omluvené absence nebo v případě, že se cvičení nekonají (státní svátky) a student nemohl navštívit jiné cvičení, otevře cvičící studentovi i starý odpovědník z předchozího týdne.

Závěrečná zkouška

Závěrečná zkouška je složena ze dvou částí (implementační a znalostní).

Implementační část zkoušky se bude konat v den zkouškového termínu dopoledne. Úkolem bude naprogramovat řešení zadaného příkladu rozděleného do jednotlivých úloh. Povolené programovací jazyky jsou C a Python. Při implementační části lze s výhodou využívat vlastní zdrojové kódy z domácích úloh a vlastní domácí přípravy. Nebude povoleno hledání na internetu, ale můžete používat lokálně uloženou dokumentaci. Z implementační části lze získat 50 bodů. K úspěšnému absolvování implementační části je potřeba získat alespoň 25 bodů; pro studenty, kteří v průběhu semestru odevzdali alespoň 75 % rozumně vyřešených domácích úloh do odevzdávárny, je tato hranice snížena na 20 bodů. Domácí úlohy nebudou opravovány průběžně, vyhodnocení bude provedeno jen pro studenty s 20 až 24 body.

Znalostní část zkoušky se bude konat v den zkouškového termínu odpoledne. Tato část bude písemná. Maximální počet bodů, které lze ze znalostní části získat, je 150. K úspěšnému absolvování znalostní části zkoušky je potřeba získat alespoň 75 bodů.

Při neúspěchu v alespoň jedné z částí zkoušky, dostává student hodnocení F a může se přihlásit na opravný termín, pokud na to má dle SZŘ nárok. V opravném termínu již student úspěšně absolvovanou část neopakuje, tj. pokud student neuspěl pouze v jedné části, opakuje jen tuto.

Absolvování a hodnocení

Pro úspěšné absolvování předmětu je nutné získat alespoň 13 bodů za seminární odpovědníky, alespoň 25 (resp. 20, viz výše) bodů z implementační části a alespoň 75 bodů ze znalostní části závěrečné zkoušky.

Výsledné hodnocení závisí na počtu všech získaných bodů, tj. součtu bodů z odpovědníků, závěrečného praktického testu a ze závěrečné zkoušky, a to následujícím způsobem:

>= 203 bodů  --- hodnocení A

>= 180 bodů  --- hodnocení B

>= 157 bodů  --- hodnocení C

>= 134 bodů  --- hodnocení D

>= 108 bodů  --- hodnocení E

<   108 bodů  --- hodnocení F

Přehled probíraných témat k jednotlivým týdnům.

Obsah:

Cvičení se zabývá opakováním znalostí z předmětů Úvod do programování skrze C/Python. Probírají se dynamické datové struktury seznam, fronta a zásobník.

Po tomto cvičení byste měli být schopni používat základní datové struktury, ovládat ukazatele/odkazy a používat vlastní složené datové typy. Pokud máte problém s implementací programovacích příkladů ze cvičení, doporučujeme navštívit konzultace k domácím úkolům. Pokud nezvládnete základní techniky v tomto cvičení, tak vám budou chybět po celý semestr.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Implementační řešení:

• Řešení v C:

• Řešení v Pythonu:

Doplňkové materiály:

Mimo vlastních přednáškových textů a cvičících příkladů přinášíme ještě množství odkazů na doplňkové a externí zdroje (nespravované vyučujícím). V těchto externích zdrojích můžete nalézt množství informací, které vám poskytnou jiný pohled na látku nebo více hlubších vědomostí (ale také někdy mohou být v rozporu s některými našimi pojmy a definicemi - v takovém případě samozřejmě dávejte předost materiálu z přednášky). Ke zvládnutí předmětu nejsou doplňkové informace nutné, ale mohou se hodit.

Obsah:

Cvičení se zabývá dokazováním korektnosti algoritmů, hledáním typických algoritmických chyb a jejich odstraňování. Jsou zadefinovány základní pojmy, které se k dokazování budou požívat během celého semestru.

Po tomto cvičení byste měli být schopni zjistit, zdali je algoritmus korektní (vzhledem k zadaným vstupním a výstupním podmínkám). Pokud je korektní, měli byste tento fakt zvládnout dokázat. Pokud není, umíte uvést příklad vstupu, pro který algoritmus není korektní (a opravit jej).

Implementační zadání:

• Zadání v C

• Zadání v Pythonu

Doplňkové materiály:

Obsah:

Cvičení se zabývá analýzou časové složitosti algoritmů. Porovnáním složitostních tříd a délkou výpočtu.

Po tomto cvičení byste měli být schopni určit složitostní třídu libovolného iterativního algoritmu a měli byste chápat důsledky pro použití.

Implementační zadání:

• Zadání v C

• Zadání v Pythonu

Doplňkové materiály:

Obsah:

Cvičení se zabývá různými přístupy návrhu algoritmů (iterativní přístup, přístup rozděluj a panuj, rekurze) a jejich porovnáním a analýzou složitosti.

Po tomto cvičení byste měli být schopni analyzovat složitost rekurzivních algoritmů, rozdělit problém na podproblémy a řešit ho technikou rozděluj a panuj.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá aplikací různých řadících algoritmů a jejich modifikací podle dat, na kterých se používají. V cvíčení se také probírají algoritmy, které seřazením dat, se kterými pracují, značně sníží svoji složitost.

Po tomto cvičení byste měli být schopni vybrat správný řadící algoritmus pro představený problém. Měli byste mít přehled o tom, jak se řadící algortmy chovají a jakou mají složitost.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Na cvičení se probírá datová struktura binární halda a její použití pro řazení a v prioritních frontách. V praktické části cvičení jsou studenti obeznámeni s implementací operací na binární haldě.

Po tomto cvičení byste měli být schopni implementovat binární haldu a umět ji využít ve správných situacích.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá datovou strukturou binární vyhledávací strom. Algoritmizací vkládání, odstraňování a vyhledávání v binárních vyhledávacích stromech. Jsou probrány různé způsoby průchodu stromem a techniky jejich návrhu (rekurze i iterativní přístup).

Po tomto cvičení byste měli být schopni pracovat s binárními vyhledávacími stromy, měli byste znát jejich využití a měli byste mít ponětí o složitosti průchodů stromy.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá rotacemi k vyvažování stromů a dopadem vyvažování na efektivitu operací na vyhledávacích stromech. Dále se probírá vyvažování pomocí červeno-černých stromů a jejich využitím v praxi.

Po tomto cvičení byste měli být schopni implementovat základní operace na červeno-černých stromech.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá n-árnimi stromy a jejich využitím. Rozvíjí myšlenku vyvážených stromů pomocí B-stromů jako optimální struktury pro ukládání dat na pevné disky.

Po tomto cvičení byste měli být schopni provést základní operace na B-stromech  obecně pracovat s n-árnímy stromy.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá implementací hašovacích tabulek a různými technikami řešení kolizí v nich. Závěr cvičení by měl shrnout dosavadní znalosti z datových struktur a jejich aplikace.

Po tomto cvičení byste měli být schopni zvolit vhodnou hašovací funkci pro vaší aplikaci hašovací tabulky. Celkově byste měli být schopni určit, která ze známých datových struktur se hodí na řešení konkrétního problému.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá základními grafovými algoritmy, tedy průchody do šířky a do hloubky. Průchody se následně aplikují na určování silně souvislých komponent grafu, hledání cyklů a určování typu hran podle průchodu DFS. Grafy jsou reprezentovány buďto maticí vzdáleností, nebo seznamem následníků, studenti se naučí převádět mezi těmito reprezentacemi.

Po tomto cvičení byste měli být schopni identifikovat případy, v nichž se dá zvolit k reprezentaci dat graf. Na grafech byste měli znát průchody do šířky a do hloubky, jejich vlastnosti a užití. Měli byste mít všechny potřebné znalosti pro navazující cvičení, které se zabývá hledáním nejkratší cesty v grafu a hledáním koster.

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá

Po tomto cvičení byste měli být schopni

Implementační zadání:

• Zadání v C:

• Zadání v Pythonu:

Doplňkové materiály:

Obsah:

Cvičení se zabývá

Po tomto cvičení byste měli být schopni

Implementační zadání:

• Zadání v C:
• Zadání v Pythonu:

Doplňkové materiály:

Implementační část zkoušky

• kdo nemáte notebook, hlaste se prosím i na termín do B130 a dostavte se nejpozději 7:50 do této místnosti
• ostatní přijďte nejpozději 7:45 před D1, kde bude viset rozřazení do D1 a D3
• přijďte včas, musíme zkontrolovat ISIC, rozesadit vás, mnozí si budete muset najít zásuvku, vypnout a odložit mobily, zapnout počítač, připojit se do ISu
• v místnostech budou navíc prodlužky, ale nabitý notebook je výhodou

• k implementaci dostanete jeden příklad se 4 úkoly, celkem za 50 bodů
• zadání si stáhnete z IS z učebních materiálů
• k úspěšnému absolvování potřebujete alespoň 20/25 bodů (dle DÚ)
• celkem máte na programování 120 minut
• svoji hotovou implementaci nahrajete do odevzdávárny
• když budete hotoví dřív, můžete skončit dřív, pokud tím nebudete rušit ostatní

• není dovoleno používat internet (výjimky: odkazovaný zobrazovač grafů, stažení zadání a uložení řešení do ISu)
• můžete používat zdrojáky uložené na disku notebooku (v počítačových učebnách použijte sdílené domovské adresáře)
• můžete používat lokálně uložené PDF manuály k programovacím jazykům
• můžete používat lokálně uložené dokumenty všeho druhu (PDF, HTML, sbírka, slajdy ...)
• rada: hledat při zkoušce v cizím zdrojáku je jen ztráta drahocenného času

• vypněte si všechny synchronizace disku, facebookova okna, aktualizace,...
• vypnuté mobily (včetně BT a WiFi) snad ani nemusím zmiňovat
• pokud uvidíme nepovolené okno nebo nepovolený provoz na síti, dostáváte F a jdete před disciplinární komisi

• po implementaci můžete být (emailem) vyzváni k ústnímu pohovoru nad nejasnostmi s Vaším řešením (stejný den, či v termínu dle domluvy)

Znalostní část zkoušky

• dostavte se nejpozději v 11:45 před D1, kde budete rozřazeni do D1 a D3
• po tradiční kontrole začnete nejpozději ve 12:00 psát zkoušku
• znalostní zkoušku řešíte na papír, nejsou povoleny žádné materiály
• na řešení budete mít 100 minut