Algorithme de multiplication de matrice booléenne

Question

Ceci est ma première question sur stackoverflow. J'ai résolu quelques exercices de "Algorithm design" de Goodrich, Tamassia. Cependant, je suis tout à fait ignorant de ce problème. Unusre où commencer et comment procéder. Tout conseil serait bon. Voici le problème:

Les matrices booléennes sont des matrices telles que chaque entrée est 0 ou 1, et la multiplication matricielle est effectuée en utilisant ET pour * et OR pour +. Supposons qu'on nous donne deux matrices booléennes aléatoires A et B NxN, de sorte que la probabilité que toute entrée dans l'une ou l'autre soit 1, soit 1/k. Montrer que si k est une constante, alors il existe un algorithme pour multiplier A et B dont le temps de fonctionnement attendu est O (n^2). Que faire si k est n?

Answer 1

La multiplication matricielle utilisant l'approche itérative standard est O (n), car vous devez parcourir sur n lignes et n colonnes et pour chaque élément multiplier une des lignes et une des colonnes , qui prend n multiplies et n-1 additions.

code Psuedo pour multiplier la matrice A par la matrice b et stocker dans une matrice c:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     int sum = 0; 
     for(m = 0; m < n; m++) 
     { 
      sum += a[i][m] * b[m][j]; 
     } 
     c[i][j] = sum; 
    } 
} 

Pour une matrice booléenne, comme spécifié dans le problème, et est utilisé dans lieu de multiplication et ou à la place de de plus, il devient ceci:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     boolean value = false; 
     for(m = 0; m < n; m++) 
     { 
      value ||= a[i][m] && b[m][j]; 
      if(value) 
       break; // early out 
     } 
     c[i][j] = value; 
    } 
} 

la chose à remarquer ici est qu'une fois que notre booléen « somme » est vrai, nous pouvons arrêter le calcul et le début de la boucle la plus interne, car ORing toutes les valeurs ultérieures avec tru e va produire vrai, donc nous pouvons immédiatement savoir que le résultat final sera vrai.

Pour toute constante k, le nombre d'opérations avant que nous puissions le faire plus tôt (en supposant que les valeurs soient aléatoires) va dépendre de k et n'augmentera pas avec n. A chaque itération, il y aura une chance (1/k) que la boucle se termine, parce que nous avons besoin de deux 1 pour que cela se produise et que la chance de chaque entrée soit de 1/k. Le nombre d'itérations avant de se terminer suivra un Geometric distribution où p est (1/k) , et le nombre attendu d '"essais" (itérations) avant "succès" (rupture de la boucle) ne dépend pas de n (sauf en tant que limite supérieure pour le nombre d'essais), de sorte que la boucle la plus interne s'exécute en temps constant (en moyenne) pour un k donné, rendant l'algorithme global O (n). La formule de distribution géométrique devrait vous donner un aperçu de ce qui se passe si k = n. Notez que dans la formule donnée sur Wikipedia k est le nombre d'essais.