Maturitarozbory témat
2

Algoritmus

📚 ZAL
Příprava: 15 min
Zkouška: 15 min
📖

Teorie

Algoritmus je konečná, jednoznačná a efektivní posloupnost kroků vedoucích k řešení úlohy. Řídicí struktury: sekvence, větev, cyklus. Složitost: časová a prostorová (O-notation). Typické rodiny: vyhledávání (lineární, binární), řazení (bubble/insert/merge/quick), procházení grafů/stromů (BFS, DFS). Důležité je korektnost (částečná a úplná) a invarinaty cyklů.

🎯

Tahák

  • 1Vlastnosti: konečnost, determinovanost, obecnost, správnost, efektivita
  • 2Řídicí struktury: sekvence / if / for/while
  • 3Big-O: O(1), O(log n), O(n), O(n log n), O(n^2)
  • 4Příklady: binární vyhledávání, quicksort, BFS/DFS
❓

Typické otázky u maturity

  • 1Jak odvodíte časovou složitost binárního vyhledávání?
  • 2Vysvětlete invarinatu cyklu na příkladu inserčního řazení.
🏷️

Klíčová slova

algoritmussložitostBig-OBFSDFSquicksort
⚡

Praktická část

Zadání:

Implementujte binární vyhledávání v TypeScriptu a dokažte jeho časovou složitost.

Kroky:

  1. 1Napište funkci binarySearch
  2. 2Ošetřete prázdné pole a nenalezení prvku
  3. 3Uveďte důkaz O(log n) přes půlení intervalu

Kód:

binarySearch.ts
export function binarySearch(arr: number[], x: number): number {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === x) return m;
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1;
}

Kontrolní seznam:

  • ✓Korektnost pro nalezený i nenalezený prvek
  • ✓Hraniční případy
  • ✓Důkaz O(log n)

Časté chyby:

  • ⚠️Přetečení při (l+r)/2 – proto l + ((r-l)>>1)
  • ⚠️Nesprávné ukončení cyklu