Supposons que l'on nous donne un tableau contenant des entiers non négatifs (pas nécessairement distincts).A[1..n]A[1..n]A[1..n] Soit un trié dans l'ordre non croissant. Nous voulons calculer A m = max i ∈ [ n ] B [ i ] + i .BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. La...
Je recherche des ressources (de préférence un manuel) sur des sujets avancés en algorithmes (sujets au-delà de ce qui est couvert dans les manuels d'algorithmes comme CLRS et DPV). Le type de matériel qui peut être utilisé pour enseigner un sujet dans un cours d'algorithmes comme le cours d'Erik...
Existe-t-il un moyen documenté de calculer les nœuds? (circonférences incrustées dans un espace euclidien tridimensionnel). Je veux dire, un type de données pour les représenter, et un algorithme pour déterminer si deux instances du type de données représentent le même nœud. Si la réponse est...
Considérons un graphe (le problème est logique à la fois pour les graphes orientés et non orientés). Appelons M G la matrice des distances de G : M G [ i , j ] est la distance de chemin la plus courte du sommet i au sommet j dans G pour une certaine fonction d'agrégation fixe (par exemple + ou max...
La fonction inverse d'Ackermann se produit souvent lors de l'analyse des algorithmes. Une excellente présentation en est ici: http://www.gabrielnivasch.org/fun/inverse-ackermann . et [Notation: [x] signifie que nous arrondissons x à l'entier le plus proche, tandis que log ∗ est la fonction de...
Je me demandais quelle est la liste des problèmes informatiques naturels actuels pour lesquels il n'y a aucun avantage de complexité connu à utiliser un ordinateur quantique. Pour commencer, je pense que le calcul de la distance d'édition est celui pour lequel l'algorithme quantique connu le plus...
Dans une formule CNF opposée en lecture deux, chaque variable apparaît deux fois, une fois positive et une fois négative. Je m'intéresse au problème , qui consiste à calculer la parité du nombre d'assignations satisfaisantes d'une formule CNF opposée lue deux
On dit que deux groupes et sont isomorphes s'il existe un homomorphisme de en qui est bijectif. Le problème d'isomorphisme de groupe est le suivant: étant donné deux groupes, vérifiez s'ils sont isomorphes ou non. Il existe différentes façons de saisir un groupe, les deux plus utilisées sont par...
La nature diviser pour mieux régner de la FFT peut-elle être généralisée à d'autres transformations (Transformation z, gazouillis, etc.) automatiquement? Existe-t-il un algorithme qui prend une description de la transformation (je ne sais pas quelles informations seraient nécessaires) et peut...
Soit un graphe connecté non régulier dont le degré est borné. Supposons que chaque nœud contienne un jeton unique.G=(V,E)G=(V,E)G= (V, E) Je veux mélanger uniformément les jetons parmi le graphique en utilisant uniquement des swaps locaux (c'est-à-dire l'échange des jetons entre deux nœuds...
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...
Salut à tous, j'essaie actuellement de trouver un sujet de thèse de master solide se rapportant à une branche de la théorie des automates ou lié aux langages formels. J'essaie de générer de bonnes idées sur ce qu'est un sujet acceptable, quelque chose d'ambitieux mais quelque chose de faisable en...
Je recherche une fonction de hachage sur les ensembles H (.) Et une relation R (.,.) Telle que si A est inclus dans B alors R (H (A), H (B)). Bien sûr, R (.,.) Doit être facile à vérifier (temps constant), et H (A) doit être calculé en temps linéaire. Un exemple de H et R est:...
J'ai cherché sur le forum pour voir si cela avait déjà été demandé, et bien que la théorie algorithmique des jeux soit discutée, je n'ai pas trouvé ce problème particulier résolu. J'essaie de comprendre quel est l'algorithme le plus connu pour calculer les équilibres de Nash approximatifs (à...
Disons que j'ai un graphique pondéré G=(V,E,w)g=(V,E,w)G = (V,E,w) tel que w:E→[−1,1]w:E→[-1,1]w:E\rightarrow [-1,1] est la fonction de pondération - notez que les poids négatifs sont autorisés. Dire que f:2V→RF:2V→Rf:2^V\rightarrow \mathbb{R} définit une propriété d'un sous - ensemble de sommets...
Motivation: dans les algorithmes standard de débit maximal de chemin d'augmentation, la boucle interne nécessite de trouver des chemins de la source au puits dans un graphique orienté et pondéré. Théoriquement, il est bien connu que pour que l'algorithme se termine même lorsqu'il existe des...
Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF . EDIT 30 e mars 2011 question n ° 2. Ajouté EDIT 29 e octobre 2010 Question reformulée après proposition András...
Étant donné un digraphe G fortement connecté avec des bords pondérés, je voudrais identifier des bords qui ne font manifestement pas partie d'un sous-graphique minimal fortement connecté (MSCS) de G. Une méthode pour trouver de tels bords est un algorithme de Floyd-Warshall modifié. En utilisant...
Une transaction de base de données classique simplifiée peut être considérée comme: lecture de M éléments effectuer un calcul basé sur ces lectures écrire quelques résultats N basés sur ces calculs, qui peuvent inclure les éléments lus à l'origine. Lors de l'exécution de ces transactions...
J'ai une question de faisabilité qui peut être formulée comme suit. On me donne un point dans un espace vectoriel dimensionnel, et je veux trouver le point le plus proche de qui satisfait un ensemble de " contraintes" de la formed q p ℓ 0pppdddqqqpppℓ0ℓ0\ell_0 Étant donné un ensemble , au plus l'un...