Questions marquées «terminology»

16
Langage infini vs langage fini

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...

14
Trouver le XOR max de deux nombres dans un intervalle: peut-on faire mieux que quadratique?

Supposons que l'on nous donne deux nombres et et que nous voulons trouver pour l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r L'algorithme naïf vérifie simplement toutes les paires possibles; par exemple en rubis, nous aurions: def max_xor(l, r) max = 0...

14
Quand

Selon l'article de Wikipedia , le L dans signifie "balayage de gauche à droite" et le "R" signifie "dérivation la plus à droite". Cependant, dans l'article original de Knuth sur les grammaires L R ( k ) , il définit L R ( k ) (à la page 610) comme un langage "traduisible de gauche à droite avec k...

14
Qu'est-ce qu'une «clé» en informatique?

Je suis un peu confus quant à la signification exacte d'une «clé» en informatique. Je comprends les paires clé-valeur, clés primaires, etc ... Mais je ne trouve pas de définition de ce que le terme "clé" signifie par lui-même. Pour autant que je sache, cela signifie simplement une donnée. Dans...