I-ADS

Cvičenia:

 

Zadania z r. 2023

  • Cvičenie x:
  • 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:
    • Naprogramujte dynamické pole s operáciou vkladania tak, že pri požiadavke na zväčšenie poľa sa alokuje dvojnásobná veľkosť pôvodného poľa.
    • Urobte amortizovanú analýzu operácií vkladania v takomto poli.
    • https://mrlvsb.github.io/upr-skripta/c/pole/dynamicka_pole.html
    • Ak stihnete, naprogramujte aj operáciu vymazávania.
  • Cvičenie 10:
    • Nasledujúce dva znáhodnené algoritmy sa dajú použiť pre riešenie problému 3-SAT. Napíšte program, ktorý využíva tieto algoritmy pre riešenie uvedeného problému a experimentálne ich porovnajte (t.j. napr. rýchlosť s akou nájdu interpretáciu premenných, pre ktoré je daná formula pravdivá.)
    • 3-sat
  • Cvičenie 11:
  • Kontrolovanie zadania č. 2 (za 15 bodov) – pokyny
    • Vopred si otestujte Váš program pre veľké vstupy a prípadne zmerajte čas trvania.
    • Veľké testovacie vstupy pre zadanie č. 2:
    • grafy
    • Vstupný graf s 18 vrcholmi (správnosť riešenia je overtiteľná vizuálne):
    • graph18
  • Cvičenie 12