A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Teória zložitosti je časť teoretickej informatiky zaoberajúca sa množstvom požadovaných zdrojov počas výpočtu riešiaceho daný problém. Najčastejšie uvažovaným zdrojom je čas (koľko krokov je potrebných na vyriešenie problému) a priestor (koľko pamäti je potrebnej na vyriešenie problému). Príklady ďalších zdrojov sú počet paralelných procesorov a celková práca vynaložená na riešenie problému v paralelnom systéme. Teória zložitosti sa odlišuje od teórie vypočítateľnosti, ktorá skúma len či sa problém dá vyriešiť alebo nie, bez uvažovania o potrebných zdrojoch.
Prehľad
Po založení teórie objasňujúcej, ktoré problémy sa dajú algoritmicky riešiť a ktoré nie, bolo prirodzené sa pýtať na relatívnu výpočtovú zložitosť vypočítateľných funkcií.
Na problémy sa pozeráme ako na formálne jazyky, a tak jeden "problém" je často celá množina otázok, kde každá otázka je slovo konečnej dĺžky z tohto jazyka. Napríklad, problém FAKTORIZÁCIA je špecifikovaný nasledovne: na vstupe je dané celé číslo zapísané v binárnom tvare, na výstupe požaduje všetky prvočíselné faktory tohto čísla. Jedna takáto otázka (teda konkrétne jedno slovo z jazyka) sa nazýva inštancia problému; napr. "vráť všetky prvočíselné faktory čísla 15" je jedna inštancia problému FAKTORIZÁCIA.
Zložitosť problému väčšinou neudávame pre každú inštanciu zvlášť, ale pre celú triedu inštancií, ktoré majú rovnakú veľkosť problému, čo je väčšinou počet bitov vstupu Turingovho stroja, ktorý problém rieši. Zložitosť je takto vyjadrená ako funkcia závislá od veľkosti vstupu. Pre konkrétnu veľkosť problému nás teda môžu zaujímať viaceré druhy zložitostí: zložitosť najhoršieho prípadu, čo je maximum cez všetky inštancie danej veľkosti, zložitosť najlepšieho prípadu, teda minimum cez všetky inštancie danej veľkosti, či priemerná zložitosť. Nie je zvykom udávať kompletný predpis zložitostnej funkcie, ale len jej asymptotický odhad.
Časová zložitosť problému je počet krokov, ktoré vykoná Turingov stroj pri riešení inštancie problému.
Pamäťová zložitosť problému je maximum z počtu použitých políčok na pracovných páskach Turingovho stroja.
Nasledujúca tabuľka udáva časové zložitosti často používaných algoritmov na triedenie:
Algoritmus | Najlepší prípad | Priemerný prípad | Najhorší prípad |
---|---|---|---|
Triedenie priamym vkladaním (Insert Sort) | O(n) | O(n2) | (n2) |
Rýchle triedenie (Quick Sort) | O(n logn) | O(n logn) | (n2) |
Triedenie haldou (Heap Sort) | O(n logn) | O(n logn) | (n logn) |
Triedenie zlučovaním (Merge Sort) | O(n logn) | O(n logn) | (n logn) |
Výpočtová zložitosť má dve základné miery:
Optimalizácia algoritmu sa týka minimalizácie jednej alebo obidvoch mier zložitosti.
Výpočtová zložitosť algoritmu priamo nesúvisí so zložitosťou samotného algoritmu z ľudského pohľadu. Algoritmus môže byť veľmi jednoduchý na pochopenie i implementáciu, napriek tomu môže byť jeho výpočtová zložitosť veľká a naopak.
Druhy výpočtovej zložitosti v závislosti od počtu vstupných prvkov n, (a,b,c sú konštanty, t je čas):
- lineárna zložitosť:
- logaritmicko lineárna:
- polynomiálna: t je funkciou nejakého polynómu n
- algoritmy so zložitosťou väčšou než je polynomiálna
Za rýchle algoritmy sa pokladajú prvé tri druhy.
Ilustráciou zložitosti je nasledujúca tabuľka, predpokladajme, že vykonanie jednej operácie trvá jednu mikrosekundu:
Funkcia počtu operácií | 20 | 40 | 60 | 80 | 100 | 200 | 500 | 1000 |
---|---|---|---|---|---|---|---|---|
n | 20 µs | 40 µs | 60 µs | 80 µs | 100 µs | 200 µs | 500 µs | 1000 µs |
n.log n | 86 µs | 0,2 ms | 0,35 ms | 0,5 ms | 0,7 ms | 1,5 ms | 4,5 ms | 10ms |
n2 | 0,4 ms | 1,6 ms | 3,6 ms | 6,4 ms | 10 ms | 40 ms | 0,25s | 1 s |
n3 | 8 ms | 64 ms | 0,22 ms | 0,5 ms | 1 s | 8 s | 125 s | 17 min |
n4 | 0,16 s | 2,56s | 13 s | 41 s | 100 s | 27 min | 17 h | 11,6 dní |
2n | 1 s | 11,7 dní | 36 600 r | 3,6.109 r | ||||
n! | 77 000 r |
Z uvedenej tabuľky vidno, že aj keby sme rýchlosť operácii zväčšili 1000x, posledný algoritmus by bol tak či tak neriešiteľný v rozumnom čase a predposledný pre väčšie n tiež.
Tú istú úlohu možno väčšinou riešiť rôznymi algoritmami s rozličnou výpočtovou zložitosťou. Napríklad triedenie sa dá jednoducho implementovať s výpočtovou zložitosťou n2, ale existujú aj algoritmy triedenia so zložitosťou n.log n.
Rozhodovacie problémy
Množstvo problémov, ktoré teória zložitosti skúma, je rozhodovacích. Rozhodovací problém je problém, ktorý má booleovskú odpoveď ÁNO/NIE. Napríklad, problém JE-PRVOČÍSLO je nasledovný: na vstupe je dané celé číslo zapísané binárne, na výstup vráť (teda rozhodni) či je prvočíslo alebo nie je. Rozhodovací problém je jazyk. Pre konkrétny problém sa tento jazyk skladá z tých inštancií problému, na ktoré je kladná odpoveď.
Rozhodovacie problémy sa uvažujú veľmi často, pretože každý problém sa dá redukovať na ekvivalentný rozhodovací problém. Napríklad, problém MÁ-FAKTOR je nasledujúci: na vstupe sú celé čísla n a k zapísané binárne, na výstupe požadajume odpoveď, či n má nejaký prvočíselný faktor menší ako k. Je zrejmé, že keď dokážeme vyriešiť problém MÁ-FAKTOR s istými zdrojmi, môžeme vyriešiť celý problém FAKTORIZÁCIA bez zreteľného nárastu zdrojov. Stačí urobiť len binárne vyhľadávanie na k pokiaľ nenájdeme najmenší faktor n. Potom vydelíme vstup týmto faktorom a pokračujeme ďalej, kým ich nenájdeme všetky.
Je potrebné si dať pozor, či skúmame jazyk kladných alebo záporných odpovedí. Ak vieme rozpoznávať jazyk kladných odpovedí (t. j. dávať odpoveď ÁNO) pre nejaký problém s istými zdrojmi, neznamená to, že vieme s takými istými zdrojmi rozpoznávať aj jazyk záporných odpovedí. Napríklad, množinu NP môžeme definovať ako množinu všetkých problémov, ktorých kladné inštancie vieme rozpoznať v nedeterministickom polynomiálnom čase. Naopak, množina Co-NP bude množina problémov, ktorých záporné inštancie vieme rozpoznať v nedeterministickom polynomiálnom čase. Dodnes nevieme, v akom vzťahu tieto triedy sú.
Dôležitý (aj keď možno trochu pesimistický) výsledok teórie zložitosti je fakt, že nech vymyslíme ľubovoľne ťažký problém (t. j. nech vyžaduje ľubovoľne veľa času a pamäti na riešenie), vždy existujú ešte ťažšie problémy. Konkrétne pre časovú zložitosť a triedu rozhodujúcich problémov v polynomiálnom čase tento výsledok hovorí veta o časovej hierarchii. Podobná veta o priestorovej hierarchii sa dá tiež sformulovať.
Často používané triedy zložitosti
Zložitostná trieda P je množina všetkých (rozhodovacích) problémov, ktoré sa dajú riešiť na deterministickom Turingovom stroji v polynomiálnom čase. Táto trieda zodpovedá intuitívnej predstave problémov, ktoré vieme efektívne riešiť.
Zložitostná trieda NP je množina (rozhodovacích) problémov, ktoré sa dajú riešiť na nedeterministických Turingových strojoch v polynomiálnom čase. Do tejto triedy patrí väčšina z nášho pohľadu zložitých problémov, ktoré by sme veľmi radi riešili efektívne, napríklad SAT, problémy hamiltonovských ciest či problém vrcholového pokrytia.
Problém P=NP
Triviálne platí inklúzia . Otázka, či trieda P je tá istá ako trieda NP (teda či platí rovnosť), je azda najdôležitejšia otvorená otázka informatiky v súčasnosti. Na riešenie problému je vypísaná cena 1 000 000 $.
Otázky ako táto evokujú koncepty ťažkosti a úplnosti. Množina problémov X je ťažká pre triedu problémov Y (X je Y-ťažká), ak každý problém z triedy Y sa dá v polynomiálnom čase transformovať na problém z X. Inými slovami, riešenie problémov v X je aspoň také „ťažké“, ako riešenie (všetkých) problémov z Y. Množina X je úplná pre Y (X je Y-úplná), ak je X je Y-ťažká a navyše . Dodnes sme našli mnoho problémov, ktoré sú (samostatne) NP-úplné (teda každý z nich je NP-ťažký a patrí do NP). Dôvod, prečo ich hľadáme a ďalej študujeme je ten, že podľa tejto definície stačí nájsť efektívne riešenie (teda deterministické v polynomiálnom čase) len pre jeden z nich a tým automaticky máme efektívne riešenie pre celú triedu NP (vďaka polynomiálnej transformovateľnosti).
Významní vedci v oblasti teórie zložitosti
Externé odkazy
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk