Algorithme de Bellman-Ford. Un article de Wikipédia, l'encyclopédie libre.
La complexité de l'algorithme est, dans le pire des cas, en pour un graphe avec n sommets et m arcs (ce qui correspond à une complexité en pour un graphe simple dense). Utilisation[modifier | modifier le code] Dans les réseaux informatiques, l'algorithme de Bellman-Ford est utilisé pour déterminer le cheminement des messages, à travers le protocole de routage RIP[1]. Pseudo-code[modifier | modifier le code] Notes et références[modifier | modifier le code] Bibliographie[modifier | modifier le code] Michel Gondran et Michel Minoux, Graphes et algorithmes, Éditions Eyrolles, coll. « Études et recherches d'Électricité de France », 1979 (réimpr. 1986), 548 p., « 2 - Le problème du plus court chemin » COURS SUR LA METHODE HONGROISE (KUHN).avi. Algorithme hongrois. Un article de Wikipédia, l'encyclopédie libre.
L'algorithme hongrois ou méthode hongroise (parfois appelé aussi algorithme de Kuhn-Munkres) est un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial. Il a été proposé en 1955 par le mathématicien américain Harold Kuhn[1], qui l'a baptisé « méthode hongroise » parce qu'il s'appuyait sur des travaux antérieurs de deux mathématiciens hongrois : Dénes Kőnig et Jenő Egerváry (en). James Munkres (en) a revu l'algorithme en 1957 et a prouvé qu'il s'exécutait en temps polynomial[2]. L'algorithme d'Edmonds pour les couplages généralise l'algorithme hongrois et traite le problème du couplage maximum dans tous les graphes en temps polynomial.
Description de l'algorithme[modifier | modifier le code] Soit n projets et n équipes, et une matrice n×n d'entiers positifs, contenant le temps nécessaire à chaque équipe pour réaliser chaque tâche. Étape 0 Étape 1 Étape 2. JAMA: Java Matrix Package. Background JAMA is a basic linear algebra package for Java.
It provides user-level classes for constructing and manipulating real, dense matrices. It is meant to provide sufficient functionality for routine problems, packaged in a way that is natural and understandable to non-experts. It is intended to serve as the standard matrix class for Java, and will be proposed as such to the Java Grande Forum and then to Sun. A straightforward public-domain reference implementation has been developed by the MathWorks and NIST as a strawman for such a class.
A sibling matrix package, Jampack, has also been developed at NIST and the University of Maryland. Capabilities. JAMA is comprised of six Java classes: Matrix, CholeskyDecomposition, LUDecomposition, QRDecomposition, SingularValueDecomposition and EigenvalueDecomposition. The Matrix class provides the fundamental operations of numerical linear algebra. Example of Use. Efficient-java-matrix-library - A fast and easy to use dense matrix linear algebra library written in Java. Latest Version: 0.26 Released: September 15, 2014 LICENSE CHANGED FROM LGPL to Apache v2.0 Introduction Efficient Java Matrix Library (EJML) is a linear algebra library for manipulating dense matrices.
Its design goals are; 1) to be as computationally and memory efficient as possible for both small and large matrices, and 2) to be accessible to both novices and experts. These goals are accomplished by dynamically selecting the best algorithms to use at runtime and by designing a clean API. EJML has three distinct ways to interact with it. The following functionality is provided: Basic Operators (addition, multiplication, ... ) Matrix Manipulation (extract, insert, combine, ... ) Linear Solvers (linear, least squares, incremental, ... ) Decompositions (LU, QR, Cholesky, SVD, Eigenvalue, ...)
A list of projects which use EJML is available by clicking HERE! Source Code on GitHub Download from SourceForge Maven Gradle Documentation Reporting Bugs. Matrix Toolkit Java. MTJ was originally developed by Bjørn-Ove Heimsund, who has taken a step back due to other commitments.
The project webpage states that "(The new maintainers are) primarily concerned with keeping the library maintained, and fixing bugs as they are discovered. There is no road plan for future releases".[1] Several citations for MTJ can be found in scientific literature, including [2] which uses its LU preconditioner. Performance of MTJ has been compared to other libraries, which can be found at Java Matrix Benchmark's site.[3] Capabilities[edit] The following is an overview of MTJ's capabilities, as listed on the project's website: Usage Examples[edit] Example of Singular Value Decomposition (SVD): SVD svd = new SVD(matA.numRows(),matA.numColumns()); SVD s = svd.factor(matA); DenseMatrix U = s.getU(); DenseMatrix S = s.getS(); DenseMatrix Vt = s.getVt(); Example of matrix multiplication: DenseMatrix result = new DenseMatrix(matA.numRows(),matB.numColumns()); matA.mult(matB,result);
Matrix.java. Below is the syntax highlighted version of Matrix.java from §9.5 Numerical Linear Algebra.
Java matrix.