
Az EITC/IS/CCTF Computational Complexity Theory Fundamentals a számítástechnika alapjainak elméleti vonatkozásaival foglalkozó európai informatikai tanúsítási program, amely egyben az interneten széles körben használt klasszikus aszimmetrikus nyilvános kulcsú kriptográfia alapja.
Az EITC/IS/CCTF Computational Complexity Theory Fundamentals tananyaga a számítástechnika alapjairól szóló elméleti ismereteket és az olyan alapfogalmakon alapuló számítási modelleket foglalja magában, mint a determinisztikus és nemdeterminisztikus véges állapotú gépek, reguláris nyelvek, kontextusmentes grammatika és nyelvelmélet, automata elmélet, Turing. Gépek, problémák eldönthetősége, rekurzió, logika és algoritmusok összetettsége az alapvető biztonság érdekében az alábbi struktúrán belüli pályázatok, amelyek átfogó és strukturált EITCI-tanúsítványi tanterv öntanuló anyagokat foglalnak magukban, hivatkozott nyílt hozzáférésű videodidaktikai tartalommal, amelyek az EITC-tanúsítvány megfelelő vizsga letételével történő megszerzésére való felkészülés alapjául szolgálnak.
Egy algoritmus számítási összetettsége a működéséhez szükséges erőforrások mennyisége. Az idő- és memóriaforrások kiemelt figyelmet kapnak. Egy probléma összetettségét a megoldására szolgáló legjobb algoritmusok összetettségeként határozzuk meg. Az algoritmusok elemzése az explicit módon megadott algoritmusok komplexitásának vizsgálata, míg a számítási komplexitáselmélet a problémamegoldások komplexitásának tanulmányozása a legismertebb algoritmusokkal. Mindkét tartomány összefonódik, mert egy algoritmus összetettsége mindig a megoldandó probléma összetettségének felső korlátja. Ezenkívül gyakran szükséges egy-egy algoritmus összetettségét a megoldandó probléma összetettségével összehasonlítani, miközben hatékony algoritmusokat készítünk. A legtöbb esetben az egyetlen információ a probléma nehézségéről az, hogy ez kisebb, mint a leghatékonyabb ismert technikák összetettsége. Ennek eredményeként sok átfedés van az algoritmuselemzés és a komplexitáselmélet között.
A komplexitáselmélet nemcsak a számítástechnika alapjául szolgáló számítási modellek megalapozásában játszik fontos szerepet, hanem a klasszikus aszimmetrikus kriptográfia (úgynevezett nyilvános kulcsú kriptográfia) alapjaiban is, amely széles körben elterjedt a modern hálózatokban, különösen az interneten. A nyilvános kulcsú titkosítás bizonyos aszimmetrikus matematikai problémák számítási nehézségén alapul, mint például nagy számok faktorizálása prímtényezőibe (ez a művelet nehéz probléma a komplexitáselméleti osztályozásban, mivel nem ismertek hatékony klasszikus algoritmusok a megoldására az erőforrások polinomiális skálázásával, nem pedig exponenciálisan a probléma bemeneti méretének növekedésével, ami ellentétben áll egy nagyon egyszerű fordított művelettel, amikor az ismert prímtényezőkkel szorozzuk az eredeti nagy számot. Ezt az aszimmetriát felhasználva a nyilvános kulcsú kriptográfia architektúrájában (a nyilvános kulcs között számításilag aszimmetrikus reláció meghatározásával, amely könnyen kiszámítható privát kulcsból, míg a magánkulcsot nem lehet könnyen számítógépezni nyilvános kulcsból, nyilvánosan bejelentik a nyilvános kulcsot, és lehetővé teszik a többi kommunikációs oldal számára, hogy azt az adatok aszimmetrikus titkosítására használják, amelyeket ezután csak a csatolt privát kulccsal lehet visszafejteni, harmadik fél számára számításilag nem elérhető, így biztonságossá téve a kommunikációt).
A számítási komplexitás elméletét főként a számítástechnika és az algoritmika úttörőinek eredményei alapján dolgozták ki, mint például Alan Turing, akinek munkája kritikus volt a náci Németország Enigma titkosításának megtörésében, amely jelentős szerepet játszott abban, hogy a szövetségesek megnyerték a második világháborút. Az adatelemzés (főleg a titkosított kommunikáció) számítási folyamatainak kidolgozását és automatizálását célzó kriptoanalízis a rejtett információk feltárása érdekében a kriptográfiai rendszerek feltörésére és a titkosított, általában katonai katonai jelentőségű kommunikáció tartalmához való hozzáférésre szolgált. Ugyancsak a kriptoanalízis katalizálta az első modern számítógépek kifejlesztését (amelyeket kezdetben a kódtörés stratégiai céljára alkalmaztak). A Brit Colossust (amelyet az első modern elektronikus és programszámítógépnek tartanak) megelőzte a lengyel „bomba”, Marian Rejewski által az Enigma-rejtjelek feltörését segítő elektronikus számítási eszköz, amelyet a lengyel hírszerzés adta át Nagy-Britanniának. az elfogott német Enigma titkosítógép, miután Lengyelország 1939-ben megszállta Németországot. Az eszköz alapján Alan Turing fejlesztette ki a fejlettebb megfelelőjét a német titkosított kommunikáció sikeres megtörésére, amelyet később modern számítógépekké fejlesztettek.
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.
A tanúsítási tanterv részletes megismeréséhez bővítheti és elemezheti az alábbi táblázatot.
Az EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum nyílt hozzáférésű didaktikai anyagokra hivatkozik videó formában. A tanulási folyamat lépésről lépésre tagolódik (programok -> órák -> témák), amely lefedi a megfelelő tantervi részeket. A résztvevők válaszokat kaphatnak, és relevánsabb kérdéseket tehetnek fel az e-learning felület Kérdések és válaszok rovatában, az EITC program aktuális tananyagának témakörében. A tartományi szakértőkkel való közvetlen és korlátlan tanácsadás elérhető a platformba integrált online üzenetküldő rendszeren, valamint a kapcsolatfelvételi űrlapon keresztül is.
A tanúsítási eljárás részleteiért ellenőrizze Hogyan működik.
Elsődleges támogató tantervi olvasmányok
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Másodlagos támogató tantervi olvasmányanyagok
O. Goldreich, Bevezetés a komplexitáselméletbe:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Támogató tantervi olvasmányok a diszkrét matematikáról
J. Aspnes, Megjegyzések a diszkrét matematikához:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Támogató tantervi olvasmányok gráfelméletről
R. Diestel, Gráfelmélet:
https://diestel-graph-theory.com/
Töltse le az EITC/IS/CCTF Computational Complexity Theory Fundamentals program teljes offline önálló tanulási előkészítő anyagát PDF-fájlban
EITC/IS/CCTF előkészítő anyagok – standard változat
EITC/IS/CCTF előkészítő anyagok – kibővített változat felülvizsgálati kérdésekkel