Une application classique de diviser pour mieux régner consiste à résoudre le problème suivant: Étant donné un tableau d'éléments distincts et comparables, comptez le nombre de paires d'inversion dans le tableau: paires telles que et .a[1…n]a[1…n]a[1\dots
Plus à cette question sur le comptage d'inversion , j'ai trouvé un article qui prouve une limite inférieure sur la complexité de l'espace pour tous les algorithmes de streaming (exacts) . J'ai affirmé que cette limite s'étend à tous les algorithmes de temps linéaire. C'est un peu audacieux car en...
J'essaie de m'enseigner l'usage du bison. Le bison de la page de manuel (1) dit à propos du bison: Générez un analyseur syntaxique déterministe LR ou LR généralisé (GLR) en utilisant les tables d'analyseur LALR (1), IELR (1) ou canonique LR (1). Qu'est-ce qu'un analyseur IELR? Tous les articles...
Je suis un homme de 16 ans qui a récemment reçu une grande encyclopédie sur l'informatique par un de mes amis. Je ne suis généralement pas très intéressé par les ordinateurs et la technologie, mais l'informatique a commencé à me fasciner. J'ai cependant l'intention d'étudier la physique et / ou les...
Je comprends que est plus rapide que et plus lent que . Ce qui est difficile à comprendre pour moi, c'est comment comparer réellement et avec où .Θ ( n )Θ(n)\Theta(n)Θ ( n logn )Θ(nJournaln)\Theta(n\log n)Θ ( n / logn )Θ(n/Journaln)\Theta(n/\log n)Θ ( n logn )Θ(nJournaln)\Theta(n \log n)Θ ( n /...
J'ai un certain nombre de questions connexes sur ces deux sujets. Tout d' abord, la plupart des textes de complexité de brillant que sur la classe . Existe-t-il une bonne ressource qui couvre la recherche de manière plus approfondie? Par exemple, quelque chose qui traite de toutes mes questions...
Planar 3SAT est NP-complet. Une instance planaire 3SAT est une instance 3SAT pour laquelle le graphique construit à l'aide des règles suivantes est planaire: ajouter un sommet pour chaque et ¯ x iXjeXjex_iXje¯Xje¯\bar{x_i} ajouter un sommet pour chaque clauseCjCjC_j ajouter un bord pour chaque...
De Wikipedia sur les algorithmes randomisés Il faut distinguer les algorithmes qui utilisent l'entrée aléatoire pour réduire le temps d'exécution prévu ou l'utilisation de la mémoire, mais qui se terminent toujours par un résultat correct dans un laps de temps limité, et les algorithmes...
Supposons que nous ayons un ensemble et que chaque membre de D soit une paire de données et de clés. Nous voulons une structure de données qui prendrait en charge les opérations suivantes:DDDDDD Insérez dans D ,(d,k)(d,k)(d,k)DDD Supprimer le membre , (pas besoin de chercher pour trouver e , par...
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...
Si est en fait égal à , comment cela améliorerait-il nos algorithmes pour factoriser les entiers plus rapidement. En d'autres termes, quel genre d'information cela nous donnerait-il pour mieux comprendre la factorisation des nombres entiers?PP{\sf P}NPNP{\sf
Je voudrais savoir s'il existe une fonction des nombres à n bits aux nombres à n bits qui présente les caractéristiques suivantes:fff fff doit être bijectif Les deux et devrait être assez rapide calculableffff−1f−1f^{-1} fff doit renvoyer un nombre qui n'a pas de corrélation significative avec son...
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...
Je suis un diplômé non-CS et mon domaine d'études n'est pas lié à CS. Cependant, dans le cadre d'un projet plus vaste visant à devenir informaticien, je souhaite obtenir une solide formation en informatique théorique et en mathématiques en ce qui concerne la CS. J'ai fait de nombreuses recherches...
Ordre d'application: Évaluez toujours complètement les arguments d'une fonction avant d'évaluer la fonction elle-même, comme - (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.X2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda...
Étant donné un tube avec des boules numérotées (aléatoire). Le tube a des trous pour retirer une balle. Considérez les étapes suivantes pour une opération: Vous pouvez choisir une ou plusieurs balles dans les trous et vous souvenir de l'ordre dans lequel vous avez choisi les balles. Vous devez...
J'ai rencontré une expérience étrange en programmation C. Considérez ce code: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Lorsque je compile et exécute ceci, je ne reçois aucune erreur ni avertissement. Comme l'a dit...
Je veux savoir si le problème suivant est décidable: Instance: un NFA A avec n états Question: Existe-t-il un nombre premier p tel que A accepte une chaîne de longueur p. Ma conviction est que ce problème est indécidable, mais je ne peux pas le prouver. Le décideur peut facilement avoir un...
J'ai fait quelques tests de différentes températures initiales dans mon algorithme de recuit de simulation et j'ai remarqué que la température de départ a un effet sur les performances de l'algorithme. Existe-t-il un moyen de calculer une bonne température