Cvičení z Programování 2

Aktuální informace naleznete na konci stránky

Obecné informace

Jedná se o cvičení k předmětu Programování 2 (NMIN102). Moje cvičení je 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).
Cvičení probíhá v pondělí od 9:50 v učebně K11.
Oficiální stránky předmětu a látku probíranou na přednáškách (včetně slajdů) najdete na stránkách 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

Ú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 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 už za ni žádné body nedostanete, proto doporučuju ř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ě semestru, 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í

Organizační záležitosti. Podmínky pro získání zápočtu a bodování úloh - viz výše.
Cvičení na rekurzi - vypsání všech podmnožin množiny {1,2, ..., n}
Třídění - připomenutí základních algoritmů

2. cvičení

Složitost algoritmů
- připomenutí definice složitosti a O-notace
- porovnávání složitosti algoritmů - příklad
Halda a práce s ní, heapsort
Třídění
- přehled algoritmů a jejich vlastností
- více např. zde

3. cvičení

Třídění - dokončení
- quicksort - krokování, složitost, volba pivota
- mergesort - krokování, vhodné případy použití
- radixsort, bucketsort - krokování, vhodné případy použití

4. cvičení

Dynamicky alokovaná paměť - úvod
- výhody a nevýhody dynamicky alokované paměti
- co se skutečně děje v paměti počítače
- lineární spojový seznam jako příklad dynamické datové struktury
Typické situace a problémy při použití ukazatelů
- více totožných objektů, rovnost ukazatelů x rovnost objektů
- více ukazatelů na stejný objekt
- ztráta ukazatele na objekt
Práce se spojovým seznamem
- přidání prvku na konec seznamu
- nalezení k-tého prvku
Domácí úkol
- Úlohy v CodExu
- Reprezentace množiny
Byly zadané úlohy celkem za 170 bodů. 60% z toho je 102 bodů. Více o bodování zde, seznam zadaných úloh zde.

5. cvičení

Práce se spojovým seznamem
- přidávání, odebírání prvků
- vypsání a zrušení seznamu
- rekurzivní návrh procedur pro práci se spojovým seznamem
- nalezení prostředního prvku pomocí pouze dvou ukazatelů
Domácí úkol
- Úlohy v CodExu
Byly zadané úlohy celkem za 300 bodů. 60% z toho je 180 bodů. Více o bodování zde, seznam zadaných úloh zde.

6. cvičení

Testík
binární vyhledávací stromy
- popis, použití, složitost operací
- různé varianty
- nevyvážené stromy - přidání a mazání prvků
- dokonale vyvážené stromy, konstrukce, vhodné a nevhodné použití
Domácí úkol
- Úlohy v CodExu
Byly zadané úlohy celkem za 330 bodů. 60% z toho je 198 bodů. Více o bodování zde, seznam zadaných úloh zde.

7. cvičení

nevyvažované binární vyhledávací stromy - dokončení
předávání argumentů procedurám a funkcím
- předávání hodnotou a odkazem , rozdíly a vhodné způsoby použití
- předávání odkazem při práci s ukazateli
AVL stromy
- popis, použití, složitost operací
- příklad
- rotace při přidávání
Domácí úkol
- Úlohy v CodExu
Byly zadané úlohy celkem za 400 bodů. 60% z toho je 240 bodů. Více o bodování zde, seznam zadaných úloh zde.

8. cvičení

B-stromy
- popis, použití, příklad přidávání do stromu
Dynamické programování
- úvod, motivace
- ukázkový příklad
- obecný návrh algoritmů dynamického programování
Domácí úkol
- Grafová hra
- Úlohy v CodExu
Byly zadané úlohy celkem za 450 bodů. 60% z toho je 270 bodů. Více o bodování zde, seznam zadaných úloh zde.

Zbylá cvičení souhrně:

správné řešení úkolu Grafová hra viz Stochastic two-player games
předávání parametrů odkazem a hodnotou
Dynamické programování
- Dokončení a složitější příklady
- Prodejce aut
Grafové algoritmy
- různé reprezentace grafu, jejich výhody a nevýhody
- hledání cest v ohodnoceném grafu
- Algoritmus Dijkstrův a Floyd-Warshallův
  - srovnání, krokování na příkladu
  - složitost
  - předpoklady, vhodné a nevhodné způsoby použití
- Algoritmy pro hledání minimální kostry grafu
  - připomenutí algoritmů, jejich složitost
  - krokování na příkladu
  - aplikace
- zmíňka o těžkých grafových problémech a jejich aplikacích
Objektově orientované programování
- úvod
  - motivace, vlastnosti, způsoby použití
  - objekty, atributy a metody
- syntaxe v Pascalu
- jednoduché příklady
- Příklad - syntaktický strom algebraického výrazu
  - rozbor problému, objektový návrh řešení, implementace
  - Počáteční šablona zde, hotové řešení zde (jedna z možností)
Hraní her
- Vlastnosti her, příklady
- Shannonova věta
- Maticové hry
  - definice a vlastnosti
  - čisté a smíšené strategie, Nashovo equilibrium
  - příklad hry s nulovým součtem - Kámen, nůžky, papír. S nenulovým součtem - vězňovo dilema.
Kombinatorické hry
- opakování základních pojmů
  - kombinatorické hry a jejich vlastnosti
  - vyhrávajicí strategie, AND-OR graf
  - strom hry a jeho prohledávání
- algoritmus Minimax
  - krokování na příkladu
  - složitost
- Alfa-Beta prořezávání
  - fungování, krokování na příkladu
  - složitost
- Techniky pro zrychlení prohledávání a zvýšení výkonu
  - odhad hodnoty pozice, metoda okénka
  - správné pořadí tahů
  - iterativní prohlubování
  - problém horizontu a jeho řešení
- další informace např. zde

Informace k zápočtům:

Bodový limit pro získání zápočtu je 270 bodů
Pokud někomu chybí body, můžete nějaké získat za bonusové úlohy:
- Bonusové úlohy v CodExu
- Amortizovaná složitost
- Objektová implementace datové struktury
- Zoo
Seznam všech zadaných úloh je 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.
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 září. Termín už není možné nijak posouvat, protože v říjnu začíná nový semestr!)
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.

Pro dohodnutí termínu předvedení programu prosím použijte rezervační systém na adrese trunda.youcanbook.me. Kdyby vám žádný z vypsaných termínů nevyhovoval, ozvěte se emailem.