
EITC/IS/CCTF Computational Complexity Theory Fundamentals är det europeiska IT-certifieringsprogrammet för teoretiska aspekter av grunderna för datavetenskap som också är en bas för klassisk asymmetrisk kryptografi med offentliga nyckel som används i stor utsträckning på Internet.
Läroplanen för EITC/IS/CCTF Computational Complexity Theory Fundamentals täcker teoretisk kunskap om grunderna för datavetenskap och beräkningsmodeller på grundläggande begrepp som deterministiska och icke-deterministiska finita tillståndsmaskiner, reguljära språk, kontextfria grammatiker och språkteori, automatteori, Turing Maskiner, avgörbarhet av problem, rekursion, logik och komplexitet av algoritmer för grundläggande säkerhetsapplikationer inom följande struktur, som omfattar omfattande och strukturerade EITCI-certifieringskurser för självlärande material som stöds av refererat öppet videodidaktiskt innehåll som en grund för förberedelser för att förtjäna denna EITC-certifiering genom att klara ett motsvarande prov.
En algoritms beräkningskomplexitet är mängden resurser som krävs för att driva den. Tid och minnesresurser ägnas särskild uppmärksamhet. Ett problems komplexitet definieras som komplexiteten hos de bästa algoritmerna för att lösa det. Analys av algoritmer är studiet av komplexiteten hos explicit givna algoritmer, medan beräkningskomplexitetsteori är studiet av komplexiteten hos problemlösningar med de mest kända algoritmerna. Båda domänerna är sammanflätade eftersom en algoritms komplexitet alltid är en övre begränsning för komplexiteten hos problemet den löser. Dessutom är det ofta nödvändigt att jämföra komplexiteten hos en viss algoritm med komplexiteten hos det problem som ska lösas samtidigt som effektiva algoritmer konstrueras. I de flesta fall är den enda information som finns tillgänglig om ett problems svårighet att det är mindre än komplexiteten hos de mest effektiva kända teknikerna. Som ett resultat finns det mycket överlappning mellan algoritmanalys och komplexitetsteori.
Komplexitetsteori spelar en viktig roll inte bara i grunderna för beräkningsmodeller som grund för datavetenskap utan också i grunderna för klassisk asymmetrisk kryptografi (så kallad public-key kryptografi) som är allmänt spridd i moderna nätverk, särskilt på Internet. Den offentliga nyckelkrypteringen är baserad på beräkningssvårigheter för vissa asymmetriska matematiska problem som till exempel faktorisering av stora tal till dess primfaktorer (denna operation är ett svårt problem i klassificeringen av komplexitetsteorin, eftersom det inte finns kända effektiva klassiska algoritmer att lösa det med resurser som skalas polynomiskt snarare än exponentiellt med ökningen av problemets indatastorlek, vilket står i motsats till en mycket enkel omvänd operation av multiplicering till kända primtalsfaktorer för att ge det ursprungliga stora talet). Genom att använda denna asymmetri i en arkitektur av publik-nyckel-kryptografin (genom att definiera en beräkningsmässigt asymmetrisk relation mellan den publika nyckeln, som lätt kan beräknas från en privat nyckel, medan den privata nyckeln inte lätt kan vara dator från en offentlig nyckel, kan man offentligt tillkännage den publika nyckeln och möjliggöra för andra kommunikationssidor att använda den för asymmetrisk kryptering av data, som sedan endast kan dekrypteras med den kopplade privata nyckeln, inte tillgänglig beräkningsmässigt för tredje part, vilket gör kommunikationen säker).
Teorin om beräkningskomplexitet utvecklades huvudsakligen på prestationer från datavetenskap och algoritmiska pionjärer, såsom Alan Turing, vars arbete var avgörande för att bryta Nazitysklands Enigma-chiffer, som spelade en djupgående roll i att allierade vann andra världskriget. Kryptanalys som syftar till att utforma och automatisera beräkningsprocesserna för att analysera data (främst krypterad kommunikation) för att avslöja den dolda informationen användes för att bryta mot kryptografiska system och få tillgång till innehållet i krypterad kommunikation, vanligtvis av strategisk militär betydelse. Det var också kryptoanalys som katalyserade utvecklingen av de första moderna datorerna (som ursprungligen tillämpades på ett strategiskt mål att kodbryta). British Colossus (som betraktas som den första moderna elektroniska och programdatorn) föregicks av den polska "bomben", en elektronisk beräkningsenhet designad av Marian Rejewski för att hjälpa till att bryta Enigma-chiffer, och överlämnades till Storbritannien av den polska underrättelsetjänsten tillsammans med den fångade tyska Enigma-krypteringsmaskinen, efter att Polen invaderades av Tyskland 1939. På basis av denna enhet utvecklade Alan Turing sin mer avancerade motsvarighet för att framgångsrikt bryta tysk krypterad kommunikation, som senare har utvecklats till moderna datorer.
Eftersom mängden resurser som krävs för att köra en algoritm varierar med storleken på indata, uttrycks komplexiteten vanligtvis som en funktion f(n), där n är indatastorleken och f(n) är antingen den värsta komplexiteten ( den maximala mängden resurser som krävs för alla indata av storlek n) eller den genomsnittliga fallets komplexitet (genomsnittet av mängden resurser över alla input av storlek n). Antalet nödvändiga elementära operationer på en ingång av storlek n anges vanligtvis som tidskomplexitet, där elementära operationer tros ta en konstant tid på en viss dator och endast ändras med en konstant faktor när de körs på en annan maskin. Mängden minne som krävs av en algoritm på en ingång av storlek n kallas rymdkomplexitet.
Tid är den mest ansedda resursen. När termen "komplexitet" används utan kval, syftar det vanligtvis på tidens komplexitet.
De traditionella tidsenheterna (sekunder, minuter och så vidare) används inte i komplexitetsteorin eftersom de är alltför beroende av den valda datorn och teknikens framsteg. Till exempel kan en dator idag exekvera en algoritm betydligt snabbare än en dator från 1960-talet, men detta beror på tekniska genombrott i datorhårdvara snarare än en inneboende kvalitet hos algoritmen. Målet med komplexitetsteorin är att kvantifiera de inneboende tidsbehoven hos algoritmer, eller de grundläggande tidsbegränsningar som en algoritm skulle införa på vilken dator som helst. Detta åstadkoms genom att räkna hur många grundläggande operationer som utförs under beräkningen. Dessa procedurer kallas vanligtvis steg eftersom de anses ta konstant tid på en viss maskin (dvs. de är opåverkade av mängden inmatning).
En annan viktig resurs är mängden datorminne som krävs för att utföra algoritmer.
En annan ofta använd resurs är mängden aritmetiska operationer. I detta scenario används termen "aritmetisk komplexitet". Tidskomplexiteten är i allmänhet produkten av den aritmetiska komplexiteten med en konstant faktor om en övre begränsning av storleken på den binära representationen av talen som förekommer under en beräkning är känd.
Storleken på de heltal som används under en beräkning är inte begränsad för många metoder, och det är orealistiskt att anta att aritmetiska operationer kräver en fast tidsperiod. Som ett resultat kan tidskomplexiteten, även känd som bitkomplexitet, vara betydligt högre än den aritmetiska komplexiteten. Den aritmetiska svårigheten att beräkna determinanten för en nn heltalsmatris är till exempel O(n^3) för standardtekniker (gaussisk eliminering). Eftersom storleken på koefficienterna kan expandera exponentiellt under beräkningen, är bitkomplexiteten för samma metoder exponentiell i n. Om dessa tekniker används i kombination med multimodulär aritmetik, kan bitkomplexiteten minskas till O(n^4).
Bitkomplexiteten, i formella termer, hänvisar till antalet operationer på bitar som krävs för att köra en algoritm. Det är lika med den tidsmässiga komplexiteten upp till en konstant faktor i de flesta beräkningsparadigm. Antalet operationer på maskinord som krävs av datorer är proportionellt mot bitkomplexiteten. För realistiska beräkningsmodeller är tidskomplexiteten och bitkomplexiteten alltså identiska.
Den resurs som ofta övervägs vid sortering och sökning är antalet poster som jämförelser. Om uppgifterna är välordnade är detta en bra indikator på tidskomplexiteten.
På alla potentiella ingångar är det omöjligt att räkna antalet steg i en algoritm. Eftersom komplexiteten hos en ingång ökar med dess storlek, representeras den vanligtvis som en funktion av inmatningens storlek n (i bitar), och därför är komplexiteten en funktion av n. För indata av samma storlek kan dock komplexiteten hos en algoritm variera avsevärt. Som ett resultat används en mängd olika komplexitetsfunktioner rutinmässigt.
Den värsta fallets komplexiteten är summan av all komplexitet för alla storlek n indata, medan genomsnittskomplexiteten är summan av all komplexitet för alla storlek n indata (detta är vettigt, eftersom antalet möjliga indata av en given storlek är ändlig). När termen "komplexitet" används utan att definieras närmare, tas hänsyn till den värsta tidskomplexiteten.
Det värsta fallet och det genomsnittliga fallets komplexitet är notoriskt svåra att beräkna korrekt. Dessutom har dessa exakta värden liten praktisk tillämpning eftersom varje förändring i maskin- eller beräkningsparadigm skulle variera komplexiteten något. Dessutom är resursanvändning inte viktig för små värden på n, därför är enkel implementering ofta mer tilltalande än låg komplexitet för små n.
Av dessa skäl ägnas mest uppmärksamhet åt komplexitetens beteende för högt n, det vill säga dess asymptotiska beteende när n närmar sig oändligheten. Som ett resultat används stor O-notation vanligtvis för att indikera komplexitet.
Beräkningsmodeller
Valet av en beräkningsmodell, som består av att specificera de väsentliga operationerna som utförs i en tidsenhet, är viktigt för att bestämma komplexiteten. Detta kallas ibland för en multitape Turing-maskin när beräkningsparadigmet inte är specifikt beskrivet.
En deterministisk beräkningsmodell är en där maskinens efterföljande tillstånd och de operationer som ska utföras helt och hållet definieras av det föregående tillståndet. Rekursiva funktioner, lambda-kalkyl och Turing-maskiner var de första deterministiska modellerna. Datorer med slumpmässig åtkomst (även kända som RAM-maskiner) är ett populärt paradigm för att simulera verkliga datorer.
När beräkningsmodellen inte är definierad, antas vanligtvis en Turing-maskin med flera band. På Turing-maskiner med flera band är tidskomplexiteten densamma som på RAM-maskiner för de flesta algoritmer, även om det kan krävas stor uppmärksamhet i hur data lagras i minnet för att uppnå denna ekvivalens.
Olika val kan göras i vissa steg av beräkningen i en icke-deterministisk datormodell, såsom icke-deterministiska Turing-maskiner. I komplexitetsteorin övervägs alla möjliga alternativ samtidigt, och icke-deterministisk tidskomplexitet är den tid som krävs när de bästa valen alltid görs. För att uttrycka det på ett annat sätt, beräkningen görs samtidigt på så många (identiska) processorer som krävs, och den icke-deterministiska beräkningstiden är den tid det tar för den första processorn att slutföra beräkningen. Denna parallellitet kan användas i kvantberäkning genom att använda överlagrade intrasslade tillstånd när man kör specialiserade kvantalgoritmer, såsom Shors faktorisering av små heltal till exempel.
Även om en sådan beräkningsmodell för närvarande inte är praktiskt genomförbar, har den teoretisk betydelse, särskilt i relation till P = NP-problemet, som frågar om komplexitetsklasserna som produceras genom att använda "polynomtid" och "icke-deterministisk polynomtid" som minst övre gränserna är desamma. På en deterministisk dator kräver simulering av en NP-algoritm "exponentiell tid". Om en uppgift kan lösas i polynomtid på ett icke-deterministiskt system, tillhör den svårighetsklassen NP. Om ett problem är i NP och inte är lättare än något annat NP-problem, sägs det vara NP-komplett. Ryggsäcksproblemet, resandeförsäljarproblemet och det booleska tillfredsställbarhetsproblemet är alla NP-kompletta kombinatoriska problem. Den mest välkända algoritmen har exponentiell komplexitet för alla dessa problem. Om något av dessa problem kunde lösas i polynomtid på en deterministisk maskin, skulle alla NP-problem också kunna lösas i polynomtid, och P = NP skulle fastställas. Från och med 2017 antas det allmänt att P NP, vilket antyder att de värsta situationerna med NP-problem är fundamentalt svåra att lösa, dvs. tar mycket längre tid än någon genomförbar tidsperiod (decennier) givet intressanta inmatningslängder.
Parallell och distribuerad datoranvändning
Parallell och distribuerad beräkning innebär att bearbetningen delas mellan flera processorer som alla arbetar samtidigt. Den grundläggande skillnaden mellan de olika modellerna är metoden för att skicka data mellan processorer. Dataöverföring mellan processorer är vanligtvis mycket snabb vid parallell beräkning, medan dataöverföring mellan processorer i distribuerad beräkning sker över ett nätverk och är därför avsevärt långsammare.
En beräkning på N processorer tar åtminstone kvoten med N av den tid det tar på en enskild processor. I verkligheten, eftersom vissa deluppgifter inte kan parallelliseras och vissa processorer kan behöva vänta på ett resultat från en annan processor, kommer denna teoretiskt idealiska gräns aldrig att uppnås.
Den viktigaste komplexitetsfrågan är alltså att utveckla algoritmer så att produkten av beräkningstiden med antalet processorer är så nära som möjligt den tid som krävs för att utföra samma beräkning på en enda processor.
Kvantberäkning
En kvantdator är en dator med en kvantmekanikbaserad beräkningsmodell. Kyrkan-Turing-avhandlingen gäller för kvantdatorer, vilket innebär att alla problem som en kvantdator kan lösa också kan lösas av en Turing-maskin. Vissa uppgifter kan dock teoretiskt lösas med en kvantdator snarare än en klassisk dator med en betydligt lägre tidskomplexitet. För närvarande är detta strikt teoretiskt, eftersom ingen vet hur man utvecklar en praktisk kvantdator.
Kvantkomplexitetsteori skapades för att undersöka olika typer av problem som kan lösas med kvantdatorer. Det används i post-kvantkryptering, vilket är processen att skapa kryptografiska protokoll som är resistenta mot kvantdatorangrepp.
Problemets komplexitet (nedre gränser)
Det infimum av komplexiteten hos de algoritmer som kan lösa problemet, inklusive oupptäckta tekniker, är problemets komplexitet. Som ett resultat är komplexiteten hos ett problem lika med komplexiteten hos alla algoritmer som löser det.
Som ett resultat representerar all komplexitet som ges i stor O-notation en komplexitet av både algoritmen och det åtföljande problemet.
Å andra sidan är det ofta svårt att få icke-triviala nedre gränser för problemkomplexitet, och det finns få strategier för att göra det.
För att lösa de flesta problem måste all indata läsas, vilket tar tid i proportion till storleken på datan. Som ett resultat har sådana problem åtminstone linjär komplexitet, eller, i big omega-notation, en komplexitet på Ω(n).
Vissa problem, som de inom datoralgebra och beräkningsalgebraisk geometri, har mycket stora lösningar. Eftersom utdata måste skrivas begränsas komplexiteten av utdatas maximala storlek.
Antalet jämförelser som krävs för en sorteringsalgoritm har en olinjär nedre gräns för Ω(nlogn). Som ett resultat är de bästa sorteringsalgoritmerna de mest effektiva eftersom deras komplexitet är O(nlogn). Det faktum att det finns n! sätt att organisera n saker leder till denna nedre gräns. Eftersom varje jämförelse delar denna samling av n! beställningar i två delar måste antalet N jämförelser som krävs för att särskilja alla beställningar vara 2N > n!, vilket innebär O(nlogn) av Stirlings formel.
Att reducera ett problem till ett annat problem är en vanlig strategi för att få reducerade komplexitetsbegränsningar.
Algoritmutveckling
Att utvärdera en algoritms komplexitet är en viktig del av designprocessen eftersom den ger användbar information om den prestanda som kan förväntas.
Det är ett frekvent missförstånd att, som ett resultat av Moores lag, som förutsäger den exponentiella tillväxten av modern datorkraft, kommer att utvärdera komplexiteten hos algoritmer att bli mindre relevant. Detta är felaktigt eftersom den ökade kraften möjliggör bearbetning av enorma mängder data (big data). Till exempel bör vilken algoritm som helst fungera bra på mindre än en sekund när man alfabetiskt sorterar en lista med några hundra poster, till exempel bibliografin för en bok. Å andra sidan, för en miljon poster (till exempel telefonnumren till en stor stad) skulle de grundläggande algoritmerna som kräver O(n2)-jämförelser behöva utföra en biljon jämförelser, vilket skulle ta tre timmar med en hastighet av 10 miljoner jämförelser per sekund. Quicksort och merge sort, å andra sidan, kräver bara nlogn-jämförelser (som genomsnittskomplexitet för det förra, som värsta fallet för det senare). Detta ger cirka 30,000,000 1,000,000 3 jämförelser för n = 10 XNUMX XNUMX, vilket bara skulle ta XNUMX sekunder vid XNUMX miljoner jämförelser per sekund.
Som ett resultat kan bedömning av komplexitet möjliggöra eliminering av många ineffektiva algoritmer före implementering. Detta kan också användas för att finjustera komplexa algoritmer utan att behöva testa alla möjliga varianter. Studiet av komplexitet gör det möjligt att fokusera ansträngningen för att öka effektiviteten i en implementering genom att bestämma de mest kostsamma stegen i en komplex algoritm.
För att bekanta dig i detalj med certifieringsläroplanen kan du utöka och analysera tabellen nedan.
EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum refererar till didaktiskt material med öppen tillgång i en videoform. Lärprocessen är uppdelad i en steg-för-steg-struktur (program -> lektioner -> ämnen) som täcker relevanta läroplansdelar. Deltagarna kan få tillgång till svar och ställa mer relevanta frågor i avsnittet Frågor och svar i gränssnittet för e-lärande under det aktuella ämnet för EITC-programmets läroplan. Direkt och obegränsad konsultation med domänexperter är också tillgänglig via det plattformsintegrerade onlinemeddelandesystemet, såväl som via kontaktformuläret.
För detaljer om certifieringsförfarandet kontrollera Hur det fungerar.
Primärt stödjande läroplansläsmaterial
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Sekundärt stödjande läroplansläsmaterial
O. Goldreich, Introduktion till komplexitetsteori:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Stödjande läroplansläsmaterial om diskret matematik
J. Aspnes, Notes on Discrete Mathematics:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Stödjande läroplansläsmaterial om grafteori
R. Diestel, grafteori:
https://diestel-graph-theory.com/
Ladda ner det fullständiga offline självlärande förberedande materialet för programmet EITC/IS/CCTF Computational Complexity Theory Fundamentals i en PDF-fil
EITC/IS/CCTF förberedande material – standardversion
EITC/IS/CCTF förberedande material – utökad version med granskningsfrågor