några dollar. Idag ser vi vad de gör och var de används med enklaste exempel. Denna lista är upprättad med tanke på deras användning i konkurrenskraftig programmering och nuvarande utvecklingspraxis.

sorteringsalgoritmer

sortering är det mest studerade konceptet inom datavetenskap. Tanken är att ordna objekten i en lista i en viss ordning. Även om varje större programmeringsspråk har inbyggda sorteringsbibliotek, är det praktiskt om du vet hur de fungerar. Beroende på krav kanske du vill använda någon av dessa.

• sammanfoga Sortera
• snabb sortering
• Bucket Sortera
• Heap Sortera
• räkna Sortera

ännu viktigare bör man veta när och var man ska använda dem. Några exempel där du kan hitta direkt tillämpning av sorteringstekniker inkluderar:

• sortering efter pris, popularitet etc i e-handelswebbplatser

sökalgoritmer

binär sökning (i linjära datastrukturer)

binär sökning används för att utföra en mycket effektiv sökning på sorterade dataset. Tidskomplexiteten är O (log2N). Tanken är att upprepade gånger dela upp i hälften av den del av listan som kan innehålla objektet tills vi begränsar det till ett möjligt objekt. Vissa applikationer är:

• när du söker efter ett namn på låten i en sorterad lista med låtar, utför den binär sökning och strängmatchning för att snabbt returnera resultaten.
• används för att felsöka i git genom git bisect

djup/bredd första sökning (i Grafdatastrukturer)

DFS och BFS är träd / graf som passerar och söker datastrukturer. Vi skulle inte gå djupt in i hur DFS / BFS fungerar men kommer att se hur de skiljer sig genom följande animering.

applikationer:

• används av sökmotorer för webbkrypning
• används i artificiell intelligens för att bygga bots, till exempel en schackbot
• hitta kortaste vägen mellan två städer i en karta och många andra sådana applikationer

Hashing

hash lookup är för närvarande den mest använda tekniken för att hitta lämpliga data med nyckel eller ID. Vi får tillgång till data genom dess index. Tidigare förlitade vi oss på sortering + binär sökning för att leta efter index medan vi nu använder hashing.

datastrukturen kallas Hash-Map eller Hash-tabell eller ordbok som kartlägger nycklar till värden effektivt. Vi kan utföra värdeuppslag med nycklar. Tanken är att använda en lämplig hashfunktion som gör nyckeln- > Värdemappning. Att välja en bra hashfunktion beror på scenariot.

applikationer:

• i routrar, för att lagra IP-adress – > Path pair för routingmekanismer
• för att utföra kontrollen om ett värde redan finns i en lista. Linjär sökning skulle vara dyrt. Vi kan också använda Set data structure för denna operation.

dynamisk programmering

dynamisk programmering (DP) är en metod för att lösa ett komplext problem genom att bryta ner det i enklare delproblem. Vi löser delproblemen, kommer ihåg deras resultat och använder dem vi gör vårt sätt att lösa det komplexa problemet, snabbt.

*skriver ner ”1+1+1+1+1+1+1+1 =” på ett pappersark * Vad är det lika med?
*räkna * åtta!
* skriver ner en annan ”1 +” till vänster * vad sägs om det?
* snabbt * nio!
Hur visste du att det var nio så snabbt?
Du har precis lagt till en mer
så du behövde inte berätta för att du kom ihåg att det fanns åtta! Dynamisk programmering är bara ett fint sätt att säga ’minnas saker att spara tid senare’

program:

• Det finns många DP algoritmer och applikationer men jag skulle nämna en och blåsa bort dig, Duckworth-Lewis metod i cricket.

exponentiering genom kvadrering

säg att du vill beräkna 232. Normalt skulle vi iterera 32 gånger och hitta resultatet. Vad händer om jag sa att det kan göras i 5 iterationer?

exponentiering genom kvadrering eller Binär exponentiering är en allmän metod för snabb beräkning av stora positiva heltalskrafter för ett tal I O(log2N). Inte bara detta, metoden används också för beräkning av polynomers och kvadratiska matriser.

ansökan:

• beräkning av stora krafter av ett tal krävs mestadels i RSA-kryptering. RSA använder också modulär aritmetik tillsammans med binär exponentiering.

Strängmatchning och tolkning

mönstermatchning / sökning är ett av de viktigaste problemen inom datavetenskap. Det har varit mycket forskning om ämnet men vi kommer bara att anlita två grundläggande nödvändigheter för någon programmerare.

KMP-algoritm (Strängmatchning)

Knuth-Morris-Pratt-algoritm används i fall där vi måste matcha ett kort mönster i en lång sträng. När vi till exempel Ctrl+F ett nyckelord i ett dokument utför vi mönstermatchning i hela dokumentet.

Reguljärt uttryck (String Parsing)

många gånger måste vi validera en sträng genom att analysera över en fördefinierad begränsning. Det används starkt i webbutveckling för URL-tolkning och matchning.

Primality Testing Algorithms

det finns deterministiska och probabilistiska sätt att bestämma om ett givet tal är primärt eller inte. Vi ser både deterministiska och probabilistiska (nondeterministiska) sätt.

sikt av Eratosthenes (deterministiska)

Om vi har viss gräns för antalet tal, säg bestämma alla primtal inom intervallet 100 till 1000 så är sikt ett sätt att gå. Längden på intervallet är en avgörande faktor, eftersom vi måste allokera viss mängd minne enligt intervallet.

för valfritt nummer n, stegvis testning upp till sqrt (n) (deterministisk)

om du vill kontrollera några siffror som är glest spridda över ett långt intervall (säg 1 till 1012), kommer Sieve inte att kunna allokera tillräckligt med minne. Du kan kontrollera för varje nummer n genom att bara korsa upp till sqrt (n) och utföra en delbarhetskontroll på n.

Fermat primality test och Miller–Rabin primality test (båda är nondeterministiska)

båda dessa är kompositionstester. Om ett tal har visat sig vara sammansatt, så är det säkert inte ett primtal. Miller-Rabin är en mer sofistikerad än Fermats. Infact, Miller-Rabin har också en deterministisk variant, men då är det ett handelsspel mellan tidskomplexitet och algoritmens noggrannhet.

ansökan:

• den enskilt viktigaste användningen av primtal är i kryptografi. Mer exakt används de i kryptering och dekryptering i RSA-algoritmen som var den allra första implementeringen av offentliga Nyckelkryptosystem
• en annan användning är i hashfunktioner som används i hashtabeller