Úvodní přednáška předmětu

doc. Mgr. Jiří Dvorský, Ph.D.Prezentace ke dni 10. května 2021

Katedra informatikyFakulta elektrotechniky a informatikyVŠB – TU Ostravacba

1/37

Osnova přednášky

Úvodní přednáška předmětu

O předmětu Algoritmy I

Prezenční forma studiaVýuka

Úkoly a jejich hodnocení

Kombinovaná forma studiaVýuka

Úkoly a jejich hodnocení

Software pro výuku

Studijní literatura

2/37

Úvodní přednáška předmětuO předmětu Algoritmy I

O předmětu Algoritmy I

UpozorněníVšechny aktuální informace k předmětu naleznete na

http://www.cs.vsb.cz/dvorsky/

Tato prezentace slouží jen pro účely úvodní přednáškya nebude dále aktualizována.

3/37

O předmětu Algoritmy I

• základní strategie algoritmického řešení úloh,• algoritmy budou demonstrovány v jazyce C++,• vazba na předmět Úvod do programování.

4/37

Rozsah předmětu, způsob zakončení

Rozsah předmětu

• výuka probíhá v letním semestru prvního ročníkubakalářského studia

• hodinová dotace:• 2 hodiny přednášky a 2 hodiny cvičení týdně v prezenčníformě a

• 6 tutoriálů v kombinované formě studia• předmět je ohodnocen 4 kredity

Zakončení – klasifikovaný zápočet

• klasifikovaný zápočet není zkouška, řídí jinými pravidly,• prostudujte si proto Studijní a zkušební řád pro studiumv bakalářských a magisterských studijních programech.

5/37

Garant předmětu, přednášející, tutor komb. formy

doc. Mgr. Jiří Dvorský, Ph.D.Kancelář: EA441Email: jiri.dvorsky@vsb.czWeb: www.cs.vsb.cz/dvorsky

K čemu je garant předmětu?Garant předmětu zodpovídá za průběh výuky celéhopředmětu, průběh cvičení, plnění úkolů na cvičenícha za korektní hodnocení úkolů. Problémy spojené se cvičenímiřešte primárně se svým cvičícím. Nepodaří-li dosáhnoutřešení problému s cvičícím obracejte se na garanta předmětu.

6/37

Prerekvizity

• Prerekvizity jsou souhrnem požadavků, které je nutnésplnit, aby si student mohl zapsat předmět. Prerekvizityjsou buď formální nebo věcné.

• Formální prerekvizity – žádné• Věcné prerekvizity:

• znalosti z předmětu Úvod do programování,• středoškolské matematiky a• obecná orientace ve výpočetní technice.

• Předmět Algoritmy I je ale povinnou prerekvizitounavazujícího předmětu Algoritmy II.

7/37

Docházka

Přednášky

• jsou obecně nepovinné• účast na nich je doporučená

Cvičení

• jsou naopak povinná,• účast a aktivita na cvičeních jsou hodnoceny,• je nutno získat dostatečné bodové hodnocení.

8/37

Studenti se specifickými nároky

Centrum Slunečnice FEI

• http://slunecnice-fei.vsb.cz/,• poskytuje podporu zpřístupňující studium i pro studentyse specifickými nároky,

• lze získat, mimo jiné, zvýšenou časovou dotaci na úkoly.

VýzvaJe vysoce žádoucí, aby studenti, kteří dostanou tuto zvýšenoučasovou dotaci, neprodleně kontaktovali svého cvičícíhoa garanta předmětu, abychom předešli případnýmproblémům!

9/37

Individuální studijní plán

Individuální studijní plán umožňuje, v odůvodněnýchpřípadech, individuální termíny pro plnění studijníchpovinností.Výzva

• Je vysoce žádoucí, aby studenti, kteří získají individuálnístudijní plán, neprodleně kontaktovali svého cvičícíhoa garanta předmětu a dohodli se na individuálníchtermínech plnění úkolů.

• Individuální studijní plán neznamená naprostou libovůliv termínech.

• Individuální studijní plán už vůbec neznamená možnostvybrat si úkoly, které budu plnit a které ne.

10/37

Konzultace

• Pokud nebudete ve výuce něčemu rozumět, potřebujetes čímkoliv poradit nebo vyřešit nějaký probléms přednáškou, cvičeními, testy, Vaší absencí na výuce atd.je možné využít si domluvit individuální konzultaci.

• Konzultaci je nutné si domluvit předem, nejlépe emailemnebo přes chat v MS Teams.

• 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ámjasné a kde jste se „zasekli“ a potřebujete poradit.

• Konzultací s vyučujícím nic neriskujete – maximálně sedozvíte co potřebujete.

• Přijďte se zeptat rovnou ke zdroji informací – internetováfóra jsou zaplevelena různými polopravdami i naprostýminesmysly.

11/37

Algoritmy I – výuka, úkoly a jejich hodnocení pro různé formystudia

• Prezenční a kombinované studium má specifickou formuvýuky.

• Obě formy studia mají specifické podmínky pro splněnípředmětu.

• Podle formy Vašeho studia se Vás týká pouze jedna zedvou následujících částí prezentace.

12/37

Úvodní přednáška předmětuPrezenční forma studia

Přednášky

• Přednášky jsou plánovány každý čtvrtek 12:30 do 14:00v prostředí MS Teams, případná prezenční výuka pakv učebně EC1.

• Témata přednášek:1. Úvodní přednáška2. Algoritmus. Strategie řešení problémů pomocí algoritmů.Významné typy řešených problémů.

3. Analýza složitosti algoritmů.4. Strategie řešení problémů hrubou silou. Třídění výběrem,bublinové třídění. Sekvenční vyhledávání. Konvexní obalmnožiny bodů. Nalezení nejbližší dvojice bodů.

5. Strategie řešení úplným prohledáváním. Problémobchodního cestujícího. Problém batohu. Průchody grafem.

13/37

Přednášky (pokrač.)

6. Strategie řešení sniž a vyřeš. Třídění vkládáním. Generovánípermutací a podmnožin. Vyhledávání půlením intervalu.Nalezení mediánu. Interpolační vyhledávání. Vyhledávánía vkládání do binárního vyhledávacího stromu.

7. Strategie řešení rozděl a panuj. QuickSort. MergeSort.Konvexní obal množiny bodů. Nalezení nejbližší dvojicebodů.

• Výše uvedená témata přednášek budou pochopitelněrozdělena do jednotlivých přednášek na celý semestr.

14/37

Cvičení

• Přímá výuka ve cvičeních odpovídá přednáškám.• Ve cvičeních pracují studenti pod vedením cvičícího nakonkrétní implementaci příkladů v jazyce C++.

• Dále je také možné konzultovat s cvičícím probírané učivo.• Rozdělení do cvičení tak, jak je uvedeno v informačnímsysté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émuEdison.

• Až na výjimky, nelze psát testy na jiných cvičeních, nežkterá máte zapsaná v Edisonu.

15/37

Cvičení (pokrač.)

• Cvičení nenahrazuje přednášku!• Neočekávejte, že pokud nebudete chodit na přednášky, takVám cvičící na cvičeních bude dělat jakousi bleskovounáhradní přednášku, abyste se vůbec mohli pustit dopří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, aleje nutné se orientovat v základních pojmech. Jinak cvičenínemají smysl.

16/37

Úkoly

• Hodnocení v předmětu Algoritmy I se skládá ze tří částí,úkolů:1. průběžné aktivity na cvičeních,2. obhajoby projektu a3. závěrečné písemné práce.

• Všechny úkoly jsou povinné.• Z každého úkolu je nutné získat aspoň minimální početbodů.

17/37

Úkoly – 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šeaktivita. Aktivita je hodnocena pomocí barevného kódu:

• zelená – student na cvičení pracoval aktivně, v látce seorientoval, dařilo se mu implementovat zadané úkoly,

• oranžová – student na cvičení byl spíše pasivní, na cvičenínebyl příliš připraven (ve znalostech měl „mezery“),implementace úkolů se příliš nedařila a

• červená – student na cvičení byl zcela pasivní, o výukunejevil zájem, implementaci úkolů nezvládl. Do tétokategorie spadá i neomluvená neúčast na cvičení.

18/37

Úkoly – průběžná aktivita na cvičeních (pokrač.)

• Každému barevnému kódu odpovídá určitá váha, která seprojeví v celkovém hodnocení všech cvičení. Zelenáaktivita má váhu 1, oranžová má váhu 0,5 a červená 0.

• Z takto získaných vah z jednotlivých cvičení se na koncisemestru vypočte průměrná váha, která se vynásobímaximálním možným počtem bodů (30) a výsledek je Vámizískaný počet bodů.

• Je zřejmé, že všechny zelené kódy odpovídají maximálnímupočtu bodů (30), samé červené kódy odpovídají nulovémupočtu bodů.

• Body za aktivitu nelze získat zpětně.

19/37

Úkoly – průběžná aktivita na cvičeních (pokrač.)

PříkladStudent Franta na pěti cvičeních získal zelené hodnocení, natřech oranžové a na dvou červené. Průměrnou váhuvypočtene jako:

5 × 1 + 3 × 0, 5 + 2 × 05 + 3 + 2 = 6, 5

10 = 0, 65.

Výsledné bodové hodnocení je tedy 0, 65 × 30 = 19, 5 bodů.

20/37

Úkoly – obhajoba projektu

• Zadání projektu bude zveřejněno na webu předmětupřibližně koncem března 2021.

• Deadline pro odevzdání je 7. května 2021 ve 23:59.• Způsob odevzdání stanoví jednotliví cvičící.• Obhajoby projektů proběhnou v zápočtovém týdnu a vezkouškovém období. Harmonogram obhajob jev 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.

21/37

Úkoly – závěrečná písemná práce

• je zaměřena na teoretické znalosti,• proběhne ve zkouškovém období, buď formou online testunebo prezenčně.

• Podrobnosti budou upřesněny v závislosti na aktuálnísituaci.

22/37

Hodnocení úkolů

• Je nutné splnit všechny výše uvedené úkoly,• a zároveň u všech úkolů aspoň minimální počet bodů.

Počet bodůÚkol minimum maximumPrůb. aktivita na cvičeních 15 30Obhajoba projektu 15 30Písemná práce 21 40Celkový počet bodů 51 100

23/37

Úvodní přednáška předmětuKombinovaná forma studia

Tutoriály

1. tutoriál – 12. února 2021 povinný• Na tomto úvodním tutoriálu Vám budousděleny informace o organizaci studiapředmětu a informace o náplni předmětu.

• Konzultace k tématům: Algoritmus. Strategieřešení problémů pomocí algoritmů.Významné typy řešených problémů.

2. tutoriál – 26. února 2021• Konzultace k tématům: Analýza složitostialgoritmů.

24/37

Tutoriály (pokrač.)

3. tutoriál – 13. března 2021• Konzultace k tématům: Strategie řešeníproblémů hrubou silou. Třídění výběrem,bublinové třídění. Sekvenční vyhledávání.Konvexní obal množiny bodů. Nalezenínejbližší dvojice bodů.

4. tutoriál – 26. března 2021• Konzultace k tématům: Strategie řešeníúplným prohledáváním. Problém obchodníhocestujícího. Problém batohu. Průchodygrafem.

25/37

Tutoriály (pokrač.)

5. tutoriál – 16. dubna 2021• Konzultace k tématům: Strategie řešení sniža vyřeš. Třídění vkládáním. Generovánípermutací a podmnožin. Vyhledávání půlenímintervalu. Nalezení mediánu. Interpolačnívyhledávání. Vyhledávání a vkládání dobinárního vyhledávacího stromu.

6. tutoriál – 14. května 2021• Konzultace k tématům: Strategie řešení rozděla panuj. QuickSort. MergeSort. Konvexní obalmnožiny bodů. Nalezení nejbližší dvojicebodů.

26/37

Úkoly

• Hodnocení v předmětu Algoritmy I se skládá ze tří částí,úkolů:1. průběžné aktivity na tutoriálech,2. obhajoby projektu a3. závěrečné písemné práce.

• Všechny úkoly jsou povinné.• Z každého úkolu je nutné získat aspoň minimální početbodů.

• Další informace o jednotlivých úkolech budou k dispozicina webu tutora.

27/37

Úkoly – průběžná aktivita na tutoriálech

Průběžná aktivita na tutoriálech znamená:

• účast na tutoriálech a

• průběžné plnění úkolů zadaných na jednotlivýchtutoriálech.

28/37

Úkoly – obhajoba projektu

• Zadání projektu bude zveřejněno na webu předmětupřibližně koncem března 2021.

• Deadline pro odevzdání je 7. května 2021 ve 23:59.• Způsob odevzdání a další náležitosti budou upřesněny nawebu tutora.

• Obhajoby projektů proběhnou v zápočtovém týdnu a vezkouškovém období. Termíny budou vypsány v systémuEdison.

• 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.

29/37

Úkoly – závěrečná písemná práce

• je zaměřena na teoretické znalosti,

• proběhne ve zkouškovém období, buď formou online testunebo prezenčně.

• Podrobnosti budou upřesněny v závislosti na aktuálnísituaci.

30/37

Hodnocení úkolů

• Je nutné splnit všechny výše uvedené úkoly,• a zároveň u všech úkolů aspoň minimální počet bodů.

Počet bodůÚkol minimum maximumPrůb. aktivita na tutoriálech 10 20Obhajoba projektu 15 30Písemná práce 26 50Celkový počet bodů 51 100

31/37

Úvodní přednáška předmětuSoftware pro výuku

Software pro výuku

Primární software

• Vývojové prostředí pro C++• Dokumentace k C++

Doplňkový software

• Dokumentační systém Doxygen, www.doxygen.org• Typografický systém LATEX, www.ctan.org

32/37

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

• Vývojové prostředí Visual Studio 2019 firmy Microsoft,spolu s integrovaným překladačem, bude užíváno jednakpro výuku a jednak jako referenční překladač přihodnocení Vašich projektů.

• Vývojové prostředí Visual Studio 2019 je k dispozici vedvou verzích

• Visual Studio Professional 2019• Visual Studio Community 2019

33/37

Vývojové prostředí pro C++ (pokrač.)

Visual Studio Professional 2019

• azureforeducation.microsoft.com/devtools• licence je určena pouze pro školní účely• tato verze je i na učebnách katedry

Visual Studio Community 2019

• visualstudio.microsoft.com/cs/free-developer-offers/

• licence není vázaná na školu

34/37

Úvodní přednáška předmětuStudijní literatura

Studijní literatura

Studijní literaturu lze rozdělit do dvou skupin:

• povinná literatura – strategie algoritmického řešeníproblémů a

• doporučená literatura – programovací jazyk C++.

Níže uvedenou literaturu využijete v předmětu AlgoritmyI i Algoritmy II.

35/37

Povinná literatura

1. LEVITIN, Anany. Introduction to the Design and Analysis ofAlgorithms. 3rd ed. Boston: Pearson, 2012. ISBN978-0-13-231681-1.

2. CORMEN, Thomas H. Introduction to algorithms. 2nd ed.Cambridge, Mass.: MIT Press, 2001. ISBN 02-620-3293-7.

3. SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003.ISBN 80-864-9756-9.

4. MAREŠ, Martin a Tomáš VALLA, 2017. Průvodce labyrintemalgoritmů [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/

5. WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press, 2015.ISBN 978-80-251-4126-7.

6. WIRTH, N. Algoritmy a štruktúry údajov. Alfa, Bratislava1989. 36/37

Doporučená literatura

1. STROUSTRUP, Bjarne. C programovací jazyk. Praha:Softwarové Aplikace a Systémy, 1997. ISBN 80-901-5072-1.

2. VIRIUS, Miroslav. Pasti a propasti jazyka C. 2., aktualiz.a rozš. vyd. Brno: CP Books, 2005. ISBN 80-251-0509-1.

3. SCHILDT, Herbert. Nauč se sám C: [poznej, vyzkoušej,používej]. Praha: SoftPress, 2001. ISBN 80-864-9713-5.

4. ECKEL, Bruce. Myslíme v jazyku C. Praha: Grada, 2000.Knihovna programátora (Grada). ISBN 80-247-9009-2.

37/37

Děkuji za pozornost

37/37