EITC/IS/CCTF Computational Complexity Theory Fundamentals

by admin / Mandag, 03 May 2021 / Udgivet i Ikke kategoriseret

Nuværende status

Ikke tilmeldt

Pris

€110

Kom i gang

Tilmeld dig denne certificering

EITC/IS/CCTF Computational Complexity Theory Fundamentals er det europæiske IT-certificeringsprogram om teoretiske aspekter af grundlaget for datalogi, som også er grundlaget for klassisk asymmetrisk offentlig nøglekryptografi, der i vid udstrækning anvendes på internettet.

Læseplanen for EITC/IS/CCTF Computational Complexity Theory Fundamentals dækker teoretisk viden om grundlaget for datalogi og beregningsmodeller på grundbegreber som deterministiske og ikke-deterministiske endelige tilstandsmaskiner, regulære sprog, kontekstfrie grammatikere og sprogteori, automatteori, Turing Maskiner, problemers afgørelighed, rekursion, logik og kompleksitet af algoritmer til grundlæggende sikkerhedsapplikationer inden for følgende struktur, der omfatter omfattende videodidaktisk indhold som reference for denne EITC-certificering.

En algoritmes beregningsmæssige kompleksitet er mængden af ressourcer, der kræves for at betjene den. Tids- og hukommelsesressourcer får særlig opmærksomhed. Et problems kompleksitet defineres som kompleksiteten af de bedste algoritmer til at løse det. Analyse af algoritmer er studiet af kompleksiteten af eksplicit givne algoritmer, hvorimod beregningsmæssig kompleksitetsteori er studiet af kompleksiteten af problemløsninger med bedst kendte algoritmer. Begge domæner er sammenflettet, fordi en algoritmes kompleksitet altid er en øvre begrænsning for kompleksiteten af det problem, den løser. Desuden er det ofte nødvendigt at sammenligne kompleksiteten af en bestemt algoritme med kompleksiteten af det problem, der skal løses, mens der konstrueres effektive algoritmer. I de fleste tilfælde er den eneste tilgængelige information om et problems vanskelighed, at det er mindre end kompleksiteten af de mest effektive kendte teknikker. Som et resultat er der meget overlap mellem algoritmeanalyse og kompleksitetsteori.

Kompleksitetsteori spiller ikke kun en vigtig rolle i grundlaget for beregningsmodeller som grundlag for datalogi, men også i grundlaget for klassisk asymmetrisk kryptografi (såkaldt offentlig nøglekryptografi), som er vidt udbredt i moderne netværk, især på internettet. Public-key-krypteringen er baseret på beregningsmæssige vanskeligheder af visse asymmetriske matematiske problemer, såsom for eksempel faktorisering af store tal til dets primfaktorer (denne operation er et svært problem i kompleksitetsteori-klassificeringen, fordi der ikke er kendte effektive klassiske algoritmer til at løse det med ressourcer, der skaleres polynomielt snarere end eksponentielt med stigningen af problemets inputstørrelse, hvilket er i modsætning til en meget simpel omvendt operation med at gange til kendte primfaktorer for at give det oprindelige store tal). Ved at bruge denne asymmetri i en arkitektur af offentlig nøglekryptografi (ved at definere en beregningsmæssigt asymmetrisk relation mellem den offentlige nøgle, der let kan beregnes fra en privat nøgle, mens den private nøgle ikke let kan computer fra en offentlig nøgle, kan man offentligt annoncerer den offentlige nøgle og gør det muligt for andre kommunikationssider at bruge den til asymmetrisk kryptering af data, som så kun kan dekrypteres med den koblede private nøgle, som ikke er beregnet tilgængelig for tredjeparter, hvilket gør kommunikationen sikker).

Teorien om beregningskompleksitet blev hovedsageligt udviklet på præstationer af datalogi og algoritmiske pionerer, såsom Alan Turing, hvis arbejde var afgørende for at bryde Nazitysklands Enigma-chiffer, som spillede en dybtgående rolle i, at allierede vandt Anden Verdenskrig. Krypteringsanalyse, der sigter mod at udtænke og automatisere de beregningsmæssige processer til at analysere data (hovedsageligt krypteret kommunikation) for at afdække den skjulte information, blev brugt til at bryde kryptografiske systemer og få adgang til indholdet af krypteret kommunikation, normalt af strategisk militær betydning. Det var også kryptoanalyse, der katalyserede udviklingen af de første moderne computere (som oprindeligt blev anvendt til et strategisk mål om kodebrud). British Colossus (betragtet som den første moderne elektroniske og programcomputer) blev forudgået af den polske "bombe", en elektronisk beregningsenhed designet af Marian Rejewski til at hjælpe med at bryde Enigma-cifre, og overdraget til Storbritannien af den polske efterretningstjeneste sammen med den erobrede tyske Enigma-krypteringsmaskine, efter at Polen blev invaderet af Tyskland i 1939. På basis af denne enhed udviklede Alan Turing sin mere avancerede pendant til med succes at bryde tysk krypteret kommunikation, som senere er blevet udviklet til moderne computere.

Fordi mængden af ressourcer, der kræves for at køre en algoritme, varierer med størrelsen af inputtet, udtrykkes kompleksiteten normalt som en funktion f(n), hvor n er inputstørrelsen, og f(n) enten er den værste kompleksitet ( den maksimale mængde ressourcer, der kræves på tværs af alle input af størrelse n) eller den gennemsnitlige sagskompleksitet (gennemsnittet af mængden af ressourcer over alle input af størrelse n). Antallet af nødvendige elementære operationer på et input af størrelse n er almindeligvis angivet som tidskompleksitet, hvor elementære operationer antages at tage en konstant mængde tid på en bestemt computer og kun ændres med en konstant faktor, når de køres på en anden maskine. Mængden af hukommelse, der kræves af en algoritme på et input af størrelse n, er kendt som rumkompleksitet.

Tid er den mest almindeligt betragtede ressource. Når udtrykket "kompleksitet" bruges uden kvalifikatoren, refererer det normalt til tidens kompleksitet.

De traditionelle tidsenheder (sekunder, minutter og så videre) anvendes ikke i kompleksitetsteori, da de er for afhængige af den valgte computer og teknologiens fremskridt. For eksempel kan en computer i dag udføre en algoritme væsentligt hurtigere end en computer fra 1960'erne, men alligevel skyldes dette teknologiske gennembrud i computerhardware snarere end en iboende kvalitet af algoritmen. Målet med kompleksitetsteori er at kvantificere algoritmernes iboende tidsbehov eller de grundlæggende tidsbegrænsninger, som en algoritme ville pålægge enhver computer. Dette opnås ved at tælle, hvor mange grundlæggende operationer der udføres under beregningen. Disse procedurer omtales almindeligvis som trin, fordi de anses for at tage konstant tid på en bestemt maskine (dvs. de er upåvirket af mængden af input).

En anden afgørende ressource er mængden af computerhukommelse, der kræves for at udføre algoritmer.

En anden ofte brugt ressource er mængden af aritmetiske operationer. I dette scenarie bruges udtrykket "aritmetisk kompleksitet". Tidskompleksiteten er generelt produktet af den aritmetiske kompleksitet med en konstant faktor, hvis en øvre begrænsning på størrelsen af den binære repræsentation af de tal, der forekommer under en beregning, er kendt.

Størrelsen af de heltal, der bruges under en beregning, er ikke begrænset til mange metoder, og det er urealistisk at antage, at aritmetiske operationer kræver en fast mængde tid. Som følge heraf kan tidskompleksiteten, også kendt som bitkompleksitet, være betydeligt højere end den aritmetiske kompleksitet. Den aritmetiske vanskelighed ved at beregne determinanten for en nn heltalsmatrix er for eksempel O(n^3) for standardteknikker (gaussisk eliminering). Fordi størrelsen af koefficienterne kan udvides eksponentielt under beregningen, er bitkompleksiteten af de samme metoder eksponentiel i n. Hvis disse teknikker bruges sammen med multi-modulær aritmetik, kan bitkompleksiteten reduceres til O(n^4).

Bitkompleksiteten refererer i formelle termer til antallet af operationer på bits, der kræves for at køre en algoritme. Det svarer til den tidsmæssige kompleksitet op til en konstant faktor i de fleste beregningsparadigmer. Antallet af operationer på maskinord, der kræves af computere, er proportionalt med bitkompleksiteten. For realistiske beregningsmodeller er tidskompleksiteten og bitkompleksiteten således identiske.

Den ressource, der ofte overvejes ved sortering og søgning, er mængden af sammenligninger af poster. Hvis dataene er godt arrangeret, er dette en god indikator for tidskompleksiteten.

På alle potentielle input er det umuligt at tælle antallet af trin i en algoritme. Fordi kompleksiteten af et input stiger med dets størrelse, er det almindeligvis repræsenteret som en funktion af inputets størrelse n (i bits), og kompleksiteten er derfor en funktion af n. For input af samme størrelse kan kompleksiteten af en algoritme imidlertid variere betydeligt. Som et resultat anvendes en række kompleksitetsfunktioner rutinemæssigt.

Worst-case kompleksiteten er summen af al kompleksitet for alle størrelse n input, mens den gennemsnitlige case kompleksitet er summen af al kompleksitet for alle størrelse n input (dette giver mening, da antallet af mulige input af en given størrelse er begrænset). Når begrebet "kompleksitet" bruges uden at blive nærmere defineret, tages der hensyn til den værste tidskompleksitet.

Worst-case og gennemsnit-case kompleksitet er notorisk svære at beregne korrekt. Desuden har disse nøjagtige værdier ringe praktisk anvendelse, fordi enhver ændring i maskin- eller beregningsparadigme ville variere kompleksiteten lidt. Desuden er ressourceforbrug ikke afgørende for små værdier af n, derfor er let implementering ofte mere tiltalende end lav kompleksitet for små n.

Af disse grunde lægges der mest opmærksomhed på kompleksitetens adfærd for høj n, det vil sige dens asymptotiske adfærd, når n nærmer sig uendelighed. Som et resultat er stor O-notation almindeligvis brugt til at angive kompleksitet.

Beregningsmodeller

Valget af en beregningsmodel, som består i at specificere de væsentlige operationer, der udføres i en tidsenhed, er afgørende for at bestemme kompleksiteten. Dette omtales nogle gange som en multitape Turing-maskine, når beregningsparadigmet ikke er specifikt beskrevet.

En deterministisk beregningsmodel er en, hvor maskinens efterfølgende tilstande og de operationer, der skal udføres, er fuldstændigt defineret af den foregående tilstand. Rekursive funktioner, lambdaregning og Turing-maskiner var de første deterministiske modeller. Random-access-maskiner (også kendt som RAM-maskiner) er et populært paradigme til at simulere computere i den virkelige verden.

Når beregningsmodellen ikke er defineret, antages der normalt en multitape Turing-maskine. På multitape Turing-maskiner er tidskompleksiteten den samme som på RAM-maskiner for de fleste algoritmer, omend der kan være behov for betydelig opmærksomhed i, hvordan data lagres i hukommelsen for at opnå denne ækvivalens.

Forskellige valg kan foretages på nogle trin af beregningen i en ikke-deterministisk computermodel, såsom ikke-deterministiske Turing-maskiner. I kompleksitetsteori betragtes alle mulige muligheder på samme tid, og ikke-deterministisk tidskompleksitet er mængden af tid, der kræves, når de bedste valg altid træffes. For at sige det på en anden måde, udføres beregningen samtidigt på så mange (identiske) processorer, som der kræves, og den ikke-deterministiske beregningstid er den tid, det tager den første processor at fuldføre beregningen. Denne parallelitet kan bruges i kvanteberegning ved at bruge overlejrede sammenfiltrede tilstande, når man kører specialiserede kvantealgoritmer, såsom Shors faktorisering af små heltal for eksempel.

Selvom en sådan beregningsmodel i øjeblikket ikke er praktisk anvendelig, har den teoretisk betydning, især i forhold til P = NP-problemet, som spørger, om kompleksitetsklasserne produceret ved at bruge "polynomiel tid" og "ikke-deterministisk polynomiel tid" som mindste øvre grænser er de samme. På en deterministisk computer kræver simulering af en NP-algoritme "eksponentiel tid." Hvis en opgave kan løses i polynomisk tid på et ikke-deterministisk system, hører den til NP-sværhedsklassen. Hvis et problem er i NP og ikke er nemmere end noget andet NP-problem, siges det at være NP-komplet. Rullesækkeproblemet, det rejsende sælgerproblem og det boolske tilfredshedsproblem er alle NP-komplette kombinatoriske problemer. Den mest kendte algoritme har eksponentiel kompleksitet for alle disse problemer. Hvis nogen af disse problemer kunne løses i polynomiel tid på en deterministisk maskine, så kunne alle NP-problemer også løses i polynomiel tid, og P = NP ville blive etableret. Fra 2017 er det almindeligt antaget, at P NP, hvilket antyder, at de værste situationer med NP-problemer er fundamentalt vanskelige at løse, dvs. tager langt længere tid end nogen mulig tid (årtier) givet interessante inputlængder.

Parallel og distribueret databehandling

Parallel og distribueret databehandling involverer opdeling af behandling på tværs af flere processorer, der alle arbejder på samme tid. Den grundlæggende skelnen mellem de forskellige modeller er metoden til at sende data mellem processorer. Datatransmission mellem processorer er typisk meget hurtig i parallel computing, hvorimod dataoverførsel mellem processorer i distribueret computing foregår på tværs af et netværk og dermed er væsentligt langsommere.

En beregning på N processorer tager mindst kvotienten med N af den tid, det tager på en enkelt processor. I virkeligheden, fordi nogle underopgaver ikke kan paralleliseres, og nogle processorer muligvis skal vente på et resultat fra en anden processor, vil denne teoretisk ideelle binding aldrig blive opnået.

Det centrale kompleksitetsproblem er således at udvikle algoritmer, således at produktet af regnetid med antallet af processorer er så tæt som muligt på den tid, det tager at udføre den samme beregning på en enkelt processor.

Kvanteberegning

En kvantecomputer er en computer med en kvantemekanik-baseret beregningsmodel. Church-Turing-afhandlingen gælder for kvantecomputere, hvilket antyder, at ethvert problem, som en kvantecomputer kan løse, også kan løses af en Turing-maskine. Nogle opgaver kan dog teoretisk løses ved hjælp af en kvantecomputer frem for en klassisk computer med en væsentlig lavere tidsmæssig kompleksitet. Foreløbig er dette strengt teoretisk, da ingen ved, hvordan man udvikler en praktisk kvantecomputer.

Kvantekompleksitetsteori blev skabt for at undersøge de forskellige typer problemer, der kan løses af kvantecomputere. Det bruges i post-kvantekryptografi, som er processen med at skabe kryptografiske protokoller, der er modstandsdygtige over for kvantecomputerangreb.

Problemets kompleksitet (nedre grænser)

Det infimum af kompleksiteten af de algoritmer, der kan løse problemet, herunder uopdagede teknikker, er kompleksiteten af problemet. Som et resultat er kompleksiteten af et problem lig med kompleksiteten af enhver algoritme, der løser det.

Som et resultat heraf repræsenterer enhver kompleksitet givet i stor O-notation en kompleksitet af både algoritmen og det medfølgende problem.

På den anden side er det ofte svært at opnå ikke-trivielle nedre grænser for problemkompleksitet, og der er få strategier til at gøre det.

For at løse de fleste problemer skal alle inputdata læses, hvilket tager tid i forhold til størrelsen af dataene. Som et resultat heraf har sådanne problemer i det mindste lineær kompleksitet eller, i big omega-notation, en kompleksitet på Ω(n).

Nogle problemer, såsom dem i computeralgebra og beregningsmæssig algebraisk geometri, har meget store løsninger. Fordi output skal skrives, er kompleksiteten begrænset af den maksimale størrelse af output.

Antallet af sammenligninger, der kræves til en sorteringsalgoritme, har en ikke-lineær nedre grænse for Ω(nlogn). Som et resultat er de bedste sorteringsalgoritmer de mest effektive, da deres kompleksitet er O(nlogn). Det faktum, at der er n! måder at organisere n ting på fører til denne nedre grænse. Fordi hver sammenligning deler denne samling af n! ordrer i to stykker, skal antallet af N sammenligninger, der kræves for at skelne alle ordrer, være 2N > n!, hvilket betyder O(nlogn) ved Stirlings formel.

At reducere et problem til et andet problem er en almindelig strategi for at opnå reducerede kompleksitetsbegrænsninger.

Algoritmeudvikling

Evaluering af en algoritmes kompleksitet er et vigtigt element i designprocessen, da det giver nyttige oplysninger om den ydeevne, der kan forventes.

Det er en hyppig misforståelse, at som et resultat af Moores lov, der forudsiger den eksponentielle vækst af moderne computerkraft, vil evaluering af kompleksiteten af algoritmer blive mindre relevant. Dette er forkert, fordi den øgede effekt giver mulighed for at behandle enorme mængder data (big data). For eksempel bør enhver algoritme fungere godt på mindre end et sekund, når du sorterer alfabetisk en liste med nogle få hundrede poster, såsom bibliografien for en bog. På den anden side, for en million indtastninger (for eksempel telefonnumrene i en stor by), ville de grundlæggende algoritmer, der kræver O(n2) sammenligninger skulle udføre en billion sammenligninger, hvilket ville tage tre timer med en hastighed på 10 millioner sammenligninger i sekundet. Quicksort og merge sort kræver på den anden side kun nlogn-sammenligninger (som gennemsnitlig-case-kompleksitet for førstnævnte, som worst-case-kompleksitet for sidstnævnte). Dette producerer omkring 30,000,000 sammenligninger for n = 1,000,000, hvilket kun ville tage 3 sekunder ved 10 millioner sammenligninger i sekundet.

Som et resultat heraf kan vurdering af kompleksitet muliggøre eliminering af mange ineffektive algoritmer før implementering. Dette kan også bruges til at finjustere komplekse algoritmer uden at skulle teste alle mulige varianter. Studiet af kompleksitet gør det muligt at fokusere indsatsen for at øge effektiviteten af en implementering ved at bestemme de dyreste trin i en kompleks algoritme.

For at gøre dig nærmere bekendt med certificeringspensum kan du udvide og analysere nedenstående tabel.

EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum refererer til didaktisk materiale med åben adgang i en videoform. Læreprocessen er opdelt i en trin-for-trin struktur (programmer -> lektioner -> emner), der dækker relevante læseplansdele. Der tilbydes også ubegrænset rådgivning med domæneeksperter.
Tjek for detaljer om certificeringsproceduren Sådan fungerer det.