EITC/IS/CCTF számítási komplexitáselmélet alapjai

Mivel az algoritmus futtatásához szükséges erőforrások mennyisége a bemenet méretétől függően változik, a komplexitást általában f(n) függvényként fejezzük ki, ahol n a bemenet mérete, f(n) pedig vagy a legrosszabb eset bonyolultsága ( a szükséges erőforrások maximális mennyisége az összes n méretű bemenetre vonatkozóan, vagy az esetek átlagos összetettsége (az erőforrások mennyiségének átlaga az összes n méretű bemenetre vonatkoztatva). Az n méretű bemeneten szükséges elemi műveletek számát általában időbonyolultságként adják meg, ahol az elemi műveletekről úgy gondolják, hogy egy adott számítógépen állandó időt vesznek igénybe, és csak egy állandó tényezővel változnak, ha egy másik gépen futnak. Az n méretű bemeneten az algoritmus által igényelt memória mennyiségét térbonyolultságnak nevezzük.

Az idő a leggyakrabban figyelembe vett erőforrás. Ha a „komplexitás” kifejezést minősítő nélkül használjuk, az általában az idő összetettségére utal.

A hagyományos időegységeket (másodperc, perc és így tovább) nem alkalmazzák a komplexitáselméletben, mivel túlságosan függenek a választott számítógéptől és a technológia fejlődésétől. Például egy mai számítógép lényegesen gyorsabban tud végrehajtani egy algoritmust, mint egy 1960-as évekbeli számítógép, ez azonban a számítógépes hardver technológiai áttöréseinek köszönhető, nem pedig az algoritmus velejárói. A komplexitáselmélet célja, hogy számszerűsítse az algoritmusok belső időigényét, vagy azokat az alapvető időkorlátokat, amelyeket egy algoritmus bármilyen számítógépre előírna. Ezt úgy érik el, hogy megszámolják, hány alapvető műveletet hajtanak végre a számítás során. Ezeket az eljárásokat általában lépéseknek nevezik, mivel úgy tekintik, hogy egy adott gépen állandó időt vesznek igénybe (azaz nincs hatással rájuk a bemenet mennyisége).

Egy másik fontos erőforrás az algoritmusok végrehajtásához szükséges számítógépmemória mennyisége.

Egy másik gyakran használt erőforrás az aritmetikai műveletek mennyisége. Ebben a forgatókönyvben az „aritmetikai összetettség” kifejezést használjuk. Az időbonyolultság általában az aritmetikai bonyolultság szorzata egy állandó tényezővel, ha ismert a számítás során előforduló számok bináris reprezentációjának méretére vonatkozó felső korlát.

A számítás során felhasznált egész számok mérete sok módszernél nincs korlátozva, és irreális azt feltételezni, hogy az aritmetikai műveletekhez meghatározott időre van szükség. Ennek eredményeként az időbonyolultság, más néven bitbonyolultság lényegesen nagyobb lehet, mint az aritmetikai összetettség. Egy nn egész mátrix determinánsának kiszámításának aritmetikai nehézsége például O(n^3) standard technikák esetén (Gauss-elimináció). Mivel az együtthatók mérete a számítás során exponenciálisan nőhet, ugyanazon módszerek bitkomplexitása exponenciális n-ben. Ha ezeket a technikákat a többmoduláris aritmetikával együtt alkalmazzuk, a bit bonyolultsága O(n^4-re) csökkenthető.

A bit összetettsége formális értelemben az algoritmus futtatásához szükséges biteken végzett műveletek számát jelenti. A legtöbb számítási paradigmában megegyezik az időbeli összetettséggel egészen egy állandó tényezőig. A számítógépek által megkövetelt gépszavakon végzett műveletek száma arányos a bit bonyolultságával. A valósághű számítási modellek esetében az időbonyolultság és a bitkomplexitás így azonos.

A rendezés és keresés során gyakran figyelembe vett erőforrás a bejegyzések összehasonlítása. Ha az adatok jól vannak elrendezve, ez jól jelzi az idő bonyolultságát.

Az összes lehetséges bemeneten lehetetlen megszámolni az algoritmus lépéseinek számát. Mivel egy bemenet összetettsége a méretével nő, általában a bemenet n méretének függvényeként ábrázolják (bitekben), így a komplexitás n függvénye. Azonos méretű bemenetek esetén azonban az algoritmus összetettsége jelentősen változhat. Ennek eredményeként számos komplexitási függvényt rutinszerűen alkalmaznak.

A legrosszabb eset komplexitása az összes komplexitás összege minden n méretű bemenetre, míg az átlagos bonyolultság az összes komplexitás összege minden n méretű bemenetre (ez logikus, mivel az adott méretű lehetséges bemenetek száma véges). Ha a „komplexitás” kifejezést további definíció nélkül használjuk, akkor a legrosszabb eseti összetettséget veszik figyelembe.

A legrosszabb eset és az átlagos eset bonyolultságát köztudottan nehéz helyesen kiszámítani. Ezen túlmenően ezeknek a pontos értékeknek kevés gyakorlati alkalmazása van, mivel a gépben vagy a számítási paradigmában bekövetkezett bármilyen változás kis mértékben változtatja a bonyolultságot. Továbbá az erőforrás-felhasználás nem fontos kis n érték esetén, ezért a könnyű implementáció gyakran vonzóbb, mint az alacsony bonyolultság kis n esetén.

Ezen okok miatt a legtöbb figyelmet a komplexitás viselkedésére fordítják magas n esetén, azaz aszimptotikus viselkedésére, amikor n közeledik a végtelenhez. Ennek eredményeként általában a nagy O jelölést használják a bonyolultság jelzésére.

Számítási modellek

A komplexitás meghatározása szempontjából fontos a számítási modell kiválasztása, amely az időegység alatt végrehajtandó lényeges műveletek meghatározásából áll. Ezt néha többszalagos Turing-gépnek is nevezik, ha a számítási paradigma nincs konkrétan leírva.

A determinisztikus számítási modell az, amelyben a gép következő állapotait és a végrehajtandó műveleteket teljes mértékben az előző állapot határozza meg. A rekurzív függvények, a lambda-számítás és a Turing-gépek voltak az első determinisztikus modellek. A véletlen hozzáférésű gépek (más néven RAM-gépek) népszerű paradigmák a valós számítógépek szimulálására.

Ha a számítási modell nincs definiálva, általában egy többszalagos Turing-gépet feltételeznek. A többszalagos Turing-gépeken az időbonyolultság ugyanaz, mint a RAM-gépeknél a legtöbb algoritmus esetében, bár jelentős odafigyelést igényelhet az adatok memóriában való tárolása az egyenértékűség eléréséhez.

A nem determinisztikus számítási modellben, például a nem determinisztikus Turing-gépekben a számítás egyes lépéseinél különféle választások választhatók. A komplexitáselméletben az összes megvalósítható opciót egyszerre veszik figyelembe, a nem-determinisztikus időbonyolultság pedig az az idő, amelyre szükség van, amikor mindig a legjobb döntéseket hozzuk. Másképpen fogalmazva, a számítás egyidejűleg annyi (azonos) processzoron történik, amennyi szükséges, és a nem determinisztikus számítási idő az az idő, amely alatt az első processzor befejezi a számítást. Ezt a párhuzamosságot fel lehet használni a kvantumszámításban, ha speciális kvantumalgoritmusok futtatásakor szuperponált összefonódott állapotokat használunk, mint például az apró egész számok Shor-féle faktorizálása.

Még ha egy ilyen számítási modell jelenleg nem is használható, elméleti jelentősége van, különösen a P = NP problémával kapcsolatban, amely azt kérdezi, hogy a „polinomiális idő” és a „nem-determinisztikus polinomidő” használatával előállított összetettségi osztályok felsőbbrendűek-e. a határok ugyanazok. Egy determinisztikus számítógépen egy NP-algoritmus szimulálásához „exponenciális idő” szükséges. Ha egy feladat polinomiális időben megoldható nem determinisztikus rendszeren, akkor az NP nehézségi osztályba tartozik. Ha egy probléma az NP-ben van, és nem könnyebb, mint bármely más NP probléma, akkor azt NP-teljesnek mondják. A hátizsák-probléma, az utazó eladó-probléma és a logikai kielégítési probléma mind NP-teljes kombinatorikus problémák. A legismertebb algoritmus exponenciális összetettséggel rendelkezik mindezen problémák esetén. Ha ezek bármelyike ​​megoldható lenne polinomiális időben egy determinisztikus gépen, akkor az összes NP probléma megoldható lenne polinomiális időben is, és P = NP jönne létre. 2017-től széles körben elterjedt a P NP feltételezése, ami arra utal, hogy az NP problémák legrosszabb helyzeteit alapvetően nehéz megoldani, azaz sokkal tovább tart, mint bármely lehetséges időtartam (évtizedek) érdekes bemeneti hosszok mellett.

Párhuzamos és elosztott számítástechnika

A párhuzamos és elosztott számítástechnika magában foglalja a feldolgozás felosztását több processzor között, amelyek mindegyike egyszerre működik. A különböző modellek közötti alapvető különbség a processzorok közötti adattovábbítás módja. A processzorok közötti adatátvitel párhuzamos számításoknál jellemzően nagyon gyors, míg az elosztott számítástechnikában a processzorok közötti adatátvitel a hálózaton keresztül történik, így lényegesen lassabb.

Egy N processzoron végzett számítás legalább az egyetlen processzoron eltöltött idő N hányadosát veszi igénybe. A valóságban, mivel egyes részfeladatok nem párhuzamosíthatók, és egyes processzoroknak meg kell várniuk egy másik processzor eredményét, ez az elméletileg ideális korlát soha nem fog megvalósulni.

A kulcsfontosságú összetettségi probléma tehát az, hogy olyan algoritmusokat kell kidolgozni, amelyek a számítási idő és a processzorok számának szorzata a lehető legközelebb álljon ahhoz az időhöz, amely ugyanazon számítás elvégzéséhez szükséges egyetlen processzoron.

Kvantumszámítás

A kvantumszámítógép egy kvantummechanikán alapuló számítási modellel rendelkező számítógép. A Church–Turing tézis igaz a kvantumszámítógépekre, ami azt jelenti, hogy minden olyan probléma, amelyet egy kvantumszámítógép meg tud oldani, egy Turing-gép is megoldhat. Néhány feladat azonban elméletileg megoldható kvantumszámítógép használatával, nem pedig egy lényegesen alacsonyabb időbeli bonyolultságú klasszikus számítógéppel. Ez egyelőre szigorúan elméleti, hiszen senki sem tudja, hogyan kell gyakorlati kvantumszámítógépet kifejleszteni.

A kvantumkomplexitás elméletét a kvantumszámítógépekkel megoldható különböző típusú problémák vizsgálatára hozták létre. A posztkvantum kriptográfiában használják, amely a kvantumszámítógépes támadásokkal szemben ellenálló kriptográfiai protokollok létrehozásának folyamata.

A probléma összetettsége (alsó határok)

A probléma megoldására alkalmas algoritmusok – beleértve a fel nem fedezett technikákat is – bonyolultságának a hiányossága a probléma összetettsége. Ennek eredményeképpen egy probléma összetettsége megegyezik bármely, azt megoldó algoritmus bonyolultságával.

Ennek eredményeként bármely nagy O jelöléssel megadott összetettség az algoritmus és a kísérő probléma összetettségét egyaránt képviseli.

Másrészt a probléma összetettségének nem triviális alsó határainak meghatározása gyakran nehéz, és erre kevés stratégia létezik.

A legtöbb probléma megoldásához minden bemeneti adatot be kell olvasni, ami az adatok nagyságával arányos időt vesz igénybe. Ennek eredményeképpen az ilyen problémák legalább lineáris bonyolultságúak, vagy nagy omega-jelöléssel Ω(n) komplexitásúak.

Egyes problémák, például a számítógépes algebra és a számítási algebrai geometria problémáinak nagyon nagy megoldásai vannak. Mivel a kimenetet meg kell írni, a bonyolultságot a kimenet maximális mérete korlátozza.

A rendezési algoritmushoz szükséges összehasonlítások számának nemlineáris alsó határa Ω(nlogn). Ennek eredményeként a legjobb rendezési algoritmusok a leghatékonyabbak, mivel bonyolultságuk O(nlogn). Az a tény, hogy vannak n! n dolog megszervezésének módjai ehhez az alsó határhoz vezetnek. Mert minden összehasonlítás felosztja ezt az n gyűjteményt! Két részre osztva az összes sorrend megkülönböztetéséhez szükséges N összehasonlítás számának 2N > n!-nek kell lennie, ami a Stirling-képlet szerint O(nlogn)-t jelent.

Egy probléma másik problémára való redukálása általános stratégia a csökkentett összetettségi korlátok elérésére.

Algoritmus fejlesztés

Az algoritmusok összetettségének értékelése a tervezési folyamat fontos eleme, mivel hasznos információkkal szolgál a várható teljesítményről.

Gyakori félreértés, hogy a modern számítógépek teljesítményének exponenciális növekedését előrevetítő Moore-törvény következtében az algoritmusok összetettségének értékelése kevésbé lesz releváns. Ez helytelen, mert a megnövekedett teljesítmény hatalmas mennyiségű adat (big data) feldolgozását teszi lehetővé. Például bármely algoritmusnak egy másodpercnél rövidebb idő alatt jól kell működnie, ha néhány száz bejegyzésből álló listát, például egy könyv bibliográfiáját, ábécé sorrendbe rendezi. Másrészt millió bejegyzéshez (például egy nagyváros telefonszámaihoz) az O(n2) összehasonlítást igénylő alapalgoritmusoknak billió összehasonlítást kellene végrehajtaniuk, ami 10-es sebesség mellett három órát vesz igénybe. millió összehasonlítás másodpercenként. A gyorsrendezés és az egyesített rendezés viszont csak nlogn-összehasonlítást igényel (az előbbi esetében átlagos összetettség, az utóbbi esetében a legrosszabb eset bonyolultsága). Ez körülbelül 30,000,000 1,000,000 3 összehasonlítást eredményez n = 10 XNUMX XNUMX esetén, ami másodpercenként XNUMX millió összehasonlításnál mindössze XNUMX másodpercet vesz igénybe.

Ennek eredményeként a komplexitás felmérése lehetővé teheti számos nem hatékony algoritmus kiküszöbölését a megvalósítás előtt. Ez összetett algoritmusok finomhangolására is használható anélkül, hogy minden lehetséges változatot tesztelni kellene. A komplexitás vizsgálata lehetővé teszi, hogy egy komplex algoritmus legköltségesebb lépéseinek meghatározásával összpontosítsuk az erőfeszítéseket egy megvalósítás hatékonyságának növelésére.