| Titre : | Algorithmique et représentation des données : 2, évaluations, arbres, graphes, analyse de textes |
| Auteurs : | Michel Lucas |
| Type de document : | texte imprimé |
| Editeur : | Paris : Masson, 1986 |
| ISBN/ISSN/EAN : | 978-2-225-80924-8 |
| Format : | 196 p / .ill / 24 cm |
| Note générale : | Bibliogr. p. 193-194 . Index |
| Langues: | Français |
| Langues originales: | Français |
| Index. décimale : | 004 (informatique en général) |
| Catégories : | |
| Mots-clés: | Algorithmique |
| Résumé : | Ce document, intitulé "Algorithmique et représentation des données, 2. Évaluations, arbres, graphes, analyse de textes" (souvent attribué à Michel Lucas), est typiquement un manuel ou un support de cours de niveau avancé (Licence 2 ou 3) en informatique. Il se concentre sur les structures de données complexes et les algorithmes associés qui permettent de modéliser et de traiter des problèmes avancés.Voici un résumé des concepts centraux :???? Les Fondations : Algorithmique AvancéeL'objectif principal est de fournir à l'étudiant les outils nécessaires pour concevoir et analyser des solutions informatiques efficaces pour des problèmes non-linéaires.1. Évaluations et Complexité AlgorithmiqueCe chapitre est fondamental. Il ne s'agit pas d'évaluer la note d'un étudiant, mais d'évaluer la performance d'un algorithme.Complexité en Temps et en Espace : Étude des fonctions de complexité (notation $O$ majuscule) pour prédire le temps d'exécution et la quantité de mémoire nécessaires en fonction de la taille des données d'entrée ($n$).Analyse d'Algorithmes : Détermination des performances au pire, au meilleur et en moyenne pour les algorithmes complexes introduits par la suite (tri, recherche, parcours).???? Structures de Données Non-LinéairesCes structures permettent de représenter des relations hiérarchiques ou des interconnexions complexes dans les données.2. Les ArbresLes arbres sont des structures fondamentales en informatique pour organiser des données de manière hiérarchique.Arbres Binaires de Recherche (ABR) : Comment insérer, chercher et supprimer des éléments de manière rapide (en $O(\log n)$ en moyenne).Arbres Équilibrés (AVL, Rouge et Noir) : Algorithmes complexes pour maintenir l'équilibre de l'arbre et garantir une complexité de recherche en $O(\log n)$ même dans le pire des cas.Arbres n-aires : Utilisation des arbres pour les structures de fichiers, les expressions arithmétiques ou la modélisation hiérarchique.3. Les GraphesLes graphes modélisent des relations complexes et des réseaux (réseaux sociaux, cartes routières, flux, dépendances).Représentations : Étude des différentes façons de stocker un graphe en mémoire (matrices d'adjacence, listes d'adjacence).Algorithmes de Parcours : Parcours en largeur (Breadth-First Search ou BFS) et Parcours en profondeur (Depth-First Search ou DFS).Problèmes de Graphes Classiques :Plus court chemin (Algorithmes de Dijkstra, Bellman-Ford).Arbres couvrants minimaux (Algorithmes de Prim, Kruskal).Problème de flot maximal.???? Application Spécifique : Analyse de TextesCe module applique les concepts algorithmiques aux données textuelles.4. Analyse de TextesIl s'agit d'appliquer les structures de données et les algorithmes pour traiter et manipuler de grandes quantités de texte.Algorithmes de Recherche de Motifs : Techniques efficaces pour trouver des occurrences d'une sous-chaîne dans une chaîne principale (e.g., algorithmes de Knuth-Morris-Pratt ou Boyer-Moore).Indexation et Compression : Utilisation d'arbres (comme les Tries) pour l'indexation de dictionnaires et application d'algorithmes (comme l'encodage de Huffman, qui utilise des arbres) pour la compression de données.Modélisation Linguistique : Début d'introduction à la façon dont les structures de données peuvent représenter la syntaxe et la sémantique (tokenisation, analyse lexicale).Ce volume vise donc à faire le pont entre les concepts algorithmiques de base (introduits dans le volume 1) et leur application concrète pour la résolution de problèmes complexes en utilisant les arbres et les graphes. |
Exemplaires (1)
| Code-barres | Cote | Support | Localisation | Section | Disponibilité |
|---|---|---|---|---|---|
| Info.A/2654 | 004/1035/1 | Livre | BU Centrale Batna 1 | Deuxième étage : Architecture, sciences et technologies | Disponible |
