Questions marquées «terminology»

Si vous pouviez renommer la programmation dynamique, comment

Demandez même à une personne ayant une formation en informatique ce qu’est une expression régulière et la réponse ira probablement au-delà de la contrainte d’être à la portée d’un automate à états finis. Par exemple, l'expression «expression régulière» /^1?$|^(11+?)\1+$/ créé par une personnalité...

Dans quelques questions récentes ( q1 q2 ), il y a eu une discussion entre "Théorie A" et "Théorie B", apparemment pour capturer le fossé entre l'étude de la logique et des langages de programmation et l'étude des algorithmes et de la complexité. Cette terminologie était nouvelle pour moi, et une...

Quelqu'un ose-t-il tenter de clarifier quelle est la relation de ces domaines d'études ou peut-être même donner une réponse plus concrète au niveau des problèmes? Comme qui comprend qui en supposant certaines formulations largement acceptées. Si j'ai bien compris, lorsque vous passez de SAT à SMT,...

Comme il n'y a pas eu de réponse à Lambda the Ultimate, je réessaye ici: les systèmes de réécriture de termes sont utilisés par exemple dans un théorème automatisé prouvant un calcul symbolique, et bien sûr pour définir des grammaires formelles. Il existe certains langages de programmation basés...

Y a-t-il des problèmes dans CS où aucun algorithme efficace n'est connu, malgré l'existence de théorèmes prouvant que de tels algorithmes efficaces doivent exister? Comment s'appellent ces problèmes? Où puis-je en savoir

L'une des choses étonnantes de l'informatique est que l'implémentation physique est en quelque sorte «hors de propos». Les gens ont réussi à construire des ordinateurs à partir de plusieurs substrats différents - relais, tubes à vide, transistors discrets, etc. Les gens pourraient bientôt réussir à...

Prenez un graphe orienté où les bords sont décorés d'un nombre naturel. On veut l'ensemble de tous les chemins entre deux sommets et telle sorte que chaque bord successif du chemin soit décoré d'un nombre naturel supérieur au nombre naturel décorant le bord précédent.ggGPPPv1v1v_1v2v2v_2 Une...

Désolé, si c'est une question naïve, mais je n'ai trouvé la justification dans aucun des principaux manuels comme Bondy-Murty, Diestel ou West. Les graphiques parfaits ont de nombreuses propriétés magnifiques, mais quelle est la seule raison pour laquelle ils sont appelés parfaits? Ou est-ce juste...

Cette question concerne la logique propositionnelle et toutes les occurrences de «résolution» doivent être lues comme «résolution propositionnelle». Cette question est quelque chose d'extrêmement basique mais cela me dérange depuis un moment. Je vois des gens affirmer que la résolution...

Pendant longtemps, j'ai pensé qu'un problème était NP-complet s'il était à la fois (1) NP-dur et (2) en NP. Cependant, dans le célèbre article "La méthode ellipsoïde et ses conséquences dans l'optimisation combinatoire" , les auteurs affirment que le problème du nombre chromatique fractionnaire...

Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...

On dit qu'une fonction f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} est constructible dans le temps , s'il existe une machine de Turing déterministe multi-bandes MMM qui sur toutes les entrées de longueur nnn fait au plus f(n)f(n)f(n) pas et pour chaque nnn il existe une entrée de longueur nnn sur...

Cette question n'est peut-être pas technique. En tant que locuteur non natif et TA pour la classe d'algorithmes, je me suis toujours demandé ce que signifie gadget dans «gadget de clause» ou «gadget variable». Le dictionnaire dit qu'un gadget est une machine ou un appareil, mais je ne sais pas...

La seule définition du «calcul» que je connaisse est l'étude des limites, des dérivés, des intégrales, etc. en analyse. Dans quel sens le calcul lambda (ou des choses comme le calcul mu) est-il un "calcul"? Comment est-il lié au calcul dans

J'écoute actuellement le discours d'Alan Kays "Est-ce vraiment complexe ou avons-nous simplement compliqué les choses?" ( https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) où il dit que "les sémaphores étaient une mauvaise idée et il y avait quelque chose appelé pseudo-temps qui était supérieur"...

Je me demande si le problème suivant a un nom ou des résultats qui y sont liés. G=(V,w)G=(V,w)G = (V,w)w(u,v)w(u,v)w(u,v)uuuvvvu,v∈Vu,v∈Vu,v \in Vw(u,v)∈[−1,1]w(u,v)∈[−1,1]w(u,v) \in [-1,1]maxS⊆V∑(u,v):u∈S or v∈Sw(u,v)maxS⊆V∑(u,v):u∈S or v∈Sw(u,v)\max_{S \subseteq V} \sum_{(u,v) : u \in S\...

Nous savons tous que la complexité minimale d'un algorithme de tri basé sur la comparaison est les comparaisons . J'essaie de faire un tri aveugle , c'est-à-dire étant donné un nombre sortie, un circuit (avec des portes booléennes, arithmétiques et de "comparaison") qui trie une liste de...

Un graphique coloré peut être décrit comme un tuple (G,c)(G,c)(G,c) où GGG est un graphique et c:V(G)→Nc:V(G)→Nc : V(G) \rightarrow \mathbb{N} est la coloration. On dit que deux graphes colorés (G,c)(G,c)(G,c) et (H,d)(H,d)(H,d) sont isomorphes s'il existe un isomorphisme π:V(G)→V(H)π:V(G)→V(H)\pi...