Epita:Algo:Cours:Info-Spe
Sommaire |
Le hachage
Contrairement aux méthodes de recherche arborescentes, dans les méthodes de hachage, la place d'un élément ne dépend pas de sa clé par rapport aux autres clés mais uniquement du résultat d'un calcul effectué sur cette clé.
Le calcul est réalisé directement sur la clé à l'aide d'une fonction qui transforme la clé en une valeur correspondant à une adresse mémoire ou un indice de tableau. L'intérêt est d'obtenir pour tous les algorithmes de manipulation (ajout, recherche, suppression) une complexité moyenne constante (ne dépendant pas du nombre d'éléments).
Les graphes
Les graphes sont des objets mathématiques qui permettent de modéliser beaucoup de problèmes combinatoires, qui sans cela et par les méthodes classiques (analyse mathématique, par exemple) seraient compliqués à aborder.
Mais les graphes ne sont pas que cela, ils sont aussi une structure de donnée informatique complexe irremplaçable dès qu'il s'agit de décrire ensemble d'objets et de relations entre ces objets. On les utilise, par exemple, pour modéliser les réseaux routiers, ferroviaires, aériens ou de communication.
Parmi les autres grandes utilités des graphes, il y a tous les problèmes de détermination de connexion et de recouvrement, les calculs de plus courts chemins. Enfin les graphes permettent aussi de décrire les systèmes dynamiques (évoluant dans le temps) comme les automates finis par exemple.
Bref, pour en savoir plus allons donc visiter les graphes.
la connexité
De manière caricaturale, nous pourrions exposer le problème ainsi : "Je suis à Paris, je souhaiterai (ardemment) me rendre à Nassau. J'ai le choix entre la voiture, le train, le bateau ou l'avion pour effectuer le trajet, quel(s) moyen(s) de transport puis-je ou non emprunter ?"
il peut être important de savoir si deux points d'un même réseau sont reliés entre eux par un chemin. Dans l'exemple précédent, il est inutile de rechercher un itinéraire entre ces deux villes (paris et Nassau) en voiture ou en train, le réseau ferroviaire ou routier ne les met pas en connexion.
Ce problème ramené au graphe consiste à mettre dans un même ensemble tous les sommets étant en relation entre eux (ayant un chemin ou une chaîne qui les relie). Il peut donc être intéressant de déterminer si un graphe est connexe ou non. En effet, avant de transmettre des données d'un point vers un autre ou bien de rechercher le plus court chemin d'un élément vers un autre, savoir si les deux extrémités concernées sont en relation peut nous faire gagner beaucoup de temps.
Pour plus de détails, allons voir de plus près ce qui touche aux connexités des graphes..
Les plus courts chemins
Reprenons notre problème de manière différente: "Finalement Nassau c'est très surfait. Je suis toujours à Paris et j'aimerai beaucoup (c'est un euphémisme) aller manger ce soir un cassoulet à Toulouse. Pourriez vous s'il vous plait m'indiquer le trajet le plus courts (de plus faible kilométrage) ?"
Pour comprendre le problème on peut regarder une carte routière. Si l'on fait abstraction des chemins peu crédibles (passer par Dunkerque pour aller de Paris à Toulouse), il reste quand même plusieurs centaines de milliers de trajets possibles. Parmi ceux-ci, il en existe un petit nombre qui méritent l'appellation de plus courts chemins. La question est: comment les repérer parmi tous les autres ?
La réponse est: en utilisant des algorithmes de plus courts chemins adaptés aux différentes problèmatiques et cas possibles.
Les arbres recouvrants
Quel rapport y a-t-il entre irriguer plusieurs zones d'une vallée avec une source d'eau unique, alimenter plusieurs villes avec une centrale énergétique, cabler un circuit électronique ou interconnecter différents réseaux locaux le plus "économiquement" possible?
Et bien, tous ces problèmes peuvent être résolus en faisant appel à une autre application classique utilisant les graphes: la construction des ARMs qui consiste à mettre en relation les différents sommets d'un graphe pour un coût cumulé minimum.
les tris dichotomique
Les tris sont utilisés dans de nombreux problèmes: Ordonnancement de tâches, Parties cachées, Dictionnaires, Graphes,etc. Il existe de nombreux algorithmes de tris. Au fur et à mesure de leur présentation, nous détaillerons leur complexité, leurs avantages et inconvénients. Cette partie du cours ne présentera que les Algorithmes de tri dichotomiques.
(Christophe "krisboul" Boullay)
