Questions qui demandent de l'aide pour développer l'intuition pour des concepts formels ou complexes.
Je pense avoir une compréhension raisonnable des complexités telles que , et .Θ ( n ) Θ ( n 2 )O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) En termes de liste, est une recherche constante, donc il ne fait que prendre la tête de la liste. est l'endroit où je parcourrais toute la...
Je comprends la preuve de l'indécidabilité du problème d'arrêt (donnée par exemple dans le manuel de Papadimitriou), basée sur la diagonalisation. Bien que la preuve soit convaincante (j'en comprends chaque étape), elle n'est pas intuitive pour moi en ce sens que je ne vois pas comment quelqu'un la...
Cette question a été inspirée par un commentaire sur StackOverflow . En plus de connaître les problèmes NP-complets du livre Garey Johnson, et bien d'autres; existe-t-il une règle empirique pour savoir si un problème ressemble à un problème NP-complet? Je ne cherche pas quelque chose de rigoureux,...
Je suis un étudiant diplômé suivant un cours de théorie du calcul et j'ai de la difficulté à produire du contenu une fois qu'on me le demande. Je suis en mesure de suivre le manuel (Introduction à la théorie du calcul de Michael Sipser) et les conférences; Cependant, lorsqu'on me demande de prouver...
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...
Je pensais avoir bien compris la saisie dépendante (DT), mais la réponse à cette question: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% B6f-to-create-intuitionistic-type-theory m'a fait penser le contraire. Après avoir lu sur DT et essayé de comprendre ce qu'ils sont, j'essaie de me...
Ci-dessous, supposons que nous travaillons avec une machine de Turing à bande infinie. En expliquant la notion de complexité temporelle à quelqu'un et pourquoi elle est mesurée par rapport à la taille d'entrée d'une instance, je suis tombé sur la revendication suivante: [..] Par exemple, il est...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
J'obtiens la preuve de passer d'un énumérateur à une machine de Turing (continuez à exécuter l'énumérateur et voyez si cela correspond à l'entrée) mais je ne vois pas comment fonctionne l'autre sens. Selon mes notes et le livre (Intro to the Theory of Computation - Sipser), pour obtenir...
Étant donné un langage , comment dire directement, sans regarder les règles de production, que ce langage n'est pas régulier?L={anbncn}L={anbncn} L= \{a^n b^n c^n\} Je pourrais utiliser le lemme de pompage mais certains gars disent juste en regardant la grammaire que ce n'est pas normal. Comment...
J'ai lu de nombreux documents sur la convolution dans le traitement d'image, et la plupart d'entre eux parlent de sa formule, de certains paramètres supplémentaires. Personne n'explique l'intuition et la véritable signification de la convolution sur une image. Par exemple, l'intuition de la...
Je ne suis pas sûr de le voir. D'après ce que je comprends, les arêtes et les sommets sont des compléments l'un pour l'autre et il est assez surprenant que cette différence existe. Existe-t-il un bon moyen / rapide / facile de voir qu'en fait, trouver un chemin hamiltonien devrait être beaucoup...
Si vous avez une langue L, sans faire de preuves, existe-t-il un moyen de savoir si elle est reconnaissable ou co-reconnaissable ou décidable? Fondamentalement, tous les conseils ou astuces qui peuvent être utilisés pour le dire. Ou peut-être les modèles communs à rechercher pour savoir de quel...