Prednaska - Vypoctova zlozitost algoritmov 7.12.2020 9:15

Zhrnutie prednášky

Predposledná prednáška predmetu zhrnula triedy výpočtovej zložitosti. Výpočtová zložitosť problému je minimum zložitostí všetkých algoritmov, ktoré ho riešia, a funkcie zložitosti sa delia na polynomiálne a nepolynomiálne (exponenciálne). Trieda P obsahuje problémy riešiteľné deterministicky v polynomiálnom čase a trieda NP problémy riešiteľné nedeterministicky v polynomiálnom čase, pričom P je jej podmnožinou. Na príkladoch násobenia čísel (kvadratické, patrí do P) a farbenia vrcholov grafu tromi farbami (overenie je polynomiálne, no hľadanie rieši exponenciálne veľa možností) bolo ukázané, ako problémy zaraďovať. Potom boli zavedené NP-úplné problémy, na ktoré sa polynomiálne redukujú všetky problémy z NP, a ako príklad bola uvedená splniteľnosť booleovskej formuly v konjunktívnej normálovej forme, ktorú možno riešiť skúšaním všetkých hodnôt premenných.

• - Výpočtová zložitosť problému je minimum zložitostí všetkých algoritmov, ktoré ho riešia.
• - Trieda P: problémy riešiteľné deterministicky v polynomiálnom čase; P je podmnožinou NP.
• - Trieda NP: problémy riešiteľné nedeterministicky v polynomiálnom čase, riešenie sa dá overiť v polynomiálnom čase.
• - Násobenie dvoch n-ciferných čísel má kvadratickú zložitosť, patrí teda do P.
• - Farbenie vrcholov grafu tromi farbami je typický NP problém: overenie je O(n²), prehľadanie všetkých možností je 3ⁿ.
• - NP-úplný problém je v NP a všetky ostatné problémy z NP sa naň dajú polynomiálne redukovať.
• - Príklad NP-úplného problému: splniteľnosť booleovskej formuly v konjunktívnej normálovej forme (SAT), riešiteľná skúšaním všetkých 2ⁿ priradení.

Zhrnutie pripravené s pomocou AI z prepisu videa.