Je lis cet article bien connu sur les univers en théorie des types . Au début, je m'attendais à quelque chose de similaire à SetωAgda, mais il s'avère que c'est même quelque chose de plus général. Il semble généraliser la construction de l'univers d'un simple type inductif-récursif à un liant...
Il existe un théorème qui dit que: Etant donné un automate à états finis ayant états, s'il existe une chaîne dont la longueur satisfait alors le langage accepté par l'automate est infini.nnnwwwn ≤ | w | ≤ 2 n - 1n≤|w|≤2n-1n \leq |w| \leq 2n-1 Je comprends la contrainte , mais je ne comprends pas...
La grammaire non contextuelle suivante présente une ambiguïté de type "balançant le reste" (imaginez que représente et b représente et c représente un autre type d'instruction ou de bloc): Saaaif expr thenbbbelseccc Par exemple,aacbcpeut être analysé comme(a(acbc))ou comme(a(ac)bc)(c'est le mot...
Dans Spanner, TrueTime & The CAP Theorem , Eric Brewer écrit: Une chose subtile à propos de Spanner est qu'il obtient la sérialisation des verrous, mais il obtient la cohérence externe (similaire à la linéarisation ) de TrueTime [non souligné dans l'original ]. Quelle est la définition de la...
Étant donné que: Un langage avec des systèmes de type très expressifs (par exemple Idris ) peut également avoir des mécanismes d'échappement comme des interfaces de fonctions étrangères / unsafePerformIO. Il existe des assistants de preuve qui peuvent être utilisés pour prouver certaines propriétés...
Dans Girard's Proofs and Types, nous pouvons lire: D'un point de vue algorithmique, le calcul séquentiel n'a pas d'isomorphisme de Curry-Howard, en raison de la multitude de façons d'écrire la même preuve. Cela nous empêche de l'utiliser comme un -calculus typé, bien que nous apercevions une...
Étant donné une matrice booléenne , soit entrées représentent la mer et entrées représentent la terre. Définissez un îlot comme verticalement ou horizontalement (mais pas en diagonale) adjacent entrées.X 0 1 1n×mn×mn \times mXX\mathrm X000111111 La question initiale était de compter le nombre...
De nombreuses classes de complexité ont des problèmes "complets". Existe-t-il des problèmes complets pour la classe de complexité des problèmes qui peuvent être résolus en temps ?O(1)O(1)O(1) Une complication est que cette classe dépend du modèle de calcul; un problème peut être résolu en temps...
Où puis-je trouver du code pour générer des promenades auto-évitables aléatoires sur des réseaux à 2 et 3 dimensions dont les longueurs latérales sont des puissances de deux? La marche doit passer par tous les points du réseau Plus précisément, comment puis-je trouver un chemin hamiltonien...
J'ai essayé de démêler les définitions de la sécurité des types et de la solidité des types et j'en ai un sacré moment. J'ai demandé à un professeur récemment et après un peu de réflexion, il a dit qu'il n'y avait vraiment aucune différence. Cependant, après avoir lu cela, il semble que: La...
En supposant que les bords ne sont pas orientés, ont un poids unique et aucun chemin négatif, ces algorithmes produisent-ils les mêmes arbres couvrant
Une déclaration du théorème de Rice est donnée à la page 35 de "Complexité computationnelle: une approche moderne" (Arora-Barak): Une fonction partielle de {0,1}∗{0,1}∗\{0,1\}^* à {0,1}∗{0,1}∗\{0,1\}^* est une fonction qui n'est pas nécessairement définie sur toutes ses entrées. On dit qu'un TM MMM...
Je travaille sur un problème lié aux carrés latins, et je veux une méthode pour ce qui se résume essentiellement au problème de décision: Entrée : Un graphe fini et simple G. Sortie : YESsi G a un automorphisme non trivial, NOsinon. Par conséquent... Question : Existe-t-il un algorithme efficace...
Je vois de nombreux problèmes algorithmiques qui réduisent toujours à quelque chose de long: Vous avez un tableau entier h[1..n]≥0h[1..n]≥0h[1..n]\geq 0 , vous devez trouver i,ji,ji,j tel que maximise (h[j]−h[i])(j−i)(h[j]−h[i])(j−i)(h[j]-h[i])(j-i) en temps O(n)O(n)O(n) . Évidemment, la solution...
Je viens tout juste de découvrir KRR (représentation des connaissances et raisonnement) et ASP, sans en avoir entendu parler auparavant (sauf un peu sur prolog). J'ai lu un peu à leur sujet et l'un de leurs principaux usages semble être les IA. Ma question serait de savoir à quel point ASP ou...
Le problème est de prouver ou de réfuter l'existence de CCC , st, ; ; . ( signifie hamming distance)| c | = 6 , ∀ c ∈ C|c|=6,∀c∈C|c| = 6,\forall c\in C| C| =32|C|=32|C| = 32ré( cje, cj) ≥ 2 , 1 ≤ i < j ≤ 32d(ci,cj)≥2,1≤i<j≤32d(c_i,c_j)\geq2,1\leq
J'ai rencontré ce problème et j'ai du mal à trouver un moyen de l'aborder. Toutes les pensées seraient grandement appréciées! Supposons que l'on nous donne une matrice , par exemple,{ - 1 , 0 , 1 }n × k {−1,0,1}n × k\{-1, 0, 1\}^{n\ \times\ k} ⎡⎣⎢⎢⎢⎢⎢⎢1- 10- 11001- 101010000010- 11- 11-...
Il existe plusieurs OOO -Notations, comme O(n)O(n)O(n) ou O(n2)O(n2)O(n^2) et ainsi de suite. Je me demandais s'il y avait des variations de celles en réalité commeO(2n2)O(2n2)O(2n^2) or O(logn2)O(logn2)O(\log n^2), or if those are mathematically incorrect. Or would it be a right thing to say that...
Je travaille sur le livre Sipser (2e édition) et suis tombé sur cet exemple, que je ne comprends pas. Dans le livre, il indique que ce NFA accepte la chaîne vide,ϵϵ\epsilon. Quelqu'un pourrait-il m'expliquer pourquoi c'est le cas? Ma compréhension est que ϵϵ\epsilon se déplacera vers q3q3q_3 qui...
Il est souvent indiqué (par exemple dans Wikipedia ) que le temps d'exécution de la recherche en largeur (BFS) sur un graphique est . Cependant, tout graphe connecté a | V | \ leq | E | +1 et, même dans un graphe non connecté, BFS ne regardera jamais un sommet en dehors du composant qui contient le...