EITC/IS/CCTF Computational Complexity Theory Fundamentals on eurooppalainen IT-sertifiointiohjelma tietojenkäsittelytieteen perusteiden teoreettisista näkökohdista, jotka ovat myös Internetissä laajalti käytetyn klassisen epäsymmetrisen julkisen avaimen kryptografian perusta.
EITC/IS/CCTF Computational Complexity Theory Fundamentalsin opetussuunnitelma kattaa teoreettisen tiedon tietojenkäsittelytieteen perusteista ja laskennallisia malleja peruskäsitteillä, kuten deterministiset ja epädeterministiset äärelliset koneet, säännölliset kielet, yhteydettömät kieliopit ja kielten teoria, automaatioteoria, Turing. Koneet, ongelmien ratkaistavuus, rekursio, logiikka ja algoritmien monimutkaisuus perustavanlaatuisille tietoturvasovelluksille seuraavassa rakenteessa, joka sisältää kattavan videodidaktisen sisällön referenssinä tälle EITC-sertifioinnille.
Algoritmin laskennallinen monimutkaisuus on sen käyttämiseen tarvittavien resurssien määrä. Aika- ja muistiresursseihin kiinnitetään erityistä huomiota. Ongelman monimutkaisuus määritellään parhaiden algoritmien monimutkaiseksi sen ratkaisemiseksi. Algoritmien analyysi tutkii eksplisiittisesti annettujen algoritmien monimutkaisuutta, kun taas laskennallinen kompleksisuusteoria tutkii ongelmaratkaisujen monimutkaisuutta tunnetuimmilla algoritmeilla. Molemmat alueet kietoutuvat toisiinsa, koska algoritmin monimutkaisuus on aina ylempi rajoite sen ratkaiseman ongelman monimutkaisuuteen. Lisäksi on usein tarpeen verrata tietyn algoritmin monimutkaisuutta ratkaistavan ongelman monimutkaisuuteen, kun rakennetaan tehokkaita algoritmeja. Useimmissa tapauksissa ainoa saatavilla oleva tieto ongelman vaikeudesta on, että se on pienempi kuin tehokkaimpien tunnettujen tekniikoiden monimutkaisuus. Tämän seurauksena algoritmianalyysin ja monimutkaisuusteorian välillä on paljon päällekkäisyyttä.
Monimutkaisuusteoria on tärkeä paitsi laskennallisten mallien perusteissa tietojenkäsittelytieteen perustana, myös klassisen epäsymmetrisen kryptografian (ns. julkisen avaimen kryptografia) perusteissa, joita levitetään laajalti nykyaikaisissa verkoissa, erityisesti Internetissä. Julkisen avaimen salaus perustuu tiettyjen epäsymmetristen matemaattisten ongelmien laskennalliseen vaikeuteen, kuten esimerkiksi suurten lukujen tekijöihin jakamiseen alkutekijöihin (tämä operaatio on vaikea ongelma kompleksisuusteorialuokituksessa, koska ei ole tunnettuja tehokkaita klassisia algoritmeja ratkaistavaksi se skaalauttamalla resurssit polynomiaalisesti eikä eksponentiaalisesti ongelman syötteen koon kasvaessa, mikä on toisin kuin hyvin yksinkertainen käänteinen operaatio kertomalla tunnetuilla alkutekijöillä alkuperäisen suuren luvun saamiseksi). Käyttämällä tätä epäsymmetriaa julkisen avaimen salausarkkitehtuurissa (määrittämällä julkisen avaimen välille laskennallisesti epäsymmetrinen suhde, joka voidaan helposti laskea yksityisestä avaimesta, kun taas yksityinen avain ei voi olla helposti tietokoneella julkisesta avaimesta, voidaan julkisesti ilmoittaa julkisesta avaimesta ja sallia muiden viestintäpuolten käyttää sitä tietojen epäsymmetriseen salaukseen, jonka salaus voidaan sitten purkaa vain kytketyllä yksityisellä avaimella, joka ei ole laskennallisesti saatavilla kolmansille osapuolille, mikä tekee viestinnästä turvallista).
Laskennallinen monimutkaisuusteoria kehitettiin pääasiassa tietojenkäsittelytieteen ja algoritmien edelläkävijöiden, kuten Alan Turingin, saavutusten perusteella, jonka työ oli kriittinen murtamaan natsi-Saksan Enigma-salauksen, jolla oli merkittävä rooli liittolaisten voittamisessa toisen maailmansodan. Salausanalyysillä, jolla pyrittiin suunnittelemaan ja automatisoimaan datan analysoinnin laskennallisia prosesseja (pääasiassa salattua viestintää) piilotiedon paljastamiseksi, käytettiin salausjärjestelmien murtamiseen ja salatun viestinnän sisältöön pääsemiseksi, yleensä strategisesti sotilaallisesti tärkeällä tavalla. Se oli myös kryptausanalyysi, joka katalysoi ensimmäisten nykyaikaisten tietokoneiden kehitystä (joita alun perin sovellettiin koodinmurron strategiseen tavoitteeseen). Brittiläistä kolossia (jota pidettiin ensimmäisenä nykyaikaisena elektroniikka- ja ohjelmatietokoneena) edelsi puolalainen "pommi", Marian Rejewskin suunnittelema elektroninen laskentalaite auttamaan Enigma-salausten murtamisessa ja jonka Puolan tiedustelupalvelu luovutti Iso-Britannialle. vangittu saksalainen Enigma-salauskone, sen jälkeen kun Puola miehitti Saksan vuonna 1939. Tämän laitteen pohjalta Alan Turing kehitti edistyneemmän vastineensa murtamaan onnistuneesti saksalaisen salatun viestinnän, joka on myöhemmin kehitetty nykyaikaisiksi tietokoneiksi.
Koska algoritmin suorittamiseen tarvittavien resurssien määrä vaihtelee syötteen koon mukaan, monimutkaisuus ilmaistaan yleensä funktiona f(n), jossa n on syötteen koko ja f(n) on joko pahimman tapauksen monimutkaisuus ( resurssien enimmäismäärä, joka tarvitaan kaikissa syötteissä, joiden koko on n) tai tapauksen keskimääräinen monimutkaisuus (resurssien määrän keskiarvo kaikista koon n syötteistä). Vaadittujen perusoperaatioiden lukumäärä syötteellä, jonka koko on n, ilmaistaan yleensä aikakompleksisuutena, jolloin perusoperaatioiden uskotaan vievän vakioaikaa tietyllä tietokoneella ja muuttuvan vain vakiokertoimella, kun ne suoritetaan eri koneella. Algoritmin vaatimaa muistia koon n syötteellä kutsutaan avaruuden kompleksisuudeksi.
Aika on useimmiten harkittu resurssi. Kun termiä "monimutkaisuus" käytetään ilman tarkennetta, se viittaa yleensä ajan monimutkaisuuteen.
Perinteisiä aikayksiköitä (sekunnit, minuutit ja niin edelleen) ei käytetä monimutkaisuusteoriassa, koska ne ovat liian riippuvaisia valitusta tietokoneesta ja tekniikan kehityksestä. Esimerkiksi tietokone nykyään pystyy suorittamaan algoritmin huomattavasti nopeammin kuin 1960-luvun tietokone, mutta tämä johtuu kuitenkin tietokonelaitteiston teknologisista läpimurroista eikä algoritmin luontaisesta laadusta. Monimutkaisuusteorian tavoitteena on kvantifioida algoritmien luontaiset aikatarpeet tai perustavanlaatuiset aikarajoitukset, jotka algoritmi asettaisi mille tahansa tietokoneelle. Tämä saadaan aikaan laskemalla, kuinka monta perustoimintoa laskennan aikana suoritetaan. Näitä toimenpiteitä kutsutaan yleisesti vaiheiksi, koska niiden katsotaan vievän vakioaikaa tietyllä koneella (eli syötteen määrä ei vaikuta niihin).
Toinen tärkeä resurssi on algoritmien suorittamiseen tarvittavan tietokoneen muistin määrä.
Toinen usein käytetty resurssi on aritmeettisten operaatioiden määrä. Tässä skenaariossa käytetään termiä "aritmeettinen monimutkaisuus". Aikamonimutkaisuus on yleensä aritmeettisen monimutkaisuuden tulo vakiokertoimella, jos laskennan aikana esiintyvien lukujen binääriesityksen koolle tiedetään ylempi rajoitus.
Laskennassa käytettävien kokonaislukujen kokoa ei ole rajoitettu monille menetelmille, ja on epärealistista olettaa, että aritmeettiset toiminnot vaativat tietyn ajan. Tämän seurauksena aikamonimutkaisuus, joka tunnetaan myös nimellä bittimonimutkaisuus, voi olla huomattavasti suurempi kuin aritmeettinen monimutkaisuus. Esimerkiksi nn kokonaislukumatriisin determinantin laskemisen aritmeettinen vaikeus on O(n^3) standarditekniikoille (Gaussin eliminaatio). Koska kertoimien koko saattaa kasvaa eksponentiaalisesti laskennan aikana, samojen menetelmien bittikompleksisuus on eksponentiaalinen n:ssä. Jos näitä tekniikoita käytetään yhdessä monimodulaarisen aritmeettisen kanssa, bitin monimutkaisuus voidaan pienentää arvoon O(n^4).
Bittien monimutkaisuus tarkoittaa muodollisesti algoritmin suorittamiseen tarvittavien bittien toimintojen määrää. Se vastaa ajallista monimutkaisuutta aina vakiotekijään asti useimmissa laskentaparadigmoissa. Tietokoneiden vaatimien konesanojen toimintojen määrä on verrannollinen bitin monimutkaisuuteen. Realistisissa laskentamalleissa aika- ja bittimonimutkaisuus ovat siis identtiset.
Lajittelussa ja haussa usein huomioitu resurssi on merkintöjen vertailut. Jos tiedot on järjestetty hyvin, tämä on hyvä osoitus ajan monimutkaisuudesta.
Kaikilla mahdollisilla syötteillä algoritmin vaiheiden lukumäärän laskeminen on mahdotonta. Koska syötteen monimutkaisuus kasvaa sen koon mukaan, se esitetään yleisesti syötteen koon n funktiona (bitteinä), joten monimutkaisuus on n:n funktio. Samankokoisten syötteiden kohdalla algoritmin monimutkaisuus voi kuitenkin vaihdella huomattavasti. Tämän seurauksena useita monimutkaisia toimintoja käytetään rutiininomaisesti.
Pahimman tapauksen monimutkaisuus on kaiken monimutkaisuuden summa kaikille koon n tuloille, kun taas keskimääräinen monimutkaisuus on kaiken monimutkaisuuden summa kaikille koon n tuloille (tämä on järkevää, koska mahdollisten syötteiden määrä tietyn kokoisille tuloille on äärellinen). Kun termiä "monimutkaisuus" käytetään määrittelemättä tarkemmin, otetaan huomioon pahimman mahdollisen ajan monimutkaisuus.
Pahimman tapauksen ja keskimääräisen tapauksen monimutkaisuus on tunnetusti vaikeaa laskea oikein. Lisäksi näillä tarkoilla arvoilla on vain vähän käytännön sovellusta, koska mikä tahansa muutos koneessa tai laskentaparadigmassa muuttaisi monimutkaisuutta hieman. Lisäksi resurssien käyttö ei ole ratkaisevaa pienille n:n arvoille, joten toteutuksen helppous on usein houkuttelevampaa kuin pieni monimutkaisuus pienelle n:lle.
Näistä syistä eniten huomiota kiinnitetään kompleksisuuden käyttäytymiseen korkealla n:llä, eli sen asymptoottiseen käyttäytymiseen n lähestyessä ääretöntä. Tämän seurauksena suurta O-merkintää käytetään yleisesti osoittamaan monimutkaisuutta.
Laskennalliset mallit
Laskentamallin valinta, jossa määritellään aikayksikössä suoritettavat olennaiset toiminnot, on ratkaiseva monimutkaisuuden määrittämisessä. Tätä kutsutaan joskus moninauhaiseksi Turingin koneeksi, kun laskentaparadigmaa ei ole erikseen kuvattu.
Deterministinen laskentamalli on sellainen, jossa koneen seuraavat tilat ja suoritettavat toiminnot ovat kokonaan edellisen tilan määrittelemiä. Rekursiiviset funktiot, lambda-laskenta ja Turingin koneet olivat ensimmäisiä deterministisiä malleja. Random-access-koneet (tunnetaan myös nimellä RAM-koneet) ovat suosittu paradigma tosimaailman tietokoneiden simuloinnissa.
Kun laskentamallia ei ole määritelty, oletetaan yleensä moninauhaiseksi Turingin koneeksi. Moninauhaisissa Turing-koneissa aika monimutkaisuus on sama kuin RAM-koneissa useimpien algoritmien kohdalla, vaikkakin tämän ekvivalenssin saavuttaminen saattaa vaatia huomattavaa huomiota tietojen tallentamiseen muistiin.
Erilaisia valintoja voidaan tehdä joissakin laskennan vaiheissa ei-deterministisessä laskentamallissa, kuten ei-deterministisessä Turingin koneessa. Monimutkaisuusteoriassa kaikki mahdolliset vaihtoehdot otetaan huomioon samanaikaisesti, ja epädeterministinen aikamonimutkaisuus on se aika, joka tarvitaan, kun parhaat valinnat tehdään aina. Toisin sanoen laskenta suoritetaan samanaikaisesti niin monella (identtisellä) prosessorilla kuin tarvitaan, ja ei-deterministinen laskentaaika on aika, joka ensimmäisellä prosessorilla kuluu laskennan suorittamiseen. Tätä rinnakkaisuutta voidaan käyttää kvanttilaskennassa käyttämällä päällekkäisiä kietoutuneita tiloja ajettaessa erikoistuneita kvanttialgoritmeja, kuten esimerkiksi Shorin pienten kokonaislukujen faktorointia.
Vaikka tällainen laskentamalli ei ole tällä hetkellä käyttökelpoinen, sillä on teoreettista merkitystä, erityisesti P = NP-ongelman suhteen, joka kysyy, ovatko monimutkaisuusluokat, jotka on tuotettu käyttämällä "polynomiaikaa" ja "ei-determinististä polynomiaikaa" vähintään ylempänä. rajat ovat samat. Deterministisellä tietokoneella NP-algoritmin simulointi vaatii "eksponentiaalista aikaa". Jos tehtävä voidaan ratkaista polynomiajassa epädeterministisessä järjestelmässä, se kuuluu NP-vaikeusluokkaan. Jos ongelma on NP:ssä eikä se ole helpompi kuin mikään muu NP-ongelma, sen sanotaan olevan NP-täydellinen. Reppureppu-ongelma, matkustava myyjä-ongelma ja Boolen tyytyväisyysongelma ovat kaikki NP-täydellisiä kombinatorisia ongelmia. Tunnetuin algoritmi on eksponentiaalinen monimutkaisuus kaikissa näissä ongelmissa. Jos jokin näistä kysymyksistä voitaisiin ratkaista polynomiajassa deterministisellä koneella, niin kaikki NP-tehtävät voitaisiin ratkaista myös polynomiajassa, ja P = NP muodostuisi. Vuodesta 2017 lähtien on yleisesti oletettu, että P NP, mikä viittaa siihen, että NP-ongelmien pahimmat tilanteet ovat pohjimmiltaan vaikeita ratkaista, eli vievät paljon kauemmin kuin mikään mahdollinen aikaväli (kymmeniä) mielenkiintoisilla syötteen pituuksilla.
Rinnakkais- ja hajautettu laskenta
Rinnakkais- ja hajautettu laskenta sisältää prosessoinnin jakamisen useille prosessoreille, jotka kaikki toimivat samanaikaisesti. Perusero eri mallien välillä on menetelmä, jolla data lähetetään prosessorien välillä. Tiedonsiirto prosessorien välillä on tyypillisesti erittäin nopeaa rinnakkaislaskennassa, kun taas prosessorien välinen tiedonsiirto hajautetussa laskennassa tapahtuu verkon yli ja on siten olennaisesti hitaampaa.
N:n prosessorin laskenta vaatii vähintään yhden prosessorin ajan N:n osamäärän. Todellisuudessa, koska joitain alitehtäviä ei voida rinnastaa ja joidenkin prosessorien on ehkä odotettava toisen prosessorin tulosta, tätä teoreettisesti ihanteellista rajaa ei koskaan saavuteta.
Keskeinen monimutkaisuuskysymys on siis kehittää algoritmeja niin, että laskenta-ajan tulo prosessorien lukumäärällä on mahdollisimman lähellä aikaa, joka tarvitaan saman laskennan suorittamiseen yhdellä prosessorilla.
Kvanttilaskenta
Kvanttitietokone on tietokone, jossa on kvanttimekaniikkaan perustuva laskentamalli. Church–Turingin teesi pätee kvanttitietokoneisiin, mikä viittaa siihen, että kaikki ongelmat, jotka kvanttitietokone voi ratkaista, voidaan ratkaista myös Turingin koneella. Jotkut tehtävät voidaan kuitenkin teoriassa ratkaista käyttämällä kvanttitietokonetta klassisen tietokoneen sijaan, jonka ajallinen monimutkaisuus on huomattavasti pienempi. Toistaiseksi tämä on tiukasti teoreettista, koska kukaan ei tiedä, miten käytännöllistä kvanttitietokonetta kehitetään.
Kvanttikompleksiteoria luotiin tutkimaan erilaisia ongelmia, jotka kvanttitietokoneet voivat ratkaista. Sitä käytetään post-kvanttisalauksessa, joka on prosessi, jossa luodaan kryptografisia protokollia, jotka kestävät kvanttitietokoneen hyökkäyksiä.
Ongelman monimutkaisuus (alarajat)
Ongelman ratkaisevien algoritmien, mukaan lukien tuntemattomat tekniikat, monimutkaisuuden huono puoli on ongelman monimutkaisuus. Tämän seurauksena ongelman monimutkaisuus on yhtä suuri kuin minkä tahansa sen ratkaisevan algoritmin monimutkaisuus.
Tämän seurauksena mikä tahansa suurilla O-merkinnöillä annettu monimutkaisuus edustaa sekä algoritmin että siihen liittyvän ongelman monimutkaisuutta.
Toisaalta ongelman monimutkaisuuden ei-triviaalien alarajojen saaminen on usein vaikeaa, ja siihen on vain vähän strategioita.
Useimpien ongelmien ratkaisemiseksi kaikki syötetiedot on luettava, mikä vie aikaa suhteessa datan suuruuteen. Seurauksena on, että tällaisilla ongelmilla on vähintään lineaarinen monimutkaisuus tai, isossa omega-merkinnässä, kompleksisuus Ω(n).
Joillakin ongelmilla, kuten tietokonealgebralla ja laskennallisessa algebrallisessa geometriassa, on erittäin suuria ratkaisuja. Koska tulos on kirjoitettava, monimutkaisuutta rajoittaa tulosteen enimmäiskoko.
Lajittelualgoritmissa tarvittavien vertailujen lukumäärällä on epälineaarinen alaraja Ω(nlogn). Tämän seurauksena parhaat lajittelualgoritmit ovat tehokkaimpia, koska niiden monimutkaisuus on O(nlogn). Se, että siellä on n! tapa järjestää n asiaa johtaa tähän alarajaan. Koska jokainen vertailu jakaa tämän joukon n! tilaukset kahteen osaan, kaikkien tilausten erottamiseen tarvittavan N vertailun määrän on oltava 2N > n!, mikä tarkoittaa O(nlogn) Stirlingin kaavan mukaan.
Ongelman pelkistäminen toiseksi ongelmaksi on yleinen strategia pienempien monimutkaisuusrajoitusten saavuttamiseksi.
Algoritmin kehittäminen
Algoritmin monimutkaisuuden arviointi on tärkeä osa suunnitteluprosessia, koska se tarjoaa hyödyllistä tietoa odotettavissa olevasta suorituskyvystä.
Usein väärinymmärretään, että Mooren lain, joka ennustaa nykyaikaisen tietokonetehon eksponentiaalista kasvua, seurauksena algoritmien monimutkaisuuden arvioiminen vähenee. Tämä on väärin, koska lisääntynyt teho mahdollistaa valtavien tietomäärien (big data) käsittelyn. Esimerkiksi minkä tahansa algoritmin pitäisi toimia hyvin alle sekunnissa, kun lajitellaan aakkosjärjestykseen muutaman sadan merkinnän luettelo, kuten kirjan bibliografia. Toisaalta miljoonan merkinnän (esimerkiksi suuren kaupungin puhelinnumerot) kohdalla O(n2)-vertailuja vaativien perusalgoritmien olisi suoritettava biljoona vertailua, mikä kestäisi kolme tuntia nopeudella 10 miljoonaa vertailua sekunnissa. Pikalajittelu ja yhdistäminen sitä vastoin vaativat vain nlogn-vertailuja (ensimmäisen tapauksessa keskimääräisenä monimutkaisuudena, jälkimmäisenä pahimman tapauksen monimutkaisuutena). Tämä tuottaa noin 30,000,000 1,000,000 3 vertailua arvolle n = 10 XNUMX XNUMX, mikä kestäisi vain XNUMX sekuntia XNUMX miljoonalla vertailulla sekunnissa.
Tämän seurauksena monimutkaisuuden arviointi voi mahdollistaa monien tehottomien algoritmien eliminoinnin ennen käyttöönottoa. Tätä voidaan käyttää myös monimutkaisten algoritmien hienosäätämiseen ilman, että sinun on testattava kaikkia mahdollisia muunnelmia. Monimutkaisuuden tutkimus mahdollistaa toteutuksen tehokkuuden lisäämisen kohdistamisen määrittämällä monimutkaisen algoritmin kalleimmat vaiheet.
Tutustuaksesi sertifioinnin opetussuunnitelmaan yksityiskohtaisesti voit laajentaa ja analysoida alla olevaa taulukkoa.
EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum -opetusohjelma viittaa avoimen pääsyn didaktisiin materiaaleihin videomuodossa. Oppimisprosessi on jaettu vaiheittaiseen rakenteeseen (ohjelmat -> oppitunnit -> aiheet), joka kattaa olennaiset opetussuunnitelman osat. Tarjolla on myös rajoittamaton konsultointi toimialueen asiantuntijoiden kanssa.
Katso tarkemmat tiedot sertifiointimenettelystä Miten se toimii.
Ensisijainen tuki opetussuunnitelman lukumateriaalit
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Toisen asteen opetussuunnitelman lukumateriaalit
O. Goldreich, Johdatus kompleksisuusteoriaan:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Tukevaa opetussuunnitelman lukumateriaalia diskreetistä matematiikasta
J. Aspnes, Notes on Discrete Mathematics:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Graafiteorian tukimateriaalia opetussuunnitelmaan
R. Diestel, Graafiteoria:
https://diestel-graph-theory.com/
Lataa täydelliset offline-itseoppimisen valmistelevat materiaalit EITC/IS/CCTF Computational Complexity Theory Fundamentals -ohjelmaa varten PDF-tiedostona
EITC/IS/CCTF valmistelumateriaalit – vakioversio
EITC/IS/CCTF valmistelumateriaalit – laajennettu versio tarkistuskysymyksillä