EITC/IS/CCTF Computational Complexity Theory Fundamentals
EITC/IS/CCTF Computational Complexity Theory Fundamentals er det europeiske IT-sertifiseringsprogrammet om teoretiske aspekter ved grunnlaget for informatikk, som også er grunnlaget for klassisk asymmetrisk offentlig nøkkelkryptografi som er mye brukt på Internett.
Læreplanen til EITC/IS/CCTF Computational Complexity Theory Fundamentals dekker teoretisk kunnskap om grunnlaget for informatikk og beregningsmodeller på grunnleggende konsepter som deterministiske og ikke-deterministiske endelige tilstandsmaskiner, regulære språk, kontekstfrie grammatører og språkteori, automatteori, Turing Maskiner, avgjørbarhet av problemer, rekursjon, logikk og kompleksitet av algoritmer for grunnleggende sikkerhetsapplikasjoner innenfor følgende struktur, som omfatter omfattende og strukturert EITCI-sertifiserings-selvlæringsmateriell støttet av referert åpen-tilgang videodidaktisk innhold som grunnlag for forberedelse til å oppnå denne EITC-sertifiseringen ved å bestå en tilsvarende eksamen.
En algoritmes beregningsmessige kompleksitet er mengden ressurser som kreves for å betjene den. Tid og hukommelsesressurser vies spesiell oppmerksomhet. Kompleksiteten til et problem er definert som kompleksiteten til de beste algoritmene for å løse det. Analyse av algoritmer er studiet av kompleksiteten til eksplisitt gitte algoritmer, mens beregningskompleksitetsteori er studiet av kompleksiteten til problemløsninger med best kjente algoritmer. Begge domenene er sammenvevd fordi kompleksiteten til en algoritme alltid er en øvre begrensning på kompleksiteten til problemet den løser. Videre er det ofte nødvendig å sammenligne kompleksiteten til en viss algoritme med kompleksiteten til problemet som skal løses mens man konstruerer effektive algoritmer. I de fleste tilfeller er den eneste tilgjengelige informasjonen om et problems vanskelighetsgrad at det er mindre enn kompleksiteten til de mest effektive kjente teknikkene. Som et resultat er det mye overlapp mellom algoritmeanalyse og kompleksitetsteori.
Kompleksitetsteori spiller en viktig rolle ikke bare i grunnlaget for beregningsmodeller som grunnlag for informatikk, men også i grunnlaget for klassisk asymmetrisk kryptografi (såkalt offentlig nøkkelkryptografi) som er mye spredt i moderne nettverk, spesielt på Internett. Den offentlige nøkkelkrypteringen er basert på beregningsmessig vanskelige visse asymmetriske matematiske problemer som for eksempel faktorisering av store tall til primfaktorene (denne operasjonen er et vanskelig problem i kompleksitetsteoriklassifiseringen, fordi det ikke er kjente effektive klassiske algoritmer å løse det med ressurser som skaleres polynomisk i stedet for eksponentielt med økningen av problemets inngangsstørrelse, som er i motsetning til en veldig enkel omvendt operasjon med å multiplisere til kjente primfaktorer for å gi det opprinnelige store tallet). Ved å bruke denne asymmetrien i en arkitektur av offentlig nøkkelkryptografi (ved å definere en beregningsmessig asymmetrisk relasjon mellom den offentlige nøkkelen, som lett kan beregnes fra en privat nøkkel, mens den private nøkkelen ikke lett kan være datamaskin fra en offentlig nøkkel, kan man offentlig kunngjøre den offentlige nøkkelen og gjøre det mulig for andre kommunikasjonssider å bruke den til asymmetrisk kryptering av data, som da bare kan dekrypteres med den koblede private nøkkelen, ikke tilgjengelig beregningsmessig for tredjeparter, og dermed gjøre kommunikasjonen sikker).
Beregningskompleksitetsteorien ble utviklet hovedsakelig på prestasjoner av pionerer innen informatikk og algoritmikk, som Alan Turing, hvis arbeid var avgjørende for å bryte Enigma-chifferet til Nazi-Tyskland, som spilte en dyp rolle i at allierte vant andre verdenskrig. Krypteringsanalyse med sikte på å utforme og automatisere beregningsprosessene for å analysere data (hovedsakelig kryptert kommunikasjon) for å avdekke den skjulte informasjonen ble brukt til å bryte kryptografiske systemer og få tilgang til innholdet i kryptert kommunikasjon, vanligvis av strategisk militær betydning. Det var også kryptoanalyse som katalyserte utviklingen av de første moderne datamaskinene (som opprinnelig ble brukt til et strategisk mål om kodebryting). British Colossus (betraktet som den første moderne elektroniske og programdatamaskinen) ble innledet av den polske "bomben", en elektronisk beregningsenhet designet av Marian Rejewski for å hjelpe til med å bryte Enigma-siffer, og overlevert til Storbritannia av den polske etterretningen sammen med den fangede tyske Enigma-krypteringsmaskinen, etter at Polen ble invadert av Tyskland i 1939. På grunnlag av denne enheten utviklet Alan Turing sin mer avanserte motpart for å lykkes med å bryte tysk kryptert kommunikasjon, som senere har blitt utviklet til moderne datamaskiner.
Fordi mengden ressurser som kreves for å kjøre en algoritme varierer med størrelsen på inngangen, uttrykkes kompleksiteten vanligvis som en funksjon f(n), der n er inngangsstørrelsen og f(n) enten er den verste kompleksiteten ( den maksimale mengden ressurser som kreves på tvers av alle input av størrelse n) eller gjennomsnittlig sakskompleksitet (gjennomsnittet av mengden ressurser over alle input av størrelse n). Antall nødvendige elementære operasjoner på en inngang av størrelse n er vanligvis oppgitt som tidskompleksitet, der elementære operasjoner antas å ta en konstant mengde tid på en bestemt datamaskin og endres bare med en konstant faktor når de kjøres på en annen maskin. Mengden minne som kreves av en algoritme på en inngang av størrelse n er kjent som plasskompleksitet.
Tid er den mest vanlige ressursen. Når begrepet "kompleksitet" brukes uten kvalifikatoren, refererer det vanligvis til tidens kompleksitet.
De tradisjonelle tidsenhetene (sekunder, minutter og så videre) brukes ikke i kompleksitetsteori siden de er for avhengige av den valgte datamaskinen og teknologiens fremgang. For eksempel kan en datamaskin i dag utføre en algoritme vesentlig raskere enn en datamaskin fra 1960-tallet, men dette er på grunn av teknologiske gjennombrudd i maskinvare snarere enn en iboende kvalitet på algoritmen. Målet med kompleksitetsteori er å kvantifisere de iboende tidsbehovene til algoritmer, eller de grunnleggende tidsbegrensningene som en algoritme vil pålegge enhver datamaskin. Dette oppnås ved å telle hvor mange grunnleggende operasjoner som utføres under beregningen. Disse prosedyrene blir ofte referert til som trinn fordi de anses å ta konstant tid på en bestemt maskin (dvs. de er upåvirket av mengden av input).
En annen viktig ressurs er mengden dataminne som kreves for å utføre algoritmer.
En annen ofte brukt ressurs er mengden av aritmetiske operasjoner. I dette scenariet brukes begrepet "aritmetisk kompleksitet". Tidskompleksiteten er vanligvis produktet av den aritmetiske kompleksiteten med en konstant faktor hvis en øvre begrensning på størrelsen på den binære representasjonen av tallene som oppstår under en beregning er kjent.
Størrelsen på heltallene som brukes under en beregning er ikke begrenset for mange metoder, og det er urealistisk å anta at aritmetiske operasjoner krever en fast tidsperiode. Som et resultat kan tidskompleksiteten, også kjent som bitkompleksitet, være betydelig høyere enn den aritmetiske kompleksiteten. Den aritmetiske vanskeligheten med å beregne determinanten til en nn heltallsmatrise er for eksempel O(n^3) for standardteknikker (gaussisk eliminering). Fordi størrelsen på koeffisientene kan ekspandere eksponentielt under beregningen, er bitkompleksiteten til de samme metodene eksponentiell i n. Hvis disse teknikkene brukes i forbindelse med multimodulær aritmetikk, kan bitkompleksiteten reduseres til O(n^4).
Bitkompleksiteten, i formelle termer, refererer til antall operasjoner på biter som kreves for å kjøre en algoritme. Det tilsvarer den tidsmessige kompleksiteten opp til en konstant faktor i de fleste beregningsparadigmer. Antall operasjoner på maskinord som kreves av datamaskiner er proporsjonalt med bitkompleksiteten. For realistiske beregningsmodeller er dermed tidskompleksiteten og bitkompleksiteten identiske.
Ressursen som ofte vurderes ved sortering og søk er mengden oppføringer sammenligninger. Hvis dataene er godt ordnet, er dette en god indikator på tidskompleksiteten.
På alle potensielle innganger er det umulig å telle antall trinn i en algoritme. Fordi kompleksiteten til en inngang øker med størrelsen, er den vanligvis representert som en funksjon av inngangens størrelse n (i biter), og derfor er kompleksiteten en funksjon av n. For innganger av samme størrelse kan imidlertid kompleksiteten til en algoritme variere betydelig. Som et resultat brukes en rekke kompleksitetsfunksjoner rutinemessig.
Worst-case-kompleksiteten er summen av all kompleksitet for alle størrelse n-inndata, mens gjennomsnitt-case-kompleksiteten er summen av all kompleksitet for alle størrelse n-inndata (dette er fornuftig, siden antallet mulige innganger av en gitt størrelse er avgrenset). Når begrepet "kompleksitet" brukes uten å være nærmere definert, tas den verste tidskompleksiteten i betraktning.
Det verste tilfellet og det gjennomsnittlige tilfellet er notorisk vanskelig å beregne riktig. Videre har disse eksakte verdiene liten praktisk anvendelse fordi enhver endring i maskin- eller beregningsparadigme vil variere kompleksiteten litt. Videre er ressursbruk ikke viktig for små verdier av n, derfor er enkel implementering ofte mer attraktivt enn lav kompleksitet for liten n.
Av disse grunnene rettes mest oppmerksomhet mot kompleksitetens oppførsel for høy n, det vil si dens asymptotiske oppførsel når n nærmer seg uendelig. Som et resultat blir stor O-notasjon ofte brukt for å indikere kompleksitet.
Beregningsmodeller
Valget av en beregningsmodell, som består i å spesifisere de essensielle operasjonene som utføres i en tidsenhet, er viktig for å bestemme kompleksiteten. Dette blir noen ganger referert til som en multitape Turing-maskin når beregningsparadigmet ikke er spesifikt beskrevet.
En deterministisk beregningsmodell er en der maskinens påfølgende tilstander og operasjonene som skal utføres er fullstendig definert av den forrige tilstanden. Rekursive funksjoner, lambda-kalkulus og Turing-maskiner var de første deterministiske modellene. Tilfeldig tilgangsmaskiner (også kjent som RAM-maskiner) er et populært paradigme for simulering av datamaskiner fra den virkelige verden.
Når beregningsmodellen ikke er definert, antas vanligvis en multitape Turing-maskin. På multitape Turing-maskiner er tidskompleksiteten den samme som på RAM-maskiner for de fleste algoritmer, selv om det kan kreves betydelig oppmerksomhet i hvordan data lagres i minnet for å oppnå denne ekvivalensen.
Ulike valg kan gjøres på noen trinn i beregningen i en ikke-deterministisk modell for databehandling, for eksempel ikke-deterministiske Turing-maskiner. I kompleksitetsteori vurderes alle mulige alternativer samtidig, og ikke-deterministisk tidskompleksitet er mengden tid som kreves når de beste valgene alltid tas. For å si det på en annen måte, blir beregningen utført samtidig på så mange (identiske) prosessorer som kreves, og den ikke-deterministiske beregningstiden er tiden det tar den første prosessoren for å fullføre beregningen. Denne parallelliteten kan brukes i kvanteberegning ved å bruke superponerte sammenfiltrede tilstander når du kjører spesialiserte kvantealgoritmer, for eksempel Shors faktorisering av små heltall.
Selv om en slik beregningsmodell foreløpig ikke er gjennomførbar, har den teoretisk betydning, spesielt i forhold til P = NP-problemet, som spør om kompleksitetsklassene produsert ved å bruke "polynomisk tid" og "ikke-deterministisk polynomtid" som minst øvre grensene er de samme. På en deterministisk datamaskin krever simulering av en NP-algoritme "eksponentiell tid." Hvis en oppgave kan løses i polynomisk tid på et ikke-deterministisk system, tilhører den vanskelighetsklassen NP. Hvis et problem er i NP og ikke er enklere enn noe annet NP-problem, sies det å være NP-komplett. Knapsekkproblemet, det reisende selgerproblemet og det boolske tilfredshetsproblemet er alle NP-komplette kombinatoriske problemer. Den mest kjente algoritmen har eksponentiell kompleksitet for alle disse problemene. Hvis noen av disse problemene kunne løses i polynomtid på en deterministisk maskin, så kunne alle NP-problemer også løses i polynomtid, og P = NP ville bli etablert. Fra og med 2017 er det allment antatt at P NP, noe som antyder at de verste situasjonene med NP-problemer er fundamentalt vanskelige å løse, dvs. tar langt lengre tid enn noe mulig tidsrom (tiår) gitt interessante inputlengder.
Parallell og distribuert databehandling
Parallell og distribuert databehandling innebærer å dele prosessering på tvers av flere prosessorer som alle opererer samtidig. Det grunnleggende skillet mellom de ulike modellene er metoden for å sende data mellom prosessorer. Dataoverføring mellom prosessorer er vanligvis veldig rask i parallell databehandling, mens dataoverføring mellom prosessorer i distribuert databehandling gjøres over et nettverk og er dermed betydelig tregere.
En beregning på N prosessorer tar minst kvotienten med N av tiden det tar på en enkelt prosessor. I virkeligheten, fordi noen deloppgaver ikke kan parallelliseres og noen prosessorer kan trenge å vente på et resultat fra en annen prosessor, vil denne teoretisk ideelle grensen aldri bli oppnådd.
Det sentrale kompleksitetsproblemet er altså å utvikle algoritmer slik at produktet av databehandlingstid med antall prosessorer er så nært som mulig tiden som kreves for å utføre den samme beregningen på en enkelt prosessor.
Kvanteberegning
En kvantedatamaskin er en datamaskin med en kvantemekanikkbasert beregningsmodell. Church-Turing-oppgaven gjelder for kvantedatamaskiner, og antyder at ethvert problem som en kvantedatamaskin kan løse, også kan løses av en Turing-maskin. Imidlertid kan noen oppgaver teoretisk løses ved hjelp av en kvantedatamaskin i stedet for en klassisk datamaskin med betydelig lavere tidskompleksitet. Foreløpig er dette strengt tatt teoretisk, da ingen vet hvordan man utvikler en praktisk kvantedatamaskin.
Kvantekompleksitetsteori ble laget for å undersøke ulike typer problemer som kan løses av kvantedatamaskiner. Det brukes i post-kvantekryptografi, som er prosessen med å lage kryptografiske protokoller som er motstandsdyktige mot kvantedataangrep.
Problemets kompleksitet (nedre grenser)
Det infimum av kompleksiteten til algoritmene som kan løse problemet, inkludert uoppdagede teknikker, er kompleksiteten til problemet. Som et resultat er kompleksiteten til et problem lik kompleksiteten til enhver algoritme som løser det.
Som et resultat representerer enhver kompleksitet gitt i stor O-notasjon en kompleksitet av både algoritmen og det medfølgende problemet.
På den annen side er det ofte vanskelig å oppnå ikke-trivielle nedre grenser for problemkompleksitet, og det er få strategier for å gjøre det.
For å løse de fleste problemer må alle inndata leses, noe som tar tid proporsjonalt med størrelsen på dataene. Som et resultat har slike problemer i det minste lineær kompleksitet, eller, i stor omega-notasjon, en kompleksitet på Ω(n).
Noen problemer, for eksempel de i datamaskinalgebra og beregningsmessig algebraisk geometri, har svært store løsninger. Fordi utdataene må skrives, er kompleksiteten begrenset av den maksimale størrelsen på utdataene.
Antall sammenligninger som kreves for en sorteringsalgoritme har en ikke-lineær nedre grense for Ω(nlogn). Som et resultat er de beste sorteringsalgoritmene de mest effektive siden deres kompleksitet er O(nlogn). Det faktum at det er n! måter å organisere n ting på fører til denne nedre grensen. Fordi hver sammenligning deler denne samlingen av n! bestillinger i to deler, må antallet N sammenligninger som kreves for å skille alle bestillinger være 2N > n!, noe som antyder O(nlogn) med Stirlings formel.
Å redusere et problem til et annet problem er en vanlig strategi for å oppnå reduserte kompleksitetsbegrensninger.
Algoritmeutvikling
Evaluering av en algoritmes kompleksitet er et viktig element i designprosessen siden den gir nyttig informasjon om ytelsen som kan forventes.
Det er en hyppig misforståelse at, som et resultat av Moores lov, som forutsier den eksponentielle veksten av moderne datakraft, vil evaluering av kompleksiteten til algoritmer bli mindre relevant. Dette er feil fordi den økte kraften tillater behandling av enorme mengder data (big data). For eksempel bør enhver algoritme fungere bra på mindre enn et sekund når du sorterer alfabetisk en liste med noen få hundre oppføringer, for eksempel bibliografien til en bok. På den annen side, for en million oppføringer (for eksempel telefonnumrene til en stor by), vil de grunnleggende algoritmene som krever O(n2)-sammenligninger måtte utføre en billion sammenligninger, noe som vil ta tre timer med en hastighet på 10 millioner sammenligninger per sekund. Quicksort og merge sort, derimot, krever bare nlogn-sammenligninger (som gjennomsnittlig kompleksitet for førstnevnte, som verstefallskompleksitet for sistnevnte). Dette gir rundt 30,000,000 1,000,000 3 sammenligninger for n = 10 XNUMX XNUMX, noe som vil ta bare XNUMX sekunder ved XNUMX millioner sammenligninger per sekund.
Som et resultat kan vurdering av kompleksitet tillate eliminering av mange ineffektive algoritmer før implementering. Dette kan også brukes til å finjustere komplekse algoritmer uten å måtte teste alle mulige varianter. Studiet av kompleksitet gjør det mulig å fokusere innsatsen for å øke effektiviteten til en implementering ved å bestemme de mest kostbare trinnene i en kompleks algoritme.
For å gjøre deg mer kjent med sertifiseringspensumet kan du utvide og analysere tabellen nedenfor.
EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum refererer til didaktisk materiale med åpen tilgang i en videoform. Læringsprosessen er delt inn i en trinnvis struktur (programmer -> leksjoner -> emner) som dekker relevante læreplandeler. Deltakerne kan få tilgang til svar og stille mer relevante spørsmål i Spørsmål og svar-delen av e-læringsgrensesnittet under emnet i EITC-programmets pensum. Direkte og ubegrenset rådgivning med domeneeksperter er også tilgjengelig via det plattformintegrerte online meldingssystemet, samt gjennom kontaktskjemaet.
Sjekk for detaljer om sertifiseringsprosedyren Hvordan det fungerer.
Primært støttende læreplan lesemateriell
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Sekundært støttende pensum lesemateriell
O. Goldreich, Introduksjon til kompleksitetsteori:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Støttende lesemateriell om diskret matematikk
J. Aspnes, Notes on Discrete Mathematics:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Støttende pensumlesemateriell om grafteori
R. Diestel, grafteori:
https://diestel-graph-theory.com/
Last ned det komplette offline selvlærende forberedende materialet for EITC/IS/CCTF Computational Complexity Theory Fundamentals-programmet i en PDF-fil
EITC/IS/CCTF forberedende materialer – standardversjon