Selon cet article de Wikipedia , les grammaires illimitées sont équivalentes aux machines de Turing. L'article note que je peux convertir n'importe quelle machine Turing en une grammaire illimitée, mais il montre uniquement comment convertir une grammaire en machine Turing. Comment puis-je vraiment...
Dans de nombreuses implémentations de recherche en profondeur d'abord que j'ai vues (par exemple: ici ), le code fait la distinction entre un sommet gris (découvert, mais pas tous ses voisins ont été visités) et un sommet noir (découvert et tous ses voisins ont été visités) . Quel est le but de...
Je m'intéresse à la question du temps d'exécution asymptotique de l'algorithme d'Ukkonen , peut-être l'algorithme le plus populaire pour construire des arbres de suffixes en temps linéaire (?). Voici une citation du livre "Algorithmes sur les chaînes, les arbres et les séquences" de Dan Gusfield...
Parfois, il est facile d'identifier la complexité temporelle d'un algorithme en l'examinant attentivement. Les algorithmes avec deux boucles imbriquées de sont évidemment . Les algorithmes qui explorent toutes les combinaisons possibles de groupes de deux valeurs sont évidemment .N 2 N 2...
Construisons deux fonctions satisfaisant:f,g:R+→R+f,g:R+→R+ f,g: R^+ → R^+ f,gf,gf, g sont continus; f,gf,gf, g augmentent de façon monotone; g ≠ O ( f )f≠O(g)f≠O(g)f \ne O(g) et .g≠O(f)g≠O(f)g \ne O(f)
Supposons que nous recevions des nombres dans un flux. Après la réception de chaque numéro, une somme pondérée des derniers chiffres doit être calculée, où les poids sont toujours les mêmes, mais arbitraires.NNN Dans quelle mesure cela peut-il être fait efficacement si nous sommes autorisés à...
Comment puis-je trier une liste de 5 entiers de telle sorte que dans le pire des cas, il faut 7 comparaisons? Je me fiche du nombre d'autres opérations qui sont effectuées. Je ne sais rien de particulier sur les entiers. J'ai essayé différentes approches de division et de conquête qui me ramènent à...
Dans l'étude Complexity of the Frobenius Problem de Ramírez-Alfonsín, un problème s'est révélé être NP-complet en utilisant les réductions de Turing. Est-ce possible? De quelle façon précisément? Je pensais que cela n'était possible que par une réduction polynomiale de plusieurs fois. Y a-t-il des...
Serait-il possible pour un environnement d'exécution de détecter des boucles infinies et d'arrêter par la suite le processus associé, ou la mise en œuvre d'une telle logique équivaudrait-elle à résoudre le problème d'arrêt? Aux fins de cette question, je définis une «boucle infinie» pour désigner...
Le langage d'assemblage est converti en langage machine par l'assembleur. Pourquoi un compilateur convertirait-il un langage de haut niveau en assembleur? Ne peut-il pas convertir directement du langage de haut niveau en code
Les structures de données persistantes sont des structures de données immuables. Les opérations sur eux renvoient une nouvelle "copie" de la structure de données, mais modifiée par l'opération; l'ancienne structure de données reste cependant inchangée. L'efficacité est généralement obtenue en...
Dans certains articles (historiques), les échecs ont été appelés la drosophile de l'intelligence artificielle. Bien que je suppose que dans la recherche actuelle, la simple application d'un algorithme de recherche est au mieux une science informatique avancée , je pense qu'il existe encore des...
Je regardais la conférence de Jim Weirich, intitulée « Aventures dans la programmation fonctionnelle ». Dans cette conférence, il présente le concept de combinateurs Y, qui trouve essentiellement le point fixe pour les fonctions d'ordre supérieur. L'une des motivations, comme il le mentionne, est...
Je lisais sur la programmation dynamique lorsque je suis tombé sur la citation suivante Un algorithme de programmation dynamique examinera toutes les façons possibles de résoudre le problème et choisira la meilleure solution. Par conséquent, nous pouvons grosso modo penser la programmation...
L' algorithme Ramer-Douglas-Peucker pour la simplification de ligne a le pire cas d' exécution . Pour des entrées aléatoires convenablement réparties, il s'est attendu à une complexité d'exécution O ( n log n ) . En 2D, il existe d'autres algorithmes avec la pire complexité d'exécution O ( n log n...
Sous Linux, les fichiers /dev/randomet les/dev/urandom fichiers sont les sources bloquantes et non bloquantes (respectivement) d'octets pseudo-aléatoires. Ils peuvent être lus comme des fichiers normaux: $ hexdump /dev/random 0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa 0000010 5652 1f08 ccb8...
Les verrous sont généralement implémentés via des instructions de test et de configuration et d'échange au niveau de la machine. Y a-t-il d'autres implémentations qui ne les utilisent pas? Aussi, pouvons-nous dire que toutes les solutions de niveau matériel au problème de la section critique...
Je cherche des exemples de problèmes qui ont une borne inférieure de Ω(|x|2Ω(|x|2\Omega(|x|^2 ) pour l'entrée xxx . Le problème doit avoir les propriétés suivantes: Ω(n2)Ω(n2)\Omega(n^2)Preuve d'exécution Ω ( n 2 ) pour tout algorithme - la première priorité est d'avoir un argument de limite...
Avec le temps des fêtes qui approche, j'ai décidé de faire des étoiles à la cannelle . C'était amusant (et le résultat savoureux), mais mon nerd intérieur a grincé des dents lorsque j'ai mis le premier plateau d'étoiles dans la boîte et elles ne tenaient pas dans une seule couche: Presque! Y a-t-il...
Supposons que vous obtenez un nombre (en utilisant bits dans le codage binaire).mmmO(logm)O(logm)O(\log m) À quelle vitesse pouvez-vous trouver (ou déterminer qu'il n'existe pas) n,k∈N,1<k≤n2:(nk)=mn,k∈N,1<k≤n2:(nk)=mn,k\in \mathbb N,