J'ai un groupe de n ensembles pour lesquels je dois calculer une sorte de valeur "d'unicité" ou de "similitude". J'ai choisi l'indice Jaccard comme une mesure appropriée. Malheureusement, l'indice Jaccard ne fonctionne que sur deux ensembles à la fois. Afin de calculer la similitude entre tous les...
Cela s'est produit alors que j'essayais de répondre à cette question sur la minimisation de la longueur de câblage . J'allais appeler cela le problème du "mariage polygame", mais Internet, donc les chatons. Yay! Supposons que nous ayons MMM chatons qui doivent être adoptées par personnes, . Pour...
L' algorithme de Bellman-Ford détermine le chemin le plus court d'une source à tous les autres sommets. Initialement, la distance entre et tous les autres sommets est définie sur . Ensuite, le chemin le plus court de à chaque sommet est calculé; cela continue pour les itérations . Mes questions...
J'essaie de résoudre un problème de graphique (ce n'est pas pour les devoirs, juste pour pratiquer mes compétences). Un DAG est donné, où est l'ensemble des sommets et les arêtes. Le graphe est représenté comme une liste d'adjacence, donc est un ensemble contenant toutes les connexions de . Ma...
Supposons que l'on nous donne deux nombres et et que nous voulons trouver pour l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r L'algorithme naïf vérifie simplement toutes les paires possibles; par exemple en rubis, nous aurions: def max_xor(l, r) max = 0...
Est-il possible d'utiliser un algorithme de tri avec une comparaison non transitive, et si oui, pourquoi la transitivité est-elle répertoriée comme exigence pour le tri des comparateurs? Contexte: Un algorithme de tri trie généralement les éléments d'une liste selon une fonction de comparaison C...
En faisant le deuxième code kata (qui vous demande d'implémenter cinq fois un algorithme de recherche binaire, à chaque fois avec une méthode différente), j'ai trouvé une solution légèrement différente qui fonctionne comme suit: Si j'ai un tableau trié de longueur 100 et que je vois que son champ...
J'ai le problème: Montrez qu'il existe un nombre réel pour lequel aucun programme n'existe qui s'exécute infiniment long et écrit les chiffres décimaux de ce nombre. Je suppose que cela peut être résolu en le réduisant au problème de l'arrêt, mais je ne sais pas comment le faire. J'apprécierais...
Étant donné un DAG non pondéré (graphique acyclique dirigé) D=(V,A)D=(V,A)D = (V,A) et deux sommets et , est-il possible de trouver le chemin le plus court et le plus long de à en temps polynomial? Les longueurs de trajet sont mesurées par le nombre d'arêtes.ssstttsssttt Je suis intéressé à trouver...
La page wikipedia sur les algorithmes de multiplication en mentionne une intéressante par Donald Knuth . Fondamentalement, cela implique de combiner la multiplication par transformée de Fourier avec une table précalculée de multiplications de taille logarithmique. Il fonctionne en temps linéaire....
Je suis un novice (débutant total à la théorie de la complexité computationnelle) et j'ai une question. Disons que nous avons un «problème du voyageur de commerce», l'application suivante des algorithmes de Dijkstra le résoudra-t-elle? À partir d'un point de départ, nous calculons la distance la...
La programmation dynamique peut réduire le temps nécessaire pour exécuter un algorithme récursif. Je sais que la programmation dynamique peut aider à réduire la complexité temporelle des algorithmes. Les conditions générales sont-elles telles que si elles sont satisfaites par un algorithme...
J'ai implémenté un tri topologique basé sur l'article Wikipedia que j'utilise pour la résolution des dépendances, mais il renvoie une liste linéaire. Quel type d'algorithme puis-je utiliser pour trouver les chemins
D'après ce que j'ai lu dans le preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Voici la définition PTAS : Un schéma d'approximation polynomiale du temps ( PTAS ) pour le...
Je recherche l'algorithme O (V + E) pour trouver la réduction transitive avec un DAG. C'est-à-dire supprimer autant d'arêtes que possible de sorte que si vous pouviez atteindre v à partir de u, pour v et u arbitraires, vous puissiez toujours atteindre après suppression des bords. S'il s'agit d'un...
Étant donné deux chaînes, comment pouvez-vous vérifier si elles sont une permutation l'une de l'autre en utilisant l'espace O (1)? La modification des chaînes n'est en aucun cas autorisée. Remarque: espace O (1) par rapport à la longueur de la chaîne ET à la taille de
Que language soit régulier.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Une factorisation de est une paire maximale d'ensembles de mots avecLL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , où | .X⋅Y={xyX⋅Y={xyX \cdot Y = \{xyx∈X,y∈Y}x∈X,y∈Y}x \in...
En faisant du calcul mental, on peut faire: Étant donné un entier k, additionnez tous les chiffres (en base 10), et si le résultat est un multiple de 3, alors k est un multiple de 3. Connaissez-vous un algorithme fonctionnant de manière similaire mais fonctionnant sur des chiffres binaires (bits)?...
Le tri par fusion est donc un algorithme de division et de conquête. Pendant que je regardais le diagramme ci-dessus, je me demandais s'il était possible de contourner fondamentalement toutes les étapes de division. Si vous parcourez le tableau d'origine en sautant de deux, vous pouvez obtenir les...
Supposons que j'ai un graphe avec M ( G ) le (inconnu) ensemble de couplages parfaits de G . Supposons que cet ensemble ne soit pas vide, alors à quel point est-il difficile d'échantillonner uniformément au hasard à partir de M ( G ) ? Et si je suis d'accord avec une distribution proche de...