Home Theses or project ideas
Úvod do umělé inteligence
☰

Algoritmizace a Programování 1, ZS 2022/2023

Čtvrtek od 14:00, N8 (IMPAKT)

Obsah

Obsah cvičení

Zápočtový test – 5. 1.

  • Algoritmizace: Řešení domácích úloh. Vzorové úlohy ze zkoušky.
  • Programování: Zápočtový test.

slidy

Prohledávání grafu – 22. 12.

  • Algoritmizace: Prohledávání. Hledání nejkratší cesty, prohledávání grafu. Materiály na cvičení: prohledávání (pseudokód), grafy.
  • Programování: Zadán domácí úkol.

slidy programy

Rekurze, slovník, soubory – 15. 12.

  • Algoritmizace: Rekurze – typové úlohy. Krabičky. Zadán domácí úkol (poslední).
  • Programování: Slovník, množina. Práce se soubory. Zadán domácí úkol.

slidy programy

Prohledávání stavového prostoru, binární stromy – 8. 12.

  • Algoritmizace: Prohledávání stavového prostoru – Přelévání vody. Zadán domácí úkol.
  • Programování: Binární stromy – výpočet výšky, symetričnost. Zadán domácí úkol.

slidy programy

Rekurze, generování – 1. 12.

  • Algoritmizace: Rekurze – faktoriál, Fibonacciho čísla. Hanojská věž – počet tahů.
  • Programování: Generování variací bez opakování a permutací, vkládání operátorů mezi čísla. Zadán domácí úkol.

slidy programy

Datové struktury, zásobník – 24. 11.

  • Algoritmizace: Řešení úlohy počet jedniček v podmatici. Datové struktury – zásobník, fronta, prioritní fronta. Binární halda – operace Odstraň prvek, Změň prioritu. Zadán domácí úkol.
  • Programování: Řešení úloh Průnik a sjednocení spojových seznamů. Zásobník – objektová implementace, použití v jiném programu (import). Zadán domácí úkol.

slidy programy

Binární vyhledávání, spojové seznamy – 10. 11.

  • Algoritmizace: Počet jedniček v podposloupnosti – prefixové součty. Binární vyhledávání – nejlevější a nejpravější výskyt. Zadán domácí úkol.
  • Programování: Spojové seznamy. Zadán domácí úkol.

slidy programy

Třídící algoritmy, spojové seznamy – 3. 11.

  • Algoritmizace: Řešení úlohy Prostřední z pěti. Třídící algoritmy. Halda.
  • Programování: Spojové seznamy - šablona. Zadán domácí úkol.

slidy programy

Invariant cyklu, work s list – 20. 10.

  • Algoritmizace: Poznámky k domácímu úkolu. Invariant cyklu. Algoritmické řešení úloh z Programování.
  • Programování: Terminál, čtení vstupu ze souboru, zápis výstupu do souboru. Úlohy na práci s list. Zadán domácí úkol.

slidy programy

O notace, list, debugging – 13. 10.

  • Algoritmizace: O notace – důkazy tvrzení. Vážení kuliček – domácí úkol (do 27. 10., viz ReCodEx–Algoritmizace).
  • Programování: Diskuse o řešeních úlohy Maximum. list, slicing, for cyklus. Debugging – breakpointy, krokování.

slidy programy

Složitost algoritmů, O notace – 6. 10.

  • Algoritmizace: Je číslo v posloupnosti? – zápis algoritmu, správnost, složitost. O notace.
  • Programování: Seznámení s VS Code a ReCodExem. If-else, while, výpis a čtení vstupu. Domácí úlohy – viz ReCodEx

slidy programy

Úvodní informace – 29. 9.

  • Úvodní informace
  • Úlohy z algoritmizace

slidy

Podmínky zápočtu

Programování I

  • 70 % bodů z domácích úkolů – zadávané každý týden, v ReCodExu
  • zápočtový test – řešení programovací úlohy v ReCodExu; na posledním (a předposledním) cvičení
  • zápočtový program – specifikace do 15. 12., odevzdání (včetně dokumentace) do 28. 2.

Algoritmizace

  • 70 % bodů z domácích úkolů – zadávané zhruba každé dva týdny, v ReCodExu

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 15. 12.), sepište specifikaci – krátký (1–2 odstavce) popis tématu (tj. co váš program bude dělat) – a pošlete mi ji ke schválení.

Až budete mít program hotový, zašlete mi ho ke kontrole, a to takovým způsobem, abych jej mohl spustit a vyzkoušet, ale také se podívat na zdrojový kód. (Pokud by to bylo problematické, můžeme se domluvit na osobním předvedení.) Součástí odevzdávaného programu musí být také dokumentace, a to uživatelská (vysvětující, jak se program ovládá) a programátorská (ta popisuje, jak program uvnitř funguje; nemá smysl popisovat každou funkci nebo proměnnou, zaměřte se na celkový návrh programu a použité algoritmy). Program odevzdejte ideálně do konce zkouškového, nejpozději však do 28. 2.

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

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. Dokumentaci můžete psát česky, slovensky, nebo anglicky.

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:

  • Jděte na https://recodex.mff.cuni.cz/login.
  • V sekci Přihlásit se pomocí externí služby (box vpravo) klikněte na Ověřit uživatele. Přihlaste se pomocí Centrální Autentizační Služby (CAS UK), přihlašovací údaje jsou stejné jako do SISu.
  • V menu vlevo je položka SIS Integrace, tam se přidejte do skupin Algoritmizace a Programování 1.
    Při prvním přihlášení se položka SIS Integrace možná v menu neobjeví, v tom případě zkuste stránku načíst znovu.
  • Pro programování byste měli vidět dvě podskupiny – Povinné Programování 1 (Čt, 14:50, N8) a Nepovinné Programování 1 (Čt, 14:50, N8).
    • Do skupiny Povinné … Vám budu zadávat domácí úkoly (viz Podmínky zápočtu).
    • Úlohy ve skupině Nepovinné … budeme řešit v hodině, doma je dodělávat nemusíte. Pokud ale budete na cvičení chybět, doporučuji se na ně podívat.

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)), dostete se k nim například přes webové rozhraní https://su.mff.cuni.cz/.

Pokud máte soubory na afs (ve škole disk Z:), dostanete se k nim 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):

  • Přístup z UNIXu, terminálu, apod.: skrze SSH, SCP nebo SFTP se lze připojit na libovolný počítač v Rotundě: ssh login@u-plXX.ms.mff.cuni.cz , místo XX zadejte číslo z rozsahu 1–29, login a heslo jako do SISu
  • Kopírování souborů z Windows:
    1. Nainstalujte si WinSCP.
    2. Vyberte Nové spojení (New Connection).
    3. Zadejte:
      • protokol: SFTP
      • hostitel (host): u-plXX.ms.mff.cuni.cz , místo XX zadejte číslo z rozsahu 1–29, např. u-pl21.ms.mff.cuni.cz
      • jméno a heslo – jako do SISu

Obsah