Sylabus prenášky
Podmínkou pro zapsání je absolvování kursu IB002 Návrh algoritmů I.

• Složitost algoritmu -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  
• Metody analýzy složitosti algoritmů --- shluková technika, technika účtů, potenciálová metoda.
  
• Datové struktury --- binomiální a Fibonacciho halda, datové struktury pro reprezentaci disjunktních množin. Příklady použití.
  
• Techniky návrhu efektivních algoritmu --- divide et impera, dynamické programování, hladové algoritmy. Obecná formulace, aplikace, teoretické základy.
  
• Grafové algoritmy --- kostry v grafech, problém nejkratších cest, toky v sítích, párování.
• Algoritmy pro práci s řetezci --- přímý algoritmus, Rabin-Karpův algoritmus, užití konečných automatů.
  
• Algoritmy pro NP-těžké problémy --- aproximativní a náhodnostní algoritmy.

Podmínky absolvování předmětu

K úspěšnému absolvování předmetu zkouškou je potřeba řešit sady problémů a absolvovat písemný test na konci semestru.

• Sady problémů

  V průběhu semestru budou zveřejněny 3 sady problémů k řešení. Sady naleznete  ve Studijních materiálech předmětu.
  Maximální počet bodů, které lze získat za jejich řešení je 340.
  Pro absolvování predmětu zkouškou je nutné získat z těchto 340 bodů alespoň 170 bodů.
  

• Písemný test

  Termíny pro písemný test budou zveřejněny cca třetí týden výuky.
  Maximální počet bodů, které lze za test získat je 160.
  Pro absolvování předmetu zkouškou je nutné získat z těchto 160 bodů alespoň 80 bodů.
  

• Výsledné hodnocení

  Výsledné hodnocení je závislé od počtu bodů, které student získá za vyřešené problémy, písemný test a na cvičeních; a to následujícím způsobem:

  
  

  >= 450 bodů  --- hodnocení A
  

  >= 400 bodů  --- hodnocení B
  

  >= 350 bodů  --- hodnocení C
  

  >= 300 bodů  --- hodnocení D
  

  >= 250 bodů  --- hodnocení E
  

  <= 249 bodů  --- hodnocení F
  

Konzultace
K dotazům využívejte, prosím, diskusní fórum předmětu.

Individuální konzultace je potřebné dohodnout  mailem.