Detail předmětu

Algoritmy a datové struktury

FEKT-BPC-ALDAk. rok: 2018/2019

Předmět je zaměřen na získání základních znalostí programovacího jazyka C a programátorských zkušeností prostřednictvím realizace základních typů algoritmů.
Získané znalosti: základy jazyka C, standardní knihovny jazyka, mechanismus správy paměti v jazyce C a ukazatele, složené datové typy jazyka, práce se soubory, návrh vlastních knihoven jazyka, implementace základních algoritmů, programovací styly, kultura správy zdrojových souborů. Seznámení s testováním a hodnocením bezpečnosti programu. Rozšíření a odlišnosti jazyka C pro embedded zařízení, normy jazyka: C99, C1X.

Jazyk výuky

čeština

Počet kreditů

7

Garant předmětu

Ing. Miloslav Richter, Ph.D.

Zajišťuje ústav

Ústav automatizace a měřicí techniky (UAMT)

Výsledky učení předmětu

Absolvent předmětu je schopen:
- provést rozbor úlohy pomocí vývojového diagramu;
- využít standardní algoritmy a navrhnout vlastní za pomoci dále uvedených mechanizmů
- vyjmenovat základní klíčová slova a operátory a umět je použít (vytvořit příklad a vysvětlit jejich základní vlastnosti)
- správně určit datový typ pro daný typ výpočtu (základní datové typy, typ ukazatel na datový typ, a složený datový typ);
- pracovat s dynamicky alokovanou pamětí (získání a uvolnění paměti, manipulace s daty v alokované paměti);
- pracovat se standardními vstupy a výstupy;
- pracovat se soubory;
- využívat základní knihovny jazyka C;
- napsat jednoduchý program pomocí funkcí;
- umí základní algoritmy třídění, vyhledávání, lineární seznamy;
- orientovat se v cizích zdrojových textech, připsat část kódu.

Prerekvizity

Absolvování kurzu BPC-UDP nebo kurzu s podobnou náplní.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování zahrnují přednášky a cvičení na počítači. Předmět využívá www stránky ve spojení s e-learningem (Moodle). Student prokazuje znalosti vypracováním testovacích příkladů na cvičeních.

Způsob a kritéria hodnocení

cca 40b - testy během cvičení na základě probrané látky.
cca 60b - písemné zkoušky, testy.
Konkrétní bodovou kombinaci (do 100bodů) a podmínky pro uspěšné ukončení předmětu stanoví každoročně aktualizována vyhláška garanta předmětu.

Osnovy výuky

1. Organizace kurzu. Popis algoritmu. Jednoduché příklady algoritmů. Rozdělení programu na zdrojové a hlavičkové soubory. Symboly preprocesoru, makra s parametry, ternární operátor.
2. Algoritmy - rozbor úlohy, bloková schémata, volba proměnných. Rekurzivní a nerekurzivní alboritmy. Součásti programu a jeho tvorba. Překlad. Optimalizace. Standardní hlavičkový soubor math.h.
3. Základní datové typy a jejich vlastnosti. ADT. Standardní a formátovaný vstup a výstup. Standardní hlavičkový soubor ctype.h. Práce se soubory.
4. Lineární seznamy, stromy - implementace a využití. Složené datové typy - struktury, uniony. Přístupy k proměnným prvku a přes ukazatel. Pojmy priorita a asociativita operátorů.
5. Bitové operace. Pole jako datový typ - typedef. Ukazatel jako datový typ. Využiti ukazatele jako alias na existující na proměnnou. Pole a ukazatele, ukazatelová aritmetika. Bitové pole jako C datový typ.
6. Stavové automaty. Definice výčtového typu - enum.
7. Grafy. Ukazatel jako parametr a návratová hodnota funkce. Konverze.
8. Algoritmy pro třídění. Dynamická alokace - stdlib.h. Vícerozměrná pole. Pole ukazatelů. Ukazatel na funkce.
9. Prohledávání. Řetězce, zpracování řetězců, práci s řetězci. string.h. Životnost a viditelnost automatických, statických a dynamických proměnných.
10. Zpracování výrazů.
11. Náhodná čísla. Maticové výpočty. Inline funkce. Lineární seznamy, binární stromy.
12. Geometrické a numerické algoritmy. Regrese. Bool, knihovna stdbool.h. Datový typ complex. Literály - pole, struktury.
13. Modifikátory proměnných - const, volatile, restrict. Programovací styly, defenzivní programování. Kultura programování. Nástroje pro dokumentaci a zpravování kódu.

Učební cíle

Cílem předmětu je na základě výuky jazyka C naučit studenty navrhnout a realizovat program či knihovnu funkcí (návrh datové struktury, volání a vazby funkcí, ladění a testování kódu, kultura programování). Na jednoduchých aplikacích vysvětlit principy algoritmizace a design programu.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.

Prerekvizity a korekvizity

Zařazení předmětu ve studijních plánech

  • Program BPC-AMT bakalářský 1 ročník, letní semestr, povinný

  • Program EEKR-CZV celoživotní vzdělávání (není studentem)

    obor ET-CZV , 1 ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Ing. Miloslav Richter, Ph.D.

Osnova

1. Organizace kurzu. Popis algoritmu. Jednoduché příklady algoritmů. Rozdělení programu na zdrojové a hlavičkové soubory. Symboly preprocesoru, makra s parametry, ternární operátor.
2. Algoritmy - rozbor úlohy, bloková schémata, volba proměnných. Rekurzivní a nerekurzivní alboritmy. Součásti programu a jeho tvorba. Překlad. Optimalizace. Standardní hlavičkový soubor math.h.
3. Základní datové typy a jejich vlastnosti. ADT. Standardní a formátovaný vstup a výstup. Standardní hlavičkový soubor ctype.h. Práce se soubory.
4. Lineární seznamy, stromy - implementace a využití. Složené datové typy - struktury, uniony. Přístupy k proměnným prvku a přes ukazatel. Pojmy priorita a asociativita operátorů.
5. Bitové operace. Pole jako datový typ - typedef. Ukazatel jako datový typ. Využiti ukazatele jako alias na existující na proměnnou. Pole a ukazatele, ukazatelová aritmetika. Bitové pole jako C datový typ.
6. Stavové automaty. Definice výčtového typu - enum.
7. Grafy. Ukazatel jako parametr a návratová hodnota funkce. Konverze.
8. Algoritmy pro třídění. Dynamická alokace - stdlib.h. Vícerozměrná pole. Pole ukazatelů. Ukazatel na funkce.
9. Prohledávání. Řetězce, zpracování řetězců, práci s řetězci. string.h. Životnost a viditelnost automatických, statických a dynamických proměnných.
10. Zpracování výrazů.
11. Náhodná čísla. Maticové výpočty. Inline funkce. Lineární seznamy, binární stromy.
12. Geometrické a numerické algoritmy. Regrese. Bool, knihovna stdbool.h. Datový typ complex. Literály - pole, struktury.
13. Modifikátory proměnných - const, volatile, restrict. Programovací styly, defenzivní programování. Kultura programování. Nástroje pro dokumentaci a zpravování kódu.


Cvičení na počítači

39 hod., povinná

Vyučující / Lektor

Ing. Miloslav Richter, Ph.D.
Ing. Ondřej Boštík
Ing. Petr Petyovský, Ph.D.
Ing. Adam Ligocki, Ph.D.
Ing. Tomáš Macho, Ph.D.

Osnova

1 Datový typ pole – práce s poli dat, využití ukazatelů
2 Jednoduché algoritmy – rozbor úlohy, vstupy, výstupy (společný dělitel, výpočet pi,...)
3 Rekurzivní algoritmy a jejich nerekurzivní tvary, srovnání (faktoriál, půlení intervalu ...)
4 Práce se strukturami (základ lineárního seznamu)
5 Základní algoritmy pro práci s lineárními seznamy
6 Binárními stromy (efektivní implementace dekodéru morseovy abecedy).
7 Test 1
8 Bitové operace – nastavení, nulování, změna bitu, maskování (bitové pole a jeho využití pro hledání prvočísel)
Kódování Base64 – rozbor, tvorba koderu a dekoderu. Ošetření chybových stavů.
9 Konečný stavový automat (zpracování souborů – odstranění komentářů, úprava zdrojových textů ...)
10 Zpracování dat, grafy, dynamická alokace paměti
11 Test 2
12 Algoritmy třídění, srovnání algoritmů. Práce s (formátovanými) soubory – načtení a uložení dat.
13 Zpracování informací v řetězcích.