Základy algoritmizace

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

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.

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/b6b36zal/kombinovane_studium

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Softwarové inženýrství a technologie (povinný předmět programu)