Algorísmia


Algorismes probabilístics (aleatorització)

Probabilitat

        Esperança                                                Moment d’ordre r

                                

Moments factorials d’ordre r                                Moment central d’ordre r

        

Variància                                                Esperança d’una funció

                                

Linealitat de les esperançes de dues variables

, excepte si X i Y són independents

, excepte si Xi i Y són indepenents

Distribucions de probabilitat

X~Binomial(n, p)        

        

X1~Bernoulli(p)

                

Demostració alternativa de la variància:

                        

                

X~Geomètrica(p)

Desigualtat de Markov

Si X és una variable aleatòria positiva i , llavors .

Demostració:

 

                        

Desigualtat de Chebyshev

Per a tota variable aleatoria X,

Demostració:

  1. Y és positiva

Generació aleatòria de permutacions

----------------------------------------------------------------------

for (int i = 1; i <= n; ++i) {

int u;

        do {

                u = random(1, n);

        } while (u està en v[1..i-1]);

        v[i] = u;

}

----------------------------------------------------------------------

Cost de l’algorisme:

La probabilitat de trobar un nombre en cada pas és: 1 | 1-1/n | 1-2/n | etc.

        ~Geom()

        

        on

~

(Un algorisme millor seria el de Floyd, que consisteix en començar amb una permutació qualsevol i llavors aleatoriament anar intercanviant parells d’elements).

QuickSort aleatoritzat

 (nota: les variables no són independents)

                        

                Amb i<j,

amb  (quan j=1, j’=2; quan j=n, j’=n-i+1)

Test de primalitat

Petit teorema de Fermat: si p és primer, llavors per tota a, , .

Test RM (Rabin-Miller):

Donat un nombre n, podem elegir un nombre a en [1..n-1] a l’atzar i comprovar  L’exponenciació  requereix  productes. Si la resposta és no, sabem que el nombre no és primer. Si és sí, és possible que sigui primer (hi ha una certa probabilitat d’error).

Nombre de Carmichael: un nombre compost N és un nombre de Carmichael si i només si per tota a, , .

Per comprovar la primalitat podem fer:

Lema Sigui N un nombre compost que no és de Carmichael, és a dir, existeix alguna a, , tal que . Sigui a un coprimer de N (és a dir, gcd(m, n)=1) tal que . Llavors  per com a mínim  elements.

Dem Si  passa el test (), llavors  no passa el test ().

És a dir, si existeix algun nombre que digui “no” al test, la meitat dels nombres diran “no”.

Per saber si un nombre és de Carmichael, agafem un N compost i impar:

a) ,

b) sigui el menor valor de  tal que , si  ,

c) en cas contrari, és un nombre primer.

                

                

        

Rabin-Karp string search

                

                

----------------------------------------------------------------------

// Cost en cas pitjor: O(n·m)

// Cost esperat: O(m)+O(n-m)+O(m·E[# positius])

//                # positius ~ Binomial(n-m, Pr{positiu})

//                E[#positius] = (n-m)·Pr{positiu}

//                Pr{positiu} <~ 1/q

//                Cost esperat: O(m)+O(n)+O(nm/q) ~= O(n+m)  (normalment q > m)

int b = # símbols de l’alfabet;

int m = P.size();

int n = T.size();

long h = calcula_factor(m, b, q); // h = b^(1-m) mod q

int p = 0; int t = 0;

for (int i = 1; i <= m; ++i) {

        p = (b*p + P[i]) % q;

        t = (b*t + T[i]) % q;

}

for (int i = 0; i <= n-m; ++i) {

        if (p == t) {

                if (P[1..m] == T[i+1..i+1+m])

                        return “occurència de P en T, en la posició i+1”

        }

        if (p < n-m) {

                t = (b*(t-h*T[i+1])+T[i+2+m]) % q;

        }

}

----------------------------------------------------------------------

Universal hashing

 és una classe universal de hashing

si i només si per a qualsevol , si agafem una funció  a l’atzar

llavors .


        

        p és un nombre primer i l’utilitzem de base

                                

        

                

                

Estructures de dades avançades

Bloom filters

És una estructura de dades per comprovar la presència d’un element. Consisteix en un vector de booleans. Tenim k funcions de hash diferents amb imatge 0..M-1. Per cada element, calculem els seus k hashs i els marquem com a certs a la taula. Per comprovar si hi és, comprovem que les k caselles del vector estiguin marcades; si alguna no ho està, no hi és (si les k caselles ho estan, pot ser que hi estigui o no - hi ha falsos positius). No és possible esborrar elements d’un filtre de Bloom (això es pot solucionar utilitzant comptadors en lloc de flags cert/fals).

Probabiliat que el bit  estigui a 0 després d’ insercions:

Probabilitat que tots els k bits consultats estiguin a 1 ( la probabilitat de falsos positius):

                 ()

Si  (amb M i k constants): .
Si
 (amb n i k constants): .

        

                

Skip lists

(Alternativa als AVL amb llistes enllaçades; més fàcils d’implementar).

----------------------------------------------------------------------

struct node {

        T info;

        vector<node*> next;

}

node *header;

int height;

bool contains(const T& x) {

        node *p = header;

        int l = height;

        while (l > 0) {

                if (p->next[l] != NULL and p->next[l]->info <= x)

                        p = p->next[l];

                else

                        --l;

        }

        return p->info == x;

}

void insert(const T& x) {

        node *p = header;

        int l = height;

        vector<node *> u(l);

        while (l > 0) {

                if (p->next[l] != NULL and p->next[l]->info <= x)

                        p = p->next[l];

                else

                        { u[l] = p; --l; }

        }

        n = new node(x);

        if (n->l > height) {

        /* 1) augmentar l’altura de la skip list

         * 2) redimensionar el header i posar els nous apuntadors a NULL

         * 3) redimensionar el vector u i possar els nous apuntadors al header

         * */

        }

}

// Per trobar l’altura d’un node:

{

        // 0 < p << 1

        n->l = 0;

        do {

                (n->l)++;

                double u = random(0, 1);

        } while (u <= p);

}

----------------------------------------------------------------------

                        

                        

                

                

        

Arbres binaris de cerca aleatoritzats (RBST)

Són un tipus d’arbre binari de cerca. Recordem els diferents tipus d’ABC:

----------------------------------------------------------------------

typedef struct node* RBST;

RBST randomized_insert(T, x) {

        if (T == NULL)

                return new node(x);

        int u = random(0, T->sz);

        if (u == 0) return insert_root(T, x);

        else if (x < T->inf)

                T->left = randomized_insert(T->left, x);

        else

                T->right = randomized_insert(T->right, x);

}

insert_root(T, x) {

        split(T, X, T-, T+);

        //
        //

        node *n = new node(x);

        x->left = T-;

        x->right = T+;

        x->sz = 1 + T-->sz + T+->sz;

        return x;

}

----------------------------------------------------------------------

 (cost esperat)
        (altura esperada)

Arbres k-dimensionals

Cost d’un “partial match”:

                s = # de coordenades especificades

                k = # de dimensions        

L’últim terme d’ depèn de la manera de triar si es parteix x o y en cada punt. La millor manera (amb ) es tallar sempre la direcció més llarga.

En dos dimensions: .

Quadtrees

Són arbres k-dimensionals amb més de dos fills per node (per a k=2, cada node té 4 fills, és a dir, divideix l’espai en 4 quadrants).

Metric Trees / Vantage Point Trees (VP-T)

Burkhard-Keller Tree (BK-T)

GHT