Ma mère suit un cours en ligne afin d'être une sorte de bibliothécaire, dans ce cours, ils couvrent les recherches booléennes, afin qu'ils puissent rechercher des bases de données efficacement, cependant, elle a reçu une question ressemblant à ceci: La recherche «x OU y» donnera 105 000 résultats,...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Il est bien connu que le 2-SAT est en P. Cependant, il semble assez intéressant que de compter le nombre de solutions pour une formule 2-SAT donnée, c'est-à-dire que # 2-SAT soit # P-difficile. Autrement dit, nous avons un exemple d'un problème pour lequel la décision est facile, mais le calcul est...
Soit un problème de comptage connu pour être # -Complete .PΠΠ\PiPPP Cela implique-t-il que est -hard (c'est-à-dire qu'il n'y a pas de PTAS pour le problème sauf si )?A P X P = N
É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...
Je travaille sur les orientations acycliques des graphes non orientés et j'ai les questions suivantes: Étant donné le graphe simple non orienté connecté , comment trouver toutes les orientations acycliques possibles de ?ggGggG Quel est le nombre d'orientations acycliques? Il est connu (d' ici )...
Laisser MMM être un NFA acyclique. Depuis MMM est acyclique, L(M)L(M)L(M) est fini. Pouvons-nous calculer |L(M)||L(M)||L(M)| en temps polynomial? Sinon, pouvons-nous l'approcher? Notez que le nombre de mots n'est pas le même que le nombre de chemins d'acceptation dans MMM, qui est facilement...