Algoritmy 1 prof. RNDr. Tomáš Masopust, DSc.

• Vše potřebné bude komunikováno na přednášce či hromadným emailem.
• Link na studijní text obdržíte v prvním týdnu semestru hromadným emailem.
• Přednáška: čtvrtek 13:15 - 14:45 (následně je místnost rezervována pro dotazy a případné hromadné konzultace)
• Cvičení
  • Účast na cvičení alespoň 75 %.
  • Domácí úkoly, nutno odevzdat alespoň 75 % (tj. 8) úkolů, viz UPolníček.
• Zkouška – písemná, termíny
  • úterý 5. ledna 2027 od 10:00 do 12:00 hodin
  • středa 20. ledna 2027 od 10:00 do 12:00 hodin (řádný i opravný)
  • čtvrtek 4. února 2027 od 10:00 do 12:00 hodin (řádný i opravný)
  • čtvrtek 17. června 2027 od 10:00 do 12:00 hodin (pouze opravný)
• Co umět ke zkoušce?
  • Jednou větou: Navrhnout algoritmus pro jednoduchý problém, dokázat jeho korektnost a analyzovat jeho časovou složitost.
  • Detailněji:
  • Znát pojmy algoritmus, časová složitost algoritmu, složitost v nejhorším a průměrném případě, korektnost algoritmu.
  • Asymptotická notace: definice, vlastnosti, příklady použití.
  • Řešení rekurentních rovnic - Master theorem a jeho použití.
  • Základní datové struktury: pole, seznam, zásobník, fronta.
  • Řazení - definice problému a přístupy k jeho řešení.
  • Řazení porovnáváním: Insert sort, Select sort, Bubble sort, Quick sort, Merge sort, Heap sort.
  • Časová složitost řadicích algoritmů.
  • Další metody řazení: Counting sort, Radix sort, Bucket sort.
  • Pořádkové statistiky.
• Zajímavosti:
  • Nejstarší doložené dokumenty obsahující algoritmy jsou téměř čtyři tisíce let staré.
  • Zajímavá esej o tom, že algoritmus je jazykem moderní vědy.