Algoritmy I

Anotace předmětu

Tento předmět je jedním z úvodních kurzů programování. Předmět si klade za cíl seznámit studenty s technikami algoritmického řešení problémů. Probírané algoritmy a datové struktury budou demonstrovány v jazyce C++. Studenti jsou vedeni k analýze algoritmizovaných problémů a k syntéze řešení z menších celků.

Garant předmětu

Garantem předmětu je doc. Mgr. Jiří Dvorský, Ph.D.

Prerekvizity

• Předmět Algoritmy I nemá žádné prerekvizity, předpokládá se znalost středoškolské matematiky a obecná orientace ve výpočetní technice.
• Předmět Algoritmy I je sám povinnou prerekvizitou navazujícího předmětu Algoritmy II. 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í v pondělí od 12:30 do 14:00 v učebně UA1 (s možností přesunu do učebny EC1).
• Níže uvedená témata přednášek budou rozdělena do jednotlivých přednášek na celý semestr.

Témata přednášek:

1. Organizační informace k předmětu Algoritmy I
2. Úvod
1. Co je to algoritmus
2. Základy algoritmického řešení problémů
3. Důležité typy problémů
4. Fundamentální datové struktury
3. Analýza složitosti algoritmů
1. Základy analýzy složitosti algoritmů
2. Asymptotické notace složitosti
3. Analýza nerekurzivních algoritmů
4. Analýza rekurzivních algoritmů
4. Strategie řešení problémů hrubou silou a úplným prohledáváním
1. Třídění výběrem a bublinové třídění
2. Sekvenční vyhledávání
3. Vyhledávání podřetězce hrubou silou
4. Problém nejbližší dvojice bodů
5. Konvexní obal množiny
6. Úplné prohledávání -- problém obchodního cestujícího a problém batohu
7. Průchod grafem do šířky
8. Průchod grafem do hloubky
5. Strategie řešení sniž a vyřeš
1. Třídění vkládáním
2. Topologické třídění
3. Generování permutací a podmnožin
4. Vyhledávání půlením intervalu
5. Hledání mediánu
6. Interpolační vyhledávání
7. Vyhledávání a vkládání do binárního vyhledávacího stromu
6. Strategie řešení rozděl a panuj
1. Třídění sléváním
2. QuickSort
3. Průchody binárním stromem
4. Násobení velkých celých čísel a násobení matic
5. Problém nejbližší dvojice bodů
6. Konvexní obal množiny

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 ověřování Vašich znalostí.
• Cvičení nenahrazuje přednášku. Cvičící není povinnen látku na začátku cvičení znovu probírat, studenti musí být na cvičení aspoň minimálně připraveni. 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.
• 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.

Docházka

• Účast na přednáškách je doporučená.
• 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,
• lze získat, mimo jiné, zvýšenou časovou dotaci na úkoly,
• Je vysoce žádoucí, aby student, který dostane zvýšenou časovou dotaci na úkoly, neprodleně kontaktoval svého cvičícího a garanta předmětu, abychom předešli případným problémům a nedorozuměním.
• 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!

Individuální konzultace

• 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 a tak dále, je možné si domluvit individuální konzultaci.
• Konzultaci je nutné si domluvit předem, nejlépe pomocí emailu.
• Pokud potřebujete poradit s učivem, připravte si materiály, které jste si k tématu prostudovali, vypište si co je Vám jasné a kde jste se "zasekli" a potřebujete poradit.

---

Úkoly a jejich hodnocení

Hodnocení v předmětu Algoritmy I 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

• Zadání projektů, včetně rozdělení projektů mezi studenty, a testovací data.
• 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 se bude psát ve zkouškovém období.
• Všechny termíny budou vypsá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ří na první pokus 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

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

---

Studijní literatura

Povinná literatura

1. LEVITIN, Anany., [2012]. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson. ISBN 978-0-13-231681-1.
2. 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.
3. SEDGEWICK, Robert, [2003]. Algoritmy v C. Praha: SoftPress. ISBN 80-864-9756-9.
4. MAREŠ, Martin a Tomáš VALLA, [2017]. Průvodce labyrintem algoritmů [online]. Praha: CZ.NIC, z.s.p.o. [cit. 2021-04-19]. CZ.NIC. ISBN 978-80-88168-19-5.
5. WRÓBLEWSKI, Piotr, [2015]. Algoritmy. Brno: Computer Press. ISBN 978-80-251-4126-7.
6. WIRTH, Niklaus, 1988. Algoritmy a štruktúry údajov. Bratislava: Alfa. ISBN 063-030-87.

Doplňková literatura

1. STROUSTRUP, Bjarne, [1997]. C++ programovací jazyk. Praha: Softwarové Aplikace a Systémy. ISBN 80-901-5072-1.
2. VIRIUS, Miroslav, [2005]. Pasti a propasti jazyka C++. 2., aktualiz. a rozš. vyd. Brno: CP Books. ISBN 80-251-0509-1.
3. SCHILDT, Herbert, [2001]. Nauč se sám C++: [poznej, vyzkoušej, používej]. Praha: SoftPress. ISBN 80-864-9713-5.
4. ECKEL, Bruce, [2000]. Myslíme v jazyku C++. Praha: Grada. Knihovna programátora (Grada). ISBN 80-247-9009-2.

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.

---

Software pro výuku

Vývojové prostředí pro C++

• Na učebnách je pro výuku k dispozici Microsoft Visual Studio 2022.
• Pro domácí přípravu si stáhněte Visual Studio Community 2022.
• Při hodnocení Vašich projektů bude používán překladač Microsoft Visual C++ a specifikace jazyka C++17, který je součástí vývojového prostředí Visual Studio Community 2022.
• Pokud si pro domácí přípravu stáhnete Visual Studio Code, či jiné prostředí, a budete používat překladač GNU C++ (g++), vyhněte se prosím nestandardním rozšířením jazyka C++, které zavádí tento překladač.

Ostatní software

Další software, který se Vám bude hodit při tvorbě Vašich programů:

• Dokumentační systém Doxygen
• Typografický systém LaTeX

---