Recherche en informatique et technologies de l’information
- Des chercheurs de l’ETH Zurich ont développé un algorithme de flot sur réseau
- Cet algorithme calcule, pour tout type de réseau, le flux maximal de trafic au coût minimal
- Il effectue ses calculs à la vitesse théoriquement la plus rapide possible
Développement d’un algorithme innovant
- Cet algorithme, développé par Rasmus Kyng et son équipe, constitue une avancée majeure dans la résolution des problèmes de flot sur réseau
- Il peut calculer un flux de trafic optimal même dans des réseaux complexes comme le réseau de transport européen
- Auparavant, le calcul du flux optimal demandait plus de temps que le traitement des données du réseau, mais l’algorithme de Kyng résout ce problème
Augmentation simultanée de la taille du réseau et du temps de calcul
- L’approche de Kyng permet à la taille du réseau et au temps de calcul d’augmenter dans la même proportion
- Jusqu’au début des années 2000, les calculs se faisaient à une vitesse de
m1.5, mais l’algorithme de Kyng est si rapide que le temps de calcul supplémentaire en devient presque négligeable
Algorithme en temps presque linéaire
- L’équipe de Kyng a développé un algorithme capable de calculer le flux optimal non seulement dans des réseaux fixes, mais aussi dans des réseaux qui évoluent dynamiquement
- Cet algorithme est également utile pour des réseaux très complexes et riches en données, comme les molécules ou le cerveau
Un algorithme fulgurant pour les réseaux changeants
- Simon Meierhans a présenté un nouvel algorithme pour résoudre le problème du flot maximal à coût minimal dans des réseaux en évolution
- Cet algorithme peut calculer le chemin optimal même dans des réseaux où de nouvelles connexions sont ajoutées ou supprimées
Le caractère innovant de l’approche de Kyng
- L’approche de Kyng permet des calculs plus rapides en combinant de nombreuses petites étapes de calcul efficaces et peu coûteuses
- Cette approche crée une nouvelle méthode en combinant les avantages des réseaux ferroviaires et des réseaux électriques
Un tournant pour l’informatique théorique
- Les travaux de Kyng accélèrent encore davantage les algorithmes grâce à de nouveaux outils mathématiques
- Ces outils organisent les structures de données des réseaux afin d’identifier rapidement les changements dans les connexions
L’avis de GN⁺
- L’algorithme de Kyng est considéré comme une avancée importante en informatique théorique
- Il pose les bases d’une résolution efficace de problèmes de très grande taille
- La rapidité de calcul dans des réseaux changeants sera utile dans divers domaines d’application, comme le traitement de données en temps réel
- Parmi les autres projets aux fonctions similaires figure l’algorithme PageRank de Google
- Lors de l’adoption de nouvelles technologies, il faut tenir compte de la compatibilité avec les systèmes existants et des coûts de maintenance
Aucun commentaire pour le moment.