Kapitola 8: Formulace úlohy, vstup, výstup, podmínky řešení (algoritmus)

Otázky k zamyšlení

• Představ si, že chceš poslat SMS kamarádovi. Co je v tomto případě formulace úlohy, vstup, výstup a podmínky řešení?
• Proč je důležité přesně vědět, co je vstupem, než začneme něco dělat?
• Může mít jedna úloha více možných výstupů? Zkus vymyslet příklad.

Úkoly pro praxi

1. Plánování snídaně: Vyber si svou oblíbenou snídani (např. míchaná vajíčka). Popiš:
   • Formulace úlohy: Co je tvým cílem?
   • Vstup: Jaké suroviny a nástroje potřebuješ?
   • Výstup: Jak bude vypadat hotová snídaně?
   • Podmínky řešení: Jaké jsou pravidla (např. nesmíš použít mikrovlnku, musí to být hotové do 10 minut)?
2. Hledání cesty: Představ si, že jsi v neznámém městě a chceš se dostat na nádraží. Popiš:
   • Formulace úlohy: Co je tvým cílem?
   • Vstup: Jaké informace máš k dispozici (např. mapa, mobil s GPS, zeptáš se kolemjdoucích)?
   • Výstup: Co je výsledkem tvého snažení?
   • Podmínky řešení: Jaké jsou omezení (např. nesmíš použít taxi, musíš tam být do 30 minut)?

* Rozšíření pro pokročilé

Vlastnosti algoritmu (formálně)

Aby postup byl skutečným algoritmem, musí splňovat tyto vlastnosti:

• Konečnost: Algoritmus musí skončit po konečném počtu kroků.
• Určitost: Každý krok musí být jednoznačně definován, bez možnosti různých výkladů.
• Vstup: Algoritmus má nula nebo více vstupů.
• Výstup: Algoritmus má alespoň jeden výstup (výsledek).
• Efektivita: Každý krok musí být dostatečně jednoduchý, aby ho bylo možné provést v rozumném čase.

Časová a prostorová složitost

U algoritmů nás zajímá, jak rychle fungují a kolik paměti potřebují:

• Časová složitost: Jak dlouho algoritmus trvá v závislosti na velikosti vstupu.
• Prostorová složitost: Kolik paměti algoritmus potřebuje.
• O-notace: Způsob zápisu složitosti: O(1), O(n), O(n²), O(log n)...

Deterministické vs. nedeterministické algoritmy

• Deterministický: Vždy dává stejný výsledek pro stejný vstup.
• Nedeterministický: Může dát různé výsledky (např. používá náhodná čísla).

* Úkoly pro pokročilé

1. Word – Formální specifikace: Vyber si jednoduchý algoritmus (např. nalezení největšího čísla ze tří). Napiš formální specifikaci: Název, Vstup (včetně datového typu), Výstup, Preconditions (předpoklady), Postconditions (co platí po skončení).
2. Excel – Porovnání algoritmů: Vytvoř tabulku srovnávající dva algoritmy řazení: Bubble Sort a Quick Sort. Sloupce: Název, Časová složitost (průměr, nejhorší), Prostorová složitost, Výhody, Nevýhody.
3. Scratch – Měření času: Vytvoř ve Scratchi dva programy pro počítání od 1 do 100. První počítá po jedné, druhý skáče po 10 a doplňuje. Použij proměnnou "čas" a porovnej, který je rychlejší.
4. Scratch – Nedeterministický algoritmus: Vytvoř program, který náhodně vybere jednu ze tří možností (kámen, nůžky, papír). Spusť 10× a zapiš výsledky. Jsou vždy stejné?

** Rozšíření pro maturitní obory

Podrobně: Složitost algoritmů

O-notace (Big O) popisuje, jak roste čas nebo paměť s velikostí vstupu:

• O(1) – konstantní: Vždy stejný čas, nezávisí na velikosti (např. přístup k prvku pole).
• O(log n) – logaritmická: Velmi efektivní, zdvojnásobení dat přidá jen 1 krok (např. binární vyhledávání).
• O(n) – lineární: Čas roste přímo úměrně velikosti (např. procházení seznamu).
• O(n log n): Efektivní řazení (např. Quick Sort, Merge Sort).
• O(n²) – kvadratická: Pomalé pro velká data (např. Bubble Sort).
• O(2ⁿ) – exponenciální: Velmi pomalé, nepoužitelné pro velká data.

Rekurze

Rekurze je technika, kdy funkce volá sama sebe:

• Základní případ (base case): Podmínka pro ukončení rekurze.
• Rekurzivní případ: Volání funkce se změněným parametrem.

Flowgorithm – Pokročilé algoritmy

Ve Flowgorithm můžeš implementovat složitější algoritmy:

• Cykly While a For: Opakování kroků.
• Pole (Array): Uložení více hodnot.
• Vnořené struktury: Cyklus v cyklu, podmínka v podmínce.

** Úkoly pro maturitní obory

1. Flowgorithm – Maximum ze tří: Vytvoř algoritmus, který načte 3 čísla a najde maximum. Použij vnořené If podmínky nebo postupné porovnání.
2. Flowgorithm – Faktoriál: Vytvoř algoritmus pro výpočet faktoriálu pomocí cyklu While. Vstup: n, výstup: n!
3. Flowgorithm – Suma pole: Vytvoř algoritmus, který načte 5 čísel do pole a vypočítá jejich součet pomocí cyklu For.
4. Excel – Analýza složitosti: Vytvoř tabulku pro n = 1, 10, 100, 1000. Sloupce: O(1), O(log n), O(n), O(n²), O(2ⁿ). Vyplň hodnoty a vytvoř graf. Který algoritmus bys vybral pro 1 milion záznamů?
5. PowerPoint – Rekurze: Vytvoř prezentaci "Co je rekurze" (8-10 snímků). Vysvětli koncept, uveď příklady (faktoriál, Fibonacci), nakresli strom volání.
6. Word – Porovnání algoritmů: Napiš dokument srovnávající Bubble Sort, Selection Sort a Quick Sort. Zahrň: popis, pseudokód, složitost, kdy použít.

*** Rozšíření pro IT obory

Pokračujeme v učení Pythonu. V této kapitole se naučíš funkce, datové struktury a práci se soubory.

Funkce

Funkce je pojmenovaný blok kódu, který můžeš opakovaně volat:

# Definice funkce
def pozdrav(jmeno):
    """Pozdraví uživatele."""
    print(f"Ahoj, {jmeno}!")

# Volání funkce
pozdrav("Anna")  # Ahoj, Anna!

# Funkce s návratovou hodnotou
def secti(a, b):
    return a + b

vysledek = secti(5, 3)  # vysledek = 8

# Funkce s výchozí hodnotou parametru
def pozdrav2(jmeno, pozdrav="Ahoj"):
    print(f"{pozdrav}, {jmeno}!")

pozdrav2("Bob")           # Ahoj, Bob!
pozdrav2("Bob", "Čau")    # Čau, Bob!

# Více návratových hodnot
def deleni(a, b):
    podil = a // b
    zbytek = a % b
    return podil, zbytek

p, z = deleni(17, 5)  # p=3, z=2
        

Seznamy (Lists)

# Vytvoření seznamu
cisla = [1, 2, 3, 4, 5]
jmena = ["Anna", "Bob", "Cyril"]
mix = [1, "text", 3.14, True]

# Přístup k prvkům (indexování od 0)
print(jmena[0])    # Anna
print(jmena[-1])   # Cyril (poslední)

# Úprava seznamu
jmena.append("Dana")        # Přidá na konec
jmena.insert(1, "Eva")      # Vloží na pozici 1
jmena.remove("Bob")         # Odstraní první výskyt
smazany = jmena.pop()       # Odstraní a vrátí poslední

# Slicing (řezy)
cisla = [0, 1, 2, 3, 4, 5]
print(cisla[1:4])    # [1, 2, 3]
print(cisla[:3])     # [0, 1, 2]
print(cisla[3:])     # [3, 4, 5]
print(cisla[::2])    # [0, 2, 4] (každý druhý)

# Užitečné metody
cisla.sort()              # Seřadí
cisla.reverse()           # Otočí pořadí
delka = len(cisla)        # Počet prvků
soucet = sum(cisla)       # Součet
maximum = max(cisla)      # Maximum
        

Slovníky (Dictionaries)

# Slovník = páry klíč: hodnota
student = {
    "jmeno": "Jan Novák",
    "vek": 16,
    "trida": "2.A"
}

# Přístup k hodnotám
print(student["jmeno"])          # Jan Novák
print(student.get("vek"))        # 16
print(student.get("skola", "?")) # ? (výchozí hodnota)

# Úprava slovníku
student["vek"] = 17              # Změna hodnoty
student["skola"] = "SPŠ"         # Přidání nového klíče
del student["trida"]             # Smazání klíče

# Procházení slovníku
for klic in student:
    print(klic, student[klic])

for klic, hodnota in student.items():
    print(f"{klic}: {hodnota}")
        

Práce se soubory

# Čtení souboru
with open("data.txt", "r", encoding="utf-8") as f:
    obsah = f.read()           # Celý soubor jako text
    # nebo
    radky = f.readlines()      # Seznam řádků

# Zápis do souboru
with open("vystup.txt", "w", encoding="utf-8") as f:
    f.write("První řádek\n")
    f.write("Druhý řádek\n")

# Připojení na konec souboru
with open("log.txt", "a", encoding="utf-8") as f:
    f.write("Nový záznam\n")

# Čtení řádek po řádku (efektivní pro velké soubory)
with open("velky.txt", "r", encoding="utf-8") as f:
    for radek in f:
        print(radek.strip())   # strip() odstraní \n
        

Ošetření chyb (try/except)

# Základní ošetření
try:
    cislo = int(input("Zadej číslo: "))
    vysledek = 100 / cislo
    print(f"Výsledek: {vysledek}")
except ValueError:
    print("To není platné číslo!")
except ZeroDivisionError:
    print("Nelze dělit nulou!")
except Exception as e:
    print(f"Neočekávaná chyba: {e}")
finally:
    print("Tento kód se provede vždy.")

# Vyvolání vlastní chyby
def nastav_vek(vek):
    if vek < 0:
        raise ValueError("Věk nemůže být záporný!")
    return vek
        

Jednoduchý projekt: Seznam úkolů

# todo.py - jednoduchá aplikace TO-DO list

def zobraz_ukoly(ukoly):
    if not ukoly:
        print("Žádné úkoly!")
        return
    for i, ukol in enumerate(ukoly, 1):
        print(f"{i}. {ukol}")

def hlavni():
    ukoly = []

    while True:
        print("\n1. Zobrazit úkoly")
        print("2. Přidat úkol")
        print("3. Splnit úkol")
        print("4. Konec")

        volba = input("Vyber možnost: ")

        if volba == "1":
            zobraz_ukoly(ukoly)
        elif volba == "2":
            ukol = input("Nový úkol: ")
            ukoly.append(ukol)
            print("Úkol přidán!")
        elif volba == "3":
            zobraz_ukoly(ukoly)
            try:
                cislo = int(input("Číslo splněného: ")) - 1
                smazany = ukoly.pop(cislo)
                print(f"Splněno: {smazany}")
            except (ValueError, IndexError):
                print("Neplatná volba!")
        elif volba == "4":
            print("Nashledanou!")
            break

hlavni()
        

*** Praktické úkoly pro IT obory

1. Funkce: Napiš funkce pro výpočet: a) obsahu kruhu, b) obvodu obdélníku, c) zda je číslo prvočíslo.
2. Seznam: Napiš program, který načte 10 čísel od uživatele, uloží je do seznamu a vypíše: průměr, maximum, minimum, seřazený seznam.
3. Slovník: Vytvoř telefonní seznam (jméno: číslo). Přidej funkce: přidat kontakt, vyhledat, smazat, zobrazit vše.
4. Soubory: Napiš program, který přečte textový soubor a spočítá počet slov, řádků a znaků.
5. TO-DO list: Rozšiř ukázkový program o ukládání/načítání úkolů ze souboru, aby se neztratily po vypnutí.