Dans les programmeurs, les algorithmes de vie et les structures de données sont le sujet le plus important s’ils veulent sortir dans le monde de la programmation et faire des des dollars. Aujourd’hui, Nous verrons ce qu’ils font et où ils sont utilisés avec des exemples les plus simples. Cette liste est préparée en tenant compte de leur utilisation dans la programmation concurrentielle et des pratiques de développement actuelles.

Algorithmes de tri

Le tri est le concept le plus étudié en informatique. L’idée est d’organiser les éléments d’une liste dans un ordre spécifique. Bien que tous les principaux langages de programmation disposent de bibliothèques de tri intégrées, cela est utile si vous savez comment ils fonctionnent. Selon les besoins, vous voudrez peut-être utiliser l’un de ces éléments.

• Tri par fusion
• Tri Rapide
• Tri par seau
• Tri par Tas
• Tri par comptage

Plus important encore, il faut savoir quand et où les utiliser. Voici quelques exemples où vous pouvez trouver une application directe des techniques de tri:

• Tri par prix, popularité, etc. dans les sites Web de commerce électronique

Algorithmes de recherche

Recherche binaire (dans des structures de données linéaires)

La recherche binaire est utilisée pour effectuer une recherche très efficace sur un ensemble de données trié. La complexité temporelle est O (log2N). L’idée est de diviser à plusieurs reprises en deux la partie de la liste qui pourrait contenir l’élément, jusqu’à ce que nous la réduisions à un élément possible. Certaines applications sont:

• Lorsque vous recherchez un nom de chanson dans une liste triée de chansons, il effectue une recherche binaire et une correspondance de chaînes pour renvoyer rapidement les résultats.
• Utilisé pour déboguer dans git via git bisect

Première recherche en profondeur/largeur (dans les structures de données de graphes)

DFS et BFS sont des structures de données parcourant et recherchant des arborescences/graphes. Nous n’irons pas en profondeur dans le fonctionnement des DFS / BFS, mais nous verrons en quoi ils sont différents grâce à l’animation suivante.

Applications:

• Utilisé par les moteurs de recherche pour l’exploration du Web
• Utilisé en intelligence artificielle pour construire des bots, par exemple un bot d’échecs
• Trouver le chemin le plus court entre deux villes sur une carte et de nombreuses autres applications de ce type

Hachage

La recherche de hachage est actuellement la technique la plus utilisée pour trouver les données appropriées par clé ou identifiant. Nous accédons aux données par son index. Auparavant, nous nous appuyions sur le Tri + la recherche binaire pour rechercher l’index alors que maintenant nous utilisons le hachage.

La structure de données est appelée Carte de hachage ou Table de hachage ou Dictionnaire qui mappe efficacement les clés aux valeurs. Nous pouvons effectuer des recherches de valeur à l’aide de clés. L’idée est d’utiliser une fonction de hachage appropriée qui effectue le mappage de valeur key->. Le choix d’une bonne fonction de hachage dépend du scénario.

Applications:

• Dans les routeurs, pour stocker l’adresse IP – > Paire de chemins pour les mécanismes de routage
• Pour vérifier si une valeur existe déjà dans une liste. La recherche linéaire serait coûteuse. Nous pouvons également utiliser une structure de données définie pour cette opération.

Programmation dynamique

La programmation dynamique (DP) est une méthode permettant de résoudre un problème complexe en le décomposant en sous-problèmes plus simples. Nous résolvons les sous-problèmes, nous nous souvenons de leurs résultats et nous les utilisons pour résoudre rapidement le problème complexe.

* écrit « 1+1+1+1+1+1+1+1 =” sur une feuille de papier * À quoi cela équivaut-il ?
* compter * Huit!
* écrit un autre « 1+ » sur la gauche * Qu’en est-il?
* rapidement * Neuf!
Comment as-tu su que c’était neuf si vite ?
Vous venez d’en ajouter un de plus
Donc vous n’avez pas eu besoin de recompter parce que vous vous êtes souvenu qu’il y en avait huit! La programmation dynamique est juste une façon élégante de dire « se souvenir de choses pour gagner du temps plus tard »

Applications:

• Il existe de nombreux algorithmes et applications DP, mais j’en nommerais un et vous époustouflerais, méthode Duckworth-Lewis au cricket.

Exponentiation par la quadrature

Disons que vous voulez calculer 232. Normalement, nous itérions 32 fois et trouvons le résultat. Et si je vous disais que cela peut se faire en 5 itérations?

L’exponentiation par quadrature ou exponentiation binaire est une méthode générale de calcul rapide de grandes puissances entières positives d’un nombre en O (log2N). Non seulement cela, la méthode est également utilisée pour le calcul des puissances de polynômes et de matrices carrées.

Application:

• Le calcul de grandes puissances d’un nombre est principalement requis dans le chiffrement RSA. RSA utilise également l’arithmétique modulaire avec l’exponentiation binaire.

La correspondance et l’analyse des chaînes

La correspondance / la recherche de motifs est l’un des problèmes les plus importants en informatique. Il y a eu beaucoup de recherches sur le sujet, mais nous n’enrôlerons que deux nécessités de base pour tout programmeur.

Algorithme KMP (Correspondance de chaînes)

L’algorithme Knuth-Morris-Pratt est utilisé dans les cas où nous devons faire correspondre un motif court dans une chaîne longue. Par exemple, lorsque nous Ctrl + F un mot-clé dans un document, nous effectuons une correspondance de motif dans l’ensemble du document.

Expression régulière (Analyse de chaîne)

Plusieurs fois, nous devons valider une chaîne en analysant une restriction prédéfinie. Il est fortement utilisé dans le développement Web pour l’analyse et la correspondance d’URL.

Algorithmes de test de primalité

Il existe des moyens déterministes et probabilistes de déterminer si un nombre donné est premier ou non. Nous verrons des moyens déterministes et probabilistes (non déterministes).

Tamis d’Ératosthène (déterministe)

Si nous avons une certaine limite sur la plage de nombres, disons déterminer tous les nombres premiers dans la plage de 100 à 1000, alors le tamis est un chemin à parcourir. La longueur de la plage est un facteur crucial, car nous devons allouer une certaine quantité de mémoire en fonction de la plage.

Pour n’importe quel nombre n, en testant progressivement jusqu’à sqrt(n) (déterministe)

Si vous souhaitez vérifier quelques nombres qui sont peu répartis sur une longue plage (disons 1 à 1012), Sieve ne sera pas en mesure d’allouer suffisamment de mémoire. Vous pouvez vérifier chaque nombre n en parcourant uniquement jusqu’à sqrt(n) et effectuer une vérification de divisibilité sur n.

Test de primalité de Fermat et test de primalité de Miller–Rabin (les deux sont non déterministes)

Les deux sont des tests de composition. S’il est prouvé qu’un nombre est composite, alors ce n’est certainement pas un nombre premier. En fait, Miller-Rabin a également une variante déterministe, mais c’est alors un jeu d’échange entre la complexité temporelle et la précision de l’algorithme.

Application:

• L’utilisation la plus importante des nombres premiers est en cryptographie. Plus précisément, ils sont utilisés dans le chiffrement et le déchiffrement dans l’algorithme RSA qui était la toute première implémentation de Cryptosystèmes à Clé Publique
• Une autre utilisation est dans les fonctions de hachage utilisées dans les tables de hachage