• Accueil LIP6
  • Page : 'rapport_recherche' inconnue (menus.php)

LIP6 1998/051

  • Rapports de recherche
    Résolution de systèmes linéaires dans les semi-anneaux et les dioïdes
  • M. Minoux
  • 51 pages - 31/12/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.051.ps.gz - 106 Ko
  • Contact : Michel.Minoux (at) nulllip6.fr
  • Ancien Thème : ANP
  • La plupart des algorithmes classiques de résolution de systèmes linéaires dans l'algèbre usuelle peut se transposer à des structures algébriques beaucoup plus générales telles que les semi-anneaux et les dioïdes. Nous présentons ici une synthèse de ces extensions : méthode itératives de JACOBI, et de GAUSS-SEIDEL généralisées ; méthodes d'élimination de GAUSS-JORDAN et "Escalier" généralisées, algorithme "glouton" généralisé. Pour le cas particulier du problème de plus court chemin dans un graphe, on retrouve ainsi de nombreux algorithmes connus : algorithmes de FORD-BELLMANN, algorithme de FLOYD, algorithme de DANTZIG et algorithme de DIJKSTRA.
  • Mots clés : semi-anneaux, dioïdes, systèmes linéaires
  • Directeur de la publication : Emmanuelle.Encrenaz (at) nulllip6.fr
Mentions légales
Carte du site