In de programmeurs leven algoritmen en datastructuren is het meest belangrijk onderwerp, als ze willen om uit te gaan in de wereld van het programmeren en maken wat geld. Vandaag zullen we zien wat ze doen en waar ze worden gebruikt met eenvoudige voorbeelden. Deze lijst is opgesteld rekening houdend met het gebruik ervan in concurrerende programmering en de huidige ontwikkelingspraktijken.

sorteeralgoritmen

sorteren is het meest bestudeerde concept in de informatica. Het idee is om de items van een lijst in een specifieke volgorde te rangschikken. Hoewel elke grote programmeertaal ingebouwde sorteerbibliotheken heeft, is het handig als je weet hoe ze werken. Afhankelijk van de behoefte kunt u een van deze gebruiken.

• samenvoegen Sorteer
• snelle Sorteer
• Bucket Sorteer
• Heap Sorteer
• tellen Sorteer

belangrijker is dat men moet weten wanneer en waar ze te gebruiken. Enkele voorbeelden waar u directe toepassing van sorteertechnieken kunt vinden zijn:

• Sorteren op prijs, populariteit etc in e-commerce websites

zoekalgoritmen

binair zoeken (in lineaire datastructuren)

binair zoeken wordt gebruikt om een zeer efficiënte zoekopdracht uit te voeren op gesorteerde dataset. De tijdscomplexiteit is O (log2N). Het idee is om herhaaldelijk te verdelen in de helft van het deel van de lijst dat het item zou kunnen bevatten, totdat we het beperken tot een mogelijk item. Sommige toepassingen zijn:

• wanneer u zoekt naar een naam van het nummer in een gesorteerde lijst van nummers, voert het binaire zoekopdracht en string-matching uit om snel de resultaten te retourneren.
• wordt gebruikt om Git te debuggen via git bisect

diepte/breedte Eerste zoekopdracht (In Graph datastructuren)

DFS en BFS zijn tree / graph die datastructuren doorkruisen en doorzoeken. We zouden niet diep ingaan op hoe DFS / BFS werken, maar zullen zien hoe ze anders zijn door de volgende animatie.

Toepassingen:

• wordt Gebruikt door zoekmachines voor het web crawlen
• Gebruikt in de kunstmatige intelligentie op te bouwen bots, bijvoorbeeld een schaken bot
• het Vinden van de kortste route tussen twee steden in een kaart en vele andere toepassingen

Hash

Hash-lookup is op dit moment de meest gebruikte techniek om de juiste gegevens door de sleutel of ID. We hebben toegang tot de gegevens door de index. Voorheen vertrouwden we op Sorteren+binair Zoeken om te zoeken naar index, terwijl we nu gebruik maken van hashing.

de gegevensstructuur wordt aangeduid als Hash-Map of Hash-tabel of woordenboek dat sleutels efficiënt toewijst aan waarden. We kunnen waarde lookups uitvoeren met behulp van sleutels. Idea is om een geschikte hash functie te gebruiken die de sleutel -> waarde mapping doet. Het kiezen van een goede hash-functie hangt af van het scenario.

toepassingen:

• in routers, om IP-adres op te slaan – > Padpaar voor routeringsmechanismen
• om de controle uit te voeren of een waarde al in een lijst bestaat. Lineair zoeken zou duur zijn. We kunnen ook Set data structuur gebruiken voor deze operatie.

dynamisch programmeren

dynamisch programmeren (DP) is een methode om een complex probleem op te lossen door het op te splitsen in eenvoudigere subproblemen. We lossen de subproblemen op, onthouden hun resultaten en gebruiken ze om snel het complexe probleem op te lossen.

* schrijft op “1+1+1+1+1+1+1+1 =” op een vel papier * waar is dat gelijk aan?
*tellen * acht!
* schrijft links nog een “1+” op* Hoe zit het daarmee?
* Snel * negen!hoe wist je dat het zo snel negen was?
Je hebt zojuist nog een
toegevoegd zodat je niet hoefde te vertellen omdat je je herinnerde dat er acht waren! Dynamisch programmeren is gewoon een mooie manier om te zeggen ‘dingen onthouden om later tijd te besparen’

toepassingen:

• Er zijn veel DP-algoritmen en toepassingen, maar ik zou er een noemen en je wegblazen, Duckworth-Lewis methode in cricket.

exponentiatie door squaring

stel dat u 232 wilt berekenen. Normaal gesproken zouden we 32 keer herhalen en het resultaat vinden. Wat als ik je vertelde dat het kan worden gedaan in 5 iteraties?

exponentiatie door squaring of binaire exponentiatie is een algemene methode voor snelle berekening van grote positieve gehele getallen van een getal in o(log2N). Niet alleen dit, de methode wordt ook gebruikt voor de berekening van bevoegdheden van veeltermen en vierkante matrices.

toepassing:

• berekening van grote bevoegdheden van een getal is meestal vereist in RSA-versleuteling. RSA maakt ook gebruik van modulaire rekenkunde samen met binaire exponentiatie.

String Matching en Parsing

Pattern matching / searching is een van de belangrijkste problemen in de informatica. Er is veel onderzoek gedaan naar het onderwerp, maar we zullen slechts twee basisbehoeften gebruiken voor elke programmeur.

KMP algoritme (String Matching)

Knuth-Morris-Pratt algoritme wordt gebruikt in gevallen waarin we een kort patroon in een lange string moeten matchen. Bijvoorbeeld, wanneer we Ctrl+F een trefwoord in een document, wij voeren patroonherkenning in het hele document.

Reguliere Expressie (string Parsing)

vaak moeten we een string valideren door te parsen over een vooraf gedefinieerde beperking. Het wordt zwaar gebruikt in webontwikkeling voor URL parsing en matching.

algoritmen voor Primaliteitstests

Er zijn deterministische en probabilistische manieren om te bepalen of een gegeven getal al dan niet een priemgetal is. We zullen zowel deterministische als probabilistische (niet-deterministische) manieren zien.

Zeef van Eratosthenes (deterministisch)

als we een bepaalde limiet hebben op het getallenbereik, stel dat we alle priemgetallen binnen het bereik 100 tot 1000 bepalen, dan is Zeef een manier om te gaan. De lengte van het bereik is een cruciale factor, omdat we een bepaalde hoeveelheid geheugen moeten toewijzen volgens het bereik.

voor elk getal n, stapsgewijs testen tot sqrt (n) (deterministisch)

in het geval u wilt controleren op enkele getallen die dun over een lange afstand zijn verdeeld (bijvoorbeeld 1 tot 1012), zal Sieve niet in staat zijn om voldoende geheugen toe te wijzen. U kunt voor elk getal n controleren door alleen naar sqrt(n) te gaan en een deelbaarheidscontrole uit te voeren op n.

Fermat primaliteitstest en Miller–Rabin primaliteitstest (beide zijn niet-deterministisch)

beide zijn compositenheidstesten. Als een getal samengesteld blijkt te zijn, dan is het zeker geen priemgetal. Miller – Rabin is een meer geavanceerde dan Fermat ‘ s. in feite, Miller-Rabin heeft ook een deterministische variant, maar dan is het een spel van de handel tussen tijd complexiteit en nauwkeurigheid van het algoritme.

toepassing:

• het belangrijkste gebruik van priemgetallen is in cryptografie. Meer precies, ze worden gebruikt in encryptie en decryptie in RSA algoritme dat de allereerste implementatie was van publieke sleutel cryptosystemen
• een ander gebruik is in Hash functies gebruikt in Hash tabellen