La recherche dichotomique est un principe très populaire en informatique. Elle permet de
trouver rapidement un élément dans une liste triée de manière efficace et rapide.
La compétence
La compétence 2 "Optimiser des applications" est d'une importance capitale pour les développeurs
de logiciels et les ingénieurs informatiques. Cette compétence se compose de quatre
sous-compétences, chacune ayant une importance unique dans l'optimisation des applications :
SC 1 : Choisir des structures de données complexes adaptées au problème :
Cette sous-compétence implique la capacité à choisir les structures de données
appropriées pour un problème donné, en fonction des besoins en termes de performances,
de mémoire et d'efficacité. Il est important de connaître les avantages et les
inconvénients de chaque structure de données (tableaux, listes, piles, files, arbres,
graphes, etc.) et de savoir les utiliser de manière appropriée pour résoudre des
problèmes spécifiques.
SC 2 : Utiliser des techniques algorithmiques adaptées pour des problèmes
complexes :
Cette sous-compétence implique la capacité à utiliser les techniques
algorithmiques les plus appropriées pour résoudre des problèmes complexes, tels que la
recherche opérationnelle, les méthodes arborescentes, l'optimisation globale,
l'intelligence artificielle, etc. Il est important de connaître les avantages et les
inconvénients de chaque technique algorithmique et de savoir les utiliser de manière
appropriée pour résoudre des problèmes spécifiques.
SC 3 : Comprendre les enjeux et moyens de sécurisation des données et du code :
Cette sous-compétence implique la capacité à comprendre les enjeux de sécurité liés à la
manipulation des données et du code dans les applications, ainsi que les moyens de
sécurisation des données et du code. Il est important de connaître les risques liés à la
sécurité des données (piratage, vol, corruption, etc.) et de savoir comment les éviter
ou les limiter.
SC 4 : Évaluer l'impact environnemental et sociétal des solutions proposées :
Cette sous-compétence implique la capacité à évaluer l'impact environnemental et
sociétal des solutions proposées en termes d'utilisation des ressources (énergie,
matériaux, etc.) et de l'impact sur la société (effets sociaux, éthiques, etc.). Il est
important de comprendre les enjeux environnementaux et sociétaux liés à la conception
d'applications et de savoir comment les minimiser ou les résoudre.
Chacune des sous-compétences de la compétence 2 "Optimiser des applications" est importante pour
garantir des performances optimales, assurer la sécurité des données et du code, et minimiser
l'impact environnemental et sociétal des applications. Les développeurs ayant une expertise dans
ces sous-compétences sont des atouts précieux pour toute entreprise ou organisation cherchant à
créer des applications performantes et responsables.
Démonstration générale :
Plus d'informations :
La recherche dichotomique, également appelée recherche binaire, est un algorithme efficace de
recherche dans une liste triée d'éléments. (SC 2 : Utiliser des techniques algorithmiques)
Cette méthode peut fonctionner avec tout type de structure triée. Dans mon cas, j'ai opté
pour
un fichier d'index binaire qui va stocké l'emplacement du mot cherché dans le dictionnaire.
(SC 1 : Choisir des structures de données complexes adaptées au problème)
Fichier d'index binaire
Cette méthode consiste à diviser la liste en deux moitiés jusqu'à ce que l'élément
recherché soit trouvé ou que la liste soit réduite à une seule valeur. Autrement dit, dans notre cas,
on va se placer à la moitié du fichier de l'index puis récupérer le mot correspondant à l'emplacement du fichier
d'index. On peut ainsi faire notre comparaison.
On compare la valeur à trouver avec l'élément situé au milieu de la liste. Si la
valeur est inférieure à l'élément central, la recherche continue dans la première moitié de la
liste. Sinon, la recherche continue dans la deuxième moitié. Dans le cadre de mon programme, la
comparaison suit l'ordre alphabétique après normalisation des mots (Majuscule et suppression des accents et caractères spéciaux).
Schéma de la recherche avec une liste de nombres triées
Ce processus est répété jusqu'à ce que l'élément recherché soit trouvé ou que la liste soit
réduite à une seule valeur. La recherche dichotomique est plus efficace que la recherche
linéaire, qui nécessite une exploration de chaque élément de la liste. Elle est particulièrement
utile pour les grandes listes de données, car elle réduit le nombre de comparaisons nécessaires
pour trouver l'élément. (Ici, ça nous évite de parcourir tous les mots et définitions du dictionnaire, un
fichier de + de 2 Millions de ligne !).
Extrait du dictionnaire
Différentes options ont été rajouté aux programme afin d'améliorer l'expérience utilisateur. Il est par exemple possible
de rechercher un mot de d'avoir une sortie en format YAML ou encore de mettre le mot en majuscule pour avoir tous les mots
équivalent à la forme normale.
Exemple de sortie YAML pour la recherche du mot 'accueil'
En résumé, la recherche dichotomique est un algorithme de recherche efficace pour les listes
triées, qui divise la liste en deux parties égales et compare la valeur à trouver avec l'élément
central. Elle est plus rapide que la recherche linéaire et est utile pour les grandes listes de
données. Elle est donc beaucoup moins énergivore et plus rapide, et donc plus écologique. (SC 4)
Made by Christian A.
Paris, France
07 68 19 05 32
anton.christian@outlook.fr
