Cvičenie - Vypočítateľnosť algoritmov.

Ciele

Oboznámiť sa s organizáciou predmetu Algoritmy a zložitosť.
Zvládnuť základné definície z oblasti výpočtovej zložitosti.
Naučiť sa vyhľadávať zdroje, oboznámiť sa so štruktúrou algoritmov a používať kurzový materiál pri softvérovej implementácii aplikačných úloh. % . %
Rozlíšiť typy zložitosti algoritmov.

Úvod

Predmet Algoritmy a zložitosť je predmetom zameraným na výpočtovú zložitosť algoritmov, triedy P, NP, NPC, heuristiky a pseudopolynomiálne algoritmy.
Oboznámte sa s organizáciou predmetu % Algoritmy a zložitosť a podmienkami udelenia zápočtu. V prípade nejasností sa opýtajte cvičiaceho.
Na každom cvičení musí byť študent schopný prezentovať aktuálne zadanie. Bez aktuálnych zdrojových textov je jeho účasť na cvičení zbytočná. Hlavný dôraz je na cvičeniach kladený na prezentáciu zadania a konzultáciu s cvičiacim.
Študijné materiály sú v systéme Moodle - predmet % Algoritmy a zložitosť . Prihlasovací kľúč
Študent si môže zvoliť režim práce "Samostatné zadanie", pričom voľbu zadania prekonzultuje s cvičiacim, ktorý určí jeho vhodnosť. Body za zadanie môže cvičiaci prideľovať aj postupne podľa vlastného uváženia s ohľadom na aktivitu študenta. Režim priebežných kontrol napredovania študenta pri vypracovávaní zadania je preferovaný.

Postup

Príklad: Koľko operácií je potrebných na výpočet súčinu dvoch štvorcových \(n\times n\) matíc \(A=(a_{ij}), B=(b_{ij})\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij}), \, B=(b_{ij})\) sú \(n\times n\) matice. Potom pre ich súčinovú maticu \(C=(c_{ij})\) platí: \[c_{ij}=\sum\limits_{k=1}^n a_{ik}\times b_{kj}.\]

Počet operácií \(+\) pre výpočet jedného elementu \(c_{ij}\) je \(n-1\).

Počet operácií \(\times \) pre výpočet jedného elementu \(c_{ij}\) je \(n\).

Celkový počet operácií pre výpočet jedného elementu \(c_{ij}\) je \(n-1+n=2n-1\).

Celkový počet operácií pre výpočet všetkých elementov matice \(C\) je \(n^2(2n-1)\).
Zobraziť riešenie Skryť riešenie
Príklad: Koľko operácií je potrebných na výpočet mocniny \(A^p\) štvorcovej \(n\times n\) matice \(A=(a_{ij})\) pre \(p\in N\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Potom pre jej \(p-\)tú mocninu \(A^p=(a^{(p)}_{ij})\) platí: \[a^{(p)}_{ij}=\sum\limits_{k=1}^n a^{(p-1)}_{ik}\,a_{kj}.\] Vytvoríme postupnosť \(A,\,A^2,\,\ldots \,,\,A^{p}\).

Podľa predchádzajúceho príkladu počet operácií potrebných na výpočet súčinu dvoch štvorcových \(n\times n\) matíc je \(n^2(2n-1)\).

Počet násobení matíc je \(p-1\).

Celkový počet operácií pre výpočet matice \(A^p\) je \((p-1)n^2(2n-1)\).
Zobraziť riešenie Skryť riešenie
Príklad: Koľko operácií je potrebných na výpočet metrickej matice \[\Gamma(A)=A\oplus A^2\oplus\dots\oplus A^n,\] kde \(A=(a_{ij})\) je \(n\times n\) matica a operácia \(\oplus\) reprezentuje maximum a operácia \(\otimes\) reprezentuje \(+\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Podľa predchádzaj[úceho príkladu je počet operácií potrebných na vytvorenie postupnosti za sebou idúcich mocnín zadanej matice \(A,\,A^2,\,\ldots \,,\,A^{n}\) daný hodnotou \((n-1)n^2(2n-1)\).

Počet operácií \(\oplus\) pre výpočet jedného prvku metrickej matice \(\gamma_{ij}\) je daný hodnotou \(n-1\).

Celkový počet operácií \(\oplus\) potrebných na výpočet všetkých prvkov metrickej matice je \(n^2(n-1)\).

Celkový počet operácií na výpočet metrickej matice \(\Gamma(A)\) je \((n-1)n^2(2n-1)+n^2(n-1)\).
Zobraziť riešenie Skryť riešenie
Príklad: Problém obchodného cestujúceho (Traveling Salesman Problem -- TSP) V individuálnej úlohe TSP je dané prirodzené číslo \( n>0 \) a matica vzdialeností medzi každou dvojicou \( n \) miest vo forme \( n\times n \) matice \( (d_{ij}) \), \( d_{ij}\in Z^+ \) (\( Z^+ \) je označenie pre kladné celé čísla). Problém: Nájsť uzavretú cestu, ktorá prechádza každým mestom práve raz, a pritom zo všetkých takýchto ciest má minimálny súčet ohodnotení hrán.
Riešenie:

Počet uzavretých ciest, ktoré obchádzajú všetky mestá práve raz je \(\frac{(n-1)!}{2}\).

Počet operácií \(+\)potrebných na výpočet váhy jednej cesty je \(n-1\).

Počet operácií potrebných na výpočet váh všetkých ciest je \(\frac{(n-1)(n-1)!}{2}\).

Počet operácií porovnania dvoch prvkov potrebných na výber najmenšieho prvku je \(\frac{(n-1)!}{2}-1\).

Celkový počet operácií potrebných na nájdenie uzavretej cesty s minimálnou váhou, ktorá obchádza všetky mestá práve raz, je \(\frac{(n-1)(n-1)!}{2}+(\frac{(n-1)!}{2}-1)\).

Jedná sa o neefektívny algoritmus, pretože je počet operácií potrebných na vyriešenie TSP-problému popísaným spôsobom vyjadrený pomocou faktoriálu. Medzi neefektívne algoritmy radíme aj tie, ktoré vyžadujú exponenciálny počet operácií.
Zobraziť riešenie Skryť riešenie
Úloha: Oboznámte sa s ďalšími algoritmami pre TSP problém.
Úloha: Aký je rozdiel medzi nimi?

Zdroje

Algoritmy a zložitosť

Doplňujúce úlohy

Úloha: Popíšte aspoň jeden efektívny algoritmus na riešenie sústavy lineárnych rovníc.

Úloha: Popíšte aspoň jeden neefektívny algoritmus na riešenie sústavy lineárnych rovníc.

Úloha: Popíšte aspoň jeden efektívny algoritmus na výpočet determinantu matice.

Úloha: Popíšte aspoň jeden neefektívny algoritmus na výpočet determinantu matice.

Úloha: Navrhnite efektívny algoritmus na usporiadanie \( n \) čísel podľa veľkosti.

Úloha: Navrhnite efektívny algoritmus na testovanie súvislosti grafu.

Úloha: Navrhnite aspoň jeden algoritmus na nájdenie aspoň jednej kostry grafu.

Úloha: Navrhnite algoritmus na hľadanie všetkých kostier grafu.

Úloha: Formulujte nasledujúci optimalizačný problém ako inštanciu, pričom je treba definovať množinu prípustných riešení \( F \) a cenovú funkciu \( c \).\\ Nájdite najkratšiu cestu medzi dvoma vrcholmi ohodnoteného grafu.

Úloha: Popíšte metódu na odčítanie decimálnych prirodzených čísel ako algoritmus.

Úloha: Zostrojte algoritmus pre nasledujúci problém: Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.\\ Je daný graf \( G=(V,E) \). Existuje v \( G \) cyklus \( (u,v,w,z,u) \) taký, že \( (v,z),\ (u,w)\not\in E \), pričom\\ (i) \( u,v,w,z \) sú ľubovoľné vrcholy\\ (ii) \(u,v,w,z \) sú pevne dané?

Úloha: Zostrojte algoritmus pre nasledujúci problém: Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.\\ Pre dané \( p\in N \) rozhodnite, či \( p \) je prvočíslo.

Úloha: Zostrojte algoritmus pre nasledujúci problém: Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.\\ Pre dané \( x,y,z \in N \) rozhodnite, či existuje \( n>0,\ n\in N \) také, že platí: \( x^n+y^n=z^n. \)

Úloha: Zostrojte algoritmus pre nasledujúci problém: Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu. Daný je graf \( G=(V,E) \) a \( s,t\in V \). Existuje v \(G \) cesta z vrchola \( s \) do vrchola \( t \)?