Stránky cvičení k NMIN102 (Programování 2), kruh 51; letní semestr 2015/16.

O cvičení

Toto cvičení z Programování 2 patří k přednáškám Martina Pergela, je primárně určeno pro kruh 51 a probíhá každé pondělí od 17.20 do 18.50 v učebně K11. Cvičím ho já, tzn. Jonáš Vidra. Kontaktovat mě můžete e-mailem na adrese příjmení@ufal.mff.cuni.cz. Nezdráhejte se mi napsat, pokud máte jakýkoliv problém – nestíháte úkol? Zapomněli jste heslo do CodExu? Nemůžete přijít na písemku nebo na hodinu? Objevili jste chybu v mém výkladu? Něco jste nepochopili? Máte málo bodů? To vše se dá vyřešit, ale musím o tom vědět.

Ujistěte se, že jste do této paralelky zapsáni v SISu a že jste v CodExu přiřazeni do příslušné skupiny. Pokud vás totiž budu chtít kontaktovat, budu používat právě tyto kanály a nezapíšete-li se, nebudete informováni o změnách. Přiřazování do CodExových skupin provádím já; v SISu se zapisujte sami, pokud vám to jde, nebo mi řekněte.

Také je potřeba, abyste se dokázali v laboratoři K11 dostat k funkčnímu počítači s kompilátorem Pascalu. To znamená, že potřebujete login do karlínské sítě nebo vlastní laptop.

Co se probralo

  1. Opakování základů Pascalu: všichni bez problémů zvládáte cykly, funkce, pole, textové řetězce, vstup a výstup.
    Rekurze dělala problémy. Sepsal jsem poznámky k úloze, kterou jsme na hodině dělali. Ujistěte se, že všemu rozumíte a že úlohu dokážete naimplementovat.
  2. Třídění porovnáváním. Tvrdili jste, že umíte hledat v setříděném poli pomocí binárního vyhledávání. Dokázali jsme, že třídění porovnáváním má složitost Θ(n⋅log(n)) a ukázali jsme si, že pokud nebudeme třídit porovnáváním, můžeme se dostat třeba i na lineární složitost (např. omezíme zadání úlohy nebo použijeme jiný výpočetní model). U tabule jsme probrali selectsort (opakovaný výběr minima) a quicksort (rozděl a panuj). Zmínil jsem princip heapsortu (opakovaný výběr maxima pomocí prioritní fronty), counting sortu (lineární složitost pro malá univerza klíčů) a spaghetti sortu (lineární složitost pro „nepočítačový“ výpočetní model). Bez ukázek jsme pak jmenovali insertsort, mergesort a radix sort. Ukázal jsem algoritmus quickselect pro výběr k-tého nejmenšího prvku pracující na podobném principu, jako quicksort (rozmyslete si, proč nejde rozumně použít pro výběr mediánového pivota při quicksortu).
  3. Pointery a alokace paměti. Probrali jsme, jak se alokuje paměť a jak se k ní přistupuje pomocí ukazatele (pointeru). Vytvořili jsme si náš první spoják, uložili jsme do něj posloupnost čísel a pak ji vypsali. Neprocvičili jsme dealokaci, což je škoda, protože ji budete potřebovat v domácím úkolu. Nejtěžší částí 3. DÚ pro vás tedy bude rozmyslet si, v jaký okamžik co dealokovat.
  4. Další procvičování pointerů. Naučili jsme se ze spojáku mazat, vyhledávat v něm a rychle ho otáčet v O(1) extra paměti. Ukázali jsme si fígle s obousměrnými spojáky a s různým přepojováním. Zmínil jsem kruhový spoják (poslední prvek je napojený zpátky na ten první) a sdílení ocasů u neměnitelných seznamů. Pak jsme porovnávali složitosti různých datových struktur a hledali jsme optimální algoritmy pro vyhledávání, přidávání a mazání.
  5. Vysvětlení pojmů zásobník (spoják či jiná datová struktura, ve které odebíráme prvky ze stejné strany, na kterou přidáváme. Jako první tedy odebereme naposledy přidaný prvek) a fronta (odebíráme z opačné strany, než přidáváme. První odebraný prvek je tedy prvním přidaným). Ukázal jsem průchod grafem do šířky, resp. hloubky za pomoci fronty, resp. zásobníku.
    Úvod do binárních vyhledávacích stromů, zatím bez vyvažování. Rozebrali jsme, jak se přidávají a vyhledávají prvky, proletěli jsme mazání.
  6. Velikonoční pondělí. Cvičení odpadá.
  7. AVL stromy. Ukázali jsme si, jak používat AVL rotace (přeuspořádání trojice prvků pod problematickým místem tak, aby se zkrátila nejdelší větev a problém se přesunul výš) a dokázali jsme, že AVL strom má logaritmickou hloubku vůči počtu prvků. Letem světem jsme probrali RB-stromy a (a,b)-stromy.
  8. Dynamické programování. Řešili jsme tři úlohy: Psaní na klávesnici na obrazovce, hledání nejdelší vybrané rostoucí podposloupnosti a hledání nejdelší souvislé rostoucí podposloupnosti s nejvýš k poklesy. U každé úlohy jsme vymysleli triviální algoritmus a pak jsme ho zlepšili pomocí metod dynamického programování.
  9. Další dynamické programování. Vymysleli jsme efektivní algoritmus pro počítání Levenshteinovy vzdálenosti stringů a zoptimalizovali jsme ho i co do zabraného prostoru. Vrátili jsme se k úloze na vracení mincí.
  10. Grafové algoritmy. Ukázali jsme si výhody a nevýhody tří způsobů reprezentace matice – seznamem hran, maticí sousednosti a maticí incidence. Probrali jsme Jarníkův algoritmus pro nalezení minimální kostry a naťukli jsme Borůvkův algoritmus pro totéž.
    Zadal jsem bonusovou úlohu – Levenshteinovu vzdálenost stringů. Je na ni hodně času.
  11. Pokračování grafových algoritmů – složitost Borůvky a Jarníka; hledání nejkratší cesty. Probrali jsme Dijkstrův algoritmus (modifikovanou vlnu), Bellman-Fordův algoritmus (opakované relaxování všech hran) a Floyd-Warshallův algoritmus (dynamické programování, které protahuje cestu přes k-tý vrchol ∀k ∈ {1 … n})
  12. Dokončení grafových algoritmů – důkaz korektnosti Floyd-Warshalla, ukázková řešení domácího úkolu, zmínka o algoritmu A*-Search.
    Binární soubory – jak se s nimi pracuje, na co jsou dobré (rychlost, typicky kompaktnější, jednoduché ukládání složitějších struktur) a na co si dávat pozor (nečitelnost, nepřenositelnost, endianita, menší odolnost proti chybám). Jak se vypořádat s ukládáním struktur do textových souborů: escapování.
  13. Objektové programování. Pojem třídy (definuje se klíčovým slovem object) a objektu (vytvoří se pomocí new()). Deklarace a definice metod v objektech. Diskrétní simulace pomocí objektově-orientovaného programování: Hledání nejlepšího algoritmu pro ovládání výtahu.
    V zadaném úkolu (Sazba textu) musíte povinně použít objektový návrh, jinak vám řešení neuznám.
  14. Objektové programování podruhé: dědičnost v objektovém systému, virtuální metody.
    Testování – manuální celého programu i automatické unit testy.

Podmínky získání zápočtu

Abyste získali zápočet, musíte

odevzdávat úkoly
Úlohy se dělí na běžné a bonusové a řeší se v CodExu, který už znáte a máte tam účet. Na každé hodině zadám jeden běžný. Termín jeho odevzdání je do začátku příštího cvičení, na kterém si úlohu společně rozebereme. Je potřeba získat alespoň 70 % všech bodů z běžných úloh. Bonusové úlohy mají delší časový limit a nepočítají se do potřebných 70 %.
vypracovat zápočtový program
Vizte sekci Zápočtové programy.
aktivně se účastnit cvičení
Účast je povinná, můžete chybět nejvýše na třech cvičeních. Vyšší absenci si však můžete nahradit – kontaktujte mne.

Jednotlivé kategorie se vzájemně ovlivňují – pokud vám bude chybět pár bodů z ůkolů, ale poctivě jste chodili a byli jste při hodinách aktivní, zápočet dostanete. A naopak.

Co dělat, když máte málo bodů

Vypracujte úlohy, které vám chybí nebo které jste nezvládli dostatečně dobře. CodEx vám za ně nedá body, ale procentuální úspěšnost řešení spočítá. Poté mě kontaktujte. Dbejte na přehlednost a správnost kódu.

Zápočtové programy

Nutnou podmínkou k získání zápočtu je napsání a obhájení zápočtového programu. Rozsáhlejší text o zápočťácích napsala Markéta Popelová, většina informací z něj platí i u nás.

Téma

Téma programu si musíte sami vymyslet a předložit mi ho ke schválení. Inspiraci hledejte např. na stránkách Martina Mareše – vybírejte úlohy s obtížností alespoň 5. (Leckde se s Martinem na hodnocení obtížnosti neshodnu, takže i některé čtyřky by šly.) Dobré náměty jsou také hry, třeba klony něčeho z osmibitů nebo složitější deskovky (složitější ve smyslu, že tam existují zajímavé netriviální strategie a protistrategie, nikoliv co do tloušťky příručky s pravidly. Hry založené z velké části na náhodě vám asi neuznám). Výstup klidně může být negrafický, do textové konzole, ale za pěkný vzhled budou body navíc. Velkou výhodu budete mít, pokud se rozhodnete naprogramovat něco užitečného, co sami potřebujete.

Zadání

Jakmile máte téma, je potřeba sepsat detailnější zadání, tedy seznam vlastností, které má výsledný program mít. Někdy je potřeba se rozepsat, ale většinou jako zadání stačí odrážkový seznam nebo dva-tři odstavce textu. Součástí zadání by určitě měl být nástřel uživatelského rozhraní – např. seznam příkazů, které váš program bude umět interpretovat; seznam přepínačů a voleb; popis grafického rozhraní a způsobu jeho ovládání. V tuhle chvíli už byste měli mít rozmyšlené hrubé rysy implementace. Zadání si opět nechte schválit, předejdete tak nepříjemnostem.

Vypracování

Pak přichází na řadu vypracování programu, testovacích vstupů a dokumentace, které je zcela ve vaší režii. Dokumentaci jsem zvýraznil, protože její kvalita je stejně důležitá jako kvalita programu.

Dokumentace by měla mít dvě složky – uživatelskou (popis ovládání, nejlépe s příklady nebo obrázky) a vývojářskou (přehled souborů, tříd, hlavních funkcí a algoritmů v programu a popis toho, jak spolu souvisejí a proč jsou napsané tak, jak jsou). Komentáře v kódu jsou samozřejmostí, ale nenahrazují vývojářskou dokumentaci. Dobrý textík o tom, jak dokumentaci psát, najdete na stránkách Rudolfa Kryla. Pro mne je vodítkem to, že vývojářská okumentace by měla jinému programátorovi umožnit napsání programu se shodnou funkcionalitou. Nemusíte tedy vysvětlovat známé algoritmy, ale určitě popište ty méně známé nebo vlastnoručně vytvořené – a především dopodrobna rozepište hlavní koncepty.

Testovací vstupy jsou další důležitou částí programu. Měl by jich být dostatek a měly by pokrývat jak pozitivní, tak negativní případy. Kromě běžných, očekávatelných vstupů se zaměřte i na vstupy anomální – např. „Co se stane, když do kalkulačky napíšu ‚1 + 2 3 3 / - *‘?“ Váš program nesmí ani po zadání takového vstupu spadnout; ideálně by měl vypsat srozumitelnou chybovou hlášku.

Pokud máte jako zápočtový program implementovat knihovnu, místo testovacích vstupů připravte demonstrační aplikaci, která vaši knihovnu bude používat.

Jazykem zápočtových úloh je Pascal + čeština / slovenština / angličtina. Jiné jazyky je možné použít po předchozí domluvě – bez problémů je připustím, bude-li váš zápočťák úloha z praxe.

Doporučuji vám vyzkoušet, že se program dá zkompilovat a spustit na počítačích v labu – prostředí mého, vašich a školních počítačů mohou být odlišná a dobře napsaný program by sice měl běžet všude, ale v případě problémů budu programy testovat ve škole.

Odevzdání

Zdrojové kódy a všechna potřebná data odevzdávejte v archivu e-mailem, dokumentaci dodejte v nějakém rozumném formátu, nejlépe jako PDF nebo archiv s prolinkovanými HTML soubory. Prosím, nepoužívejte .doc a podobné formáty – pokud budete dokumentaci psát ve Wordu, vyexportujte mi ji do PDF. Pokud jsou soubory velké (více než jednotky megabajtů), vystavte je na web a pošlete mi odkaz.

Po odevzdání se můžou stát tři věci: buď program rovnou schválím (v případě, že skutečně nebudu mít žádné připomínky), nebo vám ho rovnou vrátím k dopracování (pokud budou mé výhrady velké), nebo si vás pozvu na schůzku, na které mi program předvedete a obhájíte (většinový případ).

Obhajoba a hodnocení

Na přečtení a ohodnocení programu potřebuji alespoň týden a pak si musíme domluvit společný termín schůzky. Termín odevzdání proto stanovuji na začátek srpna (Pozor, změna!). Neznamená to, že při odevzdání 10. srpna už nedostanete zápočet, ale po uplynutí termínu vám negarantuji ohodnocení – čím pozdější odevzdání, tím menší máte šanci, že se k vašemu programu dostanu včas. Naopak velmi doporučuji odevzdat program co nejdříve – nejenže vás budu mít rád, ale hlavně dostanete možnost opravit případné nedostatky. Vizte též můj kalendář.

Zápočtový program je hodnocený podle následujících kritérií, v pořadí podle klesající důležitosti:

  1. Rozsah a kvalita dokumentace.
  2. Stabilita programu (zda nepadá, nezasekává se, neleakuje paměť …).
  3. Čitelnost kódu a komentářů.
  4. Použitelnost a funkčnost programu (zda dělá něco užitečného a zda se dá dobře ovládat).
  5. Splněnost zadání.
  6. Rozsah programu.
  7. Množství vložené práce.

Totální selhání v libovolném bodu automaticky znamená neúspěch, ale první čtyři body jsou posuzovány přísněji než zbylé tři. Jak tedy vidíte, je lepší odevzdat dobře dokumentovaný stabilní program se dvěma funkcemi, než padající zmetek s deseti funkcemi bez návodu.

Konzultace a kontakt

Potřebujete-li cokoliv, obraťte se na mě po hodině nebo e-mailem. Osobní konzultace jsou možné po domluvě, kancelář nemám.

Kalendář

Navrhované termíny předvádění zápočtových programů:

  • 15. září 13.00–14.30.
  • 19. září 11.00–15.00.
  • 23. září 12.15–15.00.
  • Pokud potřebujete další termín, ozvěte se mi co nejdříve. Jinak už žádný nevypíšu.

Programy se předvádějí v karlínském labu, v K11 nebo někde poblíž – podle toho, kde bude volno.