Cvičenie 10 – Greedy

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:

• https://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): https://jeffe.cs.illinois.edu/teaching/algorithms/book/07-mst.pdf resp. https://jeffe.cs.illinois.edu/teaching/algorithms/book/04-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

• Ali a Boris su true partyboys! Keďže majú v srdiečkách miesto pre každého tak sa rozhodli, že po skončení semestra usporiadajú obrovskú párty, kam chcú pozvať všetkých svojich kamarátov. Aby sa party dobre rozbehla a aj pokračovala dostali 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ť. Ali a Boris si spravili 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.