Základy algoritmizace
| Kód | Zakončení | Kredity | Rozsah |
|---|---|---|---|
| B0B36ZAL | Z,ZK | 6 | 2P+2C+8D |
- Vztahy:
- Předmět B0B36ZAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B6B36ZAL (vztah je symetrický)
- Předmět B0B36ZAL může být splněn v zastoupení předmětem B6B36ZAL
- Předmět B0B36ZAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B6B36ZAL (vztah je symetrický)
- Garant předmětu:
- Jiří Vokřínek
- Přednášející:
- Jiří Vokřínek
- Cvičící:
- Ladislav Serédi, Jiří Vokřínek
- Předmět zajišťuje:
- katedra počítačů
- Anotace:
-
Předmět klade důraz na návrh algoritmů, datovou abstrakci a jejich implementaci tak, aby studenti uvažovali o používání výpočetních prostředků algoritmicky a dovedli tak efektivně využít programových prostředků pro zpracování dat. V předmětu je také kladen důraz na osvojení si programovacích návyků pro vytváření čitelných a znovu použitelných programů. Zároveň je snahou vybudovat u studentů nadhled nad implementací algoritmů tak, aby studenti byli schopni zvolit vhodný programovací jazyk pro realizaci konkrétní úlohy a vyhnuli se nevhodné preferenci konkrétního jazyka jen proto, že v něm začínali.
- Požadavky:
-
Pro pochopení přednášené látky (složitost) jsou třeba středoškolské znalosti z matematiky (funkce, polynomy), které lze doplnit z běžně dostupných učebnic.
- Osnova přednášek:
-
1. Úvod do předmětu a organizace předmětu, programovací jazyky vývoj a evoluce.
2. Návrh algoritmu, způsob zápisu, program a jeho struktura. Rozklad problému na pod problémy, funkce, procedury a rekurze. Algoritmus jako prostředek generování výstupu na základě vstupu.
3. Proměnné, výrazy, základní datové typy a jejich reprezentace (číselné soustavy); chyby, přesnost a stabilita výpočtů a zdroje chyb. Reprezentace proměnných, práce se symboly, rozsah platnosti proměnných, číselné soustavy.
4. Programovací styly a kódovací konvence, odhad náročnosti implementace (pravidlo 90/10). Kódovací konvence, volby jmen proměnných a funkcí, metriky náročnosti implementace, tipy pro získání odhadu náročnosti realizace programu.
5. Řídicí struktury, větvení a cykly imperativních programovacích jazyků If-then-else, case, for, while.
6. Datové struktury (pole, řetězce, struktury).
7. Datové struktury (fronta, zásobník, prioritní fronta). Struktura pro reprezentaci fronty a zásobníků, realizace prostřednictvím pole.
8. Práce se soubory a proudy. Zpracování vstupních dat a generování dat výstupních, modely I/O operací.
9. Datové struktury (spojový seznam, asociativní pole, binární strom).
10. Optimalizace kódu, ladění, testování a logování.
11. Praktiky psaní čitelných a dobře použitelných programů (znovu použitelnost kódů).
12. Úvod do vyhledávání a řazení; úvod do složitosti algoritmů a profilování; pravidlo 80/20.
13. Přehled programovacích jazyků: objektové, logické, funkcionální a skriptovací. Přehled s poukázáním na vhodnost konkrétního programovacího jazyka s ohledem na náročnost realizace, jednoduchost používání a především čitelnost a znovu použití.
14. Úvod do překládaných programovacích jazyků (C a Java), překladač, linker, interpret. Přehled C a Java, komparativní ukázka podobnosti syntaxe.
- Osnova cvičení:
-
1. Seznámení se s počítačovou učebnou a vybranými službami fakultní sítě; úvod do vývojového prostředí a způsobu odevzdávání úloh prostřednictvím systému pro správu verzí.
2. Seznámení se se základní syntaxí zvoleného programovacího jazyka.
3. Syntaxe jazyka a implementace jednoduchých úloh. Odladění a odevzdání úloh z předchozího cvičení, zadání a realizace nové(ých) úloh(y).
4. Proměnné, výrazy a základní datové typy, ověření přesnosti výpočtu a datové reprezentace číselných typů. Procvičování výpočtů s různými datovými typy, tipy pro ladění.
5. Řídicí struktury, větvení a cykly. Odevzdání úlohy/programu, který na základě vstupu realizuje podmíněný výpočet / běh v cyklu. Součástí úlohy bude také ošetřování vstupních hodnot.
6. Datové struktury (pole, řetězce). Implementace zpracování pole hodnot a řetězců (pole řetězců), zpracování vstupního souboru dat.
7. Datové struktury (fronta, zásobník). Implementace fronty, zásobníku jako součásti složitější úlohy (výpočtu) na zpracování vstupního souboru dat.
8. Datové struktury (spojový seznam, fronta a zásobník). Spojový seznam - implementace pole, návrh struktury pro realizaci fronty a zásobníku se spojovým seznamem.
9. Datové struktury (prioritní fronta). Prioritní fronta - realizace nad polem s definicí funkcí pro push a pop.
10. Datové struktury (asociativní pole). Asociativní pole - využití pro zpracování vstupního souboru, např. generování tabulek, grafů. Ukázka a ověření náročnosti jednotlivých operací.
11. Datové struktury (binární strom, halda, prioritní fronta). Implementace binárního stromu (případně haldy) a jeho využití pro rychlejší implementaci prioritní fronty.
12. Datové struktury a algoritmy pro zpracování většího objemu dat.
13. Algoritmy řazení. Implementace algoritmu řazení Insert Sort, porovnání náročnosti jednotlivých algoritmů. Profilování.
14. Odevzdání a kontrola úloh.
- Cíle studia:
-
Předmět je orientován na pochopení a osvojení si základních principů návrhu algoritmů a rozvinutí datové abstrakce spolu s osvojením programovacích návyků, tak aby studenti byli schopni efektivně využít zápisu algoritmů prostřednictvím vhodného imperativního programovacího jazyku. Studenti se v předmětu seznámí se základními programovými konstrukty a způsoby vytváření čitelných a znovu použitelných programů pro algoritmické zpracování datových souborů.
- Studijní materiály:
-
Doporučená literatura:
1. Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, Second Edition.
- Poznámka:
- Další informace:
- https://cw.fel.cvut.cz/wiki/courses/b0b36zal/start
- Rozvrh na zimní semestr 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Softwarové inženýrství a technologie - specializace Enterprise systémy (povinný předmět programu)
- Softwarové inženýrství a technologie - specializace Technologie pro multimédia a virtuální realitu (povinný předmět programu)
- Softwarové inženýrství a technologie - specializace Business informatics (povinný předmět programu)
- Softwarové inženýrství a technologie - specializace Technologie internetu věcí (povinný předmět programu)
- Softwarové inženýrství a technologie - společný 1. ročník (povinný předmět programu)