Detail předmětu
Algoritmy
FIT-IAL Ak. rok: 2022/2023 Zimní semestr
Přehled základních datových struktur a jejich použití. Časová složitost algoritmů – úvod. Specifikace abstraktních datových typů (ADT). Specifikace a implementace ADT: seznamy, zásobník, fronta, vyhledávací tabulka. Algoritmy nad binárním stromem. Vyhledávání: sekvenční, v neseřazeném a seřazeném poli, vyhledávání se zarážkou, binární vyhledávání, binární vyhledávací strom, vyvážený strom (AVL), stromy s více klíči ve vrcholech. Vyhledávání v tabulkách s rozptýlenými položkami. Řazení, principy, řazení bez přesunu položek, řazení podle více klíčů. Nejznámější metody řazení: Select-sort, Bubble-sort, Heap-sort, Insert-sort a jeho varianty, Shell-sort, Quick sort v rekurzivní a nerekurzivní notaci, Merge-sort, List-merge-sort, Radix-sort. Rekurze a dynamické programování. Vyhledávání podřetězců v textu. Grafové algoritmy. Dokazování programů.
5 kreditů, t.j. cca 125-150 hodin představuje studijní zátěž:
- 39 hodin přednášek
- 26 hodin 2 domácí úlohy
- 35 hodin práce na projektu
- 20 hodin průběžné studium
- 30 hodin příprava na půlsemestrální a závěrečnou zkoušku
Jazyk výuky
čeština
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
- Porozumí základním principům a významu složitosti algoritmů.
- Seznámí se se základními abstraktními datovými typy a strukturami, naučí se je implementovat.
- Naučí se rekurzivní a nerekurzivní zápisy základních algoritmů.
- Seznámí se s různými variantami vyhledávacích tabulek a porozumí jejich vlastnostem.
- Naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
- Student se naučí odborné terminologii v českém i anglickém jazyce.
- Student se naučí vytvářet malé projekty v malém týmu.
- Student se naučí prezentaci a obhajobě výsledků v malém projektu.
- Student porozumí významu metod dokazování správnosti programů a tvorby dokázaných programů.
Prerekvizity
- Znalost základů programování v procedurálně orientovaném programovacím jazyce.
- Středoškolské znalosti z matematiky.
Způsob a kritéria hodnocení
- Domácí úlohy – 20 bodů
- Půlsemestrální písemná zkouška – 14 bodů
- Hodnocený projekt s obhajobou – 15 bodů
- Závěrečná písemná zkouška – 51 bodů; Pro získání bodů ze závěrečné písemné zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 24 body. V opačném případě bude zkouška hodnocena 0 body.
Učební cíle
Student porozumí základním principům složitosti algoritmů a bude je schopen využít při tvorbě programů. Student porozumí základním abstraktním datovým typům a strukturám, naučí se je implementovat a používat. Student se naučí rekurzivní a nerekurzivní zápisy základních algoritmů a bude schopen je využívat při tvorbě programů. Student se naučí vytvářet a analyzovat algoritmy vyhledávání a řazení. Student porozumí základním algoritmům pro vyhledávání v textu a základním grafovým algoritmům. Student se seznámí s rekurzivním způsobem řešení problémů a se základy dynamického programování. Student porozumí principům metod dokazování správnosti programů a znalosti bude schopen používat při tvorbě programů.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:
- U domácí úlohy může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání domácí úlohy.
- Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může svého přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní. Podmínkou pro přistoupení k tomuto termínu zkoušky je zisk alespoň 14 bodů za domácí úlohy a projekt.
- Pokud se student nemůže zúčastnit obhajoby projektu a ostatní členové týmu s tím vysloví souhlas, může získat za obhajobu stejný počet bodů jako na obhajobě přítomní členové týmu.
Použití předmětu ve studijních plánech
Program BPC-AMT: Automatizační a měřicí technika, bakalářský, volitelný
Program BPC-SEE: Silnoproudá elektrotechnika a elektroenergetika, bakalářský, volitelný
Program BPC-EKT: Elektronika a komunikační technologie, bakalářský, volitelný
Program BPC-MET: Mikroelektronika a technologie, bakalářský, volitelný
Program BPC-TLI: Telekomunikační a informační systémy, bakalářský, volitelný
Program B-MAI-P: Matematické inženýrství, bakalářský, volitelný
Program BPC-IBE: Informační bezpečnost, bakalářský, volitelný
Program BPC-AUD: Audio inženýrství, bakalářský
specializace AUDB-TECH: Zvuková technika, volitelný
Program BPC-AUD: Audio inženýrství, bakalářský
specializace AUDB-ZVUK: Zvuková produkce a nahrávání, volitelný
Program IT-BC-3: Informační technologie, bakalářský
obor BIT: Informační technologie, povinný
Program BIT: Informační technologie, bakalářský
specializace BITP: Informační technologie, povinný
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
Vyučující / Lektor
Osnova
- Přehled datových struktur. Časová složitost algoritmů.
- Abstraktní datový typ a jeho specifikace. Specifikace, implementace a použití ADT seznam.
- Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
- Algoritmy nad binárním stromem.
- Vyhledávání, sekvenční, v poli, binární vyhledávání, binární vyhledávací stromy, AVL strom.
- Stromy s více klíči ve vrcholech. Vyhledávání v tabulkách s rozptýlenými položkami.
- Řazení, principy, bez přesunu položek, s vícenásobným klíčem.
- Známé metody řazení polí I
- Známé metody řazení polí II.
- Rekurze a dynamické programování.
- Způsoby hodnocení časové složitosti algoritmů.
- Grafové algoritmy.
- Dokazování správnosti programů.
Projekt
13 hod., povinná
Osnova
- Dvě domácí úlohy – implementace operací vybraných ADT.
- Projekt s miniobhajobou skupiny studentů.