La notation Big-O cache des facteurs constants, il existe donc certains algorithmes qui sont impossibles pour toute taille d'entrée raisonnable car le coefficient sur le terme est si énorme.O(n)O(n)O(n)nnn Existe-t-il des algorithmes connus dont le temps d'exécution est mais avec un terme ordre...
Je travaille sur un éditeur de diagrammes. Les diagrammes affichent des formes 2D ( nœuds ) connectées à des connecteurs ( bords ). Je voudrais ajouter une opération qui, étant donné une sélection de nœuds, les "démêle" : elle les repositionne pour réduire le nombre d'arêtes croisées, si possible...
Mon problème est comme ceci: J'ai une disposition physique représentée sous forme de graphique. Les nœuds représentent des crochets / conduits où un fil peut ancrer et les bords sont la connexion possible entre 2 nœuds d'où le fil peut aller. Il existe des nœuds spéciaux, appelés séparateurs, à...
Considérez les programmes linéaires D u a l : → c ≤ → y T APr i m a l :A x⃗ ≤ b⃗ max c⃗ TX⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} D u a l :c⃗ ≤ y⃗ TUNEmin...
Introduction et notations: Voici une version nouvelle et simple de mon algorithme qui semble se terminer (selon mes expériences), et maintenant je voudrais le prouver. Soit la notation faire référence à un point de données dimensionnelles (un vecteur). J'ai trois ensembles A, B et C, tels que , , :...
Je cherche un algorithme pour convertir un digraphe (graphe orienté) en graphe non orienté de manière réversible, c'est-à-dire que le digraphe devrait être reconstructible si on nous donne le graphe non orienté. Je comprends que cela se fera au détriment du graphique non orienté ayant plus de...
D'après la preuve de Miller-Rabin , si un nombre passe le test de primalité de Fermat , il doit également passer le test de Miller-Rabin avec la même base (une variable dans la preuve). Et la complexité du calcul est la même.uneunea Ce qui suit est tiré du test de primalité de Fermat : Alors que...
Si alors la hiérarchie s'effondre à son deuxième niveau (par le théorème de Karp-Lipton). Mais qu'en est-il de N P et de c o N P ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP J'ai essayé de prouver que est contenu dans N P (l'autre sens est trivial si R P = N P ) mais en vain, et je ne suis même...
Une relation d'équivalence sur un ensemble de sommets finis peut être représentée par un graphique non orienté qui est une union disjointe de cliques. L'ensemble des sommets représente les éléments et une arête indique que deux éléments sont équivalents. Si j'ai un graphe et des graphes , on dit...
Étant donné deux symboles et , nous allons définir les -ème chaîne de Fibonacci comme suit:aa\text{a}bb\text{b}kkk F(k)=⎧⎩⎨baF(k−1)⋆F(k−2)if k=0if k=1elseF(k)={bif k=0aif k=1F(k−1)⋆F(k−2)else F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2)...
Vous avez nnn bâtons de longueurs arbitraires, pas nécessairement intégrales. En coupant quelques bâtons (une coupe coupe un bâton, mais nous pouvons couper aussi souvent que nous le voulons), vous voulez obtenir
Je me demande, existe-t-il une méthode d'analyse automatique de l'exécution qui fonctionne au moins sur un sous-ensemble pertinent d'algorithmes (algorithmes pouvant être analysés)? Je googlé « Analyse de l' algorithme automatique » qui m'a donné ce mais il est MATHY aussi. Je veux juste un exemple...
L'algorithme de Dijkstra est-il utilisé dans les systèmes modernes de recherche d'itinéraire tels que Google Maps ou le GPS dans votre voiture? Sinon, qu'est-ce que
Le problème est le suivant: Nous avons un tableau / grille de nombres en deux dimensions, chacun représentant un «avantage» ou un «profit». Nous avons également deux entiers fixes et (pour "largeur" et "hauteur"). Et un entier fixe .h nwwwhhhnnn Nous souhaitons maintenant superposer rectangles de...
Il existe un moyen d'effectuer une analyse floue (accepte les chaînes même avec des fautes de frappe à une certaine distance d'édition), avec un DFA et un automate Levenshtein construit au moment de l'exécution du mot d'entrée. Peut-on faire quelque chose de similaire avec un analyseur Earley? J'ai...
J'ai récemment lu une entrée de blog très intéressante de Google Research Blog sur le réseau neuronal. Fondamentalement, ils utilisent ces réseaux de neurones pour résoudre divers problèmes comme la reconnaissance d'image. Ils utilisent des algorithmes génétiques pour "faire évoluer" les poids des...
Étant donné un ensemble de points et un rayon . Quelle est la complexité de trouver le point avec un plus grand nombre de points à une distance inférieure à . Par exemple, celui qui maximise ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2rrrrrr∑ni = 11∥ x - xje∥ ≤ r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n...
J'implémente un algorithme Naive Bayes pour la catégorisation de texte avec lissage laplacien. Le problème que j'ai est que la probabilité approche de zéro parce que je multiplie de nombreuses petites fractions. Par conséquent, la probabilité donne finalement zéro. En effet, il y a plusieurs mots...
Je lis le document de Turing "Computing machines and intelligence" ( https://www.csee.umbc.edu/courses/471/papers/turing.pdf ) et j'ai trouvé un fragment dans lequel il dit: J'ai installé sur l'ordinateur de Manchester un petit programme utilisant seulement 1 000 unités de stockage, par lequel la...
Supposons que j'ai deux chaînes. Appelez - les et . Aucune chaîne n'a de caractères répétés.UNEAABBB Comment puis-je trouver la séquence la plus courte d'opérations d'insertion, de déplacement et de suppression qui transforme en , où:BUNEUNEABBB insert(char, offset)insère charau donné offsetdans la...