Editions ENI Livres | Vidéos | e-Formations
Programmer des algorithmes en C++
Introduction
Ce chapitre présente des algorithmes appliqués en C++ et traitant de problématiques actuelles dans trois domaines : la reconnaissance de motifs, la recherche du plus court chemin et la compression de données.
Reconnaissance de motifs textuels
Pour un problème donné, il n’y a pas d’algorithme universel. Certains algorithmes ne sont efficaces que dans un cas de figure particulier.
Nous nous intéressons ici à la recherche de motifs textuels, c’est-à-dire la recherche d’une sous-chaîne dans une chaîne et nous allons présenter plusieurs formes d’algorithmes.
La librairie STL, tout comme boost, propose bien entendu des fonctions pour réaliser cela, mais la logique employée pour l’implémentation n’est pas indiquée dans le fichier d’en-tête. Il est utile de connaître quelques algorithmes de référence pour les appliquer à bon escient.
1. Approche directe
L’approche naïve consiste à comparer caractère par caractère le motif recherché avec le texte d’entrée. Si toutes les comparaisons réussissent du premier au dernier caractère du motif, on dit que le motif est épuisé et la recherche est terminée.
Si la comparaison diffère avant d’arriver à la fin du motif, il est inutile de poursuivre les comparaisons pour les caractères suivants. On décale le motif d’un caractère et l’on recommence la comparaison.
L’implémentation C++ de cet algorithme ne présente aucune difficulté. On doit vérifier les caractères un par un sans dépasser la taille du motif ni celle du texte à analyser :
int recherche_motif_simple(string s, string m)
{
int pos = 0;
int p = 0;
while (pos < s.length())
{
if (s.at(pos) == m.at(0))
{
// premier caractère identique
p = 1;
// compare un par un les prochains caractères du motif
while (
p + pos < s.length() &&
...Recherche du plus court chemin
Il existe quantité de situations dans lesquelles on doit rechercher le plus court chemin ; dans le domaine de la logistique, dans celui de la conduite assistée par ordinateur, dans le domaine de la planification et de l’ordonnancement, dans les moteurs de scénario de jeu vidéo…
Avant de présenter trois algorithmes incontournables voici une petite introduction aux graphes.
1. Présentation des graphes
Nous avons étudié au chapitre La librairie standard STL une structure dynamique appelée liste. Une liste est constituée d’un élément de tête (une valeur) rattaché à une liste appelée suite. Pour parcourir la liste, on utilise volontiers une fonction récursive qui se rappelle jusqu’à atteindre la liste vide.
En considérant qu’un élément peut avoir plusieurs successeurs, on obtient un arbre constitué de nœuds. Les nœuds ont un seul ancêtre appelé père et un nombre multiple de descendants appelés fils. Les nœuds terminaux qui n’ont pas de fils sont des feuilles, tandis que l’élément au sommet de l’arbre s’appelle racine. Il existe des cas particuliers d’arbres, par exemple ceux qui ont au plus deux fils appelés B-arbres ou B-trees, le B signifiant en anglais binary pour le nombre 2.
Un graphe généralise encore la construction de l’arbre en admettant qu’un nœud (appelé sommet) compte plusieurs ancêtres.
Les graphes sont formés de deux types d’éléments : des sommets et des arcs. Les sommets représentent les objets, et les arcs établissent les relations entre ceux-ci. Les arcs peuvent être porteurs de valeurs (ou poids) mais cette caractéristique n’est pas déterminante pour l’étude d’un graphe à proprement parler.
Les graphes peuvent être orientés ou non orientés. Dans le premier cas, les arcs sont orientés et sont représentés par des flèches. Au besoin, un arc peut être bidirectionnel en étant dédoublé pour représenter chaque sens. La numérotation ou l’identification des sommets n’est pas non plus une caractéristique...
Comprimer des fichiers
La question de l’économie d’espace pour représenter l’information s’est posée très tôt. Alors que la technologie a fait des progrès fantastiques, les besoins en communication et en stockage ont également crû dans les mêmes proportions. De ce fait, on cherche constamment à réduire la taille des fichiers et la bande passante consommée.
Nous présentons deux algorithmes à la fois très connus et toujours très employés, en particulier dans les logiciels d’archivage du marché ou encore dans les modules de compression mis en œuvre pour Internet et pour le cloud.
1. Approche par statistique : l’algorithme d’Huffman
On parle aussi de codage d’Huffman, du nom de son inventeur. Le principe de cet algorithme consiste à réduire le nombre de bits pour coder des caractères fréquents (octets) dans le fichier à comprimer, et rallonger les autres.
En langue française, la lettre E est la plus fréquente, tandis que les lettres K ou Z le sont beaucoup moins. D’une façon empirique, un codage du E sur 7 bits au lieu de 8 fera gagner 1 bit à chaque occurrence.
Comme il faut toujours 256 codes différents pour représenter chaque caractère ASCII (1 octet), on admettra que les lettres les moins fréquentes aient des codages plus longs, par exemple sur 9 bits.
L’algorithme d’Huffman construit un codage binaire (un arbre à deux branches ou B-tree) à partir des statistiques des caractères. Selon les implémentations, les statistiques sont prédéfinies en fonction du type de fichier ou dynamiquement calculées à partir du fichier à compresser. Des implémentations encore plus élaborées modifient le codage en actualisant les statistiques au fur et à mesure du traitement du fichier.
a. Implémentation du codage
Le codage démarre par un comptage des occurrences de chaque caractère (représenté sur un octet) dans le fichier source. On utilise pour cela un tableau de classe Noeud qui servira à la construction de l’arbre pour le codage :
class Noeud
{
public:
int code, lcode;
int...Implémenter un réseau de neurones en C++
Voici des techniques algorithmiques un peu différentes puisqu’il s’agit de la famille des métaheuristiques qui regroupe des approches non déterministes pour résoudre des problèmes informatiquement complexes comme l’optimisation (la recherche de valeurs minimum ou maximum, la détermination d’itinéraires…) ou encore la logique dite floue. Un algorithme classique est une méthode déterministe qui déroule une séquence d’opérations pour atteindre un résultat dans un temps connu à l’avance.
Les algorithmes avec métaheuristiques poursuivent un objectif qu’ils atteindront avec une certaine précision, dans un certain temps, et ils fonctionnent avec des modèles de données généralement évolutifs. Les métaheuristiques agissent comme des catalyseurs de résultat, ce sont des sortes de « recettes » qui vont accélérer l’atteinte d’un objectif. On trouve dans cette catégorie les algorithmes de recuit simulé, les algorithmes génétiques ou encore les réseaux de neurones.
1. Un réseau de neurones pour l’algorithmique ?
On peut concevoir un réseau de neurones comme une fonction recevant des paramètres et calculant un ensemble de résultats. Les paramètres d’entrée peuvent être protéiformes, ce sont des symboles, des valeurs numériques, des lettres… Ces grandeurs sont représentées sous la forme de valeurs numériques continues ou discrètes, disons de type float, chaque exemple développant sa propre interprétation (ou encore modélisation), en assimilant la valeur à un booléen, à une grandeur numérique ou encore à un symbole.
Le réseau de neurones réagit aux paramètres de la fonction appliqués sur sa couche d’entrée ; les neurones intermédiaires s’activent au gré des interconnexions et finissent par activer à leur tour certains neurones de la couche de sortie.
L’activation est une fonction de transfert qui produit une valeur d’une certaine intensité. Il faut comprendre qu’en sortie...