Algoritmizace

Zde naleznete aktuální informace k předmětu KMI/XALGO.

Seznam přednášek

• 25.9. Úvod do algoritmů, pdf
• 9.10. Časová složitost algoritmů, pdf

Literatura

• slajdy ke kurzu Algoritmizace z prezenčního studia od prof. Bělohlávka (1. část a 2. část)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein, 2009)
• Průvodce labyrintem algoritmů (Mareš, Valla, 2022, odkaz zde)

Samostudium

1. Sada úkolů

• definujte pojmy: problém, instrukce, algoritmus a řešení problému algoritmem
• přečtěte si kapitolu 1.1 v Průvodce labyrintem algoritmů
• podívejte se na důkaz správnosti Euklidova algoritmu, který naleznete ve slajdech od prof. Bělohlávka (slajdy 52–53)
• navrhněte pseudokód algoritmů pro tyto problémy:
  1. Problém: součet lichých čísel
     • Vstup: dvě přirozená čísla m, n
     • Výstup: součet všech lichých čísel nacházejících se mezi m a n (včetně m i n)
  2. Problém: test prvočíselnosti
     • Vstup: přirozené číslo m
     • Výstup: true, pokud je m prvočíslo, jinak false
  3. Problém: mocniny čísla menší než n
     • Vstup: dvě přirozená čísla m, n, kde m ≥ 2
     • Výstup: vypíše všechny mocniny čísla m, tj. m⁰, m¹, m², …, které jsou menší než n

2. Sada úkolů

• definujte: časová složitost v nejhorším, nejlepším a průměrném případě, O, Ω a Θ
• navrhněte pseudokód algoritmu, který sečte všechna sudá čísla v poli, a určete T^max(n), T^min(n) a T^avg(n) (předpokládejte, že každé číslo je se stejnou pravděpodobností sudé nebo liché)
• rozhodněte a z definice zdůvodněte, zda platí: 2n² + 5n = Ω(n³), 2n² + 5n = Θ(n²), 2ⁿ⁺¹ = O(2ⁿ), 2²ⁿ = O(2ⁿ)
• proč tvrzení „linear-search má složitost O(n)“ platí ve všech třech případech (nejhorším, nejlepším i průměrném), ale to samé neplatí pro Ω(n)?
• doplňující materiály: 2. část slajdů od prof. Bělohlávka (od str. 28) – příklady na asymptotické meze, příklady na ostré meze a vztahy mezi jednotlivými pojmy
• doplňující materiály: Průvodce labyrintem algoritmů (kapitoly 2.1 až 2.4)