EITC/IS/CCTF Computational Complexity Theory Fundamentals ir Eiropas IT sertifikācijas programma datorzinātņu pamatu teorētiskajiem aspektiem, kas ir arī klasiskās asimetriskās publiskās atslēgas kriptogrāfijas pamatā, ko plaši izmanto internetā.
EITC/IS/CCTF skaitļošanas sarežģītības teorijas pamati ietver teorētiskās zināšanas par datorzinātņu pamatiem un skaitļošanas modeļiem uz tādiem pamatjēdzieniem kā deterministiskas un nedeterministiskas galīgo stāvokļu mašīnas, regulāras valodas, bezkonteksta gramatikas un valodu teorija, automātu teorija, Tjūrings. Mašīnas, problēmu izlemjamība, rekursija, loģika un algoritmu sarežģītība pamata drošības lietojumprogrammām šādā struktūrā, kas ietver visaptverošu video didaktisko saturu kā atsauci uz šo EITC sertifikātu.
Algoritma skaitļošanas sarežģītība ir resursu apjoms, kas nepieciešams tā darbībai. Īpaša uzmanība tiek pievērsta laika un atmiņas resursiem. Problēmas sarežģītība tiek definēta kā labāko algoritmu sarežģītība tās risināšanai. Algoritmu analīze ir skaidri norādītu algoritmu sarežģītības izpēte, savukārt skaitļošanas sarežģītības teorija ir problēmu risinājumu sarežģītības izpēte ar pazīstamākajiem algoritmiem. Abas jomas ir savstarpēji saistītas, jo algoritma sarežģītība vienmēr ir galvenais ierobežojums problēmas sarežģītībai, ko tas atrisina. Turklāt, veidojot efektīvus algoritmus, bieži vien ir jāsalīdzina noteikta algoritma sarežģītība ar risināmās problēmas sarežģītību. Vairumā gadījumu vienīgā pieejamā informācija par problēmas sarežģītību ir tāda, ka tā ir mazāka par visefektīvāko zināmo paņēmienu sarežģītību. Rezultātā algoritma analīze un sarežģītības teorija lielā mērā pārklājas.
Sarežģītības teorijai ir liela nozīme ne tikai skaitļošanas modeļu pamatos kā datorzinātņu pamatā, bet arī klasiskās asimetriskās kriptogrāfijas (tā sauktās publiskās atslēgas kriptogrāfijas) pamatos, kas tiek plaši izplatīta mūsdienu tīklos, īpaši internetā. Publiskās atslēgas šifrēšana ir balstīta uz noteiktu asimetrisku matemātisko problēmu aprēķinu sarežģītību, piemēram, lielu skaitļu faktorizāciju tā primārajos faktoros (šī operācija ir sarežģīta problēma sarežģītības teorijas klasifikācijā, jo nav zināmi efektīvi klasiski algoritmi, ko atrisināt to ar resursu mērogošanu polinomi, nevis eksponenciāli, palielinoties problēmas ievades lielumam, kas ir pretstatā ļoti vienkāršai apgrieztajai darbībai, reizināšanai ar zināmiem galvenajiem faktoriem, lai iegūtu sākotnējo lielo skaitli). Izmantojot šo asimetriju publiskās atslēgas kriptogrāfijas arhitektūrā (definējot skaitļošanas asimetrisku attiecību starp publisko atslēgu, ko var viegli aprēķināt no privātās atslēgas, savukārt privāto atslēgu nevar viegli datorizēt no publiskās atslēgas, var publiski paziņo par publisko atslēgu un ļauj citām saziņas pusēm to izmantot asimetriskai datu šifrēšanai, ko pēc tam var atšifrēt tikai ar saistīto privāto atslēgu, kas nav pieejama trešajām pusēm, tādējādi padarot saziņu drošu).
Aprēķinu sarežģītības teorija tika izstrādāta galvenokārt, pamatojoties uz datorzinātņu un algoritmu pionieru, piemēram, Alana Tjūringa, sasniegumiem, kuru darbs bija ļoti svarīgs, lai izjauktu nacistiskās Vācijas Enigma šifru, kam bija liela nozīme sabiedroto uzvarēšanā Otrajā pasaules karā. Kriptanalīze, kuras mērķis bija izstrādāt un automatizēt datu (galvenokārt šifrētas komunikācijas) analīzes skaitļošanas procesus, lai atklātu slēpto informāciju, tika izmantota, lai uzlauztu kriptogrāfijas sistēmas un piekļūtu šifrētās komunikācijas saturam, kas parasti ir stratēģiski militāri svarīgi. Tā bija arī kriptanalīze, kas katalizēja pirmo moderno datoru izstrādi (kas sākotnēji tika piemēroti stratēģiskam koda laušanas mērķim). Pirms Britu kolosa (kas tiek uzskatīts par pirmo moderno elektronisko un programmu datoru) tika izveidota poļu "bumba" - elektroniska skaitļošanas ierīce, ko Marians Rejevskis izstrādāja, lai palīdzētu lauzt Enigma šifrus, un ko Polijas izlūkdienesti nodeva Lielbritānijai. sagrābtā vācu Enigma šifrēšanas iekārta pēc tam, kad 1939. gadā Polija iebruka Vācija. Uz šīs ierīces bāzes Alans Tjūrings izstrādāja tās modernāku līdzinieku, lai veiksmīgi pārtrauktu vācu šifrēto komunikāciju, kas vēlāk tika attīstīta modernos datoros.
Tā kā algoritma palaišanai nepieciešamo resursu apjoms mainās atkarībā no ievades lieluma, sarežģītību parasti izsaka kā funkciju f(n), kur n ir ievades lielums un f(n) ir vai nu sliktākā gadījuma sarežģītība ( maksimālais resursu apjoms, kas nepieciešams visās n izmēra ievadēs) vai gadījuma vidējā sarežģītība (resursu apjoma vidējais rādītājs visās n izmēra ievadēs). Nepieciešamo elementāro operāciju skaits n izmēra ievadei parasti tiek norādīts kā laika sarežģītība, kur tiek uzskatīts, ka elementārās darbības konkrētā datorā aizņem nemainīgu laiku un mainās tikai ar nemainīgu faktoru, ja tās tiek izpildītas citā mašīnā. Atmiņas apjoms, kas nepieciešams algoritmam n izmēra ievadei, ir zināms kā telpas sarežģītība.
Laiks ir visizplatītākais resurss. Ja terminu “sarežģītība” lieto bez apzīmētāja, tas parasti attiecas uz laika sarežģītību.
Tradicionālās laika vienības (sekundes, minūtes un tā tālāk) netiek izmantotas sarežģītības teorijā, jo tās ir pārāk atkarīgas no izvēlētā datora un tehnoloģiju attīstības. Piemēram, mūsdienās dators var izpildīt algoritmu daudz ātrāk nekā dators no 1960. gadiem, tomēr tas ir saistīts ar tehnoloģiskiem sasniegumiem datoru aparatūras jomā, nevis ar algoritma raksturīgo kvalitāti. Sarežģītības teorijas mērķis ir kvantitatīvi noteikt algoritmiem raksturīgās laika vajadzības vai pamata laika ierobežojumus, ko algoritms uzliktu jebkuram datoram. To panāk, saskaitot, cik pamatoperācijas tiek veiktas aprēķina laikā. Šīs procedūras parasti sauc par soļiem, jo tiek uzskatīts, ka konkrētajā mašīnā tās aizņem nemainīgu laiku (ti, tās neietekmē ievades apjoms).
Vēl viens svarīgs resurss ir datora atmiņas apjoms, kas nepieciešams algoritmu izpildei.
Vēl viens bieži izmantots resurss ir aritmētisko darbību apjoms. Šajā scenārijā tiek lietots termins “aritmētiskā sarežģītība”. Laika sarežģītība parasti ir aritmētiskās sarežģītības reizinājums ar konstantu koeficientu, ja ir zināms skaitļu binārā attēlojuma augšējais ierobežojums, kas rodas skaitļošanas laikā.
Aprēķinos izmantoto veselo skaitļu lielums daudzām metodēm nav ierobežots, un ir nereāli pieņemt, ka aritmētiskām darbībām ir vajadzīgs noteikts laiks. Rezultātā laika sarežģītība, kas pazīstama arī kā bitu sarežģītība, var būt ievērojami augstāka par aritmētisko sarežģītību. Piemēram, nn veselu skaitļu matricas determinanta aprēķināšanas aritmētiskās grūtības standarta metodēm (Gausa eliminācija) ir O(n^3). Tā kā aprēķina laikā koeficientu lielums var palielināties eksponenciāli, to pašu metožu bitu sarežģītība ir eksponenciāla n. Ja šīs metodes izmanto kopā ar vairāku moduļu aritmētiku, bitu sarežģītību var samazināt līdz O(n^4).
Bitu sarežģītība formāli attiecas uz operāciju skaitu ar bitiem, kas nepieciešami algoritma palaišanai. Tas ir vienāds ar laika sarežģītību līdz nemainīgam faktoram lielākajā daļā skaitļošanas paradigmu. Datoriem nepieciešamo operāciju skaits ar mašīnvārdiem ir proporcionāls bitu sarežģītībai. Tādējādi reālistiskiem aprēķinu modeļiem laika sarežģītība un bitu sarežģītība ir identiskas.
Resurss, kas bieži tiek ņemts vērā kārtošanā un meklēšanā, ir ierakstu salīdzināšanas apjoms. Ja dati ir labi sakārtoti, tas ir labs laika sarežģītības rādītājs.
Visām potenciālajām ieejām nav iespējams saskaitīt algoritma soļu skaitu. Tā kā ievades sarežģītība palielinās līdz ar tās lielumu, to parasti attēlo kā ievades lieluma n funkciju (bitos), un tāpēc sarežģītība ir n funkcija. Tomēr viena lieluma ievades gadījumā algoritma sarežģītība var ievērojami atšķirties. Tā rezultātā regulāri tiek izmantotas dažādas sarežģītības funkcijas.
Sliktākā gadījuma sarežģītība ir visu sarežģītības summa visām n izmēra ieejām, savukārt vidējā sarežģītības gadījuma sarežģītības summa ir visu sarežģītības summa visām n izmēra ieejām (tas ir loģiski, jo dotā izmēra iespējamo ievades datu skaits ir ierobežots). Ja terminu “sarežģītība” lieto bez sīkākas definīcijas, tiek ņemta vērā vissliktākā laika sarežģītība.
Sliktāko un vidējo sarežģītības gadījumu ir ļoti grūti pareizi aprēķināt. Turklāt šīm precīzajām vērtībām ir maz praktiskas pielietošanas, jo jebkuras izmaiņas mašīnā vai aprēķinu paradigmā nedaudz mainītu sarežģītību. Turklāt mazām n vērtībām resursu izmantošana nav svarīga, tāpēc ieviešanas vienkāršība bieži vien ir pievilcīgāka nekā maza sarežģītība maziem n.
Šo iemeslu dēļ lielākā uzmanība tiek pievērsta sarežģītības uzvedībai augsta n gadījumā, tas ir, tās asimptotiskajai uzvedībai, kad n tuvojas bezgalībai. Rezultātā, lai norādītu sarežģītību, parasti tiek izmantots liels O apzīmējums.
Skaitļošanas modeļi
Sarežģītības noteikšanā svarīga ir skaitļošanas modeļa izvēle, kas sastāv no būtisku darbību precizēšanas, kas tiek veiktas laika vienībā. To dažreiz sauc par daudzlentu Tjūringa mašīnu, ja skaitļošanas paradigma nav īpaši aprakstīta.
Deterministiskais aprēķinu modelis ir tāds, kurā mašīnas turpmākos stāvokļus un veicamās darbības pilnībā nosaka iepriekšējais stāvoklis. Rekursīvās funkcijas, lambda aprēķini un Tjūringa mašīnas bija pirmie deterministiskie modeļi. Brīvpiekļuves iekārtas (pazīstamas arī kā RAM-mašīnas) ir populāra paradigma reālās pasaules datoru simulēšanai.
Ja aprēķina modelis nav definēts, parasti tiek pieņemts daudzlentu Tjūringa mašīna. Vairāku lentu Tjūringa iekārtām laika sarežģītība ir tāda pati kā RAM mašīnām lielākajai daļai algoritmu, lai gan, lai sasniegtu šo līdzvērtību, var būt nepieciešama liela uzmanība tam, kā dati tiek saglabāti atmiņā.
Dažos skaitļošanas posmos var izdarīt dažādas izvēles nedeterministiskā skaitļošanas modelī, piemēram, nedeterministiskās Tjūringa mašīnās. Sarežģītības teorijā visas iespējamās iespējas tiek izskatītas vienlaikus, un nedeterministiskā laika sarežģītība ir laiks, kas nepieciešams, kad vienmēr tiek izdarīta labākā izvēle. Citiem vārdiem sakot, aprēķins tiek veikts vienlaicīgi ar tik daudziem (identiskiem) procesoriem, cik nepieciešams, un nedeterministiskais aprēķina laiks ir laiks, kas pirmajam procesoram nepieciešams, lai pabeigtu aprēķinu. Šo paralēlismu var izmantot kvantu skaitļošanā, izmantojot superpozētus sapinušos stāvokļus, kad tiek darbināti specializēti kvantu algoritmi, piemēram, Šora sīku veselu skaitļu faktorizācija.
Pat ja šāds aprēķinu modelis pašlaik nav praktiski izmantojams, tam ir teorētiska nozīme, jo īpaši saistībā ar P = NP problēmu, kas jautā, vai sarežģītības klases, kas iegūtas, izmantojot “polinoma laiku” un “nedeterministisko polinoma laiku” kā augstāko vērtību. robežas ir vienādas. Deterministiskā datorā, lai modelētu NP algoritmu, ir nepieciešams “eksponenciāls laiks”. Ja uzdevumu var atrisināt polinoma laikā nedeterministiskā sistēmā, tas pieder NP grūtības klasei. Ja problēma ir NP un nav vieglāka par jebkuru citu NP problēmu, tiek uzskatīts, ka tā ir NP pilnīga. Knapsack problēma, ceļojošā pārdevēja problēma un Būla apmierinātības problēma ir NP pilnīgas kombinatoriskas problēmas. Vispazīstamākajam algoritmam ir eksponenciāla sarežģītība visām šīm problēmām. Ja kādu no šiem jautājumiem varētu atrisināt polinoma laikā deterministiskā mašīnā, tad visas NP problēmas varētu atrisināt arī polinoma laikā, un tiktu izveidots P = NP. No 2017. gada plaši tiek pieņemts, ka P NP, kas nozīmē, ka NP problēmu sliktākās situācijas ir fundamentāli grūti atrisināmas, ti, tās aizņem daudz ilgāku laiku nekā jebkurš iespējamais laika posms (desmitgades), ņemot vērā interesanto ievades garumu.
Paralēlā un sadalītā skaitļošana
Paralēlā un sadalītā skaitļošana ietver apstrādes sadalīšanu vairākos procesoros, kuri visi darbojas vienlaikus. Galvenā atšķirība starp dažādiem modeļiem ir datu nosūtīšanas metode starp procesoriem. Paralēlās skaitļošanas gadījumā datu pārraide starp procesoriem parasti ir ļoti ātra, turpretim datu pārsūtīšana starp procesoriem izkliedētā skaitļošanā notiek tīklā un tādējādi ir ievērojami lēnāka.
N procesoru aprēķins ņem vismaz daļu ar N no laika, kas nepieciešams vienam procesoram. Patiesībā, tā kā dažus apakšuzdevumus nevar paralēli un dažiem procesoriem var būt jāgaida rezultāts no cita procesora, šī teorētiski ideālā robeža nekad netiks sasniegta.
Tādējādi galvenais sarežģītības jautājums ir izstrādāt algoritmus, lai skaitļošanas laika reizinājums ar procesoru skaitu būtu pēc iespējas tuvāks laikam, kas nepieciešams, lai veiktu vienu un to pašu aprēķinu ar vienu procesoru.
Kvantu aprēķins
Kvantu dators ir dators ar uz kvantu mehāniku balstītu skaitļošanas modeli. Church–Tjūringa tēze attiecas uz kvantu datoriem, kas nozīmē, ka jebkuru problēmu, ko var atrisināt kvantu dators, var atrisināt arī Tjūringa mašīna. Tomēr dažus uzdevumus teorētiski var atrisināt, izmantojot kvantu datoru, nevis klasisko datoru ar ievērojami zemāku laika sarežģītību. Pagaidām tas ir stingri teorētiski, jo neviens nezina, kā izstrādāt praktisku kvantu datoru.
Kvantu sarežģītības teorija tika izveidota, lai izpētītu dažāda veida problēmas, kuras var atrisināt ar kvantu datoriem. To izmanto pēckvantu kriptogrāfijā, kas ir kriptogrāfijas protokolu izveides process, kas ir izturīgs pret kvantu datoru uzbrukumiem.
Problēmas sarežģītība (apakšējās robežas)
Algoritmu sarežģītība, kas var atrisināt problēmu, ieskaitot neatklātas metodes, ir problēmas sarežģītība. Rezultātā problēmas sarežģītība ir vienāda ar jebkura algoritma, kas to atrisina, sarežģītību.
Rezultātā jebkura sarežģītība, kas dota lielā O apzīmējumā, atspoguļo gan algoritma, gan saistītās problēmas sarežģītību.
No otras puses, bieži vien ir grūti iegūt netriviālas problēmas sarežģītības zemākās robežas, un ir maz stratēģiju, kā to izdarīt.
Lai atrisinātu lielāko daļu problēmu, ir jānolasa visi ievades dati, kas aizņem laiku proporcionāli datu apjomam. Rezultātā šādām problēmām ir vismaz lineāra sarežģītība vai, lielajā omega apzīmējumā, sarežģītība Ω (n).
Dažām problēmām, piemēram, datoralgebrai un skaitļošanas algebriskajai ģeometrijai, ir ļoti lieli risinājumi. Tā kā izvade ir jāraksta, sarežģītību ierobežo izvades maksimālais lielums.
Salīdzinājumu skaitam, kas nepieciešams šķirošanas algoritmam, ir nelineāra apakšējā robeža Ω(nlogn). Rezultātā labākie šķirošanas algoritmi ir visefektīvākie, jo to sarežģītība ir O(nlogn). Tas, ka ir n! veidi, kā organizēt n lietas, noved pie šīs apakšējās robežas. Jo katrs salīdzinājums sadala šo n kolekciju! pasūtījumus divās daļās, N salīdzinājumu skaitam, kas nepieciešams, lai atšķirtu visas kārtas, ir jābūt 2N > n!, kas nozīmē O(nlogn) pēc Stērlinga formulas.
Problēmas samazināšana par citu problēmu ir izplatīta stratēģija samazinātu sarežģītības ierobežojumu iegūšanai.
Algoritmu izstrāde
Algoritma sarežģītības novērtēšana ir svarīgs projektēšanas procesa elements, jo tas sniedz noderīgu informāciju par gaidāmo veiktspēju.
Bieža ir pārpratums, ka Mūra likuma rezultātā, kas paredz mūsdienu datoru jaudas eksponenciālu pieaugumu, algoritmu sarežģītības novērtēšana kļūs mazāk aktuāla. Tas nav pareizi, jo palielinātā jauda ļauj apstrādāt milzīgus datu apjomus (lielos datus). Piemēram, jebkuram algoritmam ir jādarbojas labi mazāk nekā sekundē, ja alfabētiskā secībā kārtojat sarakstu ar dažiem simtiem ierakstu, piemēram, grāmatas bibliogrāfiju. No otras puses, miljonam ierakstu (piemēram, lielas pilsētas tālruņu numuriem) pamata algoritmiem, kuriem nepieciešama O(n2) salīdzināšana, būtu jāveic triljons salīdzinājumu, kas aizņemtu trīs stundas ar ātrumu 10 miljons salīdzinājumu sekundē. No otras puses, ātrās kārtošanas un sapludināšanas kārtošanai ir nepieciešami tikai nlogn salīdzinājumi (kā vidējā gadījuma sarežģītība pirmajam, kā sliktākā gadījuma sarežģītība otrajam). Tādējādi tiek iegūti aptuveni 30,000,000 1,000,000 3 salīdzinājumu ar n = 10 XNUMX XNUMX, kas aizņemtu tikai XNUMX sekundes ar XNUMX miljoniem salīdzinājumu sekundē.
Rezultātā sarežģītības novērtēšana var ļaut pirms ieviešanas novērst daudzus neefektīvus algoritmus. To var izmantot arī sarežģītu algoritmu precizēšanai, nepārbaudot visus iespējamos variantus. Sarežģītības izpēte ļauj koncentrēt pūles realizācijas efektivitātes paaugstināšanai, nosakot sarežģītā algoritma dārgākos soļus.
Lai detalizēti iepazītos ar sertifikācijas mācību programmu, varat paplašināt un analizēt zemāk esošo tabulu.
EITC/IS/CCTF skaitļošanas sarežģītības teorijas pamatu sertifikācijas mācību programmā ir atsauces uz brīvpiekļuves didaktiskajiem materiāliem video formātā. Mācību process ir sadalīts pakāpeniskā struktūrā (programmas -> nodarbības -> tēmas), kas aptver attiecīgās mācību programmas daļas. Tiek nodrošinātas arī neierobežotas konsultācijas ar domēna ekspertiem.
Lai iegūtu sīkāku informāciju par sertifikācijas procedūru, pārbaudiet Kā tas darbojas.
Pamata atbalsta mācību programmas lasāmmateriāli
S. Arora, B. Baraks, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Vidējās atbalsta mācību programmas lasāmmateriāli
O. Goldreihs, Ievads sarežģītības teorijā:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Atbalsta mācību programmas lasāmmateriāli par diskrēto matemātiku
J. Aspnes, Piezīmes par diskrēto matemātiku:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Atbalsta mācību programmas lasāmmateriāli par grafu teoriju
R. Diestels, Grafu teorija:
https://diestel-graph-theory.com/
Lejupielādējiet pilnus bezsaistes pašmācības sagatavošanas materiālus programmai EITC/IS/CCTF Computational Complexity Theory Fundamentals PDF failā
EITC/IS/CCTF sagatavošanas materiāli – standarta versija
EITC/IS/CCTF sagatavošanas materiāli – paplašinātā versija ar pārskata jautājumiem