×
1 Vælg EITC/EITCA-certifikater
2 Lær og tag online eksamener
3 Få dine IT-kompetencer certificeret

Bekræft dine it-færdigheder og -kompetencer under den europæiske it-certificeringsramme fra hvor som helst i verden, helt online.

EITCA Academy

Standard for attestering af digitale færdigheder af European IT Certification Institute med det formål at understøtte udviklingen af ​​det digitale samfund

Log ind på din konto af enten dit brugernavn eller e-mail-adresse

OPRET EN KONTO Glemt din adgangskode?

FORGÅ DIN DETALJER?

AAH, vent, jeg HUSK NU!

OPRET EN KONTO

HAR DU ALLEREDE EN BRUGER?
EUROPÆISKE INFORMATIONSTEKNOLOGIER CERTIFICERINGSAKADEMI - AT TESTE DINE FAGLIGE DIGITALE FÆRDIGHEDER
  • TILMELD DIG
  • LOGIN
  • INFO

EITCA Academy

EITCA Academy

Det Europæiske Institut for Certifikation af Informationsteknologi - EITCI ASBL

Certificeringsmyndighed

EITCI Instituttet

Bruxelles, Den Europæiske Union

Regulerende europæisk it-certificering (EITC) -standard til støtte for it-professionalisme og det digitale samfund

  • CERTIFIKATER
    • EITCA-AKADEMIER
      • EITCA ACADEMIES-KATALOG<
      • EITCA/CG COMPUTER GRAFIK
      • EITCA/ER INFORMATIONSSIKKERHED
      • EITCA/BI FORRETNINGSINFORMATION
      • EITCA/KC Nøglekompetencer
      • EITCA/EG E-REGERING
      • EITCA/WD WEB UDVIKLING
      • EITCA/AI KUNSTIG INTELLIGENCE
    • EITC-CERTIFIKATER
      • EITC CERTIFIKATER KATALOG<
      • COMPUTERGRAFIKCERTIFIKATER
      • WEB-DESIGNCERTIFIKATER
      • 3D-DESIGNCERTIFIKATER
      • KONTOR DETS CERTIFIKATER
      • BITCOIN BLOCKCHAIN ​​CERTIFIKAT
      • WORDPRESS CERTIFIKAT
      • CLOUD PLATFORM CERTIFIKATNY
    • EITC-CERTIFIKATER
      • INTERNETCERTIFIKATER
      • KRYPTOGRAFICERTIFIKATER
      • FORRETNINGSDET CERTIFIKATER
      • TELEVERKSCERTIFIKATER
      • PROGRAMMERINGSCERTIFIKATER
      • DIGITAL PORTRETSCERTIFIKAT
      • WEBUDVIKLINGSCERTIFIKATER
      • DYPE LÆRINGSCERTIFIKATERNY
    • CERTIFIKATER FOR
      • EU OFFENTLIG ADMINISTRATION
      • LÆRERE OG UDDANNELSE
      • DET SIKKERHEDSFORLIGERE
      • GRAFIK DESIGNERE & KUNSTNERE
      • BUSINESSMEN OG MANAGERS
      • BLOCKCHAIN-UDVIKLERE
      • WEB-UDVIKLERE
      • CLOUD AI EKSPERTERNY
  • SPECIAL
  • TILSKUD
  • SÅDAN VIRKER DET
  •   IT ID
  • OM
  • KONTAKT
  • MIN BESTILLING
    Din nuværende ordre er tom.
EITCIINSTITUTE
CERTIFIED

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.

Primært understøttende læsemateriale

S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf

Sekundært understøttende læsemateriale

O. Goldreich, Introduktion til kompleksitetsteori:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html

Understøttende læsemateriale om diskret matematik

J. Aspnes, noter om diskret matematik:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Understøttende læsemateriale om grafteori

R. Diestel, grafteori:
https://diestel-graph-theory.com/

Certificeringsprogram Curriculum

Udvid alle
Introduktion 1 emne
Udvid
Lektionsindhold
0% Komplet 0/1 trin
Teoretisk introduktion
Endelige maskiner 6 emner
Udvid
Lektionsindhold
0% Komplet 0/6 trin
Introduktion til endelige maskiner
Eksempler på endelige maskiner
Operationer på regelmæssige sprog
Introduktion til ikke-bestemmende endelige statsmaskiner
Formel definition af ikke-bestemmende endelige statsmaskiner
Ækvivalens mellem deterministiske og ikke-deterministiske FSM'er
Regelmæssige sprog 5 emner
Udvid
Lektionsindhold
0% Komplet 0/5 trin
Lukning af regelmæssige operationer
Regelmæssige udtryk
Ækvivalens mellem regulære udtryk og regulære sprog
Pumping Lemma for regulære sprog
Resumé af regelmæssige sprog
Kontekstfri grammatik og sprog 4 emner
Udvid
Lektionsindhold
0% Komplet 0/4 trin
Introduktion til kontekstfri grammatik og sprog
Eksempler på kontekstfri grammatik
Typer af kontekstfri sprog
Fakta om kontekstfrie sprog
Kontekstfølsomme sprog 3 emner
Udvid
Lektionsindhold
0% Komplet 0/3 trin
Chomsky normal form
Chomsky Hierarki og kontekstfølsomme sprog
Pumpelemmet for CFL'er
Pushdown-automatik 3 emner
Udvid
Lektionsindhold
0% Komplet 0/3 trin
PDA'er: Automatisk pushdown
Ækvivalens mellem CFG'er og PDA'er
Konklusioner fra ækvivalens mellem CFG'er og PDA'er
Turing-maskiner 9 emner
Udvid
Lektionsindhold
0% Komplet 0/9 trin
Introduktion til Turing Machines
Eksempler på Turing Machine
Definition af TM'er og relaterede sprogklasser
Church-Turing-afhandlingen
Turing Machine programmeringsteknikker
Multitape Turing-maskiner
Ubestemmelse i Turing-maskiner
Turing-maskiner som problemløsere
Tællere
afgørbarhed 17 emner
Udvid
Lektionsindhold
0% Komplet 0/17 trin
Beslutbarhed og afgørelige problemer
Flere afgørelige problemer for DFA'er
Problemer vedrørende kontekstfrie sprog
Universal Turing Machine
Uendelig - tællelig og utallig
Sprog, der ikke kan genkendes fra Turing
Ubeslutsomheden af ​​stopproblemet
Sprog, der ikke kan genkendes fra Turing
Reducerbarhed - en teknik til at bevise undecidability
Halting Problem - et bevis ved reduktion
Accepterer en TM nogen streng?
Beregnelige funktioner
Ækvivalens mellem Turing Machines
Reduktion af et sprog til et andet
Postkorrespondanceproblemet
Ubeslutelighed af PCP
Lineær bundet automat
rekursion 5 emner
Udvid
Lektionsindhold
0% Komplet 0/5 trin
Program, der udskriver sig selv
Turing Machine, der skriver en beskrivelse af sig selv
Rekursionssætning
Resultater fra rekursionssætningen
Fixed Point Theorem
Logic 4 emner
Udvid
Lektionsindhold
0% Komplet 0/4 trin
Førsteordens prædikatlogik - oversigt
Sandhed, mening og bevis
Ægte udsagn og beviselige udsagn
Godels ufuldstændighedssætning
Kompleksitet 8 emner
Udvid
Lektionsindhold
0% Komplet 0/8 trin
Tidskompleksitet og stor-O notation
Beregner en algoritmes kørselstid
Tidskompleksitet med forskellige beregningsmodeller
Tidskompleksitetsklasser P og NP
Definition af NP og polynom verificerbarhed
NP-fuldstændighed
Bevis for, at SAT er NP komplet
Rumkompleksitetsklasser
EITC/IS/CCTF Computational Complexity Theory Fundamentals
  • Tweet

Om admin

Forside » Min profil

Certificeringscenter

Program Hjem Udvid alle
Introduktion
1 emne
Teoretisk introduktion
Endelige maskiner
6 emner
Introduktion til endelige maskiner
Eksempler på endelige maskiner
Operationer på regelmæssige sprog
Introduktion til ikke-bestemmende endelige statsmaskiner
Formel definition af ikke-bestemmende endelige statsmaskiner
Ækvivalens mellem deterministiske og ikke-deterministiske FSM'er
Regelmæssige sprog
5 emner
Lukning af regelmæssige operationer
Regelmæssige udtryk
Ækvivalens mellem regulære udtryk og regulære sprog
Pumping Lemma for regulære sprog
Resumé af regelmæssige sprog
Kontekstfri grammatik og sprog
4 emner
Introduktion til kontekstfri grammatik og sprog
Eksempler på kontekstfri grammatik
Typer af kontekstfri sprog
Fakta om kontekstfrie sprog
Kontekstfølsomme sprog
3 emner
Chomsky normal form
Chomsky Hierarki og kontekstfølsomme sprog
Pumpelemmet for CFL'er
Pushdown-automatik
3 emner
PDA'er: Automatisk pushdown
Ækvivalens mellem CFG'er og PDA'er
Konklusioner fra ækvivalens mellem CFG'er og PDA'er
Turing-maskiner
9 emner
Introduktion til Turing Machines
Eksempler på Turing Machine
Definition af TM'er og relaterede sprogklasser
Church-Turing-afhandlingen
Turing Machine programmeringsteknikker
Multitape Turing-maskiner
Ubestemmelse i Turing-maskiner
Turing-maskiner som problemløsere
Tællere
afgørbarhed
17 emner
Beslutbarhed og afgørelige problemer
Flere afgørelige problemer for DFA'er
Problemer vedrørende kontekstfrie sprog
Universal Turing Machine
Uendelig - tællelig og utallig
Sprog, der ikke kan genkendes fra Turing
Ubeslutsomheden af ​​stopproblemet
Sprog, der ikke kan genkendes fra Turing
Reducerbarhed - en teknik til at bevise undecidability
Halting Problem - et bevis ved reduktion
Accepterer en TM nogen streng?
Beregnelige funktioner
Ækvivalens mellem Turing Machines
Reduktion af et sprog til et andet
Postkorrespondanceproblemet
Ubeslutelighed af PCP
Lineær bundet automat
rekursion
5 emner
Program, der udskriver sig selv
Turing Machine, der skriver en beskrivelse af sig selv
Rekursionssætning
Resultater fra rekursionssætningen
Fixed Point Theorem
Logic
4 emner
Førsteordens prædikatlogik - oversigt
Sandhed, mening og bevis
Ægte udsagn og beviselige udsagn
Godels ufuldstændighedssætning
Kompleksitet
8 emner
Tidskompleksitet og stor-O notation
Beregner en algoritmes kørselstid
Tidskompleksitet med forskellige beregningsmodeller
Tidskompleksitetsklasser P og NP
Definition af NP og polynom verificerbarhed
NP-fuldstændighed
Bevis for, at SAT er NP komplet
Rumkompleksitetsklasser
EITC/IS/CCTF Computational Complexity Theory Fundamentals

BRUGERMENU

  • Mine reservationer

CERTIFIKATKATEGORI

  • EITC-certificering (105)
  • EITCA-certificering (9)

Hvad leder du efter?

  • Introduktion
  • Hvordan det virker?
  • EITCA akademier
  • EITCI DSJC-tilskud
  • Fuldt EITC-katalog
  • Din ordre
  • Udvalgt
  •   IT ID
  • Om
  • Kontakt

    EITCA Akademiets administrative kontor

    Europæisk IT-certificeringsinstitut
    Bruxelles, Belgien, Den Europæiske Union

    EITC/EITCA Certification Authority
    Gældende europæisk it-certificeringsstandard
    Adgang kontaktformular eller opkald + 32 25887351

    13 dage siden #EITC/WD/WPF WordPress Fundamentals-certifikat (en del af #EITCA/WD) attesterer ekspertise i #WordPress CMS, i... https://t.co/A2jjXPeKgj
    Følg @EITCI

    Oversæt automatisk til dit sprog

    Vilkår & Betingelser | Privatlivspolitik
    Følg @EITCI
    EITCA Academy
    • EITCA Academy på sociale medier
    EITCA Academy


    © 2008-2023  Europæisk IT-certificeringsinstitut
    Bruxelles, Belgien, Den Europæiske Union

    TOP
    Chat med support
    Chat med support
    Spørgsmål, tvivl, problemer? Vi er her for at hjælpe dig!
    Afslut chat
    Tilslutning ...
    Har du et spørgsmål? Spørg os!
    Har du et spørgsmål? Spørg os!
    :
    :
    :
    Send
    Har du et spørgsmål? Spørg os!
    :
    :
    Start chat
    Chat-sessionen er afsluttet. Tak skal du have!
    Bedøm den support, du har modtaget.
    god Bad