Cvičení NPRG030 – Programování 1 (ZS 2022/23)

Úterý 10:40, N8

Cvičení probíhá v jednom bloku s cvičením z Algoritmizace od 9:50. Předměty Algoritmizace a Programování 1 jsou úzce spojené, takže je reálně budeme chápat jako jedno dlouhé cvičení. Další podrobnosti najdete také na stránce Cvičení NPRG062 – Algoritmizace.

Druhý termín zápočtového testu z Programování 1 bude v úterý 10. 1. od 9:30 v místnosti SW1 (Malostranské nám. 25, přízemí). Pokud se vám termín nehodí, dejte mi vědět a naplánujeme ještě další.

Obsah stránky

Co jsme dělali

4. 10. (1. cvičení)

Algoritmizace: úložky – Největší číslo, Kuličky, Hra s mincemi.

Programování: základy – operátory, proměnné, vstup, výstup, podmínky (programy ze cvičení).

11. 10. (2. cvičení)

Algoritmizace: úložky – Cesty věží na šachovnici, Známky, Vážení kuliček.

Programování: cykly (programy ze cvičení).

18. 10. (3. cvičení)

25. 10. (4. cvičení)

Algoritmizace: pokračování O\mathcal{O} (složitost), binární vyhledávání (Házení vajíček).

Programování: seznamy (comprehensions), keř, strom a les v ReCodExu (programy ze cvičení).

1. 11. (5. cvičení)

Algoritmizace: úlohy s posloupnostmi.

Programování: slovník (dict), práce se soubory (programy ze cvičení).

8. 11. (6. cvičení)

Algoritmizace: zásobník.

Programování: soubory (pokračování), objekty (programy ze cvičení).

15. 11. (7. cvičení)

Algoritmizace + Programování: spojové seznamy (programy ze cvičení).

22. 11. CVIČENÍ NEBUDE

Cvičení nebude z důvodu konání Dne otevřených dveří.

29. 11. (8. cvičení)

Algoritmizace: rekurze.

Programování: generátory (programy ze cvičení).

6. 12. (9. cvičení)

Algoritmizace: zkoušková úloha na stromy.

Programování: přetěžování operátorů, dokumentace (numpydoc) (programy ze cvičení).

13. 12. (10. cvičení)

Algoritmizace: nic, jen programování.

Programování: random, argparse, json, csv, pygame, dědičnost (programy ze cvičení).

20. 12. (11. cvičení)

Programování: zápočtový test.

3. 1. (12. cvičení)

Algoritmizace + programování: základní grafové algoritmy – BFS, DFS, (navíc Dijkstra, A*), Cesta králem po šachovnici (programy ze cvičení).

Přednáška

Cvičení je vypsáno k přednášce Martina Pergela (středa 17:20).

Podmínky na zápočet

Na zápočet je potřeba

Zkouška bude až v letním semestru, takže zápočet je to jediné, co musíte získat.

Domácí úkoly

Plánuji zadat 10 úkolů po 10 bodech. Celkem tedy budete moct získat 100 bodů. Na zápočet potřebujete aspoň 67 bodů, tedy 7 splněných úkolů. Na každý úkol budete mít dva týdny na odevzdání a v tomto čase můžete úkol odevzdat i víckrát. Pro odevzdávání budeme používat systém ReCodEx.

Zápočtový test

Test se bude psát na cvičení 20. 12. a bude zadán přes ReCodEx (takže ho budete řešit jako domácí úkoly, akorát s časem omezeným délkou cvičení). Další termíny budou vypsány podle potřeby během zkouškového období – celkem máte na test tři pokusy.

Zápočtový program

Zápočtový program je větší kus software, který budete programovat doma během semestru. Nejpozději do konce výuky v ZS (8. 1. 2023) si vyberete téma a zašlete mi ho ke kontrole. Doporučuji vybrat si téma už před Vánoci, protože vánoční prázdniny můžou být dobrý termín, kdy na programu pracovat. Až bude program hotový (včetně uživatelské a programátorské dokumentace), zašlete mi ho ke kontrole takovým způsobem, abych mohl program spustit a vyzkoušet, ale také abych se mohl podívat na jeho zdrojový kód.

Zápočtový program může a nemusí být napsaný v Pythonu – použijte jazyk, který umíte nebo který nejlépe sedí na doménu problému. Na druhou stranu, já bych měl být schopný kód vašeho programu přečíst a pochopit, takže pokud chcete použít nějaký jiný jazyk než Python, domluvte se na tom se mnou už ve specifikaci programu.

Zápočtový program byste měli odevzdat nejpozději do konce zkouškového (12. 2. 2023), poté už za něj zápočet neudělím. Součástí odevzdání je i osobní předvedení programu. Až budete mít program hotový, pošlete mi ho mailem (včetně dokumentace a zdrojových kódů) a domluvíme se na termínu předvedení. Předvedení programu bude spočívat v tom, že mi ukážete, že program jde spustit a že dělá to, na čem jsme se domluvili ve specifikaci. Kromě toho od vás budu chtít shrnutí návrhu programu – high-level rozdělení do tříd/funkcí a jejich účet, prostě takové rychlé shrnutí toho, co dělá která část zdrojového kódu. Pokud chcete, můžete si na předvedení připravit krátkou prezentaci.

Vhodným přístupem, jak vyvíjet software je používat nástroj git pro správu verzí zdrojového kódu. Pokud si během vývoje zápočtového programu chcete git vyzkoušet, můžete si vytvořit repozitář na GitLabu (pro ten máme fakultní instanci), na GitHubu či na jiné podobné službě. Jestli s gitem neumíte, pak máte ideální příležitost se ho naučit, budete ho beztak jednou potřebovat (Git ve 100 sekundách, ale nám stačí prvních 60 a potom to samé, ale detailněji). Pokud git zatím používat nechcete, nemusíte. Stačí, když mi při odevzdávání pošlete i zdrojový kód programu.

Spoustu užitečných informací o zápočťácích už sepsali jiní, tak nemá smysl je znovu psát. Tady je pár odkazů: Martin Mareš má na webu svého cvičení hezky sepsané informace o zápočťácích. Navíc poskytuje i seznam témat pro inspiraci, takže doporučuji přečíst. Detailní informace včetně nápadů na témata sepsal taky Jirka Mayer. Nakonec, Rudolf Kryl má na webu návod na psaní dokumentace k zápočťáku, také doporučuji přečíst. Náležitosti tam popsané budu vyžadovat. Dokumentaci můžete psát česky, slovensky, nebo anglicky.

Užitečné informace

Dotazy a konzultace

Pokud vám něco, co říkám, nebude jasné, ptejte se. Ideálně hned, dokud je to aktuální. Je velmi pravděpodobné, že v učebně sedí několik dalších lidí s úplně stejným dotazem, ale bojí se zeptat. Nebojte se. Cvičení je pro vás. Cílem je, abyste látku pochopili, ne abych ji já jen zbytečně odvykládal.

Pokud se stydíte zeptat, nebo je váš dotaz moc dlouhý či kontroverzní, můžete se zeptat po skončení cvičení. V tomto čase většina ostatních studentů už odejde a zůstanou jen ti, kteří se mnou chtějí něco řešit.

Pokud by někdo chtěl něco dovysvětlit nebo se mu nedařilo a chtěl by probrat cokoliv jiného, napište mi email a domluvíme se na termínu konzultace.

MFF Discord

Kanál pro tohle cvičení: #alg-prg1-cv-mtopfer. Není povinné tam být, ale je to další místo, kde se můžete ptát na otázky a bavit se se mnou i se spolužáky.

V čem budeme programovat a jak to nainstaluju

Na první přednášce bude ukázka použití interpretu Pythonu z příkazové řádky, potom jednoduché prostředí IDLE, které se instaluje společně s Pythonem a nakonec Visual Studio, ve kterém bude probíhat zbytek přednášek. Já budu na cvičení používat Visual Studio Code, což je textový editor inspirovaný Visual Studiem, ale podstatně menší a hlavně běží i na Linuxu a macOS. Taky si nejspíš ukážeme PyCharm od JetBrains, který můžete jako studenti používat zdarma. Pokud už máte nainstalovaný nebo oblíbený jiný editor (Atom, Sublime, ...), problém s tím nemám.

Na počítačích v učebně jsou všechny potřebné nástroje už nainstalované.

Instalace VS Code

  1. Nainstalujte si Python 3.
  2. Nainstalujte si Visual Studio Code.
  3. Přidejte si do VS Code rozšíření pro Python (rozšíření se do VS Code přidávají v levém panelu v ikoně Extensions nebo přes odkaz z webového prohlížeče).
Stejné pokyny v angličtině najdete taky v dokumentaci VS Code.

ReCodEx

Domácí úkoly z obou cvičení budou zadávány a odevzdávány pomocí systému ReCodEx.

Jak rozchodit ReCodEx:

Řešil jsem KSPčko

Pokud jste už zdatnější a myslíte si, že by vás cvičení nebavilo, můžete se zapsat na cvičení Martina Mareše pro pokročilé. Můžete také chodit i na obě cvičení současně (v takovém případě si v SISu nechte zapsané moje cvičení).

Chci se procvičovat doma a nevím jak

Středoškolská soutěž Kasiopea má archiv domácích kol, kde se obtížnost úloh stupňuje od velmi lehkých k velmi náročným.

Korespondenční seminář z programování má online k dispozici nejen úlohy, ale i kuchařky vysvětlující nejrůznější oblasti algoritmizace, diskrétní matematiky a spousty dalších užitečných oblastí. Lehčí úlohy najdete v začátečnické kategorii.

Průvodce labyrintem algoritmů je kniha (dostupná online) shrnující látku předmětů Algoritmizace, Algoritmy a datové struktury I a Algoritmy a datové struktury II. Její úvodní kapitoly rozebírají paměťovou a časovou složitost, binární vyhledávání, Euklidův algoritmus, třídění, haldy apod.

Část textu na této stránce jsem opsal od Jirky Mayera. Díky, Jirko!