Je comprends que l'utilisation de DFS "tel quel" ne trouvera pas le chemin le plus court dans un graphique non pondéré. Mais pourquoi modifier DFS pour lui permettre de trouver les chemins les plus courts dans les graphiques non pondérés est-il une perspective désespérée? Tous les textes sur le...
Je ne suis pas certain de l'utilisation des expressions langage "infini" ou langage "fini" en théorie informatique. Je pense que la racine du problème est qu'un langage comme est infini dans le sens où il peut générer un nombre infini (mais dénombrable) de chaînes. Pourtant, il peut encore être...
Je me demande si cela est encore possible, puisque {anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL} . Par conséquent, un PDA qui peut distinguer un mot w∈{anbncn∣n≥0}w∈{anbncn∣n≥0}w\in\{a^n b^n c^n \mid n \geq 0\} du reste de {a∗b∗c∗}{a∗b∗c∗}\{a^*b^*c^*\} pourrait...
Dans cette question, nous considérons uniquement les machines Turing qui s'arrêtent sur toutes les entrées. Si k∈Nk∈Nk \in \mathbb{N} alors par TkTkT_k on désigne la machine de Turing dont le code est kkk . Considérez la fonction suivante
Je suis récemment devenu extrêmement intéressé par la compréhension et la démonstration d'aspects des langages de programmation (fonctionnels). Cependant, alors que je plonge plus profondément, des choses comme calcul, la théorie des catégories et la sémantique dénotationnelle sont un peu...
J'ai quelques objets avec priorité qui sont de type composé et qui ne sont que partiellement ordonnés . Je dois sélectionner les objets dans l'ordre de cette priorité (c.-à-d. Produire un élément minimal à chaque fois). Mais plutôt que de terminer arbitrairement la commande, je préférerais que la...
On dit que le langage est dense s'il existe un polynôme tel que pour tous lesEn d'autres termes, pour une longueur donnée, il n'existe que de nombreux mots polynomiaux de longueur qui ne sont pas enJ⊆Σ∗J⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|Jc∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N.n \in...
Dans de nombreuses discussions sur le tas binaire, seule la touche de diminution est normalement répertoriée comme opération prise en charge pour un tas min. Par exemple, CLR chapitre 6.1 et cette page wikipedia . Pourquoi la clé d'augmentation n'est-elle pas normalement répertoriée pour le segment...
J'ai utilisé FSM dans les conceptions de circuits séquentiels numériques. Mais je ne connais pas les automates finis. Quelqu'un peut-il m'aider à comprendre la différence «fondamentale» entre les deux?
Une question d'entretien courante consiste à fournir un algorithme pour déterminer si un arbre binaire donné est équilibré en hauteur (définition de l'arbre AVL). Je me demandais si nous pouvions faire quelque chose de similaire avec les arbres rouges-noirs. Étant donné un arbre binaire non coloré...
Donné est un graphe planaire et soit dénoter son encastrement dans le plan st chaque arête a la longueur . J'ai en outre un ensemble de points où chaque point est contenu dans . De plus, il tient pour tout point dans qu'il existe un avec une distance géodésique à au plus un. (La distance est...
Pourquoi avons-nous besoin de retourner le noyau en convolution 2D en premier lieu? Quel est l'avantage de cela? Alors, pourquoi ne pouvons-nous pas le laisser intact? http://www.songho.ca/dsp/convolution/convolution2d_example.html contribution noyau production "D'abord, retournez le noyau, qui est...
Considérez la question 1C de Google Code Jam suivante : La Grande Muraille de Chine commence comme une ligne infinie, où la hauteur à tous les endroits est de .000 Certains nombre de tribus , N ≤ 1000 , va attaquer la paroi de la paroi en fonction des paramètres suivants : - une date de début, D ,...
Je voudrais créer un système d'apprentissage automatique en ligne sur le Web, où les utilisateurs peuvent continuellement ajouter des échantillons classifiés et mettre le modèle à jour en ligne. Je souhaite utiliser un perceptron ou un algorithme d'apprentissage en ligne similaire. Mais, les...
Je viens d'apprendre récemment l'existence de cette mémoire temporelle hiérarchique (HTM) . J'ai déjà lu le document Hierarchical Temporal Memory: Concepts, Theory and Terminology (par Jeff Hawkins et Dileep George), qui semble assez facile à comprendre, mais un drapeau rouge est que le document...
Lorsque nous utilisons A * (ou tout autre meilleur algorithme de recherche de chemin), nous disons que l'heuristique utilisée doit être admissible , c'est-à-dire qu'elle ne doit jamais surestimer la longueur (ou les déplacements) réels du chemin de la solution. Comment une heuristique admissible...
J'ai appris que l'unité de traitement graphique a ce qu'on appelle la fusion de mémoire. À la lecture, je n'étais pas clair sur le sujet. Est-ce que cela est lié au parallélisme au niveau de la mémoire? J'ai cherché dans Google mais je n'ai pas pu obtenir de réponse satisfaisante. Il serait utile...
On dit que l'intersection d'un langage L sans contexte avec un langage M normal est toujours sans contexte. J'ai compris la preuve de la construction de produits croisés, mais je ne comprends toujours pas pourquoi elle est sans contexte mais pas régulière. Le langage généré par une telle...
Lorsque nous regardons le modèle d'acteur et les processus séquentiels communicants, nous voyons qu'ils essaient tous les deux de faire de la concurrence basée sur le passage de messages , mais ils sont distincts . (Nous voyons des implémentations du modèle CSP dans les goroutines de go-lang (et...
Pourquoi utilisons-nous d'autres bases qui ne sont ni binaires (pour les ordinateurs) ni décimales (pour les humains)? Les ordinateurs finissent par les représenter en binaire, et les humains préfèrent fortement obtenir leur représentation décimale. Pourquoi ne pas s'en tenir à ces deux...