Anotace předmětu
Předmět navazuje na obdobný předmět Algoritmy I. Náplní předmětu jsou další strategie algoritmického řešení úloh (dynamické programování, hladové algoritmy atd.) a typické příklady jejich užití.
Garant předmětu
Garantem předmětu je doc. Mgr. Jiří Dvorský, Ph.D.
Prerekvizity
- Předmět Algoritmy II má jako povinnou prerekvizitu předmět Algoritmy I. To znamená, že bez úspěšného ukončení předmětu Algoritmy I nelze ukončit ani předmět Algoritmy II i když máte předmět Algoritmy II zapsán.
Výuka
Přednášky
Přednášky probíhají každé úterý 10:45 až 12:15 v učebně EC1.
Témata přednášek
Níže uvedená témata přednášek budou rozdělena do jednotlivých přednášek na celý semestr.
- Úvodní přednáška
- Strategie řešení transformuj a vyřeš
- Záměna paměťové a časové složitosti
- Dynamické programování
- Hladové algoritmy
- Strategie řešení iterativním zlepšováním
- Meze možností algoritmického řešení problémů. P, NP a NP-úplné problémy.
- Zdolávání mezí možností algoritmického řešení problémů
Cvičení
- Ve cvičeních pracují studenti pod vedením cvičícího na konkrétní implementaci příkladů v jazyce C++.
- Přímá výuka ve cvičeních odpovídá kapitolám probíraným na přednáškách. V každém cvičení se předpokládá implementace jednoho až dvou příkladů.
- Další náplní cvičení je průběžné ověřování znalostí studentů.
- Dále je také možné konzultovat probírané učivo.
- Cvičení nenahrazuje přednášku. Neočekávejte, že pokud nebudete chodit na přednášky, tak Vám cvičící na cvičeních bude dělat jakousi bleskovou náhradní přednášku, abyste se vůbec mohli pustit do příkladů, jejichž řešení se na cvičení předpokládá. Bývá dobrým zvykem, že studenti se na cvičení aspoň minimálně připraví. Není nutné látku precizně ovládat, ale je nutné se orientovat v základních pojmech. V opačném případě cvičení nemají smysl.
- Účelem cvičení dále není příprava studentů na závěrečnou písemnou práci. Závěrečná písemná práce je zaměřena na teoretické znalosti, které jsou náplní přednášek. Náplň cvičení směřuje k projektu.
- Rozdělení do cvičení, tak jak je uvedeno v informačním systému Edison, je nutné respektovat. Není možné překračovat kapacitu cvičení. Veškeré přesuny je nutné mít zaznamenány v systému Edison. Nelze psát testy na jiných cvičeních, než která máte zapsaná v Edisonu.
Docházka
- Přednášky jsou nepovinné, nicméně účast se doporučuje.
- Naopak cvičení jsou povinná. Neúčast je nutno řádně omluvit.
- Studenti se specifickými nároky
- Na fakultě funguje Slunečnice FEI, centrum pro studenty se specifickými nároky.
- Centrum poskytuje podporu zpřístupňující studium i pro studenty se specifickými nároky
- Jako formu podporyje možné získat i zvýšenou časovou dotaci na úkoly.
- Pokud máte jakoukoliv úlevu, neprodleně kontaktujte svého cvičícího a garanta předmětu. Vyučující nemají k dispozici žádné seznamy studentů zahrnutých do tohoto programu.
- Individuální studijní plán - pokud student získá individuální studijní plán, je opět vysoce žádoucí, aby neprodleně kontaktoval svého cvičícího a garanta předmětu a dohodl se s nimi na individuálních termínech plnění úkolů. Individuální studijní plán neznamená naprostou libovůli v termínech!
Konzultační hodiny
- Pokud na přednášce nebudete něčemu rozumět, potřebujete poradit s probíranou látkou, potřebujete vyřešit nějaký organizační problém s přednáškou, cvičeními, testy, Vaší absencí na výuce atd. je možné využít konzultační hodiny.
- V tento čas jsem připraven věnovat se Vám osobně.
- Žádám Vás ale o dodržení několika pravidel:
- Konzultaci je nutné si domluvit předem, nejlépe emailem. Důvod je zcela prostý - pokud se na konzultaci nahrne najednou 50 studentů, tak se to nedá organizačně zvládnout.
- Pokud potřebujete poradit s učivem, přineste si sebou materiály, které jste si k tématu prostudovali, vypište si co je Vám jasné a naopak, kde jste se zasekli a potřebujete poradit.
Úkoly a jejich hodnocení
Hodnocení v předmětu Algoritmy II se skládá ze tří částí: průběžné aktivity na cvičeních, obhajoby projektu a závěrečné písemné práce. Všechny části jsou povinné a je nutné z každé části získat aspoň minimální počet bodů.
Průběžná aktivita na cvičeních
- Tato část hodnocení probíhá průběžně po celý semestr.
- Na každém cvičení bude cvičícím ohodnocena Vaše aktivita. Aktivita je hodnocena pomocí barevného kódu:
- zelená - student na cvičení pracoval aktivně, dařilo se mu implementovat zadané úkoly.
- oranžová - student na cvičení byl spíše pasivní, implementace úkolů se příliš nedařila.
- červená - student na cvičení byl zcela pasivní, o výuku nejevil zájem, implementaci úkolů nezvládl. Do této kategorie spadá i neomluvená neúčast na cvičení.
- Každému barevnému kódu odpovídá určitá váha, která se projeví v celkovém hodnocení všech cvičení. Zelená aktivita má váhu 1, oranžová má váhu 0,5 a červená 0.
- Celkový počet bodů za cvičení vypočteme jako 30*(součet vah z jednotlivých cvičení)/počet vah. Vzorec je možno vyjádřit slovně jako "30 krát průměrná váha z cvičení". Je zřejmé, že všechny zelené kódy odpovídají maximálnímu počtu bodů (30), samé červené kódy odpovídají nulovému počtu bodů.
- Body za aktivitu nelze získat zpětně.
Obhajoba projektu
- Zde si můžete stáhnout zadání projektů a testovací data.
- Deadline odevzdání je 10. prosince 2023.
- Způsob odevzdání stanoví jednotliví cvičící.
- Obhajoby projektů proběhnou v zápočtovém týdnu a ve zkouškovém období. Harmonogram obhajob je v kompetenci cvičících.
- Bez ohledu na to, kdy proběhnou obhajoby projektů platí, že se obhajuje verze, která byla odevzdána do deadlinu.
- Na obhajobu projektu není možný opravný termín.
Závěrečná písemná práce
- Závěrečná písemná práce proběhne ve zkouškovém období.
- Termíny budou zveřejněny v systému Edison.
- Opravný termín na závěrečnou písemnou práci je poskytován jen těm studentům, kteří u svého prvního pokusu získali aspoň 10 bodů.
| Počet bodů na prvním termínu | Opravný termín |
| 0 až 9 | NE |
| 10 až 20 | ANO |
| více než 21 | není nutný, úspěch |
- Závěrečnou písemnou práci máte možnost psát celkem dvakrát, jinak řečeno máte nárok na jednu opravu. Předmět je ukončen klasifikovaným zápočtem. Nevztahuje se tudíž na něj požadavek dvou oprav, jak to vyžaduje studijní řád u zkoušky.
- Žádné další opravy nejsou možné.
Hodnocení úkolů
Pro absolvování předmětu je potřeba splnit všechny výše uvedené úkoly. A zároveň u všech úkolů je nutné získat aspoň minimální počet bodů.
| | Minimální počet bodů | Maximální počet bodů |
| Průběžná aktivita na cvičeních | 15 | 30 |
| Obhajoba projektu | 15 | 30 |
| Závěrečná písemná práce | 21 | 40 |
| Celkem | 51 | 100 |
Obecné pokyny ke všem úkolům
- U všech úkolů jste povinni se prokázat svou studentskou kartou nebo jiným oficiálním dokladem totožnosti. Bez prokázání totožnosti Vám nebude výsledek započítán.
- Každý prohřešek vůči studijnímu řádu u testů a písemné práce bude nekompromisně postihován. Jde především o opisování, plagiátorství, a záměnu studentů.
- Je zakázáno zadání testů, písemek atd. kopírovat, fotit mobily, fotoaparáty, skenovat či jakkoliv jinak kopírovat, rozmnožovat, sdílet elektronickým způsobem a podobně.
- Předmět je ukončen klasifikovaným zápočtem. Nevztahuje se tudíž na něj požadavek dvou oprav, jak to vyžaduje studijní řád u zkoušky.
Studijní literatura
Povinná literatura
- LEVITIN, Anany., 2012. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson. ISBN 978-0-13-231681-1.
- CORMEN, Thomas H., 2001. Introduction to Algorithms. 2nd ed. Cambridge, Mass.: MIT Press. ISBN 02-620-3293-7.
- CORMEN, Thomas H., Charles Eric LEISERSON, Ronald L. RIVEST a Clifford STEIN, [2022]. Introduction to algorithms. Fourth edition. Cambridge, Massachusetts: The MIT Press. ISBN 978-026-2046-305.
- SEDGEWICK, Robert, 2003. Algoritmy v C. Praha: SoftPress. ISBN 80-864-9756-9.
- MAREŠ, Martin a Tomáš VALLA, 2017. Průvodce labyrintem algoritmů [online]. Praha: CZ.NIC, z.s.p.o. [cit. 2020-10-03]. CZ.NIC. ISBN 978-80-88168-19-5. Dostupné z: https://knihy.nic.cz/
- WRÓBLEWSKI, Piotr, 2015. Algoritmy. Brno: Computer Press. ISBN 978-80-251-4126-7.
- WIRTH, Niklaus, 1988. Algoritmy a štruktúry údajov. Bratislava: Alfa. ISBN 063-030-87.
Doplňková literatura
- STROUSTRUP, Bjarne, 1997. C++ programovací jazyk. Praha: Softwarové Aplikace a Systémy. ISBN 80-901-5072-1.
- VIRIUS, Miroslav, 2005. Pasti a propasti jazyka C++. 2., aktualiz. a rozš. vyd. Brno: CP Books. ISBN 80-251-0509-1.
- SCHILDT, Herbert, 2001. Nauč se sám C++: [poznej, vyzkoušej, používej]. Praha: SoftPress. ISBN 80-864-9713-5.
- ECKEL, Bruce, 2000. Myslíme v jazyku C++. Praha: Grada. Knihovna programátora (Grada). ISBN 80-247-9009-2.
Software pro výuku
Vývojové prostředí pro C++
- Na učebnách je pro výuku k dispozici Microsoft Visual Studio Community 2022, dále jen VS2022.
- Toto vývojové prostředí doporučuji si stáhnout i pro domácí přípravu. Obecně lze ale použít jakékoliv vývojové prostředí a kompilátor podporující minimálně specifikaci C++17.
- Vývojové prostředí VS2022 a s ním dodávaný překladač jazyka C++ bude užíváno jednak pro výuku a jednak jako referenční překladač při hodnocení Vašich případných projektů, domácích úkolů a jiných zdrojových kódů, které budete odevzdávat. Jinak řečeno, veškerý Vámi vytvořený software musí s tímto překladačem bezchybně pracovat. Není v silách vyučujících prověřovat funkčnost Vašich projektů v různých operačních systémech, vývojových prostředích, s různými kompilátory a verzemi knihoven!
- Obzvláště upozorňuji na nestandardní rozšíření jazyka C++ v překladači GNU, například jde o deklaraci pole s nekonstantní velikostí.
Ostatní software
Další software, který se Vám bude hodit při tvorbě Vašich programů:
Ostatní učební materiály
Prezentace z přednášek
- Prezentace k předmětům Algoritmy I a Algoritmy II si můžete stáhnout na této stránce.
- Prezentace z přednášek však nejsou studijním materiálem. Závěrečná písemná práce může obsahovat otázky z celého obsahu příslušných kapitol knihy A. Levitina, bez ohledu na to zda prezentace existuje nebo, zda je prezentace úplná či nikoliv.