EITC/IS/CCTF Computational Complexity Theory Theory Fundamentals on Euroopa IT sertifitseerimisprogramm arvutiteaduse aluste teoreetiliste aspektide kohta, mis on ühtlasi aluseks klassikalisele asümmeetrilisele avaliku võtmega krüptograafiale, mida laialdaselt kasutatakse Internetis.
EITC/IS/CCTF arvutusliku keerukuse teooria põhialuste õppekava hõlmab teoreetilisi teadmisi arvutiteaduse aluste ja arvutusmudelite kohta selliste põhimõistete kohta nagu deterministlikud ja mittedeterministlikud lõplikud olekumasinad, regulaarsed keeled, kontekstivabad grammatika- ja keeleteooria, automaatide teooria, Turing. Masinad, probleemide lahendatavus, rekursioon, loogika ja algoritmide keerukus põhiliste turberakenduste jaoks järgmises struktuuris, mis hõlmab põhjalikku didaktilist videosisu selle EITC sertifikaadi viitena.
Algoritmi arvutuslik keerukus on selle tööks vajalike ressursside hulk. Erilist tähelepanu pööratakse aja- ja mäluressurssidele. Probleemi keerukus on määratletud kui selle lahendamise parimate algoritmide keerukus. Algoritmide analüüs on selgesõnaliselt etteantud algoritmide keerukuse uurimine, arvutusliku keerukuse teooria aga probleemide lahenduste keerukuse uurimine tuntuimate algoritmidega. Mõlemad valdkonnad on läbi põimunud, kuna algoritmi keerukus on alati lahendatava probleemi keerukuse ülempiirang. Lisaks on tõhusate algoritmide koostamisel sageli vaja võrrelda teatud algoritmi keerukust lahendatava probleemi keerukusega. Enamikul juhtudel on probleemi keerukuse kohta ainus saadaolev teave see, et see on väiksem kui kõige tõhusamate teadaolevate tehnikate keerukus. Selle tulemusena kattub algoritmianalüüs ja keerukuse teooria palju.
Keerukuse teooria ei mängi olulist rolli mitte ainult arvutusmudelite alusena arvutiteaduse alusena, vaid ka klassikalise asümmeetrilise krüptograafia (nn avaliku võtme krüptograafia) alustes, mida tänapäevastes võrkudes, eriti Internetis, laialdaselt levitatakse. Avaliku võtmega krüptimine põhineb teatud asümmeetriliste matemaatiliste probleemide arvutusraskusel, nagu näiteks suurte arvude faktoriseerimine algteguriteks (see toiming on keerukusteooria klassifikatsioonis raske probleem, kuna puuduvad teadaolevad tõhusad klassikalised algoritmid, mida lahendada see ressursside skaleerimisega pigem polünoomiliselt kui eksponentsiaalselt koos probleemi sisendi suuruse suurenemisega, mis on vastupidine väga lihtsale pöördoperatsioonile, mille käigus korrutatakse teadaolevate algteguritega, et saada algne suur arv). Kasutades seda asümmeetriat avaliku võtme krüptograafia arhitektuuris (määrates avaliku võtme vahel arvutuslikult asümmeetrilise seose, mida saab kergesti arvutada privaatvõtme alusel, samas kui privaatvõtit ei saa avaliku võtme alusel lihtsalt arvutisse arvutada, teatama avalikust võtmest ja võimaldama teistel sidepooltel seda kasutada andmete asümmeetriliseks krüptimiseks, mida saab seejärel dekrüpteerida ainult seotud privaatvõtmega, mis pole arvutuslikult kättesaadav kolmandatele isikutele, muutes seega side turvaliseks).
Arvutusliku keerukuse teooria töötati välja peamiselt arvutiteaduse ja algoritmide pioneeride saavutuste põhjal, nagu Alan Turing, kelle töö oli kriitilise tähtsusega Natsi-Saksamaa Enigma šifri murdmisel, millel oli suur roll liitlastel Teise maailmasõja võitmisel. Krüptoanalüüsi, mille eesmärk oli kavandada ja automatiseerida andmete (peamiselt krüpteeritud side) analüüsimise arvutusprotsesse, et paljastada varjatud teave, kasutati krüptosüsteemide murdmiseks ja krüpteeritud side sisule juurdepääsu saamiseks, mis on tavaliselt sõjalise strateegilise tähtsusega. See oli ka krüptoanalüüs, mis katalüüsis esimeste kaasaegsete arvutite väljatöötamist (mida algselt rakendati koodimurdmise strateegilise eesmärgi saavutamiseks). Briti kolossile (mida peetakse esimeseks kaasaegseks elektrooniliseks ja programmarvutiks) eelnes Poola "pomm" - elektrooniline arvutusseade, mille Marian Rejewski konstrueeris Enigma šifrite purustamisel ja mille Poola luure andis Suurbritanniale üle. vallutatud Saksa Enigma krüpteerimismasin, pärast seda, kui Saksamaa 1939. aastal Poola kallale tungis. Selle seadme põhjal töötas Alan Turing välja selle arenenuma vaste, et edukalt katkestada Saksa krüpteeritud side, mis on hiljem arendatud kaasaegseteks arvutiteks.
Kuna algoritmi käitamiseks vajalik ressursside hulk varieerub sõltuvalt sisendi suurusest, väljendatakse keerukust tavaliselt funktsioonina f(n), kus n on sisendi suurus ja f(n) on kas halvimal juhul keerukus ( maksimaalne nõutav ressursside kogus kõigis n suuruses sisendites) või juhtumite keskmine keerukus (ressursside hulga keskmine kõigi suuruse n sisendite kohta). Nõutavate elementaartoimingute arv n-suurusega sisendil on tavaliselt ajaline keerukus, kus arvatakse, et elementaartoimingud võtavad konkreetses arvutis konstantse aja ja muutuvad ainult konstantse teguri võrra, kui neid käivitatakse erinevas masinas. Algoritmi jaoks n suuruse sisendi jaoks vajalikku mälumahtu nimetatakse ruumi keerukuseks.
Aeg on kõige tavalisem ressurss. Kui terminit "keerukus" kasutatakse ilma tähisteta, viitab see tavaliselt aja keerukusele.
Traditsioonilisi ajaühikuid (sekundeid, minuteid ja nii edasi) keerukuse teoorias ei kasutata, kuna need sõltuvad liiga palju valitud arvutist ja tehnoloogia arengust. Näiteks suudab tänapäeval arvuti algoritmi täita oluliselt kiiremini kui 1960. aastate arvuti, kuid selle põhjuseks on pigem arvuti riistvara tehnoloogilised läbimurded kui algoritmi omane kvaliteet. Keerukuse teooria eesmärk on kvantifitseerida algoritmidele omased ajavajadused või põhilised ajapiirangud, mida algoritm mis tahes arvutile kehtestaks. See saavutatakse loendades, kui palju põhitoiminguid arvutuse ajal tehakse. Neid protseduure nimetatakse tavaliselt sammudeks, kuna arvatakse, et need võtavad teatud masinas konstantse aja (st sisendi maht neid ei mõjuta).
Teine oluline ressurss on algoritmide täitmiseks vajalik arvutimälu maht.
Teine sageli kasutatav ressurss on aritmeetiliste tehete hulk. Selles stsenaariumis kasutatakse terminit "aritmeetiline keerukus". Ajaline keerukus on tavaliselt aritmeetilise keerukuse korrutis konstantse teguriga, kui arvutuse käigus esinevate arvude binaarse esituse suurusele on teada ülemine piirang.
Arvutamisel kasutatavate täisarvude suurus ei ole paljude meetodite puhul piiratud ja on ebareaalne eeldada, et aritmeetilised toimingud nõuavad kindlat aega. Selle tulemusena võib ajaline keerukus, tuntud ka kui biti keerukus, olla aritmeetilisest keerukusest oluliselt suurem. Näiteks nn täisarvu maatriksi determinandi arvutamise aritmeetiline raskus on standardtehnikate puhul (Gaussi eliminatsioon) O(n^3). Kuna koefitsientide suurus võib arvutamise ajal eksponentsiaalselt laieneda, on samade meetodite biti keerukus n-s eksponentsiaalne. Kui neid tehnikaid kasutatakse koos mitme mooduliga aritmeetikaga, saab biti keerukust vähendada väärtuseni O(n^4).
Bitide keerukus viitab formaalses mõttes bititega tehtavate toimingute arvule, mis on vajalikud algoritmi käitamiseks. See võrdub ajalise keerukusega kuni konstantse tegurini enamikus arvutusparadigmades. Arvutite jaoks vajalike masinsõnadega tehtavate toimingute arv on võrdeline biti keerukusega. Realistlike arvutusmudelite puhul on ajaline keerukus ja biti keerukus seega identsed.
Ressursiks, mida sorteerimisel ja otsimisel sageli peetakse, on kirjete võrdluste hulk. Kui andmed on hästi paigutatud, näitab see hästi aja keerukust.
Kõigi potentsiaalsete sisendite puhul on algoritmi sammude arvu loendamine võimatu. Kuna sisendi keerukus suureneb koos selle suurusega, esitatakse seda tavaliselt funktsioonina sisendi suurusest n (bittides) ja seega on keerukus n funktsioon. Sama suurusega sisendite puhul võib aga algoritmi keerukus oluliselt erineda. Selle tulemusena kasutatakse rutiinselt mitmesuguseid keerukuse funktsioone.
Halvima juhu keerukus on kõigi n suuruse sisendite keerukuse summa, samas kui keskmine keerukus on kõigi n suuruse sisendite keerukuse summa (see on mõistlik, kuna antud suurusega võimalike sisendite arv on lõplik). Kui terminit "keerukus" kasutatakse ilma täiendava definitsioonita, võetakse arvesse halvimal juhul aja keerukust.
Halvima ja keskmise juhtumi keerukust on kurikuulsalt raske õigesti arvutada. Lisaks on nendel täpsetel väärtustel vähe praktilist rakendust, kuna mis tahes muutus masinas või arvutusparadigmas muudaks keerukust veidi. Lisaks ei ole ressursikasutus n väikeste väärtuste puhul otsustava tähtsusega, seetõttu on juurutamise lihtsus sageli ahvatlevam kui väikese n puhul madal keerukus.
Nendel põhjustel pööratakse kõige rohkem tähelepanu keerukuse käitumisele kõrge n korral, st selle asümptootilisele käitumisele, kui n läheneb lõpmatusele. Seetõttu kasutatakse keerukuse näitamiseks tavaliselt suurt O-tähistust.
Arvutuslikud mudelid
Arvutusmudeli valik, mis seisneb ajaühikus tehtavate oluliste toimingute täpsustamises, on keerukuse määramisel ülioluline. Seda nimetatakse mõnikord mitmelindiliseks Turingi masinaks, kui arvutusparadigmat pole konkreetselt kirjeldatud.
Deterministlik arvutusmudel on selline, milles masina järgnevad olekud ja sooritatavad toimingud on täielikult määratletud eelmise olekuga. Rekursiivsed funktsioonid, lambda-arvutus ja Turingi masinad olid esimesed deterministlikud mudelid. Juhusliku juurdepääsuga masinad (tuntud ka kui RAM-masinad) on populaarne paradigma reaalmaailma arvutite simuleerimiseks.
Kui arvutusmudel pole määratletud, eeldatakse tavaliselt mitmelindilist Turingi masinat. Mitmelindiliste Turingi masinate puhul on ajaline keerukus enamiku algoritmide puhul sama, mis RAM-masinatel, ehkki selle samaväärsuse saavutamiseks võib vaja minna märkimisväärset tähelepanu sellele, kuidas andmeid mällu salvestatakse.
Mittedeterministlikus arvutusmudelis, näiteks mittedeterministlikus Turingi masinad, võib arvutamise mõnes etapis teha erinevaid valikuid. Keerukuse teoorias vaadeldakse kõiki võimalikke valikuid korraga ja mittedeterministlik ajaline keerukus on aeg, mis kulub alati parimate valikute tegemiseks. Teisisõnu tehakse arvutusi samaaegselt nii paljudel (identsetel) protsessoritel, kui on vaja, ja mittedeterministlik arvutusaeg on aeg, mis esimesel protsessoril kulub arvutuse lõpuleviimiseks. Seda paralleelsust saab kasutada kvantarvutuses, kasutades spetsialiseeritud kvantalgoritmide käitamisel kattuvaid põimunud olekuid, nagu näiteks väikeste täisarvude Shori faktoriseerimine.
Isegi kui selline arvutusmudel ei ole praegu teostatav, on sellel teoreetiline tähtsus, eriti seoses P = NP probleemiga, mis küsib, kas keerukusklassid, mis on saadud, kasutades polünoomiaega ja mittedeterministlikku polünoomiaega, on vähemalt ülemised. piirid on samad. Deterministlikus arvutis nõuab NP-algoritmi simuleerimine "eksponentsiaalset aega". Kui ülesannet saab mittedeterministlikus süsteemis lahendada polünoomilises ajas, kuulub see NP raskusklassi. Kui probleem on NP-s ja see pole lihtsam kui ükski teine NP-probleem, öeldakse, et see on NP-täielik. Seljakoti probleem, reisiva müügimehe probleem ja Boole'i rahulolu probleem on kõik NP-täielikud kombinatoorsed probleemid. Kõige tuntumal algoritmil on kõigi nende probleemide puhul eksponentsiaalne keerukus. Kui mõnda neist probleemidest saaks deterministlikul masinal lahendada polünoomilises ajas, saaks kõik NP-ülesanded lahendada ka polünoomilises ajas ja P = NP. 2017. aasta seisuga eeldatakse laialdaselt, et P NP, mis tähendab, et NP probleemide halvimaid olukordi on põhimõtteliselt raske lahendada, st kulub huvitavate sisendpikkuste juures palju kauem kui mis tahes võimalik ajavahemik (kümnendeid).
Rööp- ja hajutatud andmetöötlus
Paralleelne ja hajutatud andmetöötlus hõlmab töötlemise jagamist mitme protsessori vahel, mis kõik töötavad samal ajal. Põhiline erinevus erinevate mudelite vahel on protsessorite vahel andmete saatmise meetod. Andmeedastus protsessorite vahel on paralleelsel andmetöötlusel tavaliselt väga kiire, samas kui hajutatud andmetöötluses toimub andmeedastus protsessorite vahel üle võrgu ja on seega oluliselt aeglasem.
Arvutamiseks N protsessoril kulub ühele protsessorile kuluva aja jagatis N-ga. Tegelikkuses ei saavutata seda teoreetiliselt ideaalset piiri kunagi, kuna mõnda alamülesannet ei saa paralleelstada ja mõnel protsessoril võib tekkida vajadus oodata teise protsessori tulemust.
Põhiline keerukuse probleem seisneb seega algoritmide väljatöötamises nii, et arvutamise aja korrutis protsessorite arvuga oleks võimalikult lähedane ajale, mis kulub sama arvutuse tegemiseks ühes protsessoris.
Kvantarvutus
Kvantarvuti on kvantmehaanikapõhise arvutusmudeliga arvuti. Church-Turingi tees kehtib kvantarvutite kohta, mis viitab sellele, et kõiki probleeme, mida kvantarvuti suudab lahendada, saab lahendada ka Turingi masina abil. Mõningaid ülesandeid võib teoreetiliselt siiski lahendada pigem kvantarvuti kui klassikalise, oluliselt väiksema ajalise keerukusega arvutiga. Esialgu on see rangelt teoreetiline, sest keegi ei tea, kuidas praktilist kvantarvutit välja töötada.
Kvantkeerukuse teooria loodi selleks, et uurida erinevat tüüpi probleeme, mida kvantarvutid saavad lahendada. Seda kasutatakse postkvantkrüptograafias, mis on kvantarvutite rünnakutele vastupidavate krüptograafiliste protokollide loomise protsess.
Probleemi keerukus (alumine piir)
Probleemi lahendamiseks vajalike algoritmide, sealhulgas avastamata tehnikate keerukus on probleemi keerukus. Selle tulemusena on probleemi keerukus võrdne mis tahes seda lahendava algoritmi keerukusega.
Selle tulemusel tähistab mis tahes keerukus, mis on antud suures O-tähistuses, nii algoritmi kui ka kaasneva probleemi keerukust.
Teisest küljest on probleemi keerukuse mittetriviaalsete alampiiride saamine sageli keeruline ja selleks on vähe strateegiaid.
Enamiku probleemide lahendamiseks tuleb kõik sisendandmed läbi lugeda, mis võtab aega võrdeliselt andmete mahuga. Selle tulemusena on sellistel probleemidel vähemalt lineaarne keerukus või suures oomega-tähises keerukus Ω (n).
Mõnel probleemil, näiteks arvutialgebra ja arvutusalgebralise geomeetria puhul, on väga suured lahendused. Kuna väljund tuleb kirjutada, piirab keerukust väljundi maksimaalne suurus.
Sorteerimisalgoritmi jaoks vajalike võrdluste arvul on mittelineaarne alumine piir Ω(nlogn). Selle tulemusena on parimad sortimisalgoritmid kõige tõhusamad, kuna nende keerukus on O(nlogn). Asjaolu, et seal on n! n asja korraldamise viisid viivad selle alumise piirini. Sest iga võrdlus jagab selle n-i kogumi ära! tellimuste kaheks osaks, peab kõigi järjekordade eristamiseks vajalik N võrdluste arv olema 2N > n!, mis tähendab Stirlingi valemi järgi O(nlogn).
Probleemi taandamine teiseks on levinud strateegia väiksemate keerukusepiirangute saavutamiseks.
Algoritmi väljatöötamine
Algoritmi keerukuse hindamine on kavandamisprotsessi oluline element, kuna see annab kasulikku teavet eeldatava jõudluse kohta.
Sage on arusaamatus, et Moore'i seaduse tõttu, mis ennustab kaasaegse arvutivõimsuse eksponentsiaalset kasvu, muutub algoritmide keerukuse hindamine vähem oluliseks. See on vale, kuna suurenenud võimsus võimaldab töödelda tohutuid andmemahte (suurandmeid). Näiteks mõnesajast kirjest koosneva loendi (nt raamatu bibliograafia) tähestikulises järjestuses sorteerimisel peaks iga algoritm hästi toimima vähem kui sekundiga. Teisest küljest peaksid miljoni kirje (näiteks suure linna telefoninumbrid) jaoks O(n2) võrdlusi nõudvad põhialgoritmid tegema triljonit võrdlust, mis võtaks kiirusel 10 aega kolm tundi. miljonit võrdlust sekundis. Kiirsortimine ja ühendamine nõuab aga ainult nlogn-i võrdlusi (esimese puhul keskmise keerukuse ja teise puhul halvima keerukusega). See annab umbes 30,000,000 1,000,000 3 võrdlust väärtusega n = 10 XNUMX XNUMX, mis võtaks XNUMX miljoni võrdluse korral sekundis vaid XNUMX sekundit.
Selle tulemusena võib keerukuse hindamine võimaldada paljude ebaefektiivsete algoritmide kõrvaldamist enne rakendamist. Seda saab kasutada ka keeruliste algoritmide peenhäälestamiseks, ilma et peaks testima kõiki võimalikke variante. Keerukuse uuring võimaldab koondada jõupingutusi teostuse efektiivsuse tõstmiseks, määrates kindlaks keeruka algoritmi kõige kulukamad sammud.
Sertifitseerimisõppekavaga põhjalikumalt tutvumiseks saate allolevat tabelit laiendada ja analüüsida.
EITC/IS/CCTF arvutusliku keerukuse teooria põhialuste sertifitseerimise õppekava viitab vaba juurdepääsuga didaktilistele materjalidele videovormis. Õppeprotsess on jagatud samm-sammult struktuuriks (programmid -> tunnid -> teemad), mis hõlmab vastavaid õppekavaosi. Pakutakse ka piiramatut nõustamist domeeniekspertidega.
Sertifitseerimisprotseduuri üksikasjad leiate Mugav tellimus.
Esmane toetav õppekava lugemisvara
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Teisese toetava õppekava lugemisvara
O. Goldreich, Sissejuhatus keerukuse teooriasse:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Toetavad õppekava lugemismaterjalid diskreetse matemaatika kohta
J. Aspnes, Märkused diskreetse matemaatika kohta:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Toetavad õppekava lugemismaterjalid graafiteooriast
R. Diestel, Graafiteooria:
https://diestel-graph-theory.com/
Laadige PDF-failina alla täielikud võrguühenduseta iseõppimise ettevalmistavad materjalid programmi EITC/IS/CCTF Computational Complexity Theory Fundamentals jaoks
EITC/IS/CCTF ettevalmistusmaterjalid – standardversioon
EITC/IS/CCTF ettevalmistavad materjalid – laiendatud versioon kordusküsimustega