Je recherche une structure de données et un algorithme pour calculer le nombre minimum de changements requis pour transformer un mot en un autre, étant donné les deux mots en entrée, où les seuls changements autorisés sont ajouter une lettre à l'une des extrémités (par exemple, AB -> ABC),...
Des arborescences de partition ont-elles déjà été implémentées? Ici, je parle des arbres de partition de la géométrie de calcul. Les premières versions (presque) optimales étaient dues à Matousek et à d'autres, et plus récemment à Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf Cela me...
L'exercice suivant a été remis aux étudiants que je supervise: Étant donné points dans le plan, imaginez un algorithme qui trouve une paire de points dont la distance est minimale parmi toutes les paires de points. L'algorithme doit s'exécuter au temps .nnno(n2)o(n2)o(n^2) Il existe un algorithme...
Dans un graphe dirigé, , F ⊂ E , si G ∖ F est un DAG (graphe acyclique dirigé), F est appelé un ensemble d'arc de rétroaction. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Si chaque bord est associé à un poids , le problème de jeu d'arc à rétroaction de coût minimum est de trouver un...
Dans la section 2.2 de Cache-Inconscient B-arbres , fortement poids équilibré Les arbres de recherche sont définis comme suit: Pour une constante , chaque nœud à la hauteur a des descendants .v h Θ ( d h )réddvvvhhhΘ ( dh)Θ(dh)\Theta(d^h) Ils affirment: Les arbres de recherche qui satisfont aux...
Je recherche une structure de données très efficace pour le stockage de données similaire à la suivante. Étiquettes d'identification Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 J'ai besoin de pouvoir interroger cette structure de manière à ce qu'elle me donne une...
Je recherche une structure de données économe en espace qui contient des ensembles (sans répétition) d'éléments de taille de mots et prend en charge l'insertion rapide (O amorti (1)). Par "économe en espace", je veux dire, idéalement, n+o(n)n+o(n)n + o(n) mots pour stocker nnn éléments. Être un...
Supposons que nous ayons un semi-groupe avec les éléments . Notre objectif est de calculer les produits .S = { s 1 , s 2 , … , s n } s i ∘ s i + 1 ∘ ⋯ ∘ s j( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, … , Sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesje∘ si + 1∘ ⋯ ∘ sjsje∘sje+1∘⋯∘sjs_i\circ...
Existe-t-il une structure de données de mots-RAM de w bits avec O (1) temps par opération pour le problème suivant?: Maintenir un ensemble d'entiers non négatifs de w bits qui prend en charge les opérations add (x): ajoutez x à l'ensemble remove (x): supprime x de l'ensemble fingerprint ():...
REMARQUE : La question a été reformulée dans mes réponses: en supposant maintenant que nous pouvons trouver les ancêtres frères les plus bas en , l'ANN peut-il vraiment être exécuté en ?O ( log n )O ( 1 )O(1)O(1)O ( logn )O(logn)O(\log n) Les Quadtrees sont des indices spatiaux efficaces. J'ai un...
Les essais permettent un stockage efficace des listes d'éléments. Les préfixes sont partagés, ce qui optimise l'espace. Je cherche un moyen similaire de stocker efficacement les arbres. Je voudrais pouvoir vérifier l'appartenance et ajouter des éléments, sachant si un arbre donné est un sous-arbre...
David Rodríguez - dribeas a écrit dans un commentaire sur StackOverflow que "toutes les collections ne peuvent pas être implémentées sans verrous". Je ne suis pas sûr que ce soit vrai, et je ne trouve aucune preuve de toute façon. Cette déclaration n'est pas très précise, mais permettez-moi...
J'ai lu un peu sur les structures de données suivantes: Essais de hachage idéaux de Bagwell Tables de hachage dynamiques de Larson Arbres rouges-noirs Arbres Patricia ... et je suis sûr qu'il y en a beaucoup d'autres. J'ai vu très peu de choses sur ce que chacun est le mieux adapté, ou pourquoi je...
Il est facile de voir que pour tout nnn il existe un mappage 1-1 FFF de {0,1} n à {0,1} n + O ( log n ) de telle sorte que pour tout x le vecteur F ( x ) est " équilibré ", c'est-à-dire qu'il a un nombre égal de 1 et de 0. Est-il possible de définir un tel F pour que, étant donné x, nous pouvons...
Quelle est la meilleure limite actuelle pour effectuer des requêtes de comptage de demi-espace sur un ensemble de points dimensionnels, exprimée sous la forme d'un compromis temps / espace. Selon l'article fondamental de Matousek de 1993 (Théorème 6.2, Recherche de plage avec des coupes...
J'ai un grand ensemble de données d'arbres et je voudrais le rechercher en spécifiant un treelet (sous-graphe connecté). La requête doit renvoyer toutes les occurrences du treelet dans l'ensemble de données. Existe-t-il des algorithmes efficaces pour le faire? Je pensais à quelque chose comme des...
Deux piles peuvent être mises en œuvre efficacement en utilisant un tableau de taille fixe: la pile # 1 commence à partir de l'extrémité gauche et croît vers la droite, et la pile # 2 commence à partir de l'extrémité droite et croît vers la gauche. Est-ce la même chose possible pour trois piles?...
Nous avons un ensemble, , de listes d'éléments de l'ensemble . Chaque élément de apparaît dans une liste unique en . Je recherche une structure de données pouvant effectuer les mises à jour suivantes:N = { 1 , 2 , 3 , . . . , n }LLLN={1,2,3,...,n}N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}NNNLLL...
Voici un problème qui me dérange depuis un moment. Disons qu'une chaîne est une séquence de 1 et de 0 et qu'une chaîne générique est une séquence de 1, 0 et? S. Toutes les chaînes et les chaînes génériques ont la même longueur. Ce sont des caractères génériques UNIX standard; 10 ?? 1 correspond à...
Je cherche une structure de données, qui est essentiellement un arbre de cartes, où la carte à chaque nœud contient de nouveaux éléments, ainsi que les éléments de la carte de son nœud parent. Par carte ici, je veux dire une carte de programmation avec des clés et des valeurs, comme la carte dans...