Cvičení NPRG030 – Programování 1 (ZS 2021/22)

Pondělí 16:30, N8

Cvičení probíhá v jednom bloku s cvičením z Algoritmizace od 15:40. 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 je ve čtvrtek 13. 1. 2022 v 17:30 na Teams (odkaz v SISu). Pokud chcete další termín, ozvěte se mi.

Obsah stránky

Co jsme dělali

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

Algoritmizace: úložky – Největší číslo, Kuličky, Cesty věží na šachovnici, Známky.

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, $\mathcal{O}$ (složitost).

Programování: celou hodinu jsme dělali algoritmizaci.

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

Algoritmizace: Vážení kuliček.

Programování: cykly, funkce, seznamy, textové řetězce (programy ze cvičení).

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

Algoritmizace: binární vyhledávání (Házení vajíček), zásobník.

Programování: seznamy (comprehensions), slovník (dict), objekty (programy ze cvičení).

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

Algoritmizace: halda (str. 84 v Průvodci labyrintem algoritmů).

Programování: dodělávky z minula, práce se soubory (programy ze cvičení).

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

Algoritmizace: úlohy s posloupnostmi.

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

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

Algoritmizace: rekurze (programy ze cvičení).

Programování: spojové seznamy (moje řešení).

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

Algoritmizace: binární vyhledávací stromy.

Programování: PyGame (instalace: py -3 -m pip install -U pygame --user, programy ze cvičení).

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

Algoritmizace: zkoušková úloha na stromy.

Programování: dokumentace (numpydoc, doctest), operátory (programy ze cvičení).

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

Algoritmizace: nic, jen programování.

Programování: dědičnost, random, argparse, json, csv, Buďte lepší než Spotify (programy ze cvičení).

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

Algoritmizace: dynamické programování.

Programování: Jupyter, NumPy, Matplotlib, Pandas (programy ze cvičení).

20. 12. (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í).

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

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

Přednáška

Cvičení je vypsáno k přednášce Martina Pergela, ale klidně choďte i na přednášky Tomáše Holana.

Podmínky na zápočet

Na zápočet je potřeba

získat alespoň 2/3 bodů za domácí úkoly (7 úkolů z 10),
napsat zápočtový test (bude na posledním cvičení),
naprogramovat zápočtový program (viz níže).

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 posledním cvičení 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í).

Zápočtový program

Zápočtový program je větší kus software, který budete programovat doma během semestru. Do konce listopadu si vyberete téma a zašlete mi ho ke kontrole. Na programu pak budete pracovat, dokud nebude hotový (včetně uživatelské a programátorské dokumentace). Výsledek práce mi zašlete 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 (pokud je to problematické, můžeme se domluvit na osobním předvedení).

Zápočtový program má výjimku, že nemusí být 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 (13. 2. 2022), poté už za něj zápočet neudělím.

Byl bych rád, kdybyste program vyvíjeli v repozitáři na GitHubu nebo GitLabu (pro ten máme fakultní instanci), případně podobné službě. Ušetří to práci oběma stranám. Pokud 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).

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

Nainstalujte si Python 3.
Nainstalujte si Visual Studio Code.
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:

Jděte na https://recodex.mff.cuni.cz/login.
V sekci Přihlásit se pomocí externí služby klikněte na Ověřit uživatele.
Přihlaste se pomocí Centrální Autentizační Služby (CAS CUNI). Jméno a heslo jsou stejné jako do SISu.
V menu vlevo dole je položka SIS Integrace. Tam se přidejte do skupin Algoritmizace a Programování 1.

Ř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!