EITC/IS/CCTF Computational Complexity Theory Fundamentals is die Europese IT-sertifiseringsprogram oor teoretiese aspekte van grondslae van rekenaarwetenskap wat ook 'n basis is van klassieke asimmetriese publiekesleutel-kriptografie wat baie op die internet gebruik word.
Die kurrikulum van die EITC/IS/CCTF Computational Complexity Theory Fundamentals dek teoretiese kennis oor die grondslae van rekenaarwetenskap en berekeningsmodelle op basiese konsepte soos deterministiese en nie-deterministiese eindigetoestandmasjiene, gewone tale, konteksvrye grammatikale en taleteorie, outomateorie, Turing Masjiene, besluitbaarheid van probleme, rekursie, logika en kompleksiteit van algoritme vir fundamentele sekuriteitstoepassings binne die volgende struktuur, wat omvattende videodidaktiese inhoud as verwysing vir hierdie EITC-sertifisering insluit.
'n Algoritme se berekeningskompleksiteit is die hoeveelheid hulpbronne wat benodig word om dit te bedryf. Tyd- en geheuebronne word spesiale aandag gegee. Die kompleksiteit van 'n probleem word gedefinieer as die kompleksiteit van die beste algoritmes om dit op te los. Ontleding van algoritmes is die studie van die kompleksiteit van eksplisiet gegewe algoritmes, terwyl berekeningskompleksiteitsteorie die studie van die kompleksiteit van probleemoplossings met bekendste algoritmes is. Beide domeine is verweef omdat 'n algoritme se kompleksiteit altyd 'n boonste beperking is op die kompleksiteit van die probleem wat dit oplos. Verder is dit dikwels nodig om die kompleksiteit van 'n sekere algoritme te vergelyk met die kompleksiteit van die probleem wat opgelos moet word terwyl doeltreffende algoritmes gekonstrueer word. In die meeste omstandighede is die enigste inligting wat beskikbaar is oor 'n probleem se moeilikheid dat dit minder is as die kompleksiteit van die mees doeltreffende bekende tegnieke. As gevolg hiervan is daar baie oorvleueling tussen algoritme-analise en kompleksiteitsteorie.
Kompleksiteitsteorie speel nie net 'n belangrike rol in die grondslae van rekenaarmodelle as basis vir rekenaarwetenskap nie, maar ook in die grondslae van klassieke asimmetriese kriptografie (sogenaamde publiekesleutel-kriptografie) wat wyd versprei word in moderne netwerke, veral op die internet. Die publiekesleutel-enkripsie is gebaseer op berekeningsmoeilikheid van sekere asimmetriese wiskundige probleme, soos byvoorbeeld faktorisering van groot getalle in sy priemfaktore (hierdie bewerking is 'n moeilike probleem in die kompleksiteitsteorie-klassifikasie, omdat daar nie bekende doeltreffende klassieke algoritmes is om op te los nie. dit met hulpbronne wat polinoom eerder as eksponensieel skaal met die toename van die probleem se insetgrootte, wat in teenstelling is met 'n baie eenvoudige omgekeerde bewerking van vermenigvuldiging tot bekende priemfaktore om die oorspronklike groot getal te gee). Deur hierdie asimmetrie te gebruik in 'n argitektuur van die publiekesleutel-kriptografie (deur 'n berekenings-asimmetriese verhouding tussen die publieke sleutel te definieer, wat maklik vanaf 'n private sleutel bereken kan word, terwyl die private sleutel nie maklik vanaf 'n publieke sleutel rekenaar kan wees nie, kan 'n mens publiek die publieke sleutel aan te kondig en ander kommunikasiekante in staat te stel om dit te gebruik vir asimmetriese enkripsie van data, wat dan slegs met die gekoppelde private sleutel gedekripteer kan word, wat nie rekenaarmatig aan derde partye beskikbaar is nie, en sodoende die kommunikasie veilig maak).
Die berekeningskompleksiteitsteorie is hoofsaaklik ontwikkel op prestasies van rekenaarwetenskap- en algoritmiese pioniers, soos Alan Turing, wie se werk van kritieke belang was om die Enigma-syfer van Nazi-Duitsland te breek, wat 'n groot rol gespeel het in bondgenote wat die Tweede Wêreldoorlog gewen het. Kriptanalise wat daarop gemik is om die berekeningsprosesse van die ontleding van data (hoofsaaklik geënkripteerde kommunikasie) te ontwerp en te outomatiseer om die verborge inligting te ontbloot, is gebruik om kriptografiese stelsels te oortree en toegang te verkry tot die inhoud van geënkripteerde kommunikasie, gewoonlik van strategiese militêre belang. Dit was ook kriptanalise wat die ontwikkeling van eerste moderne rekenaars (wat aanvanklik toegepas is op 'n strategiese doelwit van kodebreking) gekataliseer het. Die Britse Kolossus (wat as die eerste moderne elektroniese en programrekenaar beskou word) is voorafgegaan deur die Poolse "bom", 'n elektroniese rekenaartoestel wat ontwerp is deur Marian Rejewski om te help om Enigma-syfers te breek, en deur die Poolse intelligensie aan Groot-Brittanje oorhandig tesame met die gevange Duitse Enigma-enkripsiemasjien, nadat Pole in 1939 deur Duitsland binnegeval is. Op grond van hierdie toestel het Alan Turing sy meer gevorderde eweknie ontwikkel om Duitse geënkripteerde kommunikasie suksesvol te verbreek, wat later in moderne rekenaars ontwikkel is.
Omdat die hoeveelheid hulpbronne wat benodig word om 'n algoritme uit te voer, wissel met die grootte van die invoer, word die kompleksiteit gewoonlik uitgedruk as 'n funksie f(n), waar n die invoergrootte is en f(n) óf die ergste-geval kompleksiteit ( die maksimum hoeveelheid hulpbronne benodig oor alle insette van grootte n) of die gemiddelde-geval kompleksiteit (die gemiddelde van die hoeveelheid hulpbronne oor alle insette van grootte n). Die aantal vereiste elementêre bewerkings op 'n invoer van grootte n word algemeen aangegee as tydskompleksiteit, waar daar geglo word dat elementêre bewerkings 'n konstante hoeveelheid tyd op 'n spesifieke rekenaar neem en slegs deur 'n konstante faktor verander wanneer dit op 'n ander masjien uitgevoer word. Die hoeveelheid geheue wat deur 'n algoritme benodig word op 'n invoer van grootte n staan bekend as ruimtekompleksiteit.
Tyd is die mees algemeen beskou as hulpbron. Wanneer die term "kompleksiteit" sonder kwalifiseerder gebruik word, verwys dit gewoonlik na die kompleksiteit van tyd.
Die tradisionele tydeenhede (sekondes, minute, ensovoorts) word nie in kompleksiteitsteorie aangewend nie, aangesien hulle te afhanklik is van die rekenaar wat gekies is en die vooruitgang van tegnologie. Byvoorbeeld, 'n rekenaar kan vandag 'n algoritme aansienlik vinniger uitvoer as 'n rekenaar uit die 1960's, maar dit is te danke aan tegnologiese deurbrake in rekenaarhardeware eerder as 'n inherente kwaliteit van die algoritme. Die doel van kompleksiteitsteorie is om die inherente tydsbehoeftes van algoritmes te kwantifiseer, of die fundamentele tydsbeperkings wat 'n algoritme op enige rekenaar sou oplê. Dit word bewerkstellig deur te tel hoeveel basiese bewerkings tydens die berekening uitgevoer word. Daar word gewoonlik na hierdie prosedures verwys as stappe omdat dit beskou word as konstante tyd op 'n spesifieke masjien (dws hulle word nie deur die hoeveelheid insette beïnvloed nie).
Nog 'n belangrike hulpbron is die hoeveelheid rekenaargeheue wat nodig is om algoritmes uit te voer.
Nog 'n hulpbron wat dikwels gebruik word, is die hoeveelheid rekenkundige bewerkings. In hierdie scenario word die term "rekenkundige kompleksiteit" gebruik. Die tydskompleksiteit is oor die algemeen die produk van die rekenkundige kompleksiteit deur 'n konstante faktor as 'n boonste beperking op die grootte van die binêre voorstelling van die getalle wat tydens 'n berekening voorkom, bekend is.
Die grootte van die heelgetalle wat tydens 'n berekening gebruik word, word nie vir baie metodes beperk nie, en dit is onrealisties om te aanvaar dat rekenkundige bewerkings 'n vaste hoeveelheid tyd benodig. Gevolglik kan die tydskompleksiteit, ook bekend as biskompleksiteit, aansienlik hoër wees as die rekenkundige kompleksiteit. Die rekenkundige moeilikheid om die determinant van 'n nn heelgetalmatriks te bereken, is byvoorbeeld O(n^3) vir standaardtegnieke (Gaussiese eliminasie). Omdat die grootte van die koëffisiënte eksponensieel kan uitbrei tydens die berekening, is die biskompleksiteit van dieselfde metodes eksponensieel in n. As hierdie tegnieke in samewerking met multi-modulêre rekenkunde gebruik word, kan die biskompleksiteit verminder word na O(n^4).
Die biskompleksiteit, in formele terme, verwys na die aantal bewerkings op bisse wat nodig is om 'n algoritme uit te voer. Dit is gelyk aan die tydelike kompleksiteit tot 'n konstante faktor in die meeste berekeningsparadigmas. Die aantal bewerkings op masjienwoorde wat deur rekenaars vereis word, is eweredig aan die biskompleksiteit. Vir realistiese modelle van berekening is die tydkompleksiteit en biskompleksiteit dus identies.
Die hulpbron wat dikwels oorweeg word by sortering en soek is die hoeveelheid inskrywingsvergelykings. As die data goed gerangskik is, is dit 'n goeie aanduiding van die tydskompleksiteit.
Op alle potensiële insette is dit onmoontlik om die aantal stappe in 'n algoritme te tel. Omdat die kompleksiteit van 'n inset toeneem met sy grootte, word dit algemeen voorgestel as 'n funksie van die inset se grootte n (in bisse), en dus is die kompleksiteit 'n funksie van n. Vir dieselfde-grootte insette kan die kompleksiteit van 'n algoritme egter aansienlik verskil. As gevolg hiervan word 'n verskeidenheid kompleksiteitsfunksies gereeld aangewend.
Die ergste-geval kompleksiteit is die som van alle kompleksiteit vir alle grootte n insette, terwyl die gemiddelde-geval kompleksiteit die som is van alle kompleksiteit vir alle grootte n insette (dit maak sin, aangesien die aantal moontlike insette van 'n gegewe grootte is eindig). Wanneer die term "kompleksiteit" gebruik word sonder om verder omskryf te word, word die ergste tydskompleksiteit in ag geneem.
Die ergste-geval en gemiddelde-geval kompleksiteit is berug moeilik om korrek te bereken. Verder het hierdie presiese waardes min praktiese toepassing omdat enige verandering in masjien of berekeningsparadigma die kompleksiteit effens sal verander. Verder is hulpbrongebruik nie deurslaggewend vir klein waardes van n nie, daarom is die gemak van implementering dikwels meer aantreklik as lae kompleksiteit vir klein n.
Om hierdie redes word die meeste aandag gegee aan die kompleksiteit se gedrag vir hoë n, dit wil sê sy asimptotiese gedrag as n oneindigheid nader. As gevolg hiervan word groot O-notasie algemeen gebruik om kompleksiteit aan te dui.
Rekenkundige modelle
Die keuse van 'n berekeningsmodel, wat bestaan uit die spesifikasie van die noodsaaklike bewerkings wat in 'n tydseenheid uitgevoer word, is deurslaggewend in die bepaling van die kompleksiteit. Dit word soms na verwys as 'n multitape Turing-masjien wanneer die berekeningsparadigma nie spesifiek beskryf word nie.
'n Deterministiese model van berekening is een waarin die masjien se daaropvolgende toestande en die bewerkings wat uitgevoer moet word, geheel en al deur die vorige toestand gedefinieer word. Rekursiewe funksies, lambda-rekening en Turing-masjiene was die eerste deterministiese modelle. Toevallige toegangsmasjiene (ook bekend as RAM-masjiene) is 'n gewilde paradigma om werklike rekenaars te simuleer.
Wanneer die berekeningsmodel nie gedefinieer is nie, word 'n multitape Turing-masjien gewoonlik aanvaar. Op multitape Turing-masjiene is die tydskompleksiteit dieselfde as op RAM-masjiene vir die meeste algoritmes, alhoewel aansienlike aandag in hoe data in die geheue gestoor word nodig mag wees om hierdie ekwivalensie te bereik.
Verskeie keuses kan gemaak word by sommige stappe van die berekening in 'n nie-deterministiese model van rekenaar, soos nie-deterministiese Turing-masjiene. In kompleksiteitsteorie word alle haalbare opsies gelyktydig oorweeg, en nie-deterministiese tydskompleksiteit is die hoeveelheid tyd wat benodig word wanneer die beste keuses altyd gemaak word. Om dit anders te stel, die berekening word gelyktydig gedoen op soveel (identiese) verwerkers as wat vereis word, en die nie-deterministiese berekeningstyd is die tyd wat die eerste verwerker neem om die berekening te voltooi. Hierdie parallellisme kan gebruik word in kwantumberekening deur gesuperponeerde verstrengelde toestande te gebruik wanneer gespesialiseerde kwantumalgoritmes uitgevoer word, soos byvoorbeeld Shor se faktorisering van klein heelgetalle.
Selfs al is so 'n berekeningsmodel nie tans prakties prakties nie, het dit teoretiese betekenis, veral met betrekking tot die P = NP-probleem, wat vra of die kompleksiteitsklasse geproduseer word deur die gebruik van "polinoomtyd" en "nie-deterministiese polinoomtyd" as die minste boonste grense is dieselfde. Op 'n deterministiese rekenaar vereis die simulering van 'n NP-algoritme "eksponensiële tyd." As 'n taak in polinoomtyd op 'n nie-deterministiese stelsel opgelos kan word, behoort dit tot die NP-moeilikheidsklas. As 'n kwessie in NP is en nie makliker is as enige ander NP-probleem nie, word gesê dat dit NP-volledig is. Die Rugsak-probleem, die reisende verkoopsman-probleem en die Boole-bevredigingsprobleem is almal NP-volledige kombinatoriese probleme. Die bekendste algoritme het eksponensiële kompleksiteit vir al hierdie probleme. As enige van hierdie kwessies in polinoomtyd op 'n deterministiese masjien opgelos kan word, dan kan alle NP-probleme ook in polinoomtyd opgelos word, en P = NP sal vasgestel word. Vanaf 2017 word dit algemeen aanvaar dat P NP, wat impliseer dat die ergste situasies van NP-probleme fundamenteel moeilik is om op te los, dit wil sê, neem baie langer as enige haalbare tydsbestek (dekades) gegewe interessante insetlengtes.
Parallelle en verspreide rekenaars
Parallelle en verspreide rekenaars behels die verdeling van verwerking oor verskeie verwerkers wat almal op dieselfde tyd werk. Die fundamentele onderskeid tussen die verskillende modelle is die metode om data tussen verwerkers te stuur. Data-oordrag tussen verwerkers is tipies baie vinnig in parallelle rekenaars, terwyl data-oordrag tussen verwerkers in verspreide rekenaars oor 'n netwerk gedoen word en dus aansienlik stadiger is.
'n Berekening op N verwerkers neem ten minste die kwosiënt met N van die tyd wat dit op 'n enkele verwerker neem. In werklikheid, omdat sommige subtake nie geparalleliseer kan word nie en sommige verwerkers dalk moet wag vir 'n resultaat van 'n ander verwerker, sal hierdie teoreties ideale binding nooit bereik word nie.
Die sleutelkompleksiteitskwessie is dus om algoritmes te ontwikkel sodat die produk van rekenaartyd deur die aantal verwerkers so na as moontlik aan die tyd is wat nodig is om dieselfde berekening op 'n enkele verwerker uit te voer.
Kwantumberekening
'n Kwantumrekenaar is 'n rekenaar met 'n kwantummeganika-gebaseerde berekeningsmodel. Die Church–Turing-proefskrif geld vir kwantumrekenaars, wat impliseer dat enige probleem wat 'n kwantumrekenaar kan oplos ook deur 'n Turing-masjien opgelos kan word. Sommige take kan egter teoreties opgelos word met 'n kwantumrekenaar eerder as 'n klassieke rekenaar met 'n aansienlik laer temporele kompleksiteit. Vir eers is dit streng teoreties, aangesien niemand weet hoe om 'n praktiese kwantumrekenaar te ontwikkel nie.
Kwantumkompleksiteitsteorie is geskep om die verskillende tipes kwessies wat deur kwantumrekenaars opgelos kan word, te ondersoek. Dit word gebruik in post-kwantumkriptografie, wat die proses is om kriptografiese protokolle te skep wat bestand is teen kwantumrekenaaraanvalle.
Kompleksiteit van die probleem (ondergrens)
Die infimum van die kompleksiteite van die algoritmes wat die probleem kan oplos, insluitend onontdekte tegnieke, is die kompleksiteit van die probleem. Gevolglik is die kompleksiteit van 'n probleem gelyk aan die kompleksiteit van enige algoritme wat dit oplos.
As gevolg hiervan verteenwoordig enige kompleksiteit wat in groot O-notasie gegee word 'n kompleksiteit van beide die algoritme en die gepaardgaande probleem.
Aan die ander kant is dit dikwels moeilik om nie-triviale ondergrense vir kwessiekompleksiteit te verkry, en daar is min strategieë om dit te doen.
Om die meeste probleme op te los, moet alle invoerdata gelees word, wat tyd neem in verhouding tot die omvang van die data. As gevolg hiervan het sulke probleme ten minste lineêre kompleksiteit, of, in groot omega-notasie, 'n kompleksiteit van Ω(n).
Sommige probleme, soos dié in rekenaaralgebra en berekeningsalgebraïese meetkunde, het baie groot oplossings. Omdat die uitvoer geskryf moet word, word die kompleksiteit beperk deur die maksimum grootte van die uitvoer.
Die aantal vergelykings wat benodig word vir 'n sorteeralgoritme het 'n nie-lineêre ondergrens van Ω(nlogn). As gevolg hiervan is die beste sorteeralgoritmes die doeltreffendste aangesien hul kompleksiteit O(nlogn) is. Die feit dat daar n! maniere om n dinge te organiseer lei tot hierdie ondergrens. Omdat elke vergelyking hierdie versameling van n verdeel! bestellings in twee stukke, moet die aantal N vergelykings wat nodig is om alle bestellings te onderskei 2N > n! wees, wat O(nlogn) deur Stirling se formule impliseer.
Om 'n probleem na 'n ander probleem te reduseer, is 'n algemene strategie vir die verkryging van verminderde kompleksiteitsbeperkings.
Algoritme ontwikkeling
Die evaluering van 'n algoritme se kompleksiteit is 'n belangrike element van die ontwerpproses aangesien dit nuttige inligting verskaf oor die prestasie wat verwag kan word.
Dit is 'n gereelde misverstand dat, as gevolg van Moore se wet, wat die eksponensiële groei van moderne rekenaarkrag voorspel, die evaluering van die kompleksiteit van algoritmes minder relevant sal word. Dit is verkeerd omdat die verhoogde krag voorsiening maak vir die verwerking van massiewe hoeveelhede data (groot data). Byvoorbeeld, enige algoritme behoort binne minder as 'n sekonde goed te funksioneer wanneer 'n lys van 'n paar honderde inskrywings, soos die bibliografie van 'n boek, alfabeties gesorteer word. Aan die ander kant, vir 'n miljoen inskrywings (byvoorbeeld die telefoonnommers van 'n groot stad), sal die basiese algoritmes wat O(n2)-vergelykings vereis 'n triljoen vergelykings moet uitvoer, wat drie uur teen 'n spoed van 10 sal neem miljoen vergelykings per sekonde. Quicksort en merge sort, aan die ander kant, vereis slegs nlogn-vergelykings (as gemiddelde-geval-kompleksiteit vir eersgenoemde, as ergste-geval-kompleksiteit vir laasgenoemde). Dit lewer ongeveer 30,000,000 1,000,000 3 vergelykings vir n = 10 XNUMX XNUMX, wat slegs XNUMX sekondes sal neem teen XNUMX miljoen vergelykings per sekonde.
As gevolg hiervan kan die beoordeling van kompleksiteit die uitskakeling van baie ondoeltreffende algoritmes voor implementering moontlik maak. Dit kan ook gebruik word om komplekse algoritmes te verfyn sonder om alle moontlike variante te toets. Die studie van kompleksiteit laat toe om die poging om die doeltreffendheid van 'n implementering te verhoog te fokus deur die duurste stappe van 'n komplekse algoritme te bepaal.
Om jouself in besonderhede te vergewis van die sertifiseringskurrikulum, kan jy die tabel hieronder uitbrei en ontleed.
Die EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum verwys na oop-toegang didaktiese materiaal in 'n videovorm. Leerproses word verdeel in 'n stap-vir-stap-struktuur (programme -> lesse -> onderwerpe) wat relevante kurrikulumdele dek. Onbeperkte konsultasie met domeinkundiges word ook verskaf.
Gaan na vir besonderhede oor die Sertifiseringsprosedure Hoe dit werk.
Primêre ondersteunende kurrikulum leesmateriaal
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Sekondêre ondersteunende kurrikulum leesmateriaal
O. Goldreich, Inleiding tot kompleksiteitsteorie:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Ondersteunende kurrikulumleesmateriaal oor diskrete wiskunde
J. Aspnes, Notas oor Diskrete Wiskunde:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Ondersteunende kurrikulumleesmateriaal oor grafiekteorie
R. Diestel, Grafiekteorie:
https://diestel-graph-theory.com/
Laai die volledige vanlyn selflerende voorbereidingsmateriaal vir die EITC/IS/CCTF Computational Complexity Theory Fundamentals-program in 'n PDF-lêer af
EITC/IS/CCTF voorbereidende materiaal – standaard weergawe
EITC/IS/CCTF voorbereidende materiaal – uitgebreide weergawe met hersieningsvrae