Cvičení z Programování 1

Obecné informace

Jedná se o cvičení k předmětu Programování 1 (NMIN101). Moje cvičení jsou primárně určená pro studenty Finanční matematiky, kruhy 60 a 61, ale můžou je samozřejmě navštěvovat i studenti jiných skupin (do vyčerpání kapacity).
Letos povedu dvě cvičení, první z nich se koná ve čtvrtek, od 9:00 do 10:30 a druhé od 10:40 do 12:10 v učebně K11. Začínáme 8. října.
Oficiální stránky předmětu a látku probíranou na přednáškách najdete na stránkách doktora Holana a doktora Pergela.
E-mail na cvičícího:

Požadavky na zápočet

docházka a aktivní účast na cvičení (maximálně 3 absence)
získat dostatek bodů za úlohy v CodExu a za další úlohy zadané ústně na cvičení
naprogramovat a odevzdat zápočtový program
absolvovat zápočtový test na konci semestru

Úlohy v CodExu

CodEx je webová aplikace, která slouží k zadávání úloh z programování, k odevzdávání výsledků a jejich automatickému vyhodnocování (více např. zde).
Pro udělení zápočtu je potřeba získat aspoň 60% bodů z úloh zadaných v CodExu (nebo ústně na cvičení). Úlohy budu zadávat postupně, takže bodový limit pro zápočet není předem známý (bude se zvyšovat s každou další zadanou úlohou). Každá úloha bude mít nastavený termín odevzdání, po termínu ji bude možné stále odevzdat, ale dostanete za ni výrazně méně bodů. Doporučuju proto řešit úlohy včas a snažit se získtat aspoň 60% bodů z každé série úloh. Pokud na začátku větší množství úloh vynecháte, tak hrozí, že později už nebudete schopní ztrátu dohnat. Více informací o úlohách a bodování najdete na zvláštní stránce.

Zápočtový program

Zápočtový program je rozsáhlejší než běžné úlohy v CodExu. Jeho účelem je, abyste si vyzkoušeli samostatně navrhnout a vytvořit větší program včetně načítání vstupů od uživatele, ošetření jejich korektnosti, odladění, napsání dokumentace a podobně. Téma pro svůj program si vybíráte sami (já ho musím schválit). Termín pro schválení tématu je zhruba v polovině listopadu, ještě vás včas upozorním na cvičení. Při výběru témat pro své programy se můžete inspirovat např. na stránkách Martina Mareše.

Co bylo na cvičení

1. cvičení (8. 10. 2015)

Organizační záležitosti
- požadavky na zápočet (viz výše)
- předmět Praktikum z programování
- obsah a cíle cvičení
Logické hry a hlavolamy
- problém s kuličkami a váhami, různé varianty, řešení konkrétních případů, odvození obecného řešení a důkaz jeho optimality
- algoritmický přístup k řešení problémů
Domácí úkol
- vytvořit si účet v labu na Karlíně, abyste mohli používat počítače v učebně

2. cvičení (15. 10. 2015)

Procvičení pojmů z přednášky a některých konstrukcí jazyka Pascal
- pojem algoritmu, jeho vlastnosti
- základní konstrukce programovacího jazyka
- proměnná, typ, hodnota, příkaz IF. Zbytek příště.
Logické hry a hlavolamy 2
- vlastnosti implikace, problém s kartičkami a jeho řešení (některé příklady jsou převzaté z této práce)
- Vězni a čepičky - různé přístupy k řešení, popis optimálního řešení, zobecnění úlohy
Domácí úkol
- Věž na šachovnici
- Vytvořit si účet v labu na Karlíně. Do příštího cvičení musejí mít všichni vytvořený účet!
Byly zadané úlohy celkem za 60 bodů. 60% z toho je 36 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

3. cvičení (22. 10. 2015)

Dokončení některých úloh z minula
Procvičení pojmů z přednášky a některých konstrukcí jazyka Pascal
- proměnné, typování, výrazy různých typů
- for cyklus
Seznámení s vývojovým prostředím jazyka Pascal
- vytvoření jednoduchého programu, kompilace a spuštění
- ovládací prvky vývojového prostředí a jejich význam
Jednoduché úlohy na použití FOR cyklu
- Vypisování hvězdiček na obrazovku v různých tvarech
Domácí úkol
- Vytvořit si účet v CodExu
Byly zadané úlohy celkem za 60 bodů. 60% z toho je 36 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

4. cvičení (29. 10. 2015)

Dokončení některých úloh z minula. Hvězdičky zde
Procvičení pojmů z přednášky a některých konstrukcí jazyka Pascal
- WHILE cyklus, jeho syntaxe a použití. Příklady.
Seznámení s vývojovým prostředím jazyka Pascal
- vytvoření jednoduchého programu, krokování na papíře, v Pascalu
- vstupy a výstupy programu
Domácí úkol
- Kruh z hvězdiček
- Trezor
Byly zadané úlohy celkem za 140 bodů. 60% z toho je 84 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

5. cvičení (5. 11. 2015)

Testík. Zadání a řešení zde
Co je to pole, jak se používá a k čemu je dobré
Jednoduché prográmky pro práci s polem
- jednorozměrné pole
- načtení a vypsání matice, výpočet součtu matic, součinu matic
Domácí úkol
- Úlohy v CodExu
Byly zadané úlohy celkem za 330 bodů. 60% z toho je 198 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

6. cvičení (12. 11. 2015)

Testík a diskuze nad řešením. Zadání a řešení zde
Dokončení úloh z minula - součin matic
Další prográmky pro procvičení práce s polem
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu, poslat mi návrh ke schválení a potom poslat krátkou specifikaci.
Byly zadané úlohy celkem za 365 bodů. 60% z toho je 219 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

7. cvičení (19. 11. 2015)

Diskuze nad řešením úlohy Trezor.
Hornerovo schéma - popis, výhody, příklady použití
Vyčíslení hodnoty polynomu v zadaném bodě.
- rozbor problému, návrh řešení, implementace
- funkce random pro generování testovacích dat
Procedury a funkce
- význam funkcí, výhody použití
- příklady
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu, poslat mi návrh ke schválení a potom poslat krátkou specifikaci.
Byly zadané úlohy celkem za 495 bodů. 60% z toho je 297 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

8. cvičení (26. 11. 2015)

Práce s textovými soubory
- příkazy pro manipulaci se soubory
- vytvoření souboru, zápis do souboru, čtení
Jednoduché příklady
- frekvenční analýza textu
- hledání vzorku v textu
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu, poslat mi návrh ke schválení a potom poslat krátkou specifikaci.
Byly zadané úlohy celkem za 575 bodů. 60% z toho je 345 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

9. cvičení (3. 12. 2015)

Hledání v poli, hledání se zarážkou, hledání v uspořádaném poli, neformální úvod do složitosti algoritmů
Lokální a globální proměnné, parametry funkcí a procedur
- překrývání globálních proměnných lokálními
- předávání řízení při volání procedur a po jejich skončení
Úvod do rekurze
- způsob fungování, jednoduchý příklad
- krokování rekurzivního programu
- základní přístupy k návrhu rekurzivních algoritmů
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu, poslat mi návrh ke schválení a potom poslat krátkou specifikaci.
Byly zadané úlohy celkem za 575 bodů. 60% z toho je 345 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

10. cvičení (10. 12. 2015)

Krokování jednoduché rekurzivní procedury
Strom rekurzivních volání
K čemu může být taky dobrá rekurze
- vyčíslení rekurentní posloupnosti (ale pozor na efektivitu)
- kreslení fraktálů (viz např. L-systémy. můžete vyzkoušet např. zde
Řešení problémů pomocí rekurze
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu, poslat mi návrh ke schválení a potom poslat krátkou specifikaci.
Byly zadané úlohy celkem za 575 bodů. 60% z toho je 345 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

11. cvičení (17. 12. 2015)

Fronta a zásobník, zásobník v rekurzi, efektivita rekurze
Generování variací s opakováním
- rozbor problému, návrh řešení, implementace. Zdrojový kód zde
- odkrokování, sestavení stromu rekurzivních volání
Úvod do prohledávání - příklad číslo 6 ze sbírky
- využití generátoru variací
- souvislosti s řešením dalších typů úloh
Domácí úkol
- Úlohy v CodExu
- Vybrat si téma zápočtového programu (to už by měli mít všichni hotové) a poslat mi krátkou specifikaci.
Byly zadané úlohy celkem za 765 bodů. 60% z toho je 459 bodů. Více o bodování najdete zde, seznam zadaných úloh zde.

12. a 13. cvičení (7. 1. a 14. 1. 2016)

Prohledávání do hloubky a do šířky
- srovnání přístupů, výhody a nevýhody, správné způsoby použití
Úlohy na prohledávání do hloubky a do šířky
Cesta figurami po šachovnici
- rozbor problému, návrh řešení, implementace s využitím fronty
- různé varianty: délka cesty x nalezení cesty, různé figury
Příklad 4 ze sbírky úloh
Šipky a některé další příklady
Domácí úkol
- Úlohy v CodExu
Byly zadané úlohy celkem za 1000 bodů. 60% z toho je 600 bodů. Další úlohy už zadávat nebudu. Pro získání zápočtu je potřeba 600 bodů z úloh. Více o bodování najdete zde, seznam zadaných úloh zde.

Informace k zápočtovému programu:

Podmínkou získání zápočtu je vypracování zápočtového programu. K tomu je potřeba udělat několik kroků:

Domluvit se se mnou na tématu
Poslat krátkou specifikaci
Napsat program na dohodnuté téma
Napsat dokumentaci k programu. Více o psaní dokumentace najdete např. zde. Na ukázku dokumentace se můžete podívat sem Hadi.zip
Poslat mi program, dokumentaci a testovací data a domluvit si termín předvedení
Předvést mi program, ukázat jeho funkce na testovacích datech, popsat jak program pracuje, jaké algoritmy a datové struktury používá. Během předvedení byste měli být schopní program na požádání mírně upravit. (Program byste měli úspěšně předvést nejlépe do konce zkouškového období, nejpozději do konce března. V odůvodněných případech lze termín mírně prodloužit.)
Je možné, že s první verzí vašeho programu / dokumentace / testovacích dat / předvedení nebudu spokojený a budete je muset předělat. Proto nenechávejte předvedení až na poslední chvíli, abyste případné úpravy stihli ještě v termínu.