Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Théorie du Laboratoire de calcul 2 : Affectation des ressources et conception du réseau

Description

Cette séance de cours couvre les algorithmes d'approximation pour les problèmes d'allocation des ressources comme le problème du Père Noël et makespan programming, ainsi que pour les problèmes de conception de réseau tels que le Traveling Salesman et Steiner forest. Il s'oriente également vers l'apprentissage d'algorithmes augmentés avec des prédictions, en discutant des algorithmes compétitifs pour le problème de reconnaissance TCP et les résultats expérimentaux.

Source officielle

Concepts associés (10)

Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

Competitive analysis (online algorithm)

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.

Algorithme online

En informatique, un algorithme en ligne, parfois aussi appelé algorithme incrémental, est un algorithme qui reçoit un flux de données en entrée, et qui doit prendre des décisions au fur et à mesure. Un cadre classique est celui dans lequel l'algorithme doit répondre à des requêtes les unes après les autres, sans connaître les requêtes à venir. Il s'oppose au concept d'algorithme hors ligne qui reçoit d'un seul coup les données qu'il a à considérer, et prend ses décisions en fonction de cette entrée.

Schéma d'approximation en temps polynomial

En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.

Acknowledgement (data networks)

In data networking, telecommunications, and computer buses, an acknowledgment (ACK) is a signal that is passed between communicating processes, computers, or devices to signify acknowledgment, or receipt of message, as part of a communications protocol. The negative-acknowledgement (NAK or NACK) is a signal that is sent to reject a previously received message or to indicate some kind of error. Acknowledgments and negative acknowledgments inform a sender of the receiver's state so that it can adjust its own state accordingly.

Afficher plus

Séances de cours associées (2)

L'appariement en ligne dans les environnements en évolution Connectez-vous à Mediaspace pour regarder cette vidéo

Explore la correspondance en ligne dans des environnements en évolution, en abordant les défis et les solutions pour adapter les algorithmes à l'évolution des données.

Réseau neuronal Rapprochement et apprentissage Connectez-vous à Mediaspace pour regarder cette vidéo

S'oriente vers l'approximation du réseau neuronal, l'apprentissage supervisé, les défis de l'apprentissage à haute dimension et la révolution expérimentale de l'apprentissage profond.