Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Web page:
https://cw.fel.cvut.cz/wiki/courses/b6b36zal/kombinovane_studium
Anotation:
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.
Study targets:
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ů.
Course outlines:
| 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. |
Exercises outline:
| 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. |
Literature:
Doporučená literatura:
| 1. | | Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, Second Edition. |
Requirements:
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.
Subject is included into these academic programs:
| Page updated 6.12.2024 17:51:05, semester: Z/2025-6, Z,L/2024-5, Send comments about the content to the Administrators of the Academic Programs |
Proposal and Realization: I. Halaška (K336), J. Novák (K336) |