460-2003/02 – Algoritmy II (ALG II)
Garantující katedra | Katedra informatiky | Kredity | 5 |
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í | Povinnost | povinný |
Ročník | 1 | Semestr | letní |
| | Jazyk výuky | čeština |
Rok zavedení | 2013/2014 | Rok zrušení | 2019/2020 |
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
Cílem předmětu je seznámit studenty s objektově orientovaným programováním a rozvinout znalosti studentů do oblasti datových struktur. Po absolvování předmětu bude student schopen:
analyzovat zadaný problém z pozice OOP,
vytvořit a odladit program C++ s využitím OOP,
využívat binární stromy a hašovací tabulky,
posoudit efektivitu zvoleného řešení daného problému.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Tento předmět je pokračováním předmětu Algoritmy I. V tomto kurzu bude kombinován výklad objektově orientovaného programování s představením dalších často používaných datových struktur - binárních stromů a hašovacích tabulek. OOP je chápáno spíše směrem ke zvládnutí implementace nejrůznějších tabulek, seznamů s operacemi vkládání, následného vyhledávání a rušení elementů, než směrem k návrhu komplexnějších systémů. Tento cíl bude naplněn v kurzech zabývajících se softwarovým inženýrstvím.
Povinná literatura:
Doporučená literatura:
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Realizace a obhajoba projektu.
Programování jednoduchých aplikací na cvičeních.
E-learning
Další požadavky na studenta
U studentů se předpokládá znalost středoškolské matematiky a uživatelská znalost počítačů.
Prerekvizity
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Náplň přednášek
Úvodní přednáška - organizační záležitosti, souhrn nutných znalostí z předmětu Algoritmy I
Lineární datové struktury - abstraktní datové struktury, zásobník, fronta, seznam
Dynamická alokace paměti - pointery, operátory reference, dereference, alokování a dealokování paměti
Spojová implementace lineárních datových struktur - využití OOP a dynamicky alokovaných struktur
Grafy - základní pojmy, graf jako datová struktura, možnosti implementace grafu
Algoritmy průchodů grafem - průchod grafu do hloubky a do šířky, aplikace průchodu grafem
Binární vyhledávací stromy I - základní pojmy, vyhledávání
Binární vyhledávací stromy II - vkládání, rušení vrcholů, průchody stromem
Vyvážené a vícecestné stromy - AVL-stromy, red-black stromy. B-stromy
Hašování - hašovací tabulky, metody řešení kolizí
Vyhledávání v textu - vyhledávání jednoho a více vzorků, elementární lexikální analýza textu
Jednoduchý překladač - překlad aritmetických a logických výrazů, postfixová notace a její interpretace pomocí zásobníku
Techniky řešení problémů - rozděl a panuj, žravý algoritmus, dynamické programování
Náplň počítačových cvičení
Opakování z předmětu Algoritmy I
Implementace zásobníku, fronty, seznamu v poli
Dynamická alokace paměti
Spojová implementace seznamu
Grafy, možnosti implementace grafů
Průchody grafem
Binární stromy
Využití hašovacích tabulek
Vyhledávání v textu
Překladač založený na rekurzivním sestupu
Náplň projektů
Zadání projektů budou směřovat ke zvládnutí OOP.
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