Cvičenia: 10. týždeň

Ciele cvičení:

• poznať a vedieť implementovať algoritmy na nájdenie najlacnejšej kostry
• vedieť, čo sú to greedy algoritmy
• vedieť argumentovať, že greedy algoritmus vypočíta korektné riešenie

Najlacnejšia kostra

Implementujte Primov (a/alebo) Kruskalov algoritmus

• nemusí ísť o tak efektívnu implementáciu, ako bola prezentovaná na prednáške (t.j. s prioritnou frontou a Union/Find údajovou štruktúrou)

Algoritmy si môžete precvičiť pri riešení úlohy z ŠVK 2012:

• http://palma.strom.sk/SVK2012/C/

Rozdiskutujte formálny dôkaz korektnosti Primovho (a/alebo) Kruskalovho algoritmu.

Greedy algoritmy

• Festivalové leto I aplikovaním greedy stratégie podľa návodu na riešenie 7. sady zadaní
  • Formálne dokážte, že použitá greedy stratégia vedie ku optimálnemu riešeniu (nápoveda: http://en.wikipedia.org/wiki/Activity_selection_problem)
• Vyriešte úlohy 3-5 z cvičení (Exercises): http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/07-greedy.pdf
  • Ak sa rozhodnete pre greedy stratégiu, nezabudnite dokázať, že je korektná.
  • Pokúste sa vyriešiť aspoň jednu z úloh.

Ďalšie úlohy

• Zuzka je true partygirl ! Keďže má v srdiečku miesto pre každého tak sa rozhodla, že po skončení karantény usporiada obrovskú párty, kam chce pozvať všetkých svojich kamarátov. Aby sa party dobre rozbehla a aj pokračovala dostal odporúčanie od sociológov, že je dobre ak každý hosť pozná aspoň 5 iných hostí a aspoň 5 hostí nepozná a môže sa s nimi zoznámiť. Zuzka si spravila zoznam všetkých hostí a všetkých dvojíc ktoré sa poznajú. Vymyslite algoritmus, pomocou ktorého nájde najväčšiu množinu hostí ktorá spĺňa dané podmienky.
• Martin ako správny informatik si uvedomuje, že znalosti z jedného predmetu môže aplikovať aj v inom predmete a tým byť ešte lepší. Na princípoch počítačov sa učil pracovať s jednoduchým počítačom. Ten však nemal konštanty iné ako 0 a 1 (ktorú bolo náročné dosiahnuť). Ale ak má jednotku pomocou základných operácii pripočítanie 1 a vynásobenie čísla dvojkou z nej môže dostať ľubovoľné prirodzené číslo. Napríklad 10=1+1+1+1+1+1+1+1+1+1. Ale existuje aj rýchlejšia cesta 10=(((1+1)*2+1)*2). Navrhnite algoritmus, ktorí vypočíta minimálny počet operácii potrebných na dosiahnutie čísla n.