460-2001/06 – Algoritmy I (ALG I)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | doc. Mgr. Jiří Dvorský, Ph.D. | Garant verze předmětu | doc. Mgr. Jiří Dvorský, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | | |
| | Jazyk výuky | angličtina |
| Rok zavedení | 2019/2020 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Seznámit studenty se technikami řešení problémů pomocí algoritmů. Po absolvování předmětu bude student schopen:
definovat a popsat vybrané techniky řešení problémů pomocí algoritmů,
demonstrovat tyto techniky na ukázkových problémech
využívat tyto techniky pro řešení jiných problémů,
pracovat s kombinacemi několika technik dohromady.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
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, strategiemi, řešení problémů pomocí algoritmů. 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ů.
Povinná literatura:
Doporučená literatura:
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu
Realizace a obhajoba projektu.
Programování jednoduchých aplikací na cvičeních.
Účast na cvičeních.
E-learning
Další požadavky na studenta
U studentů se předpokládá základní znalost jazyka C++ a středoškolské matematiky.
Prerekvizity
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Algoritmus. Strategie řešení problémů pomocí algoritmů. Významné typy řešených problémů.
Analýza složitosti algoritmů.
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ů.
Strategie řešení úplným prohledáváním. Problém obchodního cestujícího. Problém batohu. Průchody grafem.
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.
Strategie řešení rozděl a panuj. QuickSort. MergeSort. Konvexní obal množiny bodů. Nalezení nejbližší dvojice bodů.
Náplň cvičení
Analýza složitosti iterativních algoritmů.
Analýza složitosti rekurzivních algoritmů.
Implementace konvexního obalu množiny bodů. Implementace hledání dvojice nejbližších bodů.
Problém obchodního cestujícího - experimenty s úplným prohledáváním.
Využití průchodů grafem.
Implementace algoritmů pro generování permutací a podmnožin.
Experimenty s vyhledáváním půlením intervalu, interpolačním vyhledáváním. Nalezení mediánu.
Implementace binárního vyhledávacího stromu.
Implementace řešení strategií řešení rozděl a panuj.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.