Úvod

Funkce, řetězce, moduly

Prostředky pro strukturování kódu:

Bloky kódu (oddělené odsazením), např:

for i in range(10): 
	print("Budu se pilně učit.")

Programy = soubory $j m \overset{e}{ˊ} n o . p y$
Funkce

Pole

Pole Hodnoty a reference Další příklady

Strukturování kódu

Bloky kódu určují se odsazením (for, if, while …).
Program = soubor .py.
Funkce – umožňují rozdělit kód na logické části.

Funkce

Předdefinované

max(2,3)   # 3
abs(-3.4)  # 3.4
pow(2,3)   # 8

Matematické (modul `math`)

import math
math.sqrt(4.0)          # 2.0
math.sin(math.pi/6)     # 0.5

Vlastní definice

def square(x):
    return x*x

Funkce může volat jinou funkci → skládání.
Existují i hotové funkce (math.hypot místo vlastní pythagorovy věty).

Složitější příklady

Happy Birthday program s funkcí print_happy() a argumentem name.
Exponenciála exp(x) aproximovaná pomocí Taylorovy řady:
- podproblémy: faktoriál, výpočet sumy, porovnání s math.exp.

Parametry a návratové hodnoty

Funkce mohou mít:
- různé počty parametrů,
- více návratových hodnot (vrací n-tici).
return může být na více místech.
Existují i funkce bez návratu (vrací None).

Lokální a globální proměnné

Globální: definované mimo funkce → viditelné všude.
Lokální: jen uvnitř funkce.
Lokální může zastínit globální.

⚠️ Používej co nejméně globálních proměnných.

Vedlejší efekty

Funkce může kromě vrácení hodnoty měnit prostředí (tisknout, zapisovat, měnit proměnné).
Čisté funkce = bez vedlejších efektů → lepší na analýzu a testování.

Funkce vyššího řádu

Funkce může přijímat jinou funkci jako argument:

def twice(f, x):
    return f(f(x))

Lze použít lambda pro rychlou definici:

lambda x : 1 + 1/x

Moduly

Modul = .py soubor s funkcemi.
Import pomocí import math, import sys.
Používáme kvalifikovaná jména: math.cos, sys.argv.
Správný styl:

  if __name__ == "__main__":
    main()

→ zajistí, že kód se spustí jen při přímém spuštění, ne při importu.

Řetězce

Typ str = posloupnost znaků.
Indexování od 0:

	s = "Ahoj lidi"
	s[0]   # 'A'
	len(s) # 9

Spojování: a + b.
Řetězce jsou neměnné (immutable).

Náhodná čísla

import random
random.randrange(0, n)  # náhodné číslo 0..n-1

Příklad: simulace hodu mincí.
Příklad: výpočet průměru náhodně vybíraných čísel.

Shrnutí

V této přednášce jsi poznal:

jak psát funkce,
jak fungují návratové hodnoty a parametry,
rozdíl lokální vs. globální proměnné,
práci s moduly,
řetězce a jejich vlastnosti,
generování náhodných čísel.

Pole / seznamy

List = dynamické pole, může obsahovat různé typy.
Indexování od 0: a[0], záporné indexy: a[-1].
Přístup k podlistu (slice): a[i:j], a[i:], a[:j], a[:].

a = [0.3, 0.6, 0.1]
print(a[0])  # 0.3
a[2] = 1.5

Délka: len(a).
Součet: sum(a).
Maximum: max(a).
Spojování: a + b.
Opakování: a * 3.

Vytváření seznamů

Výčtem: [0.3, 0.6, 0.1]
Opakováním: [0]*10
Z posloupnosti: list(range(1,11))
Přidáváním: a += [0.0]
List comprehension: [i*i for i in range(1,11)]

Algoritmy a programování – výpisky

Autor: Jan Kybic (FEL ČVUT)
Zpracováno pro Obsidian – stručná verze bez kódu

🔢 Proměnné a výrazy

Program = transformace vstupů na výstupy.
Proměnná: pojmenované místo v paměti, do kterého ukládáme hodnotu.
Přiřazení: identifikátor = výraz.
Hodnota proměnné se může měnit (ale neměla by bez důvodu).

💬 Komentáře a základní části programu

Komentář začíná # – vysvětluje účel kódu.
Klíčová slova (např. if, else, for, while, import…) mají speciální význam.
Identifikátory: jména proměnných a funkcí (nesmí začínat číslem, nesmí být klíčové slovo).
Operátory: +, -, *, /, =, atd.
Datové typy:
- Celá čísla (int), reálná (float), řetězce (str).

📥 Vstup a výstup

print() – vypisuje data na výstup.
import sys – umožňuje čtení argumentů z příkazové řádky (sys.argv).
První argument (sys.argv[0]) = název programu.
Následující argumenty (sys.argv[1], sys.argv[2], …) = uživatelský vstup.
Formátování výstupu: možnost omezit počet desetinných míst, spojovat text s čísly.

⚠️ Chyby a ladění

Typy chyb

Syntaktické chyby (SyntaxError) – špatná struktura programu.
NameError – neznámé jméno proměnné nebo funkce.
ValueError – neplatná hodnota vstupu.
Logické chyby (bugy) – program běží, ale dává nesmyslné výsledky.

🧩 Řídicí struktury (Control Structures)

Používáme pro změnu pořadí vykonávání příkazů.

Podmínky

if, elif, else – rozhodování podle podmínek.
Porovnávací operátory: >, <, ==, !=, >=, <=.
Bloky kódu jsou určeny odsazením (indentací).
Možnosti:
- Jednoduchá podmínka: if podmínka: ...
- Dvou větví: if ... else
- Vnořená nebo zřetězená (if-elif-else).

🔁 Smyčky (Cykly)

Slouží k opakování části programu.

Smyčka `for`

Používá se pro známý počet opakování.
Typicky for i in range(n): – iterace přes sekvenci čísel.
Může mít parametry range(start, stop, step).
Umožňuje iteraci i přes kolekce (seznamy, řetězce, …).

Smyčka `while`

Opakuje se, dokud platí podmínka.
Může nahradit for, ale vyžaduje ruční inkrementaci proměnné.
Dá se snadno vytvořit nekonečný cyklus – nutná opatrnost.

Řízení běhu smyčky

break – ukončí cyklus.
continue – přeskočí aktuální iteraci.

Zkrácené přiřazení

Zápis typu x += 1 místo x = x + 1 (funguje i s jinými operátory).

🔣 Operátory dělení a modulo

/ – běžné dělení (float).
// – celé dělení (int).
% – zbytek po dělení (modulo).
Platí: (n // k) * k + (n % k) == n

📦 Datové struktury

Seznam (List)

Umožňuje ukládat více hodnot do jednoho objektu.
Prvky mohou být různých typů.
Indexování od 0.
Lze přidávat, mazat, měnit, procházet cyklem.
Důležité operace:
- přístup k prvku podle indexu,
- přidání prvku na konec,
- spojení dvou seznamů,
- hledání prvku,
- délka seznamu.

Zásobník (Stack)

LIFO – Last In, First Out.
Prvky se vkládají a odebírají z jednoho konce.
Typické operace:
- push – vložení prvku,
- pop – odebrání posledního prvku,
- top – přístup k vrcholu (bez odebrání),
- empty – kontrola, zda je prázdný.
Příklady použití:
- vyhodnocování výrazů,
- rekurze,
- návrat z funkcí.

Fronta (Queue)

FIFO – First In, First Out.
Prvky se vkládají na konec a odebírají ze začátku.
Typické operace:
- enqueue – vložení prvku,
- dequeue – odebrání prvku,
- peek – pohled na první prvek.
Použití:
- plánování procesů,
- obsluha požadavků,
- simulace front v reálných systémech.

Slovník (Dictionary)

Ukládá páry klíč–hodnota.
Rychlý přístup ke konkrétní hodnotě podle klíče.
Klíče musí být unikátní a neměnitelné (např. čísla, řetězce, n-tice).
Velmi efektivní pro mapování, vyhledávání nebo čítání výskytů.

🌀 Rekurze

Funkce, která volá sama sebe.
Musí mít základní (koncovou) podmínku, aby se zastavila.
Typické příklady:
- výpočet faktoriálu,
- Fibonacciho posloupnost,
- procházení stromových struktur.

Princip rekurze

Definuj jednoduchý případ (base case).
Definuj, jak se problém rozdělí na menší části.
Každý krok se zpracuje znovu rekurzivně.

Výhody a nevýhody

✅ Elegantní, přirozené pro hierarchické problémy.
⚠️ Může být paměťově náročnější (každé volání = nový rámec).
⚙️ Lze často nahradit iterativním řešením se zásobníkem.

⏱️ Časová a paměťová složitost

Časová složitost

Popisuje, jak rychle roste doba výpočtu s velikostí vstupu (n).
Označuje se pomocí asymptotické notace O(n).
Typické případy:
- O(1) – konstantní čas,
- O(log n) – logaritmická (např. binární vyhledávání),
- O(n) – lineární (např. procházení seznamu),
- O(n log n) – např. rychlé třídění,
- O(n²) – dvojité smyčky, pomalé algoritmy,
- O(2ⁿ) – exponenciální (např. hrubá síla).

Paměťová složitost

Udává, kolik paměti program spotřebuje v závislosti na velikosti vstupu.
Rekurze vyžaduje více paměti (zásobník volání).

Asymptotická notace

O(…) – horní odhad (nejhorší případ).
Ω(…) – dolní odhad (nejlepší případ).
Θ(…) – přesný odhad (typický případ).

🔍 Vyhledávání

Lineární vyhledávání

Prochází všechny prvky sekvenčně, dokud nenajde hledaný.
Složitost O(n).
Výhoda: funguje na libovolné struktuře (i netříděné).

Binární vyhledávání

Funguje pouze na seřazeném poli.
Opakovaně dělí vyhledávaný prostor na poloviny.
Složitost O(log n).
Výrazně efektivnější než lineární vyhledávání.

🧩 Třídicí algoritmy (Sorting)

1. Bubblesort (bublinové třídění)

Opakovaně porovnává sousední prvky a vyměňuje je.
Po každém průchodu je největší prvek „na konci“.
Složitost: O(n²).
Jednoduchý, ale velmi neefektivní pro velká data.

2. Selection sort (výběrové třídění)

Opakovaně vybírá nejmenší prvek z nesetříděné části a přesouvá ho dopředu.
Složitost: O(n²).
Menší počet výměn než Bubblesort, ale podobná časová náročnost.

3. Insertion sort (vkládací třídění)

Prvky se postupně vkládají na správné místo v již setříděné části.
Složitost: O(n²), ale velmi efektivní pro malá pole nebo téměř setříděná data.

4. Merge sort (slučovací třídění)

Rozdělí pole na poloviny, rekurzivně je setřídí a sloučí.
Složitost: O(n log n).
Stabilní, efektivní, využívá princip „rozděl a panuj“.

5. Quick sort (rychlé třídění)

Vybere tzv. pivot, rozdělí prvky na menší a větší než pivot, a rekurzivně setřídí.
Průměrná složitost: O(n log n).
Nejhorší případ: O(n²) (např. již seřazené pole).
Velmi rychlý v praxi, často používaný.

6. Counting sort / Bucket sort

Vhodné pro celá čísla v omezeném rozsahu.
Neprovádí porovnávání, ale počítá výskyty.
Složitost: O(n + k) (k = rozsah hodnot).

🔗 Struktury a algoritmy v kontextu

Typ problému	Typ algoritmu	Typická složitost
Vyhledávání	Lineární, binární	O(n), O(log n)
Třídění	Bubblesort, Quicksort, Merge sort	O(n²) – O(n log n)
Práce s daty	Zásobník, fronta, seznam	O(1) – O(n)
Rekurze	Rozklad problému	závisí na hloubce
Optimalizace	Rozděl a panuj, heuristiky	různé

The Archive

Procházet

Algoritmy a programování