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

• ČAS: každé pondělí 10:40 v SW2, ZS 2017/18.
• 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 recodexu (požadavky: aspoň polovinu bodů celkem, aspoň polovinu z druhé poloviny semestru)
• na cvičení se hodí občas přijít a 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% celkových bodů)
• 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í a můžete je bez potíží splnit rovnou, dejte mi vědět na hodině nebo mailem.

Zápočťáky#

Na zápočet 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), konvertory mezi různými formáty dat (třeba vysázení programu do HTML, nebo vytahování nějakých informací z HTML) kalkulačky, všelijaké generátory (bludiště, fraktální a bezkontextové obrázky ), zpracovávače a upravovače obrázků a zvuků, 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 (třeba splay) nebo haldy (třeba binomiální) nebo třeba skiplisty).

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 návrhu (dělá to jednu jasně definovanou věc dobře)
• 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:

• dohodnutí tématu: 4. 12. 2017
• odevzdání zápočťáků: 18. 3. 2018

Pozor, “dohodnutí tématu v termínu” neznamená, že mi poslední den 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#

• První test byl 20. 11.
• Druhý test byl 11. 12.
• Třetí test měl být na posledním cvičení, ale protože ho nebude potřebovat moc lidí, napíšeme ho mimo cvičení ať šetříme čas. Termín je libovolný (nejdéle však do 18. 3. 2018) — napište mi mail kdy si test chcete napsat, dohodneme se kdy se potkáme na MS.

Z každého testu jde dostat 2 body, celkem potřebujete 3 body z 6.

Výsledky testů je možné vidět v SISu!

Průběh cvičení#

2. 10. 2017#

Úvod a předběžnosti.

Motivační potíže k potřebě programovat: Problém s vážením, velbloud, odmocnina na počítači ze středověku.

DÚ:

• Sežeňte si login do počítačů v laboratořích! (návod: V rotundě u služby se dá zjistit kde přesně ve 4. patře se nachází člověk který ty loginy zakládá. Vezměte si ISIC.)
• Napište mi mail, ať mám na všechny funkční kontakt.

9. 10. 2017#

Člověk je bottleneck, plechové počítače, logické obvody.

DÚ:

• Beta verze systému na odevzdávání domácích úkolů by už měla fungovat! Registrujte se (registrace přes CAS, heslo stejné jako do SISu) a připojte se ke správné skupině. Pokud narazíte na potíže (přecejen to dodělali před týdnem), dejte mi vědět, opraví se.
• Na hodině jsme si hráli s logickými obvody. Rozmyslete si, co a proč by udělaly následující:
  • 2x NOT, zapojený do kruhu
  • 3x NOT, taky zapojený do kruhu

Až se zamyslíte, podívejte se na řešení: 2x NOT je skoro tohle, 3x NOT je nestabilní (a jde použít na generování náhodných čísel, třeba takhle).

16. 10. 2017#

Rychloúvod do Pascalu, nějaké jednodušší programy.

Zdrojáky z hodiny jsou tady (a budou se tam objevovat i další cvičení).

23. 10. 2017#

Pokračování úvodu do Pascalu, slovo o složitosti, nějaké lineární algoritmy. Obecné schéma programu na zpracování hromady čísel ukončené něčím speciálním (třeba nulou, jde s úpěchem aplikovat na všechny podobné programy).

DÚ bude v codexu, ale zkuste si rozmyslet:

• Jaká je složitost programu na TopN maxim?
• Galaktické volby: V galaxii je Fakt Hodně občanů i kandidátů na prezidenta galaxie. Dostanete obrovskou řadu obrovských čísel, každé číslo znamená jeden hlas pro jednoho (očíslovaného) kandidáta. Hlasů a kandidátů je bohužel tolik, že čísel postačujících pro identifikaci kandidáta nebo počtu hlasů se vám do paměti vejde jen konstantní (malý) počet; navíc každý hlas můžete zpracovat jen jednou. Naštěstí ale víte, že jeden kandidát má určitě ostrou nadpoloviční většinu hlasů. Úkol je zjistit číslo tohoto kandidáta.

30. 10. 2017#

Arraye, stringy, písmena.

(programy na histogram, ord/chr, číselné soustavy, binární násobení)

6. 11. 2017#

Arraye s délkou určenou za běhu programu, SetLength. Rekurze — obrácení posloupnosti, quicksort. Porovnávání stringů. Ignore-case quicksort implementujeme.

13. 11. 2017#

Trochu rekurze a arrayí navíc. Záznamový typ (record). Třídění excelem v lineárním čase (známější jako RadixSort). Programovali jsme v unixu protože FreePascalIDE selhalo.

20. 11. 2017#

TEST 1! Test proběhne na papír (vezměte si tužku a papír). Obsahem budou 2 jednoduché příklady, extrémně podobné některým, co jsme dělali na cvičení.

Ve zbytku času úvod do dynamických datových struktur.

27. 11. 2017#

Spojové seznamy a jejich použití: Definovali jsme (skoro-standardní) funkce list_new, list_push, list_pop, list_dispose, list_front, list_empty, list_reverse a list_move_head. Budeme je dost používat.

4. 12. 2017#

Dodělali jsme bucketsort a pár zbytkových věcí, nakousli jsme stromy a haldy.

Kostra na domácí úkol Dlouhý Div/Mod je tady. Váš kód patří tam, kde je TODO. Na příštím/popříštím cvičení to vysvětlím přesněji.

11. 12. 2017#

TEST 2 proběhne opět tužkou na papír, obsahem bude práce se spojovými seznamy.

Haldy.

18. 12. 2017#

Implementace haldy, heapsort.

Přehlídka metod prohledávání stavového prostoru: Vlna, BFS vs. DFS, IDFS, Dijkstra, prohledávání z obou směrů.

8. 1. 2017#

Zbytky: Dynamické programování, diskuse o počítání s velkými čísly, několik metod vyvažování stromů.

Bonusy!#

• PROGRAMY ZE CVIČENÍ jsou tady
• Při soubojích s domácími úkoly se může hodit seznam chybových kódů pascalu
• 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é.

Kde sehnat Pascal?#

• Na většině linuxu/BSD a unixu obecně jde sehnat FreePascal, většinou v balíčku s názvem fpc.
• To samé platí i pro MacOSX, pokud tam nemáte žádný balíkovací systém, stáhněte si FreePascal odsud.
• Pokud chcete IDE, doporučuju Geany
• Na windows jsou 4 možnosti
  • FreePascal jde stáhnout odsud
  • Dobré IDE k FreePascalu je Geany
  • FreePascal má na windowsu i vlastní IDE, které vypadá stejně jako Borland Pascal
  • Borland Pascal (originální modrou spolehlivou volbu!) nechcete. Přesto jde sehnat ke studijním účelům někde ve škole, jestli ho fakt chcete, zeptejte se na přednášce.

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

Třeba takhle.

Jak si domácí úkol vyzkoušet ve stejném prostředí, jako ve kterém se vyhodnocuje?#

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
  • V putty si můžete znormálnit chování NumPadu
• 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 0 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., tak konkrétní příkaz, kterým (re)codex kompiluje programy je: fpc -g -O2 -Sg -Ci -Cr -Ct program.pas.

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í. haha.)
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.