Trochu informací o cvičení z programování

• ČAS: každou středu 14:00 v SU2, ZS 2016/17.
• KONTAKT: exa.exa@gmail.com, do předmětu napište NPRG030 (jinak hrozí, že zapadnete do nánosu ostatních mailů).

Zápočet#

Na zápočet potřebujete splnit následující podmínky:

• plnit domácí úkoly v CodExu (požadavky: aspoň polovinu bodů celkem, aspoň polovinu z druhé poloviny semestru)
• na cvičeních vypadat aktivně a přítomně (když vás v lednu před zkouškovým uvidím poprvé, předpokládám potíže)
• napsat test (budou zhruba 3, stačí cca 50% úspěšnost)
• vyrobit zápočťák

Pokud už umíte programovat v nějakém jazyce s pointery (tj. C, Pascal) a myslíte si, že požadavky pro vás budou triviální, dejte mi vědět na hodině nebo mailem.

Zápočťáky#

Na zápočet si potřebujete vymyslet, navrhnout a naprogramovat zápočtový program. Mělo by jít o nějaký menší projekt (cca 200 až 500 řádků smysluplného kódu) který neotřele řeší nějakou zajímavou nebo zábavnou úlohu. Cílem zápočťáku je prokázat, že umíte dát do kupy konzistentní kus software.

Vhodná témata jsou miniaturní rychlé hry, zpracovávače a formátovače textu, miniaturní programovací jazyky (želva/karel, malinké virtuální CPU, forth), kalkulačky, všelijaké generátory (bludiště, fraktální a bezkontextové obrázky ) pomůcky pro jiné matfyzácké úlohy (numerická řešení rovnic, limity, derivace, matice, …) nebo nějaké pěkné algoritmy a datové struktury (nějaké lepší stromy nebo haldy).

Inspirace dále např. u Martina Mareše nebo třeba tady

Nevhodná témata jsou věci s příliš nejasným využitím nebo programy co jsou na internetu už dostupné v tisících kopií a různých variantách.

Na zápočťáku se hodnotí:

• kvalita kódu (čitelnost a struktura)
• kvalita implementace (nechcípe to, nepočítá to špatně)
• rozsah (a přiměřená obtížnost řešené úlohy)
• dodržení termínů (za zmeškání termínu budu přidávat obtížnost)

Termíny (konečné):

• dohodnutí tématu: 7. 12. 2016, 23:59:59.999
• odevzdání zápočťáků: 28. 2. 2017 15. 3. 2017

Upozorňuju, že “dohodnutí tématu v termínu” neznamená, že mi 7.12. ve 23:59:59 přijde mail. Téma je potřeba prodiskutovat a odsouhlasit. Počítejte s tím, že první návrh většinou neprojde.

Téma a splněnost zápočťáků je evidovaná v SISu v grupíku (teď se tomu možná říká “studijní mezivýsledek”). Zkontrolujte si to, nesrovnalosti hlašte.

Testy#

(detaily viz. níže)

• První test bude 9. listopadu
• Druhý test bude 7. prosince
• Třetí test bude 4. ledna (pokud bude potřeba)

Výsledky testů jsou vidět v SISu!

Průběh cvičení#

5. 10. 2016#

Úvod, předběžnosti, programování velblouda.

DÚ: Zaregistrujte se do CodExu, vytvořte si login v labu, a pošlete mi e-mail, že vás mám přidat do CodExové skupiny. (1 bonus bod)

12. 10. 2016#

Programování dřevěných počítačů. Hledání vhodného vývojového prostředí. Rychloúvod do pascalu: Přehlídka toho jak vypadá program, begin/end, if, for/while/repeat, integery. Jednoduché problémy s cykly a malými čísly.

DÚ: odteď už vždycky v CodExu.

19. 10. 2016#

• obecné schéma programu co zpracovává řadu čísel
• top X
• galaktické volby
• program na chybějící číslo

26. 10. 2016#

• chary, stringy, arraye! (+ jak je vidí CPU)
• histogram
• počítání s písmeny, ord, chr
• načtení čísla v nějaké divné soustavě
• násobení dlouhých čísel (binárních)

2. 11. 2016#

• funkce a procedury (a jak jsou zařízené v HW)
• rekurze a diskuze o jejích nebezpečenstvích, faktoriál
• něco jsme setřídili (bublacím sortem a quicksortem)
• setLength

9. 11. 2016#

• TEST 1, obsahem měla být práce na poli (lopatování arrayí), ale zjednodušil jsem to.
• find/replace a podobná stringová zábava
• BONUS - Řešení starších DÚ jsou odteď k dispozici, budu to postupně upgradovat.

16. 11. 2016#

• dlouhá čísla (výsledek snažení zde )
• debugování v pascalu
• Základní kostra na uvaření domácího úkolu (kde je TODO, tam patří váš kód).

23. 11. 2016#

• zlomová hodina o pointerech a ruční alokaci paměti: typ pointer, reference a dereference, getmem, freemem, sizeof, new, dispose.
• složené typy
• spojové seznamy, detekce cyklu
• demo jak si vyzkoušet věci na UNIXu se stejným kompilátorem, jaký má CodEx. Popis viz. dole v bonusech.

30. 11. 2016#

• aplikace spojových seznamů:
  • bucketsort
  • postfixová kalkulačka s nekonečnou pamětí

Upozornění: Zdroják úkolu s dlouhým dělením už je na webu. Knihovnu na práci se seznamy tam dám, až bude po termínu seznamového úkolu.

7. 12. 2016#

• TEST 2 — Aplikace pointerů na práci se spojovými seznamy. Např.: nalezení prvku, přidání/ubrání prvku uprostřed/na konci seznamu, kopírování, spojování a obracení seznamů, filtrování (hromadné odstranění prvků nesplňujících nějakou podmínku), nějaké jednoduché třídění, apod.
• binární haldy

Upozornění: Jednoduchá knihovna na práci se seznamy je mezi řešeními domácích úkolů.

14. 12. 2016#

• stromy a rotace
• nějaká primitivní varianta vyvažování
• zdroják zde — bez vyvažování je to samozřejmě pomalejší.

Návod na domácí úkol s roztržitým profesorem:

Potřebujete datovou strukturu, která umí udržet pořadí a dá se jí ubírat z prostředka a přidávat na začátek. Tj. nějaký strom.

Zároveň potřebujete aby operace běžěly jakž takž rychle, ideálně O (log n). Takže musí být nějak vyvážený.

Především ale potřebujete umět v O (log n) vybrat v pořadí k-tý prvek, to se ve stromě nejlépe provede tím, že si v každém uzlu pamatuje a udržuje počet uzlů tvořících celý podstrom. Trochou počítání pak jde při cestě od kořene vždycky jednoduše vybrat správné odbočky přesně ke k-tému prvku: Např. když hledám v pořadí pátý prvek a v levém podstromě jsou jen 3 prvky, pátý bude určitě ležet v pravém podstromě, kde bude v pořadí první.

Počítání prvků jde použít i na vyvažování — když se vám zdá, že je někde velká nerovnováha, prostě uděláte rotaci správným směrem.

Inspirace a víc materiálu ke čtení např. zde. Exaktní dodržení vyvažovacích podmínek (nebo dvojrotace apod.) ale není vůbec potřeba řešit.

21. 12. 2016#

• Levá stěna vs. Vlna vs. BFS vs. DFS vs. IDFS
• aplikace na bludiště (RandomFirstSearch, kód zde )
• 29.12. zveřejněno řešení byrokratického a kafového domácího úkolu

4. 1. 2017 (předpoklad)#

• TEST 3 — “záchranný termín”, obsah bude podobný jako v testu 2 + extra úloha za bod na věci z předchozích 3 cvičení. Pokud chcete zápočet a ještě nemáte dost testových bodů, tento test musíte absolvovat. Test je poslední, náhradní termíny je bezpodmínečně nutné domluvit si předem. Pokud máte už dost bodů, stejně je fajn si to napsat cvičně.
• infixová kalkulačka

11. 1. 2017 (předpoklad)#

• asi algoritmy na grafech, třeba nejkratší cesta/cesty

Bonus!!#

• Při soubojích s CodExem se může hodit seznam chybových kódů pascalu
• Řešení některých starších DÚ jsou k dispozici tady, budu to postupně upgradovat.
• Na cvičeních se občas oháním argumenty typu “…ale tohle je fuj”, “…z toho není moc poznat, co to dělá”, případně občas “když budete dělat tohle, budete trpět”. O důvodech podobných pohnutků a o obrovském množství velice praktických poznatků, které vznikly při vývoji jednoho z nejrozšířenějších programovacích prostředí na světě vůbec, se můžete dočíst v knížce E. S. Raymonda The Art of UNIX Programming (online verze). Popisuje i poměrně masivní kus počítačové historie. Pokud poprvé programujete nějaký větší systém, najdete návod (a hodně vytříbených odstrašujících příkladů) o tom, jak to nezmršit. Občas trochu filozofické.

Jak vyrobit rozumný uživatelský interface pro jednoduchou zápočťákovou hru?#

Třeba takhle.

Jak si program vyzkoušet ve stejném prostředí, jako CodEx?#

Potřebujete stroj s nějakým UNIXem (můžete si nainstalovat třeba virtuální ubuntu, ale v labu je dost počítačů na které se jde přihlásit odkudkoliv) a na něm nainstalovaný kompilátor FPC.

Do labu se přihlásíte takhle:

• z Putty.nl si stáhnete Putty, což je SSH klient pro windows
• odněkud z internetu si stáhněte WinSCP, tím jde na unixy nahrávat soubory
• Připojujete se k počítači u-plX.ms.mff.cuni.cz, místo X doplníte číslo 1 až cca 23 podle toho, který počítač chcete obtěžovat. Jsou to jeden po druhém přesně všechny počítače vlevo v labu.
• Login a heslo je stejné jako když se přihlašujete ručně nablízko.

UNIXové prostředí je pro programování podstatně vhodnější než windows, jen se o nové uživatele moc nestará, takže je potřeba si sehnat nějaký návod. Ten dostanete až v rámcí úvodu do unixu v 2. semestru, mezitím si můžete přečíst třeba tohle . Potom:

1. Pomocí WinSCP nahrajete program.pas na unixový počítač
2. Pomocí Putty se tam přihlásíte, vlezete (cd) do adresáře, kam jste soubor nahráli
3. napíšete fpc program.pas, vedle se vám vyrobí spustitelný soubor program
4. program spustíte pomocí ./program. Když se rozbije, stačí Ctrl+C, to ho přeruší.

Pokud chcete i range checky apod., konkrétní příkaz, kterým codex kompiluje programy je: fpc -g -O2 -Sg -Ci -Cr -Ct program.pas (viz zde ).

Trik: do souboru si můžete uložit testovací vstup.

1. spustíte cat > test.in
2. napíšete celý vstup
3. ukončíte Ctrl+D (což je zkratka pro EOF. Když to omylem zmáčknete dvakrát, pošlete EOF i konzoli, takže vás odpojí.)
4. program spustíte pomocí ./program < test.in
5. podobně si můžete schovat výstup programu: ./program <test.in >vysledek (a koukat se na něj: cat vysledek ).

Pokud chcete soubory editovat humánně přímo na místě, můžete zkusit vi program.pas. Vi je extrémně užitečný editor (aktuálně jeden ze dvou nejlepších editorů na planetě), pro nové uživatele samozřejmě smrtící. Je fajn si předtím zkusit vimtutor. V případě zoufalství použijte nano.