Cvičení z Programování I
Písemku na spojové seznamy jsme si napsali na prvním cvičení po Vánočních prázdninách. V tomto dokumentu jsou podrobné informace.
Co jsme dělali
- 30. 9. 2010
- 7. 10. 2010
- 14. 10. 2010
- 21. 10. 2010
- obsah cvičení… + nějaké to povídaní o dokumentaci zápočťáku
- sito.pas
- 28. 10. 2010 – státní svátek (výročí narození Billa Gatese)
- 4. 11. 2010
- bitové operace, výpočet kobinačního čísla, výpis čísel 2^i * 5^j * 7^k…
- bithacks.pas – binární operátory
- sito257.pas – program vypisující čísla zapsatelná jako 2^i * 5^j * 7^k pomocí síta
- grafika.pas – OpenGL ve freepascalu
- 11. 11. 2010
- 18. 11. 2010
- 25. 11. 2010
- 2. 12. 2010
- spojáky - vytváření, procházení, prohazování sousedních uzlů, otáčení celého seznamu, …
- zdroják – spojáky včetně obracení
- 9. 12. 2010
- 16. 12. 2010
- binární stromy, průchody do hloubky rekurzivním voláním a vypisování v inorderu, preorderu, postorderu, nalezení nejmenšího uzlu (v inorderovém uspořádání), nalezení následníka, insert, delete
- zdroják – řešení příkladů se stromy
- 6. 1. 2011
- písemka na spojáky
- vymysleli jsme trie
- 13. 1. 2011
- reprezetace k-árních a obecných stromů v paměti, reprezentace orientovaných grafů (neorientované získáme nahrazením každé hrany dvěma orientovanými)
- průchod do hloubky a do šířky
- vyhodnocení výrazu v postfixu
- topologické uspořádání orientovaného grafu
Zápočet
Updatnul jsem tabulku, takže v 3. sloupci by měl být celkový počet bodů k 20. únoru.
Samozřejmě, další body můžete získávat i nadále (viz úlohy).
Kdyby někdo dospěl k názoru, že už dost bodů na zápočet moc dobře získat
nemůže, tak napište a nějak to vyřešíme.
Znovu opakuji, že na odevzdání zápočťáku není žádný termín,
nicméně doporučuji dodělat ho co nejdřív — dokud vám nezabírají moc času úkoly či písemky předmětů z letního semestru.
| zápočet | (jméno) | body celkem | body z mikropísemek | body mimo CodEx |
|---|---|---|---|---|
| Čurda Jan | 40+45+0 | POPRAVA(20b), ZDROJAK(15b), TEST(10b) | ||
| ANO | Dudr Vladimír | 81+7+5 | 3+2 | TEST(7b) |
| Eis Tomáš | 11+95+6 | 3+3 | POPRAVA(20b), ZDROJAK(15b), VAZENI12(10+5b), TEST(10b), CYKLENI(35b) | |
| ANO | Hladík Tomáš | 64+45+6 | 3+3 | POPRAVA(20b), VAZENI12(10b), ZDROJAK(8b), TEST(7b) |
| Holka Matúš | 0+0+2 | 0+2 | ||
| Ivanová Soňa | 98+35+2 | 2 | TEST(5b), SPOJAKY(25+5b) | |
| Kamenská Lydia | 0+0+0 | |||
| Kašparová Tereza | 0+0+0 | |||
| Kořínek Karel | 0+0+3 | 0+3 | ||
| Kuklinca Marek | 56+75+3 | 3 | VAZENI12(10+5b), VAZENI(15b), POPRAVA(20b), ZDROJAK(15b), TEST(10b) | |
| Myroslava Vursta | 1+0+0 | |||
| Ondra Smilek | 0+0+0 | |||
| Pařízek Tomáš | 1+30+0 | VAZENI12(10b), POPRAVA(20b) | ||
| Pech Jan | 41+25+5 | 3+2 | POPRAVA(10b), ZDROJAK(15b) | |
| Pinkas Jakub | 11+0+2 | 2 | ||
| ANO | Polický Martin | 30+95+2 | 2 | POPRAVA(20b), FAKTORIAL(10b), FAKTORIAL_ADV(20b), CYKLENI(35b), TEST(10b) |
| Provazník Jan | 0+0+5 | 3+2 | ||
| Strzadala Jakub | 11+0+5 | 3+2 | ||
| ANO | Tuláček Michal | 30+65+5 | 3+2 | |
| ANO | Turanec Matúš | 28+82+6 | 3+3 | POPRAVA(20b), VAZENI(15b), VAZENI(10+5b), TOVARNA(10b), ZDROJAK(15b), TEST(7b) |
| Uhnák Peter | 68+41+0 | POPRAVA(20b), TOVARNA(10b), bugreport(1b), TEST(10b) | ||
| ANO | Vášová Viktorie | 81+42+2 | 2 | POPRAVA(10b), TEST(7b), SPOJAKY(25b) |
| ANO | Velemínský Filip | 57+82+5 | 2+3 | POPRAVA(20b), VAZENI12(10b), SPOJAKY(25+5b), ZDROJAK(15b), TEST(7b) |
| ANO | Vondruš Vladimír | 36+70+6 | 3+3 | POPRAVA(20b), VAZENI(15b), VAZENI12(10+5b), TOVARNA(10b), TEST(10b) |
Podmínky pro zápočet
Zápočet dostanete za:
- docházku alespoň 66% (na první dvě cvičení není brán ohled),
- získání 100 bodů (za domácí úlohy),
- správné napsání písemky na spojové seznamy (v lednu),
- vypracování zápočtového programu.
Nesplnění jakékoliv podmínky je možné si vždy opravit (např. pokud někomu bude chybět docházka, vymyslím pro něj nějaký ten příklad; pokud se nepovede písemka, můžeme udělat opravnou, resp. opravnou opravnou atd.) Samozřejmě, ideální je řešit věci včas. Zejména zápočtový program je nejlepší dokončovat během zimních prázdnin, protože během zkouškového už není na nějaké rozsáhlé programování dost času.
Pokud s čímkoliv (včetně domácích úkolů) budete potřebovat pomoct, domluvte se se mnou na konzultaci. Domácí úkoly sice za vás nevyřeším, ale poradím vám.
Domácí úlohy
Domácí úkoly budou jednak programovací (zadané v systému CodEx, který si na cvičení představíme), u kterých půjde o to odladit program řešící nějaký problém, a také teoretické, kde půjde spíš o myšlenku než o konkrétní implementaci. Řešení teoretických úkolů můžete odevzdávat mailem (bylo by fajn dát do předmětu kód úkolu) nebo na papíře během cvičení. Praktické/programovací úkoly se odevzdávají pomocí CodExu (ukážeme si). Pokud úkol vyřešíte do 28 dnů od zadání, dostanete počet bodů uvedený v třetím sloupečku. Po uplynutí této doby se počet bodů snižuje na polovinu.
| datum zadání | kód úkolu | body | zadání |
|---|---|---|---|
| 2. 10. | POPRAVA | 20 | Banda lupičů má být popravena, ale mají ještě poslední šanci se zachránit. Jsou postaveni do řady tak, že každý vidí všechny před sebou, ale nevidí nikoho za sebou. Každému je náhodně na hlavu umístěn kloubouk ? buď černý nebo bílý. Nyní jdou stráže odzadu a každý vězeň hádá, jakou barvu má klobou na jeho hlavě. Pokud uhodne, je propuštěn, pokud neuhodne, je popraven. Jediné, co lupiči více vepředu slyší jsou barvy klobouků. Jakou strategii by měli zvolit, aby se jich dokázalo zachránit co nejvíce? (Počítáme jen ty, kteří se zachrání s jistotou.) |
| 10. 10. | VAZENI | 15 | Dokažte, že máte-li n-1 mincí stejné hmotnosti a jednu těžší, je k nalezení té těžší potřeba alespoň log3n (zaokrouhleno nahoru) vážení na rovnoramenných vahách. Že tolik vážení stačí, to jsme ukázali na cvičení; zbývá tedy dokázat, že na méně vážení to už nejde. |
| 10. 10. | VAZENI12 | 10 | Dostali jste 12 kuliček, z nichž jedna je lehčí nebo těžší než ostatní. Popište, jak trojím vážením na rovnoramenných vahách zjistit, která to je a jestli je lehčí nebo těžší. Bonus 5 bodů dostanete, pokud ukážete, že na více než 12 kuliček už jsou potřeba 4 vážení. |
| 24. 10. | ZDROJAK | 15 |
Spíše takový programátorský hlavolam:
Napište program v Pascalu, který vypíše na výstup svůj vlastní (celý)
zdrojový kód. Nesmí však použít žádný externí soubor či například
předpokládat, že na nějakém místé na disku je odpovídající .pas soubor
uložený. Několik tipů: 1) Návěstí programu, čili takové to “program ahoj;” je možné vynechat. Stejně tak člověk může pro jednoduchost odstranit většinu nových řádků a např. mezery kolem operátorů. 2) Výraz #97 reprezentuje znak s ASCII kódem 97, tedy “a” (obdobně pro jiné kódy/znaky). Tyto výrazy je dokonce možné zřetězit: #65#104#111#106 odpovídá řetězci 'Ahoj'. Program, který vypíše prvních 19 znaků svého zdrojového kódu tedy může vypadat takto: const x='const x='; begin write(x,#39,x,#39#59); end.Můžete postupovat např. tak, že do zdrojáku přidáte další konstantu nebo konstanty jejichž (možná několikanásobné) vypsání povede k výpisu úplného zdrojového kódu. |
| 25. 10. | RIM | 10 | Převod římských čísel do dvojkové soustavy - zadáno v CODEXu! |
| 5. 11. | SIFRA | 10 | Césarova šifra - zadáno v CODEXu! |
| 12. 11. | POKLESLA | 10 | Pokleslá podposloupnost - zadáno v CODEXu! |
| 14. 11. | FAKTORIAL | 10 | Výpočet poslední nenulové číslice n! - zadáno v CODEXu! |
| 14. 11. | FAKTORIAL_ADV | 20 | Předchozí příklad (FAKTORIAL) je možné vyřešit poměrně snadno v čase O(n) - tedy v čase lineárním vzhledem k velikosti čísla n na vstupu, z jehož faktoriálu máme vypsat poslední nenulovou číslici. Pokud se vám podaří vymyslet chytřejší algoritmus pracující v čase O(log n), dostanete 20 bonusových bodů. Celkem tedy za vaše řešení dostanete 30 bodů (nebo 15 bodů po termínu). (Pokud takové řešení budete do CodExu submitovat, upozorněte mě na to mailem, ať vám nezapomenu bonusové body započítat.) |
| 21. 11. | SORT | 10 | Typické třídění - zadáno v CODEXu! |
| 21. 11. | PERMUTACE | 10 | Nalezení následující permutace v lexikografickém uspořádání - zadáno v CODEXu! |
| 25. 11. | TOVARNA | 10 | Získali jste práci v továrně na výrobu procesorů. Tuto práci si nemůžete vynachválit (kdo by nechtěl chodit celý den v těch legračních skafandrech!) Výroba procesorů ovšem není žádná hračka, takový procesor se skládá z milionů malých “krabiček”, které implementují základní binární logické operace jako AND, OR, XOR, IMPLIKACE a rovnost a také unární operaci negace (NOT). Každá logická operace bere jako své argumenty dva nebo jeden boolean a vrací opět hodnotu typu boolean. Tak například a AND b vrací True právě tehdy když levý i pravý operand nabývají hodnoty True. a IMPLIKACE b vrací False jen pokud je a (levý operand) rovné True a b (pravý operand) rovné False (v ostatních případech vrací True). Výroba procesorů by se značně zjednodušila a zlevnila, pokud by nebylo nutné vyrábět “krabičky” implementující všechny uvedené operace, ale jenom několik základních z nich a zbytek vyjádřit pomocí těchto základních. Ukažte, že všechny výše uvedné operace je možné vyjádřit pouze pomocí operací IMPLIKACE a NOT (akcionáři vaší firmy z takového výsledku budou jistě nadšeni). Odpovědí by tedy mělo být tvrzení ve tvaru, že a AND b je to samé jako (NOT b) IMPLIKACE a a podobně pro ostatní operace. (Tenhle konkrétní výrok zrovna pravdivý není, je zde uveden jen pro demonstrování toho, jak takový pokus o řešení může vypadat.) |
| 11. 12. | DOMINO | 20 | Domino - zadáno v CODEXu! |
| 18. 12. | CYKLENI | 35 | Dostali jste (jednosměrný) spojový seznam. Navrhněte algoritmus, který v lineárním čase a konstantním prostoru zjistí, jestli je daný seznam zacyklený - tzn. jestli dochází k tomu, že jeden prvek seznamu odkazuje na některý z předchozích, což při procházení seznamem vede k tomu, že je část seznamu navštěvována znovu a znovu v nekonečné smyčce. (Počet kroků algoritmu by měl být lineární vůči skutečnému počtu prvků seznamu.) |
| 20. 12. | VODA | 20 | Přelévání vody - zadáno v CODEXu! |
| 26. 12. | SPOJAKY | 25 | Naprogramujte alespoň 5 příkladů ze seznamu příkladů pro písemku na spojové seznamy. Tento příklad (a ty následující) nemá deadlinu, takže je ho možné odevzdávat kdykoliv za plný počet bodů. Pokud vyřešíte alespoň 10 z těchto příkladů, dostanete ještě 5 bodů jako bonus. |
| 11. 1. | DOBRA_CISLA | 10 | Jednoduchá úloha Dobrá čísla - zadáno v CODEXu! |
| 11. 1. | ROZKLAD | 20 | Rozklad na součet - úloha na rekurzi - zadáno v CODEXu! |
| 11. 1. | JEDEN | 20 | Jeden proti stu - zadáno v CODEXu! |
Zápočtový program
Zápočtový program je takový první větší program, na kterém byste si měli vyzkoušet problémy s psaním softwaru. Každý si může vymyslet vlastní téma, ale pro inspiraci se můžete podívat na témata od Martina Mareše (zápočťáku pro zimní semestr zhruba odpovídají témata s obtížností 3 a vyšší). Typicky studenti píší nějaký běžný program (kalendář, umělá inteligence pro piškvorky, program pro učení psaní na klávesnici všemi deseti, nějaká malá hra, …) ozvláštněný speciálními featurami. Nicméně vůbec neuškodí napsat něco zcela originálního.
Ideální by bylo, kdyby program měl praktickou hodnotu a skutečné se dal reálně používat. Každopadně ale musí mít rozumné uživatelské rozhranní, které kontroluje korektnost uživatelova vstupu a umožnuje mu program pohodlně ovládat. (Pokud byste chtěli programovat knihovnu funkcí, je možné se na tom dohodnout. V takovém případě je uživatelské rozhraní nahrazeno napsáním několika krátkých prográmků demonstrujících vzorové/triviální použití vaší knihovny.)
Zápočtový program můžete psát v běžných programovacích jazycích (C, C++, Pascal, Delphi, C#, Java, Python, Ruby, …), použití funkcionálních jazyků (Haskel, LISP, …) bych pro účely Programování I příliš nedoporučoval, ale pádný argument by mě asi přesvědčil. (P", LOLCODE, Brainfuck a spol. se použivat nesmí.) Webové aplikace (typu “redakční systém v PHP”) jsou jako zápočťák minimálně problematické - typicky obsahují hodně kódu a nic komplikovaného. Předpokládá se, že pokud si zvolíte elementárnější jazyk (C, Pascal), můžete dělat trošku jednodušší úlohu.
Do 15. listopadu je nutné poslat mi mailem specifikaci vašeho zápočťáku. To znamená, že do uvedeného data byste mi měli poslat pár vět o tom, co hodláte odevzdat jako zápočťák a jaké featury to určitě bude mít. Já vám na oplátku potvrdím, že je téma v pořádku.
Nedílnou součástí zápočťáku je dokumentace – a to jak uživatelská, tak vývojářská. Ta první popisuje, jak program ovládat; nejlépe pomocí nějakých screenshotů uživatelského rozhraní, vzorových uživatelských vstupů – prostě takový tutorial. Ta druhá by měla jednak popisovat, jak vypadá architektura programu (která funkce volá kterou, kde se data načtou, kde se zpracují, …). Není nutné popisovat každou malou funkci, pouze ty zásadní, které skutečně řeší nějakou část zadaného problému. Cílem vývojářské dokumentace by mělo být, aby po jejím přečtení dokázal jakýkoliv programátor v rozumném čase začít pracovat na rozšiřování vašeho programu (nemusel pracně hledat, na jakém místě v programu kontrolujete korektnost vstupu a podobně). Pochopitelně, zdrojový kód by sám o sobě měl obsahovat komentáře. Dokumentaci odevzdávejte v nějakém rozumném formátu (HTML, PDF, …).
Je nejlepší, pokud mi přijdete svůj zápočťák předvést např. na počítači v labu. (Vyhnete se tím všelijakým problémům s kompatibilitou a budeme si moct hned povědět jak moc skvělý váš program je.) Počítejte ale s tím, že k odevzdanému zápočťáku mohu mít nějaké (nejspíš drobné) výhrady, které bude nutné opravit.
Kontakt
Na úvodní stránce je uvedený kontakt na mě (lukas.mach@gmail.com, ICQ: 114 214 358). Pokud vám hned (během 1 dne) neodpovím, tak se něco pokazilo. Neváhejte to poslat znovu (případně jinou cestou). Do předmětu mailu prosím dejte řetězec „PRG1“.