Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023

Základy algoritmizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah
B0B36ZAL Z,ZK 6 2P+2C+8D
Předmět nesmí být zapsán současně s:
Základy algoritmizace (B6B36ZAL)
Přednášející:
Jiří Vokřínek (gar.)
Cvičící:
Jiří Vokřínek (gar.), Ladislav Serédi
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 2022/2023:
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
místnost T2:H1-130
Serédi L.
16:15–17:45
(přednášková par. 1
paralelka 104)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Serédi L.
18:00–19:30
(přednášková par. 1
paralelka 106)

Dejvice haly
AlgDejvice - Veřejná
Út
místnost T2:H1-130
Serédi L.
07:30–09:00
(přednášková par. 1
paralelka 105)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Serédi L.
11:00–12:30
(přednášková par. 1
paralelka 101)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Serédi L.
16:15–17:45
(přednášková par. 1
paralelka 102)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Serédi L.
18:00–19:30
(přednášková par. 1
paralelka 103)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:D3-309
Vokřínek J.
12:45–14:15
(přednášková par. 1)
Dejvice
T2:D3-309
St
Čt

Rozvrh na letní semestr 2022/2023:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 30. 1. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6626406.html