Vogliamo trovare un algoritmo per determinare se un numero in input \(n\) e' primo. Una soluzione inefficiente testa tutti gli interi fra \(2\) e \(\sqrt{n}\).

boolean isPrimeNaif(int n)
  for i=1 to sqrt(n) do
    if n/i == floor(n/i) then
      return false
  return true

Per migliorare l'algoritmo possiamo ricordare il piccolo teorema di Fermat che dimostra che se \(n\) e' primo, allora:

\[\forall b,2\le b < n:\ b^{n-1}mod\ n=1\]

Allora:

boolean isPrime1(int n)
  b = random(2, n-1)
  if b^{n-1} mod n != 1 then
    return false
  return true

Tuttavia esistono dei numeri composti che non sono primi ma rispettano la condizione. Infatti il piccolo teorema di Fermat non e' un se e solo se: se il numero e' primo allora la condizione vale, ma non il contrario. Dobbiamo sfruttare un altro risultato teorico per migliorare l'algoritmo.

Miller-Rabin: Se \(n\) e' primo, allora per ogni intero \(b\), con \(2\le b < n\) valgono entrambe le seguenti condizioni:

• \(mcd(n, b)=1\)
• \(b^m\ mod\ n = 1\lor \exists i, 0\le i < v:b^{m2^i}mod\ = n-1\)

con \(n-1=m2^v\), \(m\) dispari.

Contrapposizione: Se esiste un intero \(b\) con \(w\le b < n\) tale che almeno una delle seguenti condizione e' vera:

• \(mcd(n, b)\neq 1\)
• \(b^m\ mod\ n\ne 1 \land \forall i, 0\le i

allora \(n\) e' composto.

boolean isPrime(int n)
  for i =1 to k do
    b=random(2, n-1)
    if isComposize(n, b) then
      return false
  return true

Complessità: \(O(klog^2(n)log(log(n))log(log(log(n))))\). Rabin ha dimostrato che se \(n\) e' composto allora ci sono almeno \((n-1)^{3/4}\) testimoni in \([2, ..., n-1]\). Il test di compostezza ha una probabilità inferiore a \(1/4\) di rispondere erroneamente.

Data un'espressione algebrica polinomiale \(p(x_1, ..., x_n)\) in \(n\) variabili, determinare se \(p\) e' identicamente nulla oppure no. Una funzione polinomiale è identicamente nulla se è uguale a zero per ogni valore della variabile indipendente, \(p(x)=0\ \forall x\in D\).

Algoritmo:

• Si genera una $n$-pila di valori \(v_1, ..., v_n\)
• Si calcola \(x=p(v1, ..., v_n)\)
  • Se \(x\neq 0\), \(p\) non e' identicamente nulla
  • Se \(x=0\), \(p\) potrebbe essere identicamente nulla
• Se ogni \(v_i\) e' un valore intero casuale compreso fra \(1\) e \(2d\) dove \(d\) e' il grado del polinomio, allora la probabilita' di errore non supera \(\frac{1}{2}\).
• Si ripete \(k\) volte, riducente la probabilita' di errore a \((\frac{1}{2})^k\).

Alcune strutture dati utili viste in precedenza sono:

• Bit set: si usa un solo bit per oggetto ma bisogna avere una elenco prefissato di oggetti
• Tabelle hash: struttura dinamica ma alta occupazione di memoria

Introduciamo ora i Bloom filters, struttura dinamica con bassa occupazione di memoria, ma elementi non possono essere cancellati e non si ha memorizzazione con una risposta probabilistica.

Le funzioni che possiamo chiamare sono:

• \(insert(key)\): Inserisce l'elemento \(key\) nel bloom filter
• \(boolean\ contains(key)\): se restituisce false allora l'elemento \(key\) e' sicuramente non presente nell'insieme. Se restituisce true l'elemento \(key\) può essere presente oppure no (falsi positivi).

Sia \(\epsilon\) la probabilità di falso positivo. I bloom filter richiedono \(1.44log_2(\frac{1}{\epsilon})\) bit per elemento inserito.

Implementazione: si ha un vettore booleano \(A\) si \(m\) bit, inizializzato a false e \(k\) funzioni hash \(h_1, h_2, ..., h_k:U\rightarrow [0, m-1]\).

insert(key)
  for i=1 to k do
    A[h_i(key)]=true

boolean contains(key)
  for i=1 to k do
    if A[h_i(key)]==false then
      return false
  return true

Qualche formula ora senza dimostrazione:

• Dati \(n\) oggetti, \(m\) bit, \(k\) funzioni hash, la probabilità di un falso positivo e' pari a \(\epsilon (1-e^{\frac{-kn}{m}})^k\)
• Dati \(n\) oggetti e \(m\) bit, il valore ottimale per \(k\) e' pari a \(k=\frac{m}{n}\ln2\)
• Dati \(n\) oggetti e una probabilità di falsi positivi \(\epsilon\), il numero di bit \(m\) richiesti e' pari a \(m=-\frac{n\ln\epsilon}{(\ln2)^2}\)

Dato un array \(A\) contenente \(n\) valore e un valore \(1\le k \le n\), trovare l'elemento che occuperebbe la posizione \(k\) se il vettore fosse ordinato.

Da notare che il problema di trovare la mediana e' equivalente al problema della selezione con \(k=\frac{n}{2}\)

Ovviamente possiamo ordinare il vettore e prendere il valore in posizione \(k\), con costo \(O(nlogn)\). Per piccoli valori di \(k\) si potrebbe invece create un heap e poppare il min finché non arriviamo al $k$-appesimo min.

Un'approccio potrebbe essere utilizzare il quick sort assumendo che la probabilità di scegliere un numero come pivot sia la stessa tra tutti i numeri del vettore. A questo punto si può dimostrare che il tempo medio e' \(O(n)\).

Item selection(Item[] A, int start, int end, int k)
  if start==end then
    return A[start]
  else
    int j = pivot(A, start, end)
    int q = j-start+1
    if k==q then
      return A[j]
    else if k < q then
      return selection(A, start, j-1, k)
    else
      return selection(A, j+1, end, k-q)

---

Travel: Algoritmi, Index