sorteringsalgoritmer

sortering er det mest studerede koncept inden for Datalogi. Ideen er at arrangere elementerne i en liste i en bestemt rækkefølge. Selvom hvert større programmeringssprog har indbyggede sorteringsbiblioteker, er det praktisk, hvis du ved, hvordan de fungerer. Afhængigt af krav kan du bruge nogen af disse.

• Flet sortering
• hurtig sortering
• Bucket sortering
• Heap sortering
• Tællesortering

endnu vigtigere skal man vide, hvornår og hvor man skal bruge dem. Nogle eksempler, hvor du kan finde direkte anvendelse af sorteringsteknikker omfatter:

• sortering efter pris, popularitet osv i e-handel hjemmesider

søgealgoritmer

binær søgning (i lineære datastrukturer)

binær søgning bruges til at udføre en meget effektiv søgning på sorteret datasæt. Tidskompleksiteten er O (log2N). Ideen er at gentagne gange opdele i halvdelen af den del af listen, der kan indeholde varen, indtil vi indsnævrer den til en mulig vare. Nogle applikationer er:

• når du søger efter et navn på sangen i en sorteret liste over sange, udfører den binær søgning og strengtilpasning for hurtigt at returnere resultaterne.
• bruges til at debugge i git gennem git bisect

Dybde/Bredde første søgning (I graf datastrukturer)

DFS og BFS er træ / graf gennemkører og søger datastrukturer. Vi ville ikke gå dybt ind i, hvordan DFS/BFS fungerer, men vil se, hvordan de er forskellige gennem følgende animation.

applikationer:

• brugt af søgemaskiner til gennemsøgning
• brugt i kunstig intelligens til at bygge bots, for eksempel en skakbot
• Find korteste vej mellem to byer på et kort og mange andre sådanne applikationer

Hashing

hash-opslag er i øjeblikket den mest anvendte teknik til at finde passende data efter nøgle eller id. Vi får adgang til data ved hjælp af dets indeks. Tidligere var vi afhængige af sortering + binær søgning for at se efter indeks, mens vi nu bruger hashing.

datastrukturen kaldes Hash-kort eller Hash-tabel eller ordbog, der kortlægger nøgler til værdier effektivt. Vi kan udføre værdiopslag ved hjælp af nøgler. Ideen er at bruge en passende hash-funktion, der gør nøglen – > værdikortlægning. At vælge en god hash-funktion afhænger af scenariet.

applikationer:

• i routere, for at gemme IP-adresse – > Stipar til routingmekanismer
• for at udføre kontrollen, om der allerede findes en værdi på en liste. Lineær søgning ville være dyrt. Vi kan også bruge Sæt datastruktur til denne operation.

dynamisk programmering

dynamisk programmering (DP) er en metode til løsning af et komplekst problem ved at opdele det i enklere underproblemer. Vi løser delproblemerne, husker deres resultater og bruger dem, vi gør vores måde at løse det komplekse problem hurtigt.

*skriver ned “1+1+1+1+1+1+1+1 =” på et ark papir * Hvad er det lig med?
*tæller * otte!
* skriver ned en anden “1 +” til venstre* Hvad med det?
* hurtigt * ni!
Hvordan vidste du, at det var ni så hurtigt?
du har lige tilføjet en mere
så du behøvede ikke at fortælle, fordi du huskede, at der var otte! Dynamisk programmering er bare en fancy måde at sige ‘huske ting for at spare tid senere’

applikationer:

• Der er mange dp-algoritmer og applikationer, men jeg vil navngive en og blæse dig væk.

Eksponentiering ved kvadrering

sig, at du vil beregne 232. Normalt ville vi gentage 32 gange og finde resultatet. Hvad hvis jeg fortalte dig, at det kan gøres i 5 iterationer?

Eksponentiering ved kvadrering eller binær eksponentiering er en generel metode til hurtig beregning af store positive heltalskræfter af et tal i o(log2N). Ikke kun dette, metoden bruges også til beregning af beføjelser af polynomer og firkantede matricer.

ansøgning:

• beregning af store kræfter af et tal kræves for det meste i RSA-kryptering. RSA bruger også modulær aritmetik sammen med binær eksponentiering.

String Matching and Parsing

mønstertilpasning / søgning er et af de vigtigste problemer inden for Datalogi. Der har været en masse forskning om emnet, men vi vil hverve kun to grundlæggende fornødenheder til enhver programmør.

KMP algoritme (String Matching)

Knuth-Morris-Pratt algoritme bruges i tilfælde, hvor vi skal matche et kort mønster i en lang streng. For eksempel, når vi Ctrl+F et nøgleord i et dokument, udfører vi mønstertilpasning i hele dokumentet.

Regulært udtryk (Strengparsing)

mange gange skal vi validere en streng ved at analysere over en foruddefineret begrænsning. Det er meget brugt i Internet udvikling til URL parsing og matching.

Primalitetstestalgoritmer

der er deterministiske og sandsynlige måder at bestemme, om et givet tal er primært eller ej. Vi vil se både deterministiske og probabilistiske (ikke-deterministiske) måder.

Sieve of Eratosthenes (deterministisk)

Hvis vi har en vis grænse for antallet af tal, siger Bestem alle primtal inden for området 100 til 1000, så er Sieve en vej at gå. Længden af rækkevidde er en afgørende faktor, fordi vi er nødt til at afsætte en vis mængde hukommelse i henhold til rækkevidde.

for et hvilket som helst tal n, trinvis test op til deterministisk(n)

Hvis du vil kontrollere for få tal, der er tyndt spredt over en lang rækkevidde (sige 1 til 1012), kan Sieve ikke tildele nok hukommelse. Du kan kontrollere for hvert nummer n ved kun at krydse op til KVRT(n) og udføre en delbarhedskontrol på n.

Fermat primalitetstest og Miller–Rabin primalitetstest (begge er ikke-deterministiske)

begge disse er komposit test. Hvis et tal viser sig at være sammensat, så er det sikkert ikke et primtal. Miller-Rabin er en mere sofistikeret end Fermats.faktisk har Miller-Rabin også en deterministisk variant, men så er det et spil af handel mellem tidskompleksitet og nøjagtighed af algoritmen.

ansøgning:

• den vigtigste anvendelse af primtal er i kryptografi. Mere præcist bruges de i kryptering og dekryptering i RSA-algoritme, som var den allerførste implementering af offentlige Nøglekryptosystemer
• en anden anvendelse er i hashfunktioner, der bruges i Hash-tabeller