Popis předmětu - B0B36ZAL
B0B36ZAL | Základy algoritmizace | ||
---|---|---|---|
Role: | P | Rozsah výuky: | 2P+2C+8D |
Katedra: | 13136 | Jazyk výuky: | |
Garanti: | Vokřínek J. | Zakončení: | Z,ZK |
Přednášející: | Vokřínek J. | Kreditů: | 6 |
Cvičící: | Serédi L., Vokřínek J. | Semestr: | Z |
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/b0b36zal/startAnotace:
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.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ů.Obsah:
Náplň předmětu je koncipována s důrazem 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. Také z tohoto důvodu bude pro demonstraci vybraných algoritmů použit jednoduchý programovací jazyk, který umožní přímočarou implementaci algoritmů blízkou zápisu v pseudo-kódu. Mezi uvažované kandidáty patří skriptovací jazyky Python, Lua nebo Ruby. Přednášky budou založeny na demonstraci motivačních programů a prezentaci programových konstruktů a implementaci algoritmů dávající do souvislosti teoretické vlastnosti algoritmů s praktickým zápisem poukazující na čitelnost a strukturu zdrojových kódů, reálnou výpočetní náročnost a s tím související nástroje pro profilování a ladění. V závěru semestru budou stručně představeny základní vlastnosti programovacích jazyků Java a C, které budou detailně probírány v navazujících semestrech. Praktická cvičení jsou zaměřena na získání a procvičování programovacích návyků tak, aby byli studenti schopni samostatně vytvářet čitelné kódy a pracovat tak na větších softwarových projektech a ve větších projektových týmech. Z tohoto důvodu bude vyžadováno odevzdání úloh prostřednictvím systému pro správu verzí (např. prostřednictvím fakultní platformy gitlab), který bude odevzdávanou úlohu také automaticky ověřovat a testovat robustnost ošetření vstupních hodnot. V prvních týdnech semestru budou studenti seznámeni s vývojovým prostředím a způsobem odevzdávání úloh. Na následujících cvičeních budou zadávány domácí úlohy vycházející a rozšiřující zadání úloh řešených na cvičení. Rozsah těchto úloh bude volen tak, aby bylo možné úlohy stihnout v rámci dedikované časové dotace domácí práce do příštího cvičení. Pozdní odevzdání (též v případě úloh řešených na cvičení) bude možné s příslušnou bodovou ztrátou, která bude úměrná době odevzdání po termínu. Hlavní motivací těchto úloh je kromě pravidelného programování studenty přimět k průběžné práci a postupnému plnění úloh. Sekundárním cílem je také poskytnout studentům zkušenost s odhadem časové náročnosti implementačních prací, který bude podpořen záznamem historie odevzdávání ze systému pro správu verzí. Studenti budou v průběhu semestru získávat body za odevzdané úlohy a programovací písemky. Bodové hodnocení úlohy se skládá z bodů za správnost a efektivitu kódu, dále pak z bodů zohledňující kvalitu zdrojových kódů, jejich čitelnost a znovu použitelnost.Osnovy 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. |
Osnovy 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. |
Literatura:
Doporučená literatura:1. | Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, Second Edition. |
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.Předmět je zahrnut do těchto studijních plánů:
Plán | Obor | Role | Dop. semestr |
BPSIT_2021 | Před zařazením do oboru | P | 1 |
BPSIT4_2021 | Technologie internetu věcí | P | 1 |
BPSIT3_2021 | Business informatics | P | 1 |
BPSIT2_2021 | Technologie pro multimédia a virtuální realitu | P | 1 |
BPSIT1_2021 | Enterprise systémy | P | 1 |
Stránka vytvořena 8.11.2024 14:51:21, semestry: L/2023-4, Z/2025-6, Z,L/2024-5, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |