Problème dynamique (algorithmes) - Dynamic problem (algorithms)
Les problèmes dynamiques dans la théorie de la complexité informatique sont des problèmes énoncés en termes de changement des données d'entrée. Dans sa forme la plus générale, un problème de cette catégorie est généralement énoncé comme suit:
- Étant donné une classe d'objets d'entrée, trouvez des algorithmes et des structures de données efficaces pour répondre à une certaine question sur un ensemble d'objets d'entrée chaque fois que les données d'entrée sont modifiées, c'est-à-dire que des objets sont insérés ou supprimés.
Les problèmes de cette classe ont les mesures de complexité suivantes:
- Espace - la quantité d' espace mémoire nécessaire pour stocker la structure de données;
- Temps d'initialisation - temps requis pour la construction initiale de la structure de données;
- Temps d'insertion - temps requis pour la mise à jour de la structure de données lorsqu'un élément d'entrée supplémentaire est ajouté;
- Temps de suppression - temps requis pour la mise à jour de la structure de données lorsqu'un élément d'entrée est supprimé;
- Temps de requête - temps nécessaire pour répondre à une requête;
- Autres opérations spécifiques au problème en question
L'ensemble global des calculs pour un problème dynamique est appelé un algorithme dynamique .
De nombreux problèmes algorithmiques énoncés en termes de données d'entrée fixes (appelés problèmes statiques dans ce contexte et résolus par des algorithmes statiques ) ont des versions dynamiques significatives.
Cas spéciaux
Les algorithmes incrémentaux , ou algorithmes en ligne , sont des algorithmes dans lesquels seuls les ajouts d'éléments sont autorisés, éventuellement à partir des données d'entrée vides / triviales.
Les algorithmes décrémentaux sont des algorithmes dans lesquels seules les suppressions d'éléments sont autorisées, en commençant par l'initialisation d'une structure de données complète.
Si les ajouts et les suppressions sont autorisés, l'algorithme est parfois appelé entièrement dynamique .
Exemples
Élément maximal
- Problème statique
- Pour un ensemble de N nombres, trouvez le maximum.
Le problème peut être résolu en temps O (N).
- Problème dynamique
- Pour un ensemble initial de N nombres, maintenez dynamiquement le nombre maximal lorsque l'insertion et les suppressions sont autorisées.
Une solution bien connue à ce problème consiste à utiliser un arbre de recherche binaire auto-équilibré . Il prend de l'espace O (N), peut être initialement construit en temps O (N log N) et fournit des temps d'insertion, de suppression et d'interrogation en O (log N).
- Le problème de maintenance de la file d'attente prioritaire
- C'est une version simplifiée de ce problème dynamique, où l'on ne demande de supprimer que l'élément maximal. Cette version peut faire avec des structures de données plus simples.
Graphiques
Étant donné un graphe, conservez ses paramètres, tels que la connectivité, le degré maximal, les chemins les plus courts, etc., lorsque l'insertion et la suppression de ses arêtes sont autorisées.
