I-ADS

Cvičenia:

  • Cvičenie 1:
    • cvicenie1.pdf
    • cvicenie1data.txt
    • Pre neorientovaný graf G=(V,E) bez slučiek vymyslite (greedy) algoritmus na jeho vrcholové ofarbenie (pozrite si aj Brookovu vetu). Skúste nájsť graf, ktorý Váš algoritmus nedokáže ofarbiť minimálnym počtom farieb.
    • Pozrite si Kruskalov algoritmus na nájdenie najlacnejšej kostry grafu.
    • Napíšte algoritmus, ktorý pre dané vstupné pole n prirodzených čísel, pričom každý prvok poľa patrí do intervalu <0;k>, predspracuje vstup a po predspracovaní dokáže odpovedať na otázku,  koľko prvkov poľa patrí do intervalu <a;b> pre ľubovoľné a,b také, že 0 ≤ a ≤ b ≤ k, s výpočtovou zložitosťou O(1). Zložitosť predspracovania môže byť Θ(n + k).
  • Cvičenie 2:
  • Cvičenie 3:
  • Cvičenie 4:
  • Cvičenie 5:
  • Cvičenie 6:
  • Cvičenie 7:
  • Cvičenie 8:
    • Úloha 35.1-3 zo s.1111 z knihy Cormen a kol.: Introduction to algorithms
      Professor Bundchen navrhuje nasledovnú heuristiku na riešenie problému vrcholového pokrytia. Opakovane vyberajte vrchol s najväčším stupňom a odstráňte všetky hrany s ktorými inciduje. Nájdite príklad, na ktorom ukážete, že profesorova heuristika nemá aproximačný pomer 2.
      (Pomôcka: Skúste bipartitný graf s vrcholmi rovnakých stupňov vľavo a vrcholmi rôznych stupňov vpravo.)
  • Cvičenie 9:
    • Experimentálne overte aproximačný pomer pre znáhodnený algoritmus na riešenie problému MAX3SAT.