Cvičení z Algoritmizace a Programování 1, ZS 2023/2024

Pátek od 9:00 v N11 (IMPAKT)
Cvičení vede Jakub Mestek (jakub.mestek<at>mff.cuni.cz)
Cvičení v AR 2022/2023

Obsah cvičení

12. cvičení, 12. 1.

Algoritmizace: Vzorové úlohy ze zkoušky.

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

11. cvičení, 5. 1.

Programování: Gitlab. Unittesty - vzor.

[slidy]

21. 12.

Výuka zrušena.

V ReCodExu zadány poslední domácí úkoly.

10. cvičení, 15. 12.

Algoritmizace: Prohledávání. Zkoušková úloha.

Programování: Práce se soubory - strom.txt.

Git: pěkný návod sepsal kolega Michal Töpfer.

[slidy] [programy]

9. cvičení, 8. 12.

Binární stromy – prohledávání do šířky. Prohledávání stavového prostoru – Přelévání vody.

[slidy] [programy]

8. cvičení, 24. 11.

Rekurze. Binární stromy.

7. cvičení, 24. 11.

Algoritmizace: Rekurzivní generování – variace bez opakování, K ciferná čísla s daným ciferným součtem.

Programování: Spojové seznamy – těžší úlohy.

[slidy] [programy]

17. 11.

Výuka zrušena – státní svátek.

V případě jakýchkoli otázek nebo nejasností (k DÚ, látce z přednášek, ...) mi napište e-mail, možnost konzultace.

6. cvičení, 10. 11.

Algoritmizace: Datové struktury – zásobník, fronta. Binární halda.

Programování: Spojové seznamy.

[slidy] [programy]

5. cvičení, 03. 11.

Algoritmizace: Binární vyhledávání. Vážení kuliček.

Programování: Funkce.

[slidy] [programy]

4. cvičení, 27. 10.

Algoritmizace: Hornerovo schéma - převod mezi soustavami. Rozklad na prvočísla.

Programování: Debugging – breakpointy, krokování. Úlohy na práci s list. Zadán domácí úkol.

[slidy] [programy]

3. cvičení, 20. 10.

Algoritmizace: O notace – důkazy tvrzení. Domácí úkol.

Programování: Diskuse o řešení úlohy Druhá největší hodnota, invariant cyklu. list, slicing, for cyklus.

[slidy] [programy (upraveno)]

2. cvičení, 13. 10.

Algoritmizace: Je číslo v posloupnosti? – zápis algoritmu, správnost, složitost. Asymptotická složitost a O notace (přiště v tom ještě budeme pokračovat).

Programování: Seznámení s VS Code a ReCodExem. If-else, while, výpis a čtení vstupu. Domácí úkoly – viz ReCodEx

[slidy] [programy]

1. cvičení, 6. 10.

Úvodní informace

Úlohy z algoritmizace

První domácí úkol – Kabel na mrakodrap

[slidy]

Úlohy na procvičení

Pro domácí procvičování jsou vhodné úlohy ze středoškolských programovacích/algoritmizačních soutěží. Na jejich stránkách najdete archivy minulých ročníků, obsahující nejen zadání, ale i vzorová řešení. Pro trénink určování složitosti algoritmů můžete použít i třeba řešení vašich domácích úkolů do Programovaní.

Podmínky získání zápočtu

Programování 1

Algoritmizace

Zápočtový program

Zápočtový program je větší software, který naprogramujete doma během semestru. Téma si vymyslíte sami, jakmile jej budete mít rozmyšlené (nejpozději však do 31. 12.), sepište specifikaci – krátký (1–2 odstavce) popis, co váš program bude dělat – a pošlete mi ji ke schválení.

Zápočtový program nemusí být nutně napsán v Pythonu, můžete použít jiný jazyk, který dobře znáte nebo se hodí pro vybranou úlohu. Pokud ale budete chtít použít jiný jazyk než Python, domluvte se na tom se mnou předem (= uveďte to ve specifikaci).

Program se odevzdává skrz fakultní Gitlab, kde budete mít připraven repozitář (/teaching/nprg030/2024-winter/student-LOGIN_DO_SISU), který si naklonujete a přidáte do něj váš program. Postup a základní práci s Gitem si ukážeme na cvičení. Jakmile bude mít program hotový, pošlete mi e-mail s odkazem na váš repozitář. Já se na program podívám a ohodnotím ho.

Součástí odevzdávaného programu musí být také dokumentace, která má tři hlavní části: Vhodný způsob, jak psát dokumentaci je vytvořit si v repozitáři složku docs a v ní mít několik souborů ve formátu Markdown (.md). Do souboru README.md pak vložte rozcestník (odkazy) na jednotlivé části dokumentace. Dokumentaci můžete psát česky, slovensky, nebo anglicky.

Program odevzdejte ideálně do konce zkouškového, nejpozději však do 29. 2. Doporučuji ale odevzdat ho do konce zkouškového, během výuky v letním semestru už budete mít jiné starosti.

Pěkný seznam možných témat má na svém webu Martin Mareš, další návrhy a informace k zápočtovému programu sepsal i Jirka Mayer. Návod a rady k psaní dokumentace najdete na webu Rudolfa Kryla.

Návody

ReCodEx

Pro zadávání a odvezdávání domácích úkolů budeme používat systém ReCodEx.

Programovací úkoly vám ReCodEx ihned zkontroluje a oboduje. Pokud vaše řešení nebude 100%, můžete odevzdat nové. Počet pokusů bude omezen na 50, počítat se bude ten nejlepší. Teoretické úkoly (z Algoritmizace) budu opravovat ručně, tudíž budete mít obvykle jen jeden pokus.

Jak ReCodEx zprovoznit:

Vývojové prostředí

Používat můžete cokoliv, já budu na cvičeních používat Visual Studio Code.

Instalace:

  1. Stáhněte a nainstalujte si Python (https://www.python.org/downloads/). Při instalaci zaškrtněte Add Python to PATH.
  2. Stáhněte a nainstalujte si Visual Studio Code (https://code.visualstudio.com/download).
  3. Ve VSCode v menu vlevo vyberte Extensions a přidejte si rozšíření Python.

Přístup k souborům na školních počítačích

Pokud máte soubory uložené na Studentském úložišti (disk (su.mff.cuni.cz)), dostane se k nim například přes webové rozhraní https://su.mff.cuni.cz/.

Pokud máte soubory na afs (ve škole disk Z:), můžete se k nim připojit vzdáleně pomocí OpenAFS, návod na wiki laboratoře Rotunda.

Jiný způsob, momentálně bohužel z důvodu rekonstrukce laboratoře nefunkční, je skrze vzdálený přístup na nějaký počítač v počítačové laboratoři Rotunda (co dalšího tam můžete dělat zde):