Algoritmos aleatorizados

Algoritmos aleatorizados ou algoritmos probabilísticos usam bits aleatórios como uma entrada auxiliar para realizar a computação. A idéa é obter algoritmos mais rápidos e/ou mais simples para problemas computacionais, mas em alguns casos são a única solução conhecida. Aleatoriedade é muito útil na vida moderna:

Uma transação entre Naufrago.com.br (S) e Consumidor (C):

  1. S sorteia dois números primos {P} e {Q}, determina {N = P\cdot Q};S determina um par {(e,d)} tal que {e\cdot d ~\mathrm{mod} ~(P-1)(Q-1) = 1};
  2. S envia {(N,e)} pra C mas {P}, {Q} e {d} são mantidos em segredo;
  3. se {X} é o número do cartão de crédito de C, que envia {X^e ~\mathrm{mod} ~N} pra S;
  4. S recupera o número: {X= (X^e ~\mathrm{mod} ~N)^d ~\mathrm{mod} ~N}.

Um espião poderia tentar achar {d} por força bruta, mas levaria mais de uma vida pra testar todas as possibilidades. (mais informações aqui e aqui)

Além de criptografia, aleatoriedade é importante para quebra de simetria em problemas de sincronização, como jantar dos filósofos.   Os primeiros algoritmos aleatorizados foram para testar primalidade (nos anos 70), não se conhecia algoritmo determinístico de tempo polinomial até o AKS (30 anos depois). Ainda assim, os teste porbabilísticos são muito confiáveis e muito (muito) mais rápidos, ainda são úteis.

No manual do MAXIMA encontramos (http://maxima.sourceforge.net/docs/manual/en/maxima_31.html):

Function: primep (n)
Primality test. If primep (n) returns false, n is a composite number and if it returns true, n is a prime number with very high probability.For n less than 341550071728321 a deterministic version of Miller-Rabin’s test is used. If primep (n) returns true, then n is a prime number.

For n bigger than 341550071728321 primep uses primep_number_of_tests Miller-Rabin’s pseudo-primality tests and one Lucas pseudo-primality test. The probability that n will pass one Miller-Rabin test is less than 1/4. Using the default value 25 for primep_number_of_tests, the probability of n beeing composite is much smaller that 10^-15.

Option variable: primep_number_of_tests
Default value: 25Number of Miller-Rabin’s tests used in primep.

e no manual do MATHEMATICA encontramos

  • PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
  • As of 1997, this procedure is known to be correct only for n<10^(16), and it is conceivable that for larger n it could claim a composite number to be prime.
  • The Primality Proving Package contains a much slower algorithm that has been proved correct for all n. It can return an explicit certificate of primality.

Modelos probabilísticos de computação tem aplicações muito interessantes como as Provas com Conhecimento Zero em que dois algoritmos, Alice e Bob, executam um protocolo para Alice convencer Bob que conhece uma senha sem efetivamente mostrar essa senha, veja aqui uma ilustração muito interessante desse protocolo.

A seguir daremos dois exemplos de algoritmo aleatorizado (se quiser mais comece por aqui).

Seleção aleatorizado. O problema é: Dada uma lista S de inteiros, determinar o k-ésimo menor. Um solução simples é ordenar e devolver S[k], mas ordenar é um trabalho extra que pode ser evitado.

Dado uma sequência de números S = (xi, . . . ,xf )
Devolve o k-ésimo menor elemento de S.

 1 se |S|=1 então devolva x1;

 2 seja x um elemeto escolhido aleatoriament em S;

 3 para cada y em S faça

 4         se y < x então insira y em S1;

 5         senão insira y em S2;

 6 se |S1|<k então devolva recursivamente o k-|S1| ésimo menor elemento de S2;

 7 senão, devolva recursivamente o k ésimo menor elemento de S1.

(O laço da linha 3 é um particionamento como feito no quicksort) Se escolhas ruim forem feitas então esse algoritmo realiza O(n^2) comparações, mas na média ele é linear; aqui média é sobre os sorteios na linha 2 e não sobre uma distribuição nas instâncias como é feito na análise de caso médio de algoritmos determinísticos. A probabiladade do algoritmo acima não sortear o pivô dentre os 10% menores elementos de S nem entre os 10% maiores elementos de S é \frac 45, nesse caso dizemos que o sorteio foi bom. O número esperado de sorteios até ocorrer um que seja bom é 54 (explicação aqui), portanto a cada (no máximo) 2 sorteios em média, ocorre um sorteio bom, portanto, a cada (no máximo) 2  particionamentos em média o tamanho do vetor é reduzido em 10%, logo o número esperado  de comparações é

\displaystyle c(n) \leq c\left( \frac{9n}{10}\right) +n

o que pode ser provado, por indução, que o número esperado de comparações é  c(n) = O(n).

Vejamos que a mesma estratégia funiona para o quicksort, agora faremos uma análise mais precisa e mostramos que não só o tempo médio é O(n\log n) como esse tempo ocorre com altíssima probabilidade.

Quicksort aleatorizado. O quicksort é um algoritmo de ordenação que, grosso modo, funciona da seguinte maneira: dado uma sequência {S} de números, quicksort{(S)} compara o primeiro elemento, que é chamado pivô, com cada outro elemento de {S}; os elementos menores que o pivô formam a subsequência {S_1} e os maiores que o pivô formam a subsequência {S_2}; devolva a sequência {(\mathit{quicksort}(S_1),\mathrm{piv\hat{o}},\mathit{quicksort}(S_2))}.

O quicksort foi inventado por C. A. R. Hoare em 1960 e é muito rápido em geral, mas é lento em algumas raras instâncias especiais. O algoritmo tem complexidade de ordem {n\log n} em média e a {n^2} no pior caso. É sabido que para garantir tempo {O(n\log n)} é suficiente garantir que as subsequências geradas no pivoteamento tenham sempre uma fração constante do tamanho da sequência que as origina. Por exemplo, se {S_1} sempre tem 10% do tamanho de {S} então o tempo gasto pelo quicksort numa instância de tamanho {n} é dada, aproximadamente, pela equação de recorrência {T(n) = T(0,1n)+T(0,9n)+n} cuja solução é é uma função assintoticamente limitada por {n\log_{10/9} n}. Para conhecer esses fatos com mais detalhes sugerimos ao leitor uma consulta ao [CLR]. A figura abaixo ilustra um exemplo de pior caso e um exemplo de melhor caso da árvore de recursão para uma sequência de tamanho 6.

A esquerda temos uma árvore de recursão do quicksort onde o pivô é a mediana da sequência. A árvore da direita é o caso onde o pivô é sempre o menor elemento da sequência.

Na versão probabilística do quicksort a aleatoriedade é usada para descaracterizar o pior caso no sentido de que escolhendo pivô como qualquer elemento da sequência com grande chance evitamos os 10% menores e os 10% maiores elementos do vetor de modo que maior parte do tempo os pivoteamentos garantem pelo menos uma fração constante da sequência original no menor lado.

Nesta seção vamos mostrar que, com essa estratégia, o número esperado de comparações entre elementos de {S} é {O( n \log n)} com alta probabilidade.

Vamos supor que na entrada não há repetição, ou seja, todos os elementos de {S} são distintos. O seguinte algoritmo é o quicksort aleatorizado.

Dado uma sequência de números S = (x1, x2, . . . ,xn )
Devolve os elementos de S ordem crescente.

 1 se |S|= 1 então devolva(S);

 2 senão

 3     seja x um elemeto escolhido aleatoriament em S;

 4     para cada y em S , y diferente de x faça

 5         se y < x então insira y em S1;

 6         senão se y > x insira y em S2;

 7               senão insira y em Sx;

 8 ordene, recursivamente, S1 e S2;

 9 devolva (S1, Sx, S2) .

O particionamento (ou pivoteamento) de {S} nas linhas 3, 4, 5 e 6 do algoritmo acima, é considerado um sucesso se {\min\{|S_{1}|,|S_{2}|\}\geq ({1/10})|S|}, caso contrário, dizemos que o particionamento foi um fracasso. Não há nada de especial na escolha de {{1/10}}. Discutimos acima que se uma proporção for mantida no particionamento, digamos que a menor parte tem uma fração {\alpha} da entrada, então a recorrência {t(n)\leq t(\lfloor{\alpha n}\rfloor) + t(\lfloor{(1-\alpha)n}\rfloor) + cn} para constantes {\alpha,c>0} tem solução {O(n\log n)}.

Assim, cada particionamento é um experimento de Bernoulli com parametro {p}. Um sucesso ocorre se a escolha aleatória {x\in_{\mathrm{R}} S} não é um elemento dentre os 10% maiores elementos de {S} nem um dos elementos dentre os 10% menores, ou seja, 80% dos elementos de {S} são boos escolhas para {x}, portanto, a probabilidade de sucesso é de {{4/5}}.

Exercício 1 Mostre que um elemento da entrada participa de no máximo {\lfloor{\log_{ {10}/{9}} n}\rfloor} particionamentos com sucesso.

Consideremos uma execução do quicksort com entrada {S=x_1,x_2,\dots,x_n}. Seja {X_{i}} o número de comparações entre o elemento {x_i} da entrada e algum pivô durante toda uma execução do algoritmo. Em cada particionamento {x_i} é comparado uma única vez (com o pivô); notemos que se {x_{i}} é escolhido pivô então ele nunca mais participará de um particionamento e nunca mais será comparado com outro elemento de {S}. Assim, o número total de comparações durante toda execução é {X=\sum_{i=1}^{n}X_{i}}.

Fixemos {i\in\{1,2,\dots,n\}}. Se {Y_{k}} é o número de particionamentos ocorridos entre o {k}-ésimo particionamento com sucesso (exclusive) do qual {x_i} participa e o próximo particionamento com sucesso (inclusive) do qual {x_{i}} participa, então Y_{k} tem distribuição geométrica com parâmetro p, em que {p = 4/5}, logo o valor esperado para Y_k é  {\mathop{\mathbb E} Y_{k} < 2}. Ainda, pelo exercício 1 um elemento da entrada participa de no máximo {\lfloor{\log_{10/9} n}\rfloor} particionamentos com sucesso, logo

\displaystyle X_{i} = \sum_{k= 1}^{\rfloor{\log_{\frac {10}9} n}\lfloor}Y_{k}.

Pela linearidade do valor esperado

\displaystyle   \mathop{\mathbb E} X_{i} < 2\lfloor{\log_{\frac {10}9} n}\rfloor ~\quad \textrm{e} ~\quad \mathop{\mathbb E} X < 2n \lfloor{\log_{\frac {10}9} n}\rfloor \ \ \ \ \ (1)

Com isso, provamos o seguinte.

Lema 1 O número esperado de comparações numa execução do quicksort aleatorizado sobre uma entrada com {n} elementos é {O(n\log n)}. {\Box}

É sabido, da Análise de Algoritmos [CLR] que todo algoritmo de ordenação baseado em comparação faz no mínimo da ordem de {n\log n} comparações para ordenar {n} elementos, ou seja, em média o quicksort aleatorizado é o melhor possível. Porém, saber que um algoritmo é bom em média, não nos garante que ele é bom quase-sempre. Vamos mostrar que com alta probabilidade o desempenho do algoritmo está próximo da média, isto é, para quase-toda instância o número de comparações está próximo da média (e bem longe do pior caso). Vamos provar o seguinte resultado.

Teorema 2 O número de comparações numa execução do quicksort aleatorizado com uma entrada de tamanho {n} é {O(n\log n)} com probabilidade

\displaystyle 1 - O(n^{-6}).

Demonstração: Definimos

\displaystyle  L = \lceil{8 \log_{\frac {10}9} n}\rceil

e consideramos o evento {X_{i} > L}, ou seja, segundo (1) {x_{i}} foi comparado mais do que quatro vezes o valor esperado para o número de comparações realizadas pelo algoritmo entre {x_i} e os pivôs. Teremos {X_{i} > L } se em { L } particionamentos ocorrem menos que { \lfloor{ \log_{10/9} n}\rfloor} sucessos, ou seja, o número de fracassos em {L} particionamentos é pelo menos

\displaystyle  \lceil{8 \log_{\frac {10}9} n}\rceil - \lfloor{ \log_{\frac {10}9} n}\rfloor > {8 \log_{\frac {10}9} n}- \log_{\frac {10}9} n = 7\log_{\frac {10}9} n.

Seja {Z_i} o número de particionamentos com fracasso pelos quais {x_{i}} passa em {L} particionamentos. Então, essa variável tem distribuição binomial {Z_i \sim \mathrm{Bi} \big( L,1-p\big)} com {p = 4/5}. Vamos estimar a probabilidade do evento {Z_i > 7 \log_{10/9} n}, com isso, teremos uma estimativa para a probabilidade de {X_{i} > L}. A probabilidade de ocorrerem {j} fracassos em {L} experimentos é {\binom{L}{j} \left( 1-p \right)^{j} p^{L -j}}, portanto,

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}\left(Z_i \geq 7\log_{\frac {10}9} n\right) &\leq& \sum_{j\geq \lceil{7 \log_{\frac {10}9} n}\rceil}\binom{L}{j} \left( 1-p \right)^{j} p^{L -j}\\ &\leq& \sum_{j\geq\lceil{7 \log_{\frac {10}9} n}\rceil}\binom{L}{j} \left( \frac 15 \right)^{j} \\ & \leq&\sum_{j\geq\lceil{7 \log_{\frac {10}9} n}\rceil} \left( \frac{\mathrm{e}L}{5j} \right)^{j} \\ &\leq& \sum_{j\geq\lceil{7 \log_{\frac {10}9} n}\rceil} \left( \frac{\mathrm{e}L }{5\lceil{7\log_{\frac {10}9} n}\rceil} \right)^{j} \end{array}

mas

\displaystyle  \frac{\mathrm{e}\lceil{8\log_{\frac {10}9} n}\rceil}{5\lceil{7\log_{\frac {10}9} n}\rceil} < \frac 25 \cdot \frac{9\log_{\frac {10}9} n}{{8\log_{\frac {10}9} n}} < \frac 9{10}

assim,

\displaystyle  \begin{array}{rcl}  \sum_{j\geq\lceil{7 \log_{\frac {10}9} n}\rceil} \left( \frac{\mathrm{e}\lceil{8\log_{\frac {10}9} n}\rceil}{5\lceil{7\log_{\frac {10}9} n}\rceil} \right)^{j} \leq \sum_{j\geq\lceil{7 \log_{\frac {10}9} n}\rceil} \left( \frac 9{10} \right)^{j} = O(n^{-7}). \end{array}

Portanto, a probabilidade de existir {i} com {X_{i} > \lceil{8 \log_{\frac {10}9} n}\rceil} é

\displaystyle  \mathop{\mathbb P}\left(\bigcup_{i=1}^{n} \left[ X_{i} > \lceil{8 \log_{\frac {10}9} n}\rceil \right]\right) = O(n^{-6}),

logo, com probabilidade {1 - O( n^{- 6} )} vale que { X_{i} \leq 8 \log_{ {10}/9} n} para todo {i} e que, com essa probabilidade, quicksort aleatorizado executa {\leq 8n\log_{ {10}/9} n} comparações entre elementos da entrada. \Box

Probabilidade condicional e independência

Num espaço de probabilidade discreto {(\Omega,\mathop{\mathbb P})}, a probabilidade condicional do evento {E} com respeito ao evento {A}, em que {\mathop{\mathbb P}(A)>0}, é definida por

\displaystyle  \mathop{\mathbb P}(E ~|~ A) = \frac{\mathop{\mathbb P}(A\cap E)}{\mathop{\mathbb P}(A)} \ \ \ \ \ (1)

e {\mathop{\mathbb P}(E ~|~ A)} é lido como a probabilidade de {E} dado {A}.

Exemplo: Dois dados, um azul e outro verde, são lançados e cada uma das seis faces são eqüiprováveis nos dois dados (dizemos que os dados são equilibrados). Qual é a probabilidade do dado verde ter resultado 6 dado que a soma dos resultados foi 8? O espaço amostral tem {36} elementos eqüiprováveis, formado pelos pares ordenados {({azul},{verde})} dos resultados possíveis. O evento “a soma é 8” é {A=\{(2,6),(3,5),(4,4),(5,3),(6,2)\}} logo a probabilidade é {1/5}. De outro modo, {E=\{(x,6)\colon 1\leq x\leq 6,\;x\in{\mathbb N}\}} e

\displaystyle  \mathop{\mathbb P}(E~|~A) = \frac{\mathop{\mathbb P}(A\cap E)}{\mathop{\mathbb P}(A)}= \frac{\mathop{\mathbb P}\left(\big\{(2,6)\big\}\right)}{\mathop{\mathbb P}(A)}= \frac{1/36}{5/36}=\frac 15.

Exercício 2 Sejam {A_{1},A_{2},\dots,A_{n}} eventos num espaço de probabilidade. Prove que

\displaystyle  \mathop{\mathbb P}\left(\bigcap_{i=1}^{n}A_{i}\right)= \mathop{\mathbb P}(A_1)\prod_{j=2}^{n} \mathop{\mathbb P}\left(A_{j}~\bigg|~\bigcap_{i=1}^{j-1}A_{i}\right)

Dizemos que os eventos {A} e {B} em {(\Omega,\mathop{\mathbb P})} são independentes se

\displaystyle   \mathop{\mathbb P}(A\cap B)=\mathop{\mathbb P}(A)\mathop{\mathbb P}(B). \ \ \ \ \ (2)

Uma coleção de eventos {E_{1},\dots,E_{n}} é mutuamente independente se

\displaystyle   \mathop{\mathbb P}\left(\bigcap_{\ell=1}^{n} E_{i}\right)= \prod_{\ell=1}^{k} \mathop{\mathbb P}(E_{i_{\ell}}) \ \ \ \ \ (3)

Exemplo: Considere três lançamentos de uma moeda equilibrada, {E_{12}} é o evento “o resultado da primeira e da segunda coincidem”, {E_{13}} o evento “o resultado da primeira e da terceira coincidem” e {E_{23}} o evento “o resultado da segunda e da terceira coincidem”. Claramente, {\mathop{\mathbb P}(E_{12})=\mathop{\mathbb P}(E_{13})=\mathop{\mathbb P}(E_{23})=1/2}. Os eventos são 2-a-2 independentes, por exemplo, {E_{12}\cap E_{13}=\{ (cara,cara,cara),(coroa,coroa,coroa)\}} com probabilidade {1/4}, entretanto esses eventos não são mutuamente independentes pois {\mathop{\mathbb P}( E_{12}\cap E_{13}\cap E_{23})=1/4\neq \mathop{\mathbb P}( E_{12}) \mathop{\mathbb P}( E_{13}) \mathop{\mathbb P}(E_{23})=1/8}.

Método Monte Carlo para Corte Mínimo

Seja {G=(V,E)} um grafo. Sem perda de generalidade podemos supor que {V=\{1,2,\dots,n\}}. Um subconjunto de arestas de {G} da forma

\displaystyle  E(A,\overline{A})= \Big\{ \{u,v\} \in E(G)\colon u\in A \textrm{ e } v \in \overline{A} \Big\}

é chamado de corte definido por {A} em {G}. Um corte mínimo em {G} é um corte com

\displaystyle \mathrm{mincut}(G) = \min_{\substack{A\subset V \\ \emptyset \neq A \neq V}}\big|E(A,\overline{A})\big|

arestas. O problema que estamos interessados é, dados um grafo {G} determinar {\mathrm{mincut}(G)}.

Um multigrafo é um par {(V,E)} onde {V} é um conjunto finito cujos elementos são chamados de vértices e {E} é um multiconjunto} finito onde cada elemento é chamado de aresta e é formado por dois vértices distintos. Seja {M} um multigrafo. Em {M} definimos por contração da aresta {e}, para qualquer {e\in E(M)}, a operação que resulta no multigrafo com os extremos de {e} identificados e os laços sobre esses extremos removidos, o multigrafo resultante é denotado por {M/e}.

A idéia do algoritmo que apresentaremos a seguir para determinar se {\mathrm{mincut}(G)} é repetir a seqüência de operações

  • sortear aresta,
  • contrair a aresta sorteada,

até que restem 2 vértices. As arestas múltiplas que ligam esses 2 vértices são arestas de um corte no grafo original.

Exercício 3 Prove que após um número qualquer de contrações de arestas, um corte no multigrafo resultante é um corte no grafo original. Conclua que a seqüência de operações {(i)} sortear aresta, {(ii)} contrair a aresta sorteada até que restem 2 vértices num grafo {G} termina com um corte de {G}.

Por exemplo, a figura abaixo representa uma seqüência de três contrações de arestas, a aresta que sofre a contração está em negrito.

Se no próximo passo identificarmos os vértices {1,4,5} com o {2,3} então temos o corte definido por {A=\{6\}} em {G} (fig.~(a)), que tem duas arestas e é um corte mínimo. Por outro lado, se identificarmos {2,3} e {6} então temos o corte definido por {A=\{2,3,6\}} e que tem 4 arestas (fig.~(b)).

O seguinte algoritmo recebe um grafo {G} e um inteiro positivo {k} e responde após {k} rodadas mutuamente independentes da operação sorteia e contrai até restar 2 vértices o tamanho de um corte em {G}.

 Dado : um grafo G com pelo menos 3 vértices e k ∈ N. 
 Devolve: um corte provavelmente mínimo

1   min ← +∞; 

2   repita 

3       i ← 0; 

4       G_0 ← G; 

5       repita 

6           e ← aresta sorteada em E(Gi); 

7           G_{i+1} ← G_i / e; 

8           i ← i + 1; 

9       até que i = n − 2 ;

10      se |E(G_{n−2})| ≤ min então min ← |E(G)|;

11  até que complete k rodadas ;

12  devolva min.

Lema 1 Seja {G} com pelo menos três vértices. Fixado um corte mínimo {C} em {G}, a probabilidade do algoritmo acima determinar {C} no laço interno é pelo menos {1/\binom n2}.

Demonstração: Seja {G=(V,E)} um grafo e {C=E(A,\overline{A})} um corte mínimo em {G} definido por {A\subset V} e com {c} arestas. Notemos que de {\mathrm{mincut}(G) \geq c} o grau mínimo de um vértice em {G} é pelo menos {c} e que, portanto, {G} tem pelo menos {cn/2} arestas. O algoritmo encontra {C} se nas {n-2} iterações somente contrai arestas com ambos os extremos em {A} ou ambos extremos em {\overline A}. O espaço amostral é dado pelas sequências de {n-2} arestas distintas que correspondem as escolhas aleatórias.

Seja {B_{i}} o evento “na {i}-ésima escolha aleatória feita na linha 4, {e\not\in C}”, isto é,

\displaystyle B_i=\{(e_1,\dots,e_{n-2}) \in\Omega \: e_i\not\in C\}.

A probabilidade de escolher uma aresta de {C} na primeira escolha aleatória é {|C|/|E(G_0)| \leq c/(nc/2)}, logo

\displaystyle  \mathop{\mathbb P}(B_{1})\geq 1-\frac{c}{cn/2} = 1-\frac 2n.

Agora, a probabilidade de escolher uma aresta de {C} na segunda escolha, dado que uma aresta de {C} não foi escolhida na primeira, é {|C|/|E(G_1)| \leq c/(c(n-1)/2)} pois o multigrafo tem {n-1} vértice e grau mínimo pelo menos {c}, logo

\displaystyle \mathop{\mathbb P}(B_{2}~|~B_{1})\geq 1-\frac{c}{c(n-1)/2}

e, genericamente,

\displaystyle  \mathop{\mathbb P}\left(B_{i} ~\Big| ~\bigcap_{j=1}^{i-1} B_{j}\right) \geq 1 -\frac{2}{n-i+1}.

A probabilidade de nenhuma aresta escolhida ser de {C} é {\mathop{\mathbb P}\left( \bigcap_{i=1}^{n-2} B_i\right)} e pelo exercício 1 temos que

\displaystyle  \mathop{\mathbb P}\left(\bigcap_{i=1}^{n-2}B_{i}\right) \geq \prod_{i=1}^{n-2} \left( \frac{n-i-1}{n-i+1} \right)= \frac 2{n(n-1)}

e o lema segue da definição de coeficiente binomial. \Box

Corolário A probabilidade do algoritmo
não encontrar um tal corte C em nenhuma das k rodadas do laço
na linha 1 é no máximo

\displaystyle  \left(1-\frac 2{n(n-1)}\right)^k .\Box

o que é quantitativamente razoával para, por exemplo, {k =n^2\log n}. Sabe-se que (1-1/x)^x < 1/e, em que e = 2,71..., portanto quando k = \binom n2 temos probabilidade menor que 1/e < 0,37 de que o corte não seja mínimo. Quando {k = n^2\log n} temos probabilidade menor que (1/e)^{\ln(n)} = \frac 1n de que o corte não seja mínimo.

O repita interno pode ser implementado em tempo {O(n^2)}, portanto o tempo do algoritmo é {O(n^4\log n)}. É possível implementar de modo esperto que resulta em tempo {O(n^2\log^c n)} para uma constante {c>0} [seção 10.2.2 de MOTWANI, Rajeev.; RAGHAVAN, Prabhakar.. Randomized algorithms. Cambridge: Cambridge University, 1995 chamada 004.015192 / MOTr].

Exercicio 4 Seja {G} um multigrafo tal que {\mathrm{mincut}(G)\geq m}. Prove que o grau mínimo de um vértice em {G} é {m} e que {G} tem pelo menos {mn/2} arestas.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s