Algoritmy I

Prezenční studium

Anotace předmětu

Výuka

Úkoly a jejich hodnocení

Studijní literatura

Software pro výuku

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


Výuka

Přednášky

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í

Docházka

Individuální konzultace


Ú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

Obhajoba projektu

Závěrečná písemná práce

Počet bodů na prvním termínuOpravný termín
0 až 9NE
10 až 20ANO
více než 21není 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ích1530
Obhajoba projektu1530
Závěrečná písemná práce2140
Celkem51100

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 z přednášek nejsou studijním materiálem. Slouží přednášejícímu jako osnova jeho výkladu a studentům jako přehled probrané látky. Pročtení těchto několika prezentací není možné považovat za dostatečnou přípravu. 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++

Ostatní software

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