Graphes, dioïdes et semi-anneaux : nouveaux modèles et algorithmes [ Livre] / Michel, Gondran / Michel, Minoux

Auteur principal: Gondran, MichelCo-auteur: Minoux, MichelLangue: Français ; de l'oeuvre originale, Français.Publication : Londres : Tec & doc, 2001Description : 1 vol. (XVI-415 p.) ; 25 cmISBN: 2743004894.Classification: F 5 Théorie des graphesRésumé: L'ouvrage illustre la richesse de ces structures algébriques que sont les dioïdes et semi-anneaux par des dizaines d’exemples liés aux disciplines scientifiques les plus diverses. Il met en évidence leurs liens profonds avec les graphes et propose une synthèse de leurs nombreuses applications, dans les sciences fondamentales et les sciences de l’ingénieur : résolution d’une grande variété de problèmes de recherche de chemins optimaux dans les graphes, extension des algorithmes classiques de plus courts chemins à des problèmes de cheminement non classiques (plus courts chemins avec contraintes de temps, avec longueurs des arcs dépendant du temps etc.) , analyse des données, classification hiérarchique et analyse des préférences , modèles algébriques du flou et de l’incertain , automatique des systèmes à évènements discrets , résolution d’équations non-linéaires de la physique telles que : Hamilton-Jacobi, équation de Bürgers , développement d’analyses “linéaires” pour des problèmes non-linéaires (analyse MIN-PLUS, analyse MIN-MAX). De par la diversité des modèles et des méthodes de résolution étudiés, cet ouvrage propose des outils nouveaux applicables à tous les domaines scientifiques. Sommaire Pré-semi-anneaux, semi-anneaux et dioïdes. Quelques exemples fondateurs. Semi-groupes et monoïdes. Monoïdes ordonnés. Pré-semi-anneaux et pré-dioïdes. Semi-anneaux. Dioïdes. Exercices. Propriétés combinatoires des (pré-)semi-anneaux. Introduction. Polynômes et séries formelles à coefficients. Matrices carrées à coefficients dans un (pré-)semi-anneau. Bidéterminant d’une matrice carrée. Bipolynôme caractéristique. Bidéterminant d’un produit de matrices : une propriété combinatoire des pré-semi-anneaux. Le théorème de Cayley-Hamilton dans les présemi-anneaux. Semi-anneaux, bidéterminants et arborescences. Une généralisation de l’identité de Mac Mahon aux pré-semi-anneaux commutatifs. Exercices. Topologies des ensembles ordonnés. Dioïdes topologiques. Introduction. La Sup-Topologie et la Inf-Topologie dans des ensembles partiellement ordonnés. Convergence dans la Sup-Topologie et borne supérieure. Continuité des fonctions. Semi-continuité. Le théorème du point fixe dans un ensemble ordonné. Dioïdes topologiques. Les éléments p-stables d’un dioïde. Résiduation et solutions généralisées. Exercices. Résolution de systèmes linéaires dans les dioïdes. Introduction. Problème du plus court chemin et résolution de système linéaire dans un dioïde. Quasi-inverse d’une matrice à éléments dans un semi-anneau. Existence et propriétés. Algorithmes itératifs pour la résolution de systèmes linéaires. Algorithmes directs : méthode de Gauss-Jordan généralisée et variantes. Exemples d’application : problèmes de cheminement dans les graphes. Exercices. Dépendance et indépendance linéaires dans les semi-modules et les moduloïdes. Introduction. Semi-modules et moduloïdes. Bidéterminant et indépendance linéaire. Exercices. Valeurs propres et vecteurs propres d’endomorphismes. Introduction. Existence de valeurs propres et de vecteurs propres : résultats généraux. Valeurs propres et vecteurs propres dans les dioïdes idempotents. Caractérisation des moduloïdes propres. Valeurs propres et vecteurs propres dans les dioïdes à structure de groupes multiplicatifs. Valeurs propres, bidéterminant et bipolynôme caractéristique. Applications en Analyse de Données. Applications en automatique : anneaux théorie des systèmes dynamiques linéaires dans le dioïde (R Dioïdes et analyses non-linéaires. Introduction. Analyse MINPLUS. Inf-convergences en analyse MINPLUS. Solutions faibles en analyse MINPLUS et solutions de viscosité. Solutions explicites d’EDP non linéaires en analyse MINPLUS. Analyse MINMAX. La transformée de Cramer. Exercices. Répertoire de monoïdes, (pré-)semi-anneaux et dioïdes. Semi-anneaux et anneaux. Dioïdes..Sujet - Nom commun: Semi-anneaux (mathématiques) | Corps algébriques | Graphes, Théorie des | Algorithmes
Current location Call number Status Notes Date due Barcode
ENS Rennes - Bibliothèque
Informatique
F 5 GON (Browse shelf) Available F 5 Théorie des graphes 015544
ENS Rennes - Bibliothèque
Informatique
F 5 GON (Browse shelf) Available F 5 Théorie des graphes 012969

Bibliogr. p. 397-408. Index

L'ouvrage illustre la richesse de ces structures algébriques que sont les dioïdes et semi-anneaux par des dizaines d’exemples liés aux disciplines scientifiques les plus diverses. Il met en évidence leurs liens profonds avec les graphes et propose une synthèse de leurs nombreuses applications, dans les sciences fondamentales et les sciences de l’ingénieur : résolution d’une grande variété de problèmes de recherche de chemins optimaux dans les graphes, extension des algorithmes classiques de plus courts chemins à des problèmes de cheminement non classiques (plus courts chemins avec contraintes de temps, avec longueurs des arcs dépendant du temps etc.) , analyse des données, classification hiérarchique et analyse des préférences , modèles algébriques du flou et de l’incertain , automatique des systèmes à évènements discrets , résolution d’équations non-linéaires de la physique telles que : Hamilton-Jacobi, équation de Bürgers , développement d’analyses “linéaires” pour des problèmes non-linéaires (analyse MIN-PLUS, analyse MIN-MAX). De par la diversité des modèles et des méthodes de résolution étudiés, cet ouvrage propose des outils nouveaux applicables à tous les domaines scientifiques.

Sommaire
Pré-semi-anneaux, semi-anneaux et dioïdes. Quelques exemples fondateurs. Semi-groupes et monoïdes. Monoïdes ordonnés. Pré-semi-anneaux et pré-dioïdes. Semi-anneaux. Dioïdes. Exercices. Propriétés combinatoires des (pré-)semi-anneaux. Introduction. Polynômes et séries formelles à coefficients. Matrices carrées à coefficients dans un (pré-)semi-anneau. Bidéterminant d’une matrice carrée. Bipolynôme caractéristique. Bidéterminant d’un produit de matrices : une propriété combinatoire des pré-semi-anneaux. Le théorème de Cayley-Hamilton dans les présemi-anneaux. Semi-anneaux, bidéterminants et arborescences. Une généralisation de l’identité de Mac Mahon aux pré-semi-anneaux commutatifs. Exercices. Topologies des ensembles ordonnés. Dioïdes topologiques. Introduction. La Sup-Topologie et la Inf-Topologie dans des ensembles partiellement ordonnés. Convergence dans la Sup-Topologie et borne supérieure. Continuité des fonctions. Semi-continuité. Le théorème du point fixe dans un ensemble ordonné. Dioïdes topologiques. Les éléments p-stables d’un dioïde. Résiduation et solutions généralisées. Exercices. Résolution de systèmes linéaires dans les dioïdes. Introduction. Problème du plus court chemin et résolution de système linéaire dans un dioïde. Quasi-inverse d’une matrice à éléments dans un semi-anneau. Existence et propriétés. Algorithmes itératifs pour la résolution de systèmes linéaires. Algorithmes directs : méthode de Gauss-Jordan généralisée et variantes. Exemples d’application : problèmes de cheminement dans les graphes. Exercices. Dépendance et indépendance linéaires dans les semi-modules et les moduloïdes. Introduction. Semi-modules et moduloïdes. Bidéterminant et indépendance linéaire. Exercices. Valeurs propres et vecteurs propres d’endomorphismes. Introduction. Existence de valeurs propres et de vecteurs propres : résultats généraux. Valeurs propres et vecteurs propres dans les dioïdes idempotents. Caractérisation des moduloïdes propres. Valeurs propres et vecteurs propres dans les dioïdes à structure de groupes multiplicatifs. Valeurs propres, bidéterminant et bipolynôme caractéristique. Applications en Analyse de Données. Applications en automatique : anneaux théorie des systèmes dynamiques linéaires dans le dioïde (R Dioïdes et analyses non-linéaires. Introduction. Analyse MINPLUS. Inf-convergences en analyse MINPLUS. Solutions faibles en analyse MINPLUS et solutions de viscosité. Solutions explicites d’EDP non linéaires en analyse MINPLUS. Analyse MINMAX. La transformée de Cramer. Exercices. Répertoire de monoïdes, (pré-)semi-anneaux et dioïdes. Semi-anneaux et anneaux. Dioïdes.

Powered by Koha