EITC/IS/CCTF Computational Complexity Theory Fundamentals este programul european de certificare IT cu privire la aspectele teoretice ale fundamentelor informaticii, care sunt, de asemenea, o bază a criptografiei clasice asimetrice cu cheie publică foarte utilizată pe Internet.
Curriculum-ul EITC/IS/CCTF Fundamentele teoriei complexității computaționale acoperă cunoștințele teoretice despre fundamentele informaticii și modelele computaționale pe concepte de bază, cum ar fi mașini cu stări finite deterministe și nedeterministe, limbaje obișnuite, teoria gramaticilor și limbajelor fără context, teoria automatelor, Turing Mașini, determinabilitatea problemelor, recursiunea, logica și complexitatea algoritmică pentru aplicații fundamentale de securitate în cadrul următoarei structuri, cuprinzând conținut video didactic cuprinzător ca referință pentru această Certificare EITC.
Complexitatea de calcul a unui algoritm este cantitatea de resurse necesare pentru a-l opera. Resurselor de timp și memorie li se acordă o atenție deosebită. Complexitatea unei probleme este definită ca fiind complexitatea celor mai buni algoritmi pentru rezolvarea acesteia. Analiza algoritmilor este studiul complexității algoritmilor dați în mod explicit, în timp ce teoria complexității computaționale este studiul complexității soluțiilor de probleme cu cei mai cunoscuți algoritmi. Ambele domenii sunt împletite deoarece complexitatea unui algoritm este întotdeauna o constrângere superioară a complexității problemei pe care o rezolvă. În plus, este adesea necesar să se compare complexitatea unui anumit algoritm cu complexitatea problemei de rezolvat în timp ce se construiesc algoritmi eficienți. În majoritatea circumstanțelor, singura informație disponibilă cu privire la dificultatea unei probleme este că aceasta este mai mică decât complexitatea celor mai eficiente tehnici cunoscute. Ca rezultat, există o mulțime de suprapunere între analiza algoritmului și teoria complexității.
Teoria complexității joacă un rol important nu numai în bazele modelelor computaționale ca bază pentru informatică, ci și în bazele criptografiei asimetrice clasice (așa-numita criptografie cu cheie publică), care este larg răspândită în rețelele moderne, în special în Internet. Criptarea cu cheie publică se bazează pe o dificultate de calcul a anumitor probleme matematice asimetrice, cum ar fi, de exemplu, factorizarea numerelor mari în factorii săi primi (această operație este o problemă dificilă în clasificarea teoriei complexității, deoarece nu sunt cunoscuți algoritmi clasici eficienți de rezolvat). aceasta cu resurse care se scalează polinomial mai degrabă decât exponențial odată cu creșterea dimensiunii de intrare a problemei, ceea ce este în contrast cu o operație inversă foarte simplă de înmulțire la factori primi cunoscuți pentru a da numărul mare inițial). Folosind această asimetrie într-o arhitectură a criptografiei cu cheie publică (prin definirea unei relații asimetrice computațional între cheia publică, care poate fi calculată cu ușurință dintr-o cheie privată, în timp ce cheia privată nu poate fi ușor computerizată dintr-o cheie publică, se poate face public anunță cheia publică și permite altor părți de comunicare să o utilizeze pentru criptarea asimetrică a datelor, care pot fi apoi decriptate numai cu cheia privată cuplată, care nu este disponibilă computațional pentru terți, făcând astfel comunicarea securizată).
Teoria complexității computaționale a fost dezvoltată în principal pe realizările pionierilor informaticii și algoritmicii, cum ar fi Alan Turing, a cărui activitate a fost esențială pentru spargerea cifrului Enigma al Germaniei naziste, care a jucat un rol profund în câștigarea aliaților în cel de-al Doilea Război Mondial. Criptanaliza care vizează conceperea și automatizarea proceselor de calcul de analiză a datelor (în principal comunicații criptate) în scopul dezvăluirii informațiilor ascunse a fost utilizată pentru a încălca sistemele criptografice și pentru a obține acces la conținutul comunicațiilor criptate, de obicei de importanță militară strategică. Criptanaliza a fost, de asemenea, cea care a catalizat dezvoltarea primelor computere moderne (care au fost aplicate inițial unui obiectiv strategic de spargere a codurilor). Colosul britanic (considerat ca fiind primul computer modern electronic și program) a fost precedat de „bomba” poloneză, un dispozitiv electronic de calcul proiectat de Marian Rejewski pentru a ajuta la spargerea cifrurilor Enigma și predat Marii Britanii de către serviciile de informații poloneze împreună cu mașina de criptare Enigma germană capturată, după ce Polonia a fost invadată de Germania în 1939. Pe baza acestui dispozitiv, Alan Turing și-a dezvoltat omologul mai avansat pentru a întrerupe cu succes comunicarea criptată germană, care a fost ulterior dezvoltată în calculatoare moderne.
Deoarece cantitatea de resurse necesară pentru a rula un algoritm variază în funcție de dimensiunea intrării, complexitatea este de obicei exprimată ca o funcție f(n), unde n este dimensiunea intrării și f(n) este fie complexitatea în cel mai rău caz ( cantitatea maximă de resurse necesară pentru toate intrările de dimensiunea n) sau complexitatea medie a cazului (media cantității de resurse pentru toate intrările de dimensiunea n). Numărul de operații elementare necesare pe o intrare de dimensiunea n este de obicei declarat ca complexitate în timp, unde se crede că operațiunile elementare durează o perioadă constantă de timp pe un anumit computer și se modifică doar cu un factor constant atunci când sunt rulate pe o altă mașină. Cantitatea de memorie necesară unui algoritm pentru o intrare de dimensiunea n este cunoscută sub numele de complexitate spațială.
Timpul este resursa considerată cel mai adesea. Când termenul „complexitate” este folosit fără calificativ, se referă de obicei la complexitatea timpului.
Unitățile tradiționale de timp (secunde, minute și așa mai departe) nu sunt folosite în teoria complexității, deoarece se bazează prea mult pe computerul ales și pe progresul tehnologiei. De exemplu, un computer de astăzi poate executa un algoritm substanțial mai rapid decât un computer din anii 1960, totuși, acest lucru se datorează progreselor tehnologice în hardware-ul computerului, mai degrabă decât unei calități inerente a algoritmului. Scopul teoriei complexității este de a cuantifica nevoile inerente de timp ale algoritmilor sau limitările fundamentale de timp pe care un algoritm le-ar impune oricărui computer. Acest lucru se realizează prin numărarea câte operații de bază sunt efectuate în timpul calculului. Aceste proceduri sunt denumite în mod obișnuit pași, deoarece se consideră că necesită timp constant pe o anumită mașină (adică, nu sunt afectate de cantitatea de intrare).
O altă resursă crucială este cantitatea de memorie de calculator necesară pentru a efectua algoritmi.
O altă resursă des folosită este cantitatea de operații aritmetice. În acest scenariu, este folosit termenul „complexitate aritmetică”. Complexitatea timpului este, în general, produsul complexității aritmetice cu un factor constant dacă se cunoaște o constrângere superioară a mărimii reprezentării binare a numerelor care apar în timpul unui calcul.
Mărimea numerelor întregi utilizate în timpul unui calcul nu este constrânsă pentru multe metode și este nerealist să presupunem că operațiile aritmetice necesită o perioadă fixă de timp. Ca rezultat, complexitatea timpului, cunoscută și ca complexitate de biți, poate fi semnificativ mai mare decât complexitatea aritmetică. Dificultatea aritmetică de a calcula determinantul unei matrice nn întregi, de exemplu, este O(n^3) pentru tehnicile standard (eliminarea gaussiană). Deoarece dimensiunea coeficienților s-ar putea extinde exponențial în timpul calculului, complexitatea de biți a acelorași metode este exponențială în n. Dacă aceste tehnici sunt utilizate împreună cu aritmetica multi-modulară, complexitatea biților poate fi redusă la O(n^4).
Complexitatea biților, în termeni formali, se referă la numărul de operații pe biți necesare pentru a rula un algoritm. Echivalează complexitatea temporală până la un factor constant în majoritatea paradigmelor de calcul. Numărul de operații pe cuvintele mașină necesare computerelor este proporțional cu complexitatea biților. Pentru modelele realiste de calcul, complexitatea timpului și complexitatea biților sunt astfel identice.
Resursa care este adesea luată în considerare în sortare și căutare este cantitatea de comparații de intrări. Dacă datele sunt bine aranjate, acesta este un bun indicator al complexității timpului.
Pe toate intrările potențiale, numărarea numărului de pași dintr-un algoritm este imposibilă. Deoarece complexitatea unei intrări crește odată cu dimensiunea ei, aceasta este reprezentată în mod obișnuit ca o funcție a mărimii intrării n (în biți), și astfel complexitatea este o funcție a lui n. Pentru intrări de aceeași dimensiune, totuși, complexitatea unui algoritm poate varia substanțial. Ca rezultat, o varietate de funcții de complexitate sunt utilizate în mod obișnuit.
Complexitatea cazului cel mai rău este suma tuturor complexității pentru toate intrările de dimensiune n, în timp ce complexitatea cazului mediu este suma tuturor complexității pentru toate intrările de dimensiune n (acest lucru are sens, deoarece numărul de intrări posibile de o dimensiune dată este finit). Atunci când termenul „complexitate” este folosit fără a fi definit în continuare, se ia în considerare complexitatea timpului din cel mai rău caz.
Cel mai rău caz și complexitatea cazului mediu sunt notoriu dificil de calculat corect. Mai mult, aceste valori exacte au o aplicație practică redusă, deoarece orice schimbare a mașinii sau a paradigmei de calcul ar varia ușor complexitatea. În plus, utilizarea resurselor nu este crucială pentru valorile mici ale lui n, prin urmare ușurința de implementare este adesea mai atrăgătoare decât complexitatea scăzută pentru n mic.
Din aceste motive, cea mai mare atenție este acordată comportamentului complexității pentru n mare, adică comportamentului său asimptotic pe măsură ce n se apropie de infinit. Ca rezultat, notația mare O este folosită în mod obișnuit pentru a indica complexitatea.
Modele computaționale
Alegerea unui model de calcul, care constă în precizarea operațiilor esențiale care se efectuează într-o unitate de timp, este crucială în determinarea complexității. Aceasta este uneori denumită o mașină Turing cu mai multe benzi atunci când paradigma de calcul nu este descrisă în mod specific.
Un model determinist de calcul este unul în care stările ulterioare ale mașinii și operațiile care trebuie efectuate sunt în întregime definite de starea anterioară. Funcțiile recursive, calculul lambda și mașinile Turing au fost primele modele deterministe. Mașinile cu acces aleatoriu (cunoscute și ca RAM-mașini) sunt o paradigmă populară pentru simularea computerelor din lumea reală.
Când modelul de calcul nu este definit, se presupune de obicei o mașină Turing cu mai multe benzi. Pe mașinile Turing cu mai multe benzi, complexitatea timpului este aceeași ca pe mașinile RAM pentru majoritatea algoritmilor, deși poate fi necesară o atenție considerabilă modului în care datele sunt stocate în memorie pentru a obține această echivalență.
Pot fi făcute diferite alegeri la unele etape ale calculului într-un model de calcul nedeterminist, cum ar fi mașinile Turing nedeterministe. În teoria complexității, toate opțiunile fezabile sunt luate în considerare în același timp, iar complexitatea timpului nedeterministă este cantitatea de timp necesară când se fac întotdeauna cele mai bune alegeri. Altfel spus, calculul se face simultan pe câte procesoare (identice) sunt necesare, iar timpul de calcul nedeterminist este timpul necesar primului procesor pentru a finaliza calculul. Acest paralelism poate fi folosit în calculul cuantic prin utilizarea stărilor încurcate suprapuse atunci când rulează algoritmi cuantici specializați, cum ar fi factorizarea lui Shor a numerelor întregi mici, de exemplu.
Chiar dacă un astfel de model de calcul nu este practicabil în prezent, el are o semnificație teoretică, în special în ceea ce privește problema P = NP, care întreabă dacă clasele de complexitate produse prin utilizarea „timpului polinom” și „timpului polinom nedeterminist” sunt cel puțin superioare. limitele sunt aceleași. Pe un computer determinist, simularea unui algoritm NP necesită „timp exponențial”. Dacă o sarcină poate fi rezolvată în timp polinomial pe un sistem nedeterminist, aceasta aparține clasei de dificultate NP. Dacă o problemă este în NP și nu este mai ușoară decât orice altă problemă NP, se spune că este NP-complet. Problema rucsacului, problema vânzătorului ambulant și problema satisfacabilității booleene sunt toate probleme combinatorii NP-complete. Cel mai cunoscut algoritm are o complexitate exponențială pentru toate aceste probleme. Dacă oricare dintre aceste probleme ar putea fi rezolvată în timp polinomial pe o mașină deterministă, atunci toate problemele NP ar putea fi rezolvate și în timp polinomial și ar fi stabilit P = NP. Începând cu 2017, se presupune pe scară largă că P NP, ceea ce implică că cele mai grave situații ale problemelor NP sunt fundamental dificil de rezolvat, adică durează mult mai mult decât orice interval de timp fezabil (decenii) având în vedere lungimi interesante de intrare.
Calcul paralel și distribuit
Calculul paralel și distribuit implică împărțirea procesării pe mai multe procesoare care funcționează toate în același timp. Distincția fundamentală între diferitele modele este metoda de trimitere a datelor între procesoare. Transmisia de date între procesoare este de obicei foarte rapidă în calculul paralel, în timp ce transferul de date între procesoare în calculul distribuit se face printr-o rețea și, prin urmare, este substanțial mai lent.
Un calcul pe N procesoare ia cel puțin câtul cu N din timpul necesar unui singur procesor. În realitate, deoarece unele subsarcini nu pot fi paralelizate și unele procesoare ar putea fi nevoite să aștepte un rezultat de la un alt procesor, această limită ideală teoretic nu va fi niciodată atinsă.
Problema cheie de complexitate este astfel de a dezvolta algoritmi astfel încât produsul timpului de calcul prin numărul de procesoare să fie cât mai aproape posibil de timpul necesar pentru a efectua același calcul pe un singur procesor.
Calcul cuantic
Un computer cuantic este un computer cu un model de calcul bazat pe mecanica cuantică. Teza Church-Turing este valabilă pentru calculatoarele cuantice, ceea ce sugerează că orice problemă pe care o poate rezolva un computer cuantic poate fi rezolvată și de o mașină Turing. Cu toate acestea, unele sarcini ar putea fi rezolvate teoretic folosind un computer cuantic, mai degrabă decât un computer clasic cu o complexitate temporală semnificativ mai mică. Deocamdată, acest lucru este strict teoretic, deoarece nimeni nu știe cum să dezvolte un computer cuantic practic.
Teoria complexității cuantice a fost creată pentru a investiga diferitele tipuri de probleme care pot fi rezolvate de computerele cuantice. Este utilizat în criptografia post-cuantică, care este procesul de creare a protocoalelor criptografice care sunt rezistente la atacurile computerizate cuantice.
Complexitatea problemei (limitele inferioare)
Infimumul complexităților algoritmilor care pot rezolva problema, inclusiv tehnicile nedescoperite, este complexitatea problemei. Ca urmare, complexitatea unei probleme este egală cu complexitatea oricărui algoritm care o rezolvă.
Ca rezultat, orice complexitate dată în notație mare O reprezintă o complexitate atât a algoritmului, cât și a problemei însoțitoare.
Pe de altă parte, obținerea unor limite inferioare netriviale privind complexitatea problemei este adesea dificilă și există puține strategii pentru a face acest lucru.
Pentru a rezolva majoritatea problemelor, toate datele de intrare trebuie citite, ceea ce necesită timp proporțional cu magnitudinea datelor. Ca rezultat, astfel de probleme au o complexitate cel puțin liniară sau, în notația omega mare, o complexitate de Ω(n).
Unele probleme, cum ar fi cele din algebra computerizată și geometria algebrică computațională, au soluții foarte mari. Deoarece ieșirea trebuie scrisă, complexitatea este constrânsă de dimensiunea maximă a ieșirii.
Numărul de comparații necesare pentru un algoritm de sortare are o limită inferioară neliniară a Ω(nlogn). Ca urmare, cei mai buni algoritmi de sortare sunt cei mai eficienți, deoarece complexitatea lor este O(nlogn). Faptul că există n! modalități de organizare a n lucruri duce la această limită inferioară. Pentru că fiecare comparație împarte această colecție de n! comenzile în două bucăți, numărul de N comparații necesare pentru a distinge toate ordinele trebuie să fie 2N > n!, implicând O(nlogn) prin formula lui Stirling.
Reducerea unei probleme la o altă problemă este o strategie comună pentru obținerea unor constrângeri de complexitate redusă.
Dezvoltarea algoritmului
Evaluarea complexității unui algoritm este un element important al procesului de proiectare, deoarece oferă informații utile despre performanța la care se poate aștepta.
Este o neînțelegere frecventă că, ca urmare a legii lui Moore, care prezice creșterea exponențială a puterii computerelor moderne, evaluarea complexității algoritmilor va deveni mai puțin relevantă. Acest lucru este incorect deoarece puterea crescută permite procesarea unor cantități masive de date (date mari). De exemplu, orice algoritm ar trebui să funcționeze bine în mai puțin de o secundă atunci când sortați alfabetic o listă de câteva sute de intrări, cum ar fi bibliografia unei cărți. Pe de altă parte, pentru un milion de intrări (de exemplu, numerele de telefon ale unui oraș mare), algoritmii de bază care necesită comparații O(n2) ar trebui să efectueze un trilion de comparații, ceea ce ar dura trei ore la o viteză de 10. milioane de comparații pe secundă. Sortarea rapidă și sortarea prin îmbinare, pe de altă parte, necesită doar comparații nlogn (ca complexitate medie a cazului pentru prima, ca complexitate a cazului cel mai rău pentru cea din urmă). Acest lucru produce aproximativ 30,000,000 de comparații pentru n = 1,000,000, ceea ce ar dura doar 3 secunde la 10 milioane de comparații pe secundă.
Ca rezultat, evaluarea complexității poate permite eliminarea multor algoritmi ineficienți înainte de implementare. Acest lucru poate fi folosit și pentru a ajusta algoritmi complecși fără a fi nevoie să testați toate variantele posibile. Studiul complexității permite concentrarea efortului pentru creșterea eficienței unei implementări prin determinarea celor mai costisitoare pași ai unui algoritm complex.
Pentru a vă familiariza în detaliu cu curriculumul de certificare, puteți extinde și analiza tabelul de mai jos.
Curriculum-ul de certificare EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification face referire la materiale didactice cu acces deschis într-o formă video. Procesul de învățare este împărțit într-o structură pas cu pas (programe -> lecții -> subiecte) care acoperă părți relevante ale curriculumului. De asemenea, se oferă consultanță nelimitată cu experți în domeniu.
Pentru detalii despre procedura de certificare verificați Abordare.
Materiale de lectură de sprijin pentru curriculum primar
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Materiale de lectură pentru curriculum secundar
O. Goldreich, Introducere în teoria complexității:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Materiale de citire a curriculumului de sprijin pe matematică discretă
J. Aspnes, Note despre matematica discretă:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Materiale de citire a curriculumului de susținere pe teoria graficelor
R. Diesel, Teoria grafurilor:
https://diestel-graph-theory.com/
Descărcați materialele pregătitoare complete pentru auto-învățare offline pentru programul EITC/IS/CCTF Computational Complexity Theory Fundamentals într-un fișier PDF
Materiale pregătitoare EITC/IS/CCTF – versiune standard
Materiale pregătitoare EITC/IS/CCTF – versiune extinsă cu întrebări de revizuire