Je lisais une question sur Stack Overflow demandant si c'était NP- difficile de lister tous les cycles simples dans un graphique contenant un nœud particulier et il m'est venu à l'esprit que je ne pouvais penser à aucune classe de complexité existante qui était bien adaptée pour parler de problèmes...
Je suis un étudiant universitaire en informatique ayant une grande passion pour étudier les mathématiques. Je suis fermement convaincu que l'informatique ou l'informatique théorique est une branche directe des mathématiques et de la logique et je suis également d'avis qu'un diplôme en informatique...
Au moins en Java, si j'écris ce code: float a = 1000.0F; float b = 0.00004F; float c = a + b + b; float d = b + b + a; boolean e = c == d; la valeur de serait . Je crois que cela est dû au fait que les flotteurs sont très limités dans la manière de représenter avec précision les nombres. Mais je ne...
Voulez-vous améliorer ce post? Fournissez des réponses détaillées à cette question, y compris des citations et une explication de la raison pour laquelle votre réponse est correcte. Les réponses sans suffisamment de détails peuvent être modifiées ou supprimées. Il existe souvent des langages de...
Y a-t-il eu des recherches sur la complexité de la preuve d'une résolution du problème P = NP? Sinon, étant donné le manque de progrès sur le problème, serait-il déraisonnable de supposer que toute preuve qui résout le problème P = NP nécessitera un nombre d'étapes
Nous avons une grille N1× N2N1×N2N_1 \times N_2 . Nous avons une collection de rectangles sur cette grille, chaque rectangle peut être représenté en tant que N1N1N_1 -by- N2N2N_2 matrice binaire RRR . Nous voulons couvrir la grille avec ces rectangles. La version de décision de cet ensemble de...
On m'a dit que nous utiliserions une liste si le graphique est clairsemé et une matrice si le graphique est dense . Pour moi, c'est juste une définition brute. Je ne vois pas grand-chose au-delà. Pouvez-vous préciser quand serait-ce le choix naturel à faire? Merci
Un ensemble est dénombrable s'il a une bijection avec les nombres naturels et est numériquement calculable (ce) s'il existe un algorithme qui énumère ses membres. Tout ensemble non finissable pouvant être énuméré doit être dénombrable puisque nous pouvons construire une bijection à partir de...
Supposons que vous ayez un tableau de taille contenant des entiers de à inclus, avec exactement cinq répétitions. J'ai besoin de proposer un algorithme qui puisse trouver les nombres répétés en temps . Je ne peux, pour ma vie, penser à rien. Je pense que le tri, au mieux, serait ? La traversée du...
Il existe des temps spatiaux relativistes (par exemple des temps spatiaux MH; voir Hogarth 1994) où une ligne du monde de durée infinie peut être contenue dans le passé d'un observateur fini. Cela signifie qu'un observateur normal peut avoir accès à un nombre infini d'étapes de calcul. En supposant...
J'ai l'impression que pour chaque problème NP-complet, pour une infinité de tailles d'entrée , le nombre d'instances oui sur toutes les entrées possibles de taille n est (au moins) exponentiel en n .nnnnnnnnn Est-ce vrai? Peut-il être prouvé (probablement uniquement en supposant que )? Ou...
Quelqu'un dans une discussion a évoqué (il estime) qu'il peut y avoir au moins un nombre continu de stratégies pour aborder un problème spécifique. Le problème spécifique était les stratégies de trading (pas les algorithmes mais les stratégies) mais je pense que c'est à côté du point de ma...
J'ai rencontré un algorithme pour résoudre un problème du monde réel, et je me souviens d'un cours que j'ai pris où j'ai fait quelque chose de très similaire pour certains pour un problème de devoirs. Fondamentalement, c'est un tracé de points, et les lignes sont dessinées pour être équidistantes...
J'ai écrit ∑i = 1n1je= ∑i = 1nO (1)= O (n)∑je=1n1je=∑je=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) mais mon ami dit que c'est faux. De la feuille de triche TCS, je sais que la somme est également appelée qui a une croissance...
Le problème de bande passante minimale consiste à trouver un ordre des nœuds de graphique sur une ligne entière qui minimise la plus grande distance entre deux nœuds adjacents. Le problème de décision est NP-complet même pour les arbres binaires. Résultats de complexité pour la minimisation de la...
Je cherchais des problèmes ouverts intéressants et faciles à énoncer en calculabilité (compréhensibles par les étudiants de premier cycle prenant leur premier cours en calculabilité) pour donner des exemples de problèmes ouverts (et, évidemment, je veux que les étudiants puissent comprendre le...
Les algorithmes et les structures de données sans cache sont une nouveauté introduite par Frigo et al. dans Cache-inconscient algorithmes, 1999 . La thèse de Prokop de la même année présente également les premières idées. L'article de Frigo et al. présentent quelques résultats expérimentaux...
Soit GGG une grammaire sans contexte. Une chaîne de terminaux et de nonterminals est dit être une forme propositionnelle de si vous pouvez l' obtenir en appliquant des productions de zéro fois ou plus au symbole de début de . Let l'ensemble des formes phrastiques de
J'essaie de prouver qu'un arbre binaire avec nnn nœuds a au plus ⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceilfeuilles. Comment pourrais-je procéder avec l'induction? Pour les personnes qui suivaient la question initiale sur les tas, elle a été déplacée ici
J'expliquais à un ami le célèbre algorithme de sélection déterministe du temps linéaire ( algorithme de la médiane des médianes). La récursivité dans cet algorithme (tout en étant très simple) est assez sophistiquée. Il existe deux appels récursifs, chacun avec des paramètres différents. J'essayais...