Programování 1 (NPRG030) a Algoritmizace (NPRG062)

Algoritmizace - podmínky pro získání zápočtu:

  • vypracování domácích úkolů - dosažení alespoň 70% z celkového počtu bodů, "hranice přežití": 50% (pokud získáte alespoň 50% bodů, bude možné si body doplnit vyřešením dalších náhradních úloh)
  • docházka - za každou účast na cvičení získáte 1 bod navíc (nepočítá se do základu)
  • osobní prezentace alespoň jednoho domácího úkolu

Zápočet JE podmínkou ke zkoušce.

Programování - podmínky pro získání zápočtu:

  • aktivní práce v hodinách
  • pravidelné řešení domácích úkolů zadávaných v ReCodExu - dosažení alespoň 70% z celkového počtu bodů, "hranice přežití": 50%
  • na konci semestru - praktický zápočtový test u počítačů - test se bude psát na posledním cvičení, ve zkouškovém období budete mít 2 opravné pokusy
  • vypracování zápočtového programu (včetně zpracování písemné dokumentace)

V zimním semestru zkouška není.

Úlohy z Programování

Pro získání zápočtu je potřeba mít na konci semestru alespoň 70% z celkového počtu vypsaných bodů za domácí úlohy.

Praktické úlohy budou zpravidla zadávány každý týden.

Autor řešení musí být schopen na cvičení vysvětlit svůj program.

Úkoly se budou odevzdávat pomocí systému ReCodEx https://recodex.mff.cuni.cz/

Řešení úloh je samostatná práce! Můžete se samozřejmě o úlohách bavit mezi sebou, ale řešení musí vypracovat každý sám za použití svých vlastních schopností a vlastní inteligence.

Úlohy z Algoritmizace

Pro získání zápočtu je potřeba mít na konci semestru alespoň 70% z celkového počtu vypsaných bodů za domácí úlohy.

Plán: Bude zadáno 8 úkolů po 10 bodech.

Za účast na cvičení získáte 1 bonusový bod (docházka bude evidována v Postal Owl https://owl.mff.cuni.cz/).

Domácí úkoly z algoritmizace ("na papír") spočívají většinou v návrhu a slovním popisu efektivního algoritmu.

Úkoly se budou odevzdávat pomocí systému Postal Owl https://owl.mff.cuni.cz/.

Praktický zápočtový test u počítačů

Bude se jednat o úlohu zadanou v ReCodExu v podobném rozsahu jako úlohy zadávané v průběhu semestru. Pro úspěšné složení testu bude potřeba získat v ReCodExu plný počet bodů, tedy musí projít všechny testy. Hodnotí se nejen funkčnost vytvořeného programu, ale i to, jak je program navržen a naprogramován. Není při tom vyžadována (časová) optimalizace algoritmu. Stačí, nejsou-li ani algorimus ani jeho implementace "vysloveně hloupé". Vzhledem k omezenému času se nepožaduje, aby byl program komentován (i když komentáře vytvářené současně s programem vám mohou práci na programu podstatně zjednodušit i zrychlit).

Student musí být schopen svoje řešení vysvětlit.

Test se bude psát na školních počítačích.

Zápočtový program

Zápočtový program je rozsáhlejší než běžné úlohy v ReCodExu. Jeho účelem je, abyste si vyzkoušeli samostatně navrhnout a vytvořit větší program včetně načítání vstupů od uživatele, ošetření jejich korektnosti, odladění, napsání dokumentace. Téma pro svůj program si vybíráte sami (já ho musím schválit).

Postup, jak vypracovat zápočtový program:

  • vybrat si téma a domluvit se na něm se mnou (do Vánoc)
  • poslat krátkou specifikaci (do Silvestra)
  • napsat samotný program
  • napsat dokumentaci k programu - uživatelskou a programátorskou
  • program i dokumentaci průběžně ukládat na mff gitlab
  • až bude program hotový, odevzdat do Postal Owl link na repository na gitlabu; repository musí obsahovat: finální verzi programu, programátorskou a uživatelskou dokumentaci, případně testovací dat
  • domluvit si termín předvedení (nejčastěji tak, že se přihlásíte na vypsaný termín v SISu)
  • předvést mi program při krátké prezentaci, ukázat jeho funkce (na testovacích datech), popsat jak program pracuje, jaké algoritmy a datové struktury používá. Během předvedení byste měli být schopni program na požádání mírně upravit.

    Je možné, že s první verzí vašeho programu / dokumentace / testovacích dat / předvedení nebudu spokojená a budete je muset předělat. Proto nenechávejte předvedení až na poslední chvíli, abyste případné úpravy stihli ještě v termínu. (vše nejpozději do konce zimního zkouškového období 13.2.2026)

Při výběru témat pro své programy se můžete inspirovat např. na stránkách Martina Mareše: témata zápočtových programů - Martin Mareš nebo mezi tématy Tomáše Holana témata zápočtových programů - Tomáš Holan

O dokumentaci podle Martina Mareše:

Uživatelská dokumentace. To je stručný popis toho, jak se program používá (tedy třeba v jakém formátu se mu zadává vstup a v jakém vydá výstup). Nepište od ní evidentní věci, spíš to, co by bězný uživatel nečekal. Také by tam mělo být řečeno, co vlastně program dělá :)

Uživatelská dokumentace by také měla obsahovat návod, jak program spustit (jaké knihovny je potřeba doinstalovat, atd.)

Programátorská dokumentace. V ní je stručně popsáno, jak program funguje uvnitř. Nemusíte komentovat každý řádek programu, spíš popište celkovou koncepci. Pokud používáte nějaké netriviální algoritmy, je to dobré zmínit. Pokud používáte něco, co jste nevymysleli sami, je na místě citovat zdroje.

Text o dokumentaci k (nejen) zápočtovému programu od doktora Kryla: Jak psát dokumentaci zápočtového programu

Co bude/bylo na cvičení:

1. CVIČENÍ:

Algoritmizace
  • podmínky získání zápočtu
  • jednoduché algoritmy, invariant

  • Kuličky

    V nádobě jsou černé a bílé kuličky. Je tam Č černých a B bílých. Kuličky budu z nádoby odebírat následujícím způsobem: Vytáhnu dvě a místo nich jednu jinou vrátím do nádoby:

      Bílá  + Bílá  --> Bílá
  Černá + Bílá  --> Černá
  Černá + Černá --> Bílá

    Jakou barvu bude mít poslední kulička co v nádobě zbyde?

Programování

2. CVIČENÍ:

Algoritmizace
  • časová a paměťová složitost jednoduchých algoritmů
Programování

3. CVIČENÍ:

Algoritmizace
  • definice velkého O
  • dokazování tvrzení o asymptotických složitostech
Programování - pondělí
  • procvičování - seznam, indexování, slicing, operace se seznamem (.split() a další), načtení vstupu
Programování - čtvrtek
  • ladění ve VS Code, první funkce

4. CVIČENÍ:

Algoritmizace
  • dokažte nebo vyvraťte (některá z tvrzení jsme dokazovali na cvičení, případné dotazy na příštím cvičení)
    1. 5n + 3 ∈ O(n)
    2. n2 ∈ O(n3)
    3. 3n3 ∈ O(n2)
    4. 2n+1 ∈ O(2n)
    5. f(n) ∈ Θ(g(n)) -> g(n) ∈ O(f(n))
    6. f1(n) ∈ O(g(n)) a f2(n) ∈ O(g(n)) -> f1(n) + f2(n) ∈ O(g(n))
    7. f1(n) ∈ O(g(n)) a f2(n) ∈ O(g(n)) -> f1(n) * f2(n) ∈ O(g(n))
    8. f(n) ∈ O(g(n)) -> k*f(n) ∈ O(g(n)) pro libovolnou konstantu k>0.
    9. f(n) ∈ O(g(n)) -> 1/f ∈ O(g(n))
    10. f(n) ∈ O(g(n)) -> 1/f ∈ O(1/g(n))
Programování
  • ladění ve VS Code, první funkce

6. CVIČENÍ

Programování

8. CVIČENÍ

Algoritmizace
  • zásobník - další příklady použití
  • lineární spojové seznamy - základní operace
    • určit počet prvků
    • vypsat všechny hodnoty
    • nalezení posledního prvku
    • vyhledání prvku s danou hodnotou
    • přidání prvku na začátek, na konec seznamu
    • vytvoření seznamu z dat na vstupu
    • vytvoření kopie seznamu
    • přidání prvku na dané místo
    • přidání prvku do uspořádaného seznamu (na správné místo)
    • odebrání prvku ze začátku, z konce seznamu
    • odebrání daného prvku
    • zrušení všech prvků v seznamu s danou hodnotou
    • obrácení pořadí prvků v seznamu
    • uspořádání prvků v seznamu podle hodnoty
    • spojení dvou seznamů do jednoho (ze sebe)
  • rekurzivní generování - první pokusy
Programování

9. CVIČENÍ

Rekurzivní generování

  • Napište rekurzivní funkci, která vytiskne pro zadané n "šipku z hvězdiček": 
        *
    **
    ***
    ****
    ***
    **
    *
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n z nul a jedniček.
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n nebo kratší z nul a jedniček.
  • (Napište rekurzivní funkci, která vypíše všechny možné posloupnosti délky n z nul, jedniček, dvojek a trojek.)
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n z čísel od 0 do 9.
  • Naprogramujte rekurzivní funkci, která vygeneruje všechny posloupnosti 0 a 1 délky n, ve kterých je právě k jedniček.
  • Naprogramujte rekurzivní funkci, která vygeneruje všechny slova délky n, která se skládají ze slabik. Slabikou myslíme jednu souhlásku a jednu samohlásku, tedy souhlásky a samohlásky se ve slově mají střídat.
  • Napište rekurzivní funkci, která vypíše všechny možné rozklady čísla n na součet. Např. 
         5 = 1+1+1+1+1
     5 = 1+1+1+2
     5 = 1+1+3
     5 = 1+2+2
     5 = 1+4
     5 = 2+3
     5 = 5
  • (Microsoft Interview Question) Given a number n, print following pattern without using any loop. 
    Input: n = 16
Output: 16, 11, 6, 1, -4, 1, 6, 11, 16

Input: n = 10
Output: 10, 5, 0, 5, 10