Conjectura, RAM e Algoritmos

Prévia do material em texto

Conjectura: afirmação sem demonstração e ninguém fornece uma contra-prova que a 
afirmação é falsa.
-
Caso Base: n=1
1 = 12
Hipótese: n=k
1+3+5+...+(2k-1) = k2
Passo de Indução: n=k+1
1+3+5+...+(2(k+1)-1) = (k+1)2
1+3+5+...(2k-1) + (2(k+1)-1) = (k+1)2
k2 + (2(k+1)-1) = (k+1)2
k2 + 2k+1 = (k+1)2
Ex: 1+3+5+...+(2n-1) = n2○
Princípio da Indução Matemática:-
Técnicas de Demonstração de Teoremas
quarta-feira, 3 de março de 2010
08:02
 Página 1 de P.A.A. 
Random Acces Machine: modelo simplificado-
Instruções executadas sequencialmente (não há concorrência)-
Aritméticos: ADD, SUBTRACT, MULTIPLY, DIVIDE, REMINDER, FLOOR, CEILING○
Movimentação de Dados: LOAD, STORE, COPY○
Controle de Fluxo: JUMP INCONDICIONAL, CHAMA DE SUBROTINA, RETURN○
Há instruções comumente encontradas em computadores reais-
Cada instrução exige uma quantidade de tempo específica-
Tipos de Dados: Inteiro e Float-
Modelo RAM
Em geral, o tempo de execução de um algoritmo é proporcional ao (está em função do) 
tamanho da entrada.
-
Ex: ordenar, de forma crescente, a sequencia "1,2,3,4,5,6" é mais rápido que ordenar 
"6,5,4,3,2,1", na melhor da hipóteses (caso 1) serão feitas n comparações, e na pior 
(caso 2), serão feitas n*n comparações.
○
O formato da entrada influencia no tempo de execução do algoritmo-
Ex: multiplicação de 2 números○
Para muitos problemas, a medida mais natural é o número de itens da entrada. Para muitos 
problemas, a melhor medidade é a quantidade bits necessários para representar a entrada em 
notação binária.
-
Deve-se indicar a medidade do tamanho da entrada que está sendo usada em cada problema 
estudado.
-
Tamanho da Entrada do Problema: quantidade de dados que serão executados no programa
É o conjunto de passos (operações primitivas) executadas pelo algortimo.-
É necessário que seja tão independente de máquina quanto possível.-
Costuma-se adotar uma quantidade de tempo de execução constante "Ci " para cada linha "i".-
Tempo de Execução:
Paradigmas de Projetos de Algortimos
segunda-feira, 8 de março de 2010
10:53
 Página 2 de P.A.A. 
Abordagem Incremental: insere-se aos poucos os valores○
Ordenado o vetor A[1...(j-1)] insere-se um novo item A[j] em seu devido lugar em [1...j]○
Características:-
Entrada: uma sequência com "n" números A[i] = <a1, a2, ... , an>○
Saída: uma permutação <a'1, a'2, ... , a'n> tal que a'1 < a'2 < ... < a'n>○
Dados-
Código Custo Vezes
1. PARA j <- 2 ATÉ N FAÇA
2. KEY <- A[j] 
3. /*insere A[j] na sequência ordenada 
A[1..(j-1)] */
4. i <- j-1
5. ENQUANTO (i>0 E A[i]>KEY) FAÇA
6. A[i+1] <- A[i]
7. i <- i-1
8. FIM ENQUANTO
9. A[i+1] <- KEY
10.FIM PARA
C1
C2
C4
C5
C6
C7
C9
 
N
N-1
N-1
2+3+...+n
(2-1) + (3-1) + ... + 
(n-1)
(2-1) + (3-1) + ... + 
(n-1)
N-1
Tempo de Execução Total:
f(n) = ( C1 * N ) +
 [ C2 * (N-1) ] +
 [ C4 * (N-1) ] +
 [ C5 * (2+3+...+N) ] +
 [ C6 * ((2-1) + (3-1) + ... + (n-1)) ] +
 [ C7 * ((2-1) + (3-1) + ... + (n-1)) ] +
 [ C9 * (N-1) ]
 
 
 
- 1 (Provado por Indução)
 
 
 
(Provado por Indução)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-1 (Provado por Indução)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Tj significa o número de iterações realizadas no loop durante a execução do 
algoritmo

Supondo que:
 + 
 
 
 
 
 
 
 
□
 + 
 
□
 □
a*n+b□
Ɵ(n)□
Tj = 1
Melhor Caso:
Tj = j
Pior Caso:
Algortimo-
Exemplo: Ordenação por Inserção 
Incremental
segunda-feira, 8 de março de 2010
10:51
 Página 3 de P.A.A. 
 + 
 
 
 
 
 
 
 
□
 + 
 
 
 
 
 
 
 
 
 
 
□
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
□
a*n2 + b*n + c□
Ɵ(n2)□
Tj = j
Tj = j/2
Caso Médio:
 Página 4 de P.A.A. 
Conceito: Divide o problema em cários subproblemas similares ao problema original, mas menores. 
Resolve os problemas recursivamente e então combina as soluções para construir a solução do 
problema original.
Divida o problema em certo numero de subproblemas.-
Conquista os subproblemas ao resolvê-los recursivamente. Se os tamanhos dos subproblemas 
são pequenos, resolva-os trivialmente.
-
Combine as soluções dos subproblemas em uma solução para o problema original.-
Envolve 3 passos q cada nível de recursão:
Divida a sequência com itens em 2 subsequências, sendo cada com (n/2) itens.-
Conquista: orndene as 2 subsequências recursivamente usando merge sort. Retorne quando a 
sequência tiver 1 item.
-
A: é um vetor
p: inicial□
q: meio da sequência□
r: final□
p, q, r: índices que numeram os itens do vetor, tal que p<=q<r
merg(A,p,q,r),○
Combine: intercale as 2 subsequências ordenadas para produzir a resposta ordenada. Para 
realizar a intercalação, usa-se o procedimento:
-
O procedimento supõe que os subarrays A[p..q] e A[q+1..r] estão ordenandos. O 
procedimento interncala as 2 sequências para formar o subarray A[p..r]
Tempo de Execução expresso por uma função linear n=r-p+1. O número de itens intercalados-
Algoritmo: Ɵ(n)-
Merge(A,p,q,r)
01. n1 <- q-p+1 Cte
02. n2 <- r-p Cte
03. /*cria vetores L[1..n1+1] e R[1..n2+1]
04. PARA i <- 1 ATÉ n1 FAÇA N1+1
05. L[i] <- A[p+i-1] N1
06. FIM PARA
07. PARA j<- 1 ATÉ n2 FAÇA N2+1
08. R[j] <- A[q+j] N2
09. FIM PARA
10. L[n1 + 1] <- oo Cte
11. R[n2 + 1] <- oo Cte
12. i <- 1 Cte
13. j <-1 Cte
14. PARA k <- p ATÉ r r=p+1
15. SE (L[i] <= R[j]) ENTÃO
16. A[k] <- L[i]
17. i <= i+1
18. SENÃO
Exemplo: Ordenação por Merge segue se maneira estrita o paradigma "Divisão e Conquista".
Divisão e Conquista
segunda-feira, 8 de março de 2010
10:53
 Página 5 de P.A.A. 
18. SENÃO
19. A[k] <- R[j]
20. j <- j+1
21. FIM SE
22. FIM PARA
Melhor Caso: Ω(n lg n)
Pior caso: Ơ(n lg n)
 Página 6 de P.A.A. 
Indução
quarta-feira, 14 de abril de 2010
08:06
 Página 7 de P.A.A. 
Fibonacci
Retorna n;
Se (n <= 1){
}
Retorna Fib(n-1) + Fib(n-2);
Senão{
}
Fib(n){
}
Recursividade
quarta-feira, 14 de abril de 2010
08:07
 Página 8 de P.A.A. 
Exemplo: Encontrar um item numa tabela (verificar seqüencialmente todas as entradas da 
tabela) é chamado de busca linear.
Exemplo: encontrar os divisores de um número natural n.
- Força Bruta / Pesquisa Exaustiva: um algoritmo que enumera sistematicamente todas as 
alternativas possíveis para a solução, e verifica se cada alternativa satisfaz o problema.
Força Bruta
segunda-feira, 12 de abril de 2010
11:14
 Página 9 de P.A.A. 
Backtracking é uma árvore de pesquisa exaustiva, cujos nós correspondem a soluções parciais. 
Percorrer a árvore em direção às folhas corresponde a obter soluções parciais no caminho da 
solução final. Percorrer a árvore das folhas para a raiz corresponde a retroceder 
(backtracking). Para alguma solução parcial geral obtida anteriormente, a partir da qual seja 
interessante prosseguir em direção a outras folhas.
Exemplo: encontrar a saída de um labirinto: segue-se em uma direção, sempre guardando os 
pontos em que haja mais de um caminho a seguir. Ao encontrar o final de uma passagem, 
retorna-se ao último ponto guardado e percorre-se um novo caminho que ainda não havia sido 
percorrido. Fazer isto até sair do labirinto. (um algoritmo Força Bruta voltaria ao início a cada 
tentativa mal sucedida).
Exemplo: 3-coloring: seja o grafo G(V,E), que terão seus vértices coloridos, tal que 2 vértices 
adjacentes não podem ter a mesma cor. O número de soluções possíveis é 3n, onde n é o 
número de vértices.
Se (U=V) então imprima “Coloração Completa”Obtenha um vértice v que não pertença a U
Adicione v a U com cor c
3-cores (G,U)
Se nenhum vizinho de v está colorido com a cor c, então
Fim-Se
Para c<-1 a 3, faça
Fim-Para
Senão
Fim-Se
Inicio
Fim
- Branch and Bound: é uma variação do backtracking para problemas de otimização. Encontrar 
o mínimo ou o máximo de alguma função objetiva.
Exemplo: encontrar o mínimo de cores para coloris um grafo, sendo que vértices adjacentes 
não poder ter a mesma cor.
Se (U=V) então imprima “Coloração Completa”
Obtenha um vértice v que não pertença a U
Adicione v a U com cor c
3-cores (G,U)
Se nenhum vizinho de v está colorido com a cor c, então
Fim-Se
Para c<-1 a 3 m, faça
Fim-Para
Senão
Fim-Se
Inicio
Fim
- Tentativa e Erro / Backtracking: é uma melhoria para a abordagem “Força Bruta”. Durante a 
execução de um algoritmo “Tentativa e Erro”, é gerada uma árvore de subtarefas formada pelos 
possíveis caminhos de desenvolvimento do problema. Um algoritmo do tipo “Backtracking” 
consegue eliminar múltiplas soluções não-ótimas sem ser necessário examiná-las explicitamente. Tal 
melhoria economiza quantidade relevante de recursos que eram gastos analisando soluções 
inválidas.
Backtracking
segunda-feira, 12 de abril de 2010
11:14
 Página 10 de P.A.A. 
Dijkstra: o menor caminho de um vértice para todos os outros. Não funciona com pesos 
negativos
○
Entrada: G(V,A) não orientado, conexo, ponderado, com n vértices
Saída: árvore T
T <- uma aresta de peso mínimo
e <- aresta de peso mínimo incidente a um vértice em T e que não 
forme ciclo em T se adicionada à árvore
T <- T+{e}
Para i<-1 até n-2 faça
Fim-Para
Retorne T
Inicio
Fim
Prim: gradativamente insere-se novos vértices, partindo de qualquer aresta e formando 
o caminho através da escolha da menor aresta dentre as opções de escolha. Sempre 
tomando cuidado para manter a estrutura da árvore (não formar ciclos).
○
Kruskal: gradativamente insere-se novos vértices, escolhendo sempre a aresta de menor 
peso e formando o caminho através da escolha de outras menores arestas, formando 
várias árvores, se necessário. Sempre tomando cuidado para manter a estrutura da 
árvore (não formar ciclos). 
○
Entrada: G(V,A) não orientado, conexo, ponderado, com n vértices
Saída: árvore T
T<- vazia
"Construa uma fila de prioridade F contendo todas as arestas A com 
custos associados"
Insere (v, C)
Para cada vértice v que pertença a V faça
Fim-Para
C<- vazio
(v,w) <- retira(f)
C <- R1 união R2 - R1 - R2
Insere((v,w), T)
Se v e w estão em conjuntos distintos R1 e R2 em C, então
Fim-Se
Enquanto |C| < 1 faça
Fim-enquanto
Retorne T
Inicio
Fim
Árvore geradora minima é uma árvore que percorrerá os vértices○
Exemplo:
- Algoritmos Gulosos: constróem a solução a cada alternativa , sempre escolhendo a próxima que 
ofecere o benefício mais evidente e imediato.
Algortimos Gulosos
segunda-feira, 12 de abril de 2010
11:15
 Página 11 de P.A.A. 
Bellman-Ford: complexidade n3-
Floyd-Warshall: complexidade n3-
Entrada: G(V,A): grafo orientado, ponderado, com (n) vértices, representado pela matriz de adjacência C[n][n]
Saída: C[n][n] alterada
C[i][j] <- min ( C[i][j] , C[i][k] + C[k][j] ) //relaxamento: "sair de i e chegar em j passando por k"
Se (i != j) e (j != k) então
Fim-Se
Para j<-1 até n, faça
Fim-Para
Para i<-1 até n, faça
Fim-Para
Para k<-1 até n, faça
Fim-Para
Retorne C
Início
Fim
C 1 2 3
1 0 4 9
2 ∞ 0 1
3 7 ∞ 0
k i j Alterações
1 1 1 (sem alteração) : i=j
2 (sem alteração)
3 (sem alteração)
2 1 (sem alteração) : j=k
2 (sem alteração) : i=j
3 (sem alteração)
3 1 (sem alteração)
2 Alterado : C[3][2] = 11
3 (sem alteração) : i=j
2 1 1
2
3 Alterado : C[1][3] = 5 
2 1
2
3
3 1
2
3
3 1 1
2
3
2 1
2
3
Conceito: Calcula a solução para todos os subproblemas, partindo dos subproblemas menores para os maiores. Armazena os resultados dos 
subproblemas menores em uma tabela. A resolução dos subproblemas maiores utilizam os resultados dos menores.
É método de Tabulamento (não é um código computacional)Programação Dinâmica
segunda-feira, 12 de abril de 2010
08:00
 Página 12 de P.A.A. 
3 1
2
3
(n3)
Fibonacci-
mem[0] <- 0
mem[1] <- 1
ind <- 1
mem[ind+1] <- mem[ind]+mem[ind-1]
ind <- ind+1
Se (n= ind+1){
}
mem[n]<- fib(n-2)+fib(n-1)
ind<-n
Senão Se (n>ind){
}
Retorne mem[n]
Fib(n)
}
 Página 13 de P.A.A. 
Diferenças entre Paradigmas
Força-Bruta Backtracking Branch-and-Bound
Testa todas as opções e, se não obter 
sucesso, voltará ao início para tentar as 
outras opções.
Testa todas as opções e, se não obter 
sucesso, voltará ao subproblema anterior 
para tentar as outras opções.
Para de testar as opções quando nota-se que a 
melhor solução foi encontrada. Se não obter 
sucesso, voltará ao subproblema anterior para 
tentar as outras opções.
Incremental Gulosos
Adiciona-se um novo elemento à solução. Problemas de minimização
Gulosos Programação Dinâmica
Pode não resultar na solução ótima global porque faz uso de 
soluções ótimas locais (melhor solução, que é óbvia no 
momento).
- Utiliza o resultado de subproblemas para resolver problemas maiores.-
Não pode ser sempre utilizada porque nem sempre se tem a solução menor.-
Divisão e Conquista Prog. Dinâmica
Conquista é recursiva.-
Diferenças entre Algortimos de Árvore Geradora Mínima
Prim Kruskal
Procura a menor aresta adjacente.-
Sem formar ciclos.-
Procura a menor aresta.-
Sem formar ciclos.-
Diferenças entre Algortimos de Caminho Mínimo
Dijkstra Bellman-Ford Floyd-Warshall
Inicio em 1 vértices, fim em qualquer vértice.-
Não aceita pesos negativos-
Inicio em 1 vértices, fim em qualquer vértice.-
Aceita pesos negativos-
Início em qualquer vértices, fim em qualquer vértice.-
Aceita pesos negativos-
Algoritmos para Ciclos em Grafos
Ciclo Euleriano Caminho Euleriano Caminho Hamiltoniano
Passar por todos os vértices sem repetir arestas.-
Formar um ciclo (iniciar e terminar no mesmo vértice)-
Há solução se não houver vértice de grau ímpar.-
Passar por todas as arestas sem repetir vértices.-
Iniciar e terminar em quaisquer vértices.-
Há solução se todos os vértices ...-
Passar por todos os vértices sem repetir arestas.-
Iniciar e terminar em quaisquer vértices.-
...-
REVISÃO
segunda-feira, 10 de maio de 2010
10:23
 Página 14 de P.A.A. 
A ordem de crescimento de funções do tempo de execução dos algortimos fornece uma 
caracterização da eficiência do algoritmo e também permite comparar o desempenho de algoritmos 
distintos para o mesmo problema.
Apesar de, por vezes, ser possível determinar o tempo de execução exato do algoritmo, como foi 
feito para o algortimo de ordenação por inserção, a precisão pode não justificar a problemática do 
cálculo.
Ex: Se f(n2 + 4n + 60), para entradas grandes, basta f(n2)
Para entradas grandes, as constantes multiplicativas e termos de baixa ordem de um tempo de 
execução exatos são dominados pelos efeitos do tamanho da entrada do termo de mais alta ordem.
Ao se estudar tamanhos de entrada bastantegrandes para se conhecer a ordem de crescimento 
relevante, estuda-se a eficiência assintótica de algoritmos: o tempo de execução de um algoritmo 
aumenta com o tamanho da entrada no limite.
Geralmente, um algoritmo que é assintóticamente mais eficiente será a melhor escolha, exceto para 
entradas muito pequenas.
Notação Ơ (ômicron grande): fornece um limite superior (upper bound) de crescimento 
assintótico de uma função. Para uma função dada g(n), denota-se por Ơ(g(n)), o conjunto de 
funções:
-
Ơ(g(n)) = { f(n) : existem constantes positivas c e nƠ, tal que 0 <= f(n) <= c g(n)
 "é um conjunto": para qualquer n >= nƟ }
Uma função f(n) E Ơ(g(n)). Se há constante positiva c tal que f(n) é igual ou inferior a c g(n), 
para n suficientemente grande.
Um abuso de linguagem comum entre autores:
f(n) = Ơ(g(n)) ou f(n) é Ơ(g(n))
OBS: nƟ é o valor de entrada menor possível que, a partir desse valor, as entradas são 
consideradas grandes.Para valores menores, as funções não podem ser definidas como "mais 
eficiente" ou não.
f(n) = a*n + b
g(n) = n
Ex: Melhor Caso (Inserção):
Notação Ω (ômega grande): fornece um limite inferior (lower bound) de crescimento 
assintótico de uma função. Para uma função dada g(n), denota-se por Ω(g(n)), o conjunto de 
funções:
-
Ω(g(n)) = { f(n) : existem constantes positivas c e nƟ, tal que 0 <= c g(n) <= f(n)
 "é um conjunto": para qualquer n >= nƟ }
Uma função f(n) E Ω(g(n)). Se há constante positiva c tal que f(n) é igual ou superiora c g(n), 
para n suficientemente grande.
f(n) = a*n2 + b*n + c
g(n) = n2
Ex: Pior Caso (Inserção):
Um abuso de linguagem comum entre autores:
Notação de Funções
segunda-feira, 15 de março de 2010
10:05
 Página 15 de P.A.A. 
Um abuso de linguagem comum entre autores:
f(n) = Ω(g(n)) ou f(n) é Ω(g(n))
Notação Ɵ (teta): fornece um limite restrito (tight bound) de crescimento assintótico de uma 
função. Para uma função dada g(n), denota-se por Ɵ(g(n)), o conjunto de funções:
-
Ɵ(g(n)) = { f(n) : existem constantes positivas c1, c2, e nƟ, tal que 0 <= c1 g(n) <= f(n) <= c2 g(n)
 "é um conjunto": para qualquer n >= nƟ }
Uma função f(n) E Ɵ(g(n)). Se há constantes positivas c1 e c2 tal que f(n) é igual ou superior a c1
g(n) e f(n) é igual ou inferior a c2 g(n), para n suficientemente grande.
Um abuso de linguagem comum entre autores:
f(n) = Ɵ(g(n)) ou f(n) é Ɵ(g(n))
Melhor Caso: Ω(n lg n)
Pior caso: Ơ(n lg n)
Logo, Ɵ(n lg n) - (NÃO É CASO MÉDIO)
Ex: Merge Sort: (ver teorema abaixo)
Intuitivamente, vamos estudar a razão de se ignorar os termos de mais baixa ordem e os 
coeficientes do termo de mais alta ordem de uma função. Por exemplo:
 
 
 
Deve-se determinar constantes positivas c1, c2, e nƟ tal que:
 
 
 
 
Dividindo-se por n2, obtém-se: 
 
 
 
 
O lado direito da inequação pode ser verificado para qualquer valor n>= 1. Ao se escolher c2 >= 1/2
O lado esquerdo da inequação pode ser verificado para qualquer valor n>= 7. Ao se escolher c1 <=
1/14
Já que toda constante é um polinômio de grau zero, expressa-se Ɵ(n0) ou Ɵ(1), outro abuso de 
linguagem bastane utilizado.
Se f(n) E Ɵ(g(n)), então f(n) E Ơ(g(n)), porque Ɵ(g(n)) está contido em Ơ(g(n))
Teorema: para 2 funções f(n) e g(n), f(n) E Ɵ (g(n)) se, e somente se, f(n) E Ω(g(n)) e f(n) E Ơ(g(n)).
 Página 16 de P.A.A. 
Raiz: c*f(n)
a: número de chamadas recursivas (número de filhos da raiz)
Ex:
 
 
 
 
Nível 1: c*n
Nível 2: 2*c*n
Nível 3: 4*c*n
Nível 4: 8*c*n
...
Nível T(1): c*n2
 
Número de Níveis: 
Custo Total: 1cn+2cn+4cn+8cn+16cn...
 
 
 
 
Método Árvore de Recursão
segunda-feira, 29 de março de 2010
10:22
 Página 17 de P.A.A. 
Serve para obter limites assintóticos de recorrência par algoritmos de divisão e conquista.
Consiste, em princípio, em 2 passos:
1. Estimar (adivinhar) a forma da solução
2. Usar a indução matemática para encontar as constantes e mostrar que a solução está correta.
Ex:
 
 
 
 
Estima-se que a solução é Ơ(n lg n).
Deve-se provar que T(n) <= c n lg n par auma escolha apropriada da constante.
Hipótese (o limite é verificado para 
 
 
 ):
 
 
 
 
 
 
 
 
 
 
Substitui-se na recorrência:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Base da Indução: deve-se mostar que T(n) <= cnlg(n) é verificado para as condições de contorno.
Supõe-se que T(0)=0 e T(1)=1
 
 
 
 
 
Para n=1, o limite T(n)<=c*n*lg(n) torna-se T(1)<=c*1*lg(1), que não verifica T(1)=1
Utilizando-se notação assintótica, deve-se provar que T(n)<=cnlg(n) para n>=no, onde no é uma 
constante que deve ser escolhida.
 
 
 
 
 
P r T * * :
 
Para c=1, a base da indução falha.
Para c=2, a base da indução é verdadeira.
Concusão: para qualquer valor de n, apenas constantes maiores ou iguais a 2 atendem a condição.
A função "chão" foi retirada porque trata-se de 
uma inequação "menor ou igual".
Estudar PAA (Substituição)Método Substituição
segunda-feira, 22 de março de 2010
10:10
 Página 18 de P.A.A. 
Fornece limites para recorrência com a forma:
 
 
 
 
Onde T(n/b) representa a "conquista" e f(n) representa a "divisão".
a: quantas vezes o algortimo se chama
b: valor que o vetor é dividido a cada iteração
Teorema Mestre:
Considere a>=1, b>1 e f(n) é uma função.
 
 
 
 
 
 
 
 
 
 
 
 
 
T(n) pode ser limitada assintoticamente como:
Ou seja, usado quando 
1. Se para alguma constante e>0, então 
Ou seja, usado quando 
2. Se ,então .
Ou seja, usado quando 
3. Se para alguma constante e>0 e se 
 
 
 para alguma constante c<1 e 
todos n suficientemente grandes, entçao T(n)=Ɵ(f(n))
Ex:
 
 
 
 
a=9; b=3; f(n)=n
 
Como (assintoticamente), será usado o caso 1.
 
 
 
Logo, e=1.
Isso foi possível por que polinomialmente
Por sim, conclui-se que:
 
Ex:
 
 
 
 
a=1; b=3/2; f(n)=1
Método Mestre
segunda-feira, 22 de março de 2010
10:51
 Página 19 de P.A.A. 
a=1; b=3/2; f(n)=1
 
Como (assintoticamente), será usado o caso 2.
 
Ex:
 
 
 
 
a=3; b=4; f(n)=n*lg(n)
 
Como (assintoticamente), será usado o caso 3.
 
 
e=0,2
Verificar a condição de regularidade:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
c=3/4
Como encontrou-se uma constante "c" válida, a condição foi satisfeita
Ex: 
 
 
 
 
a=2 ; b=2 ; f(n)=n*lg(n)
 
Como (assintoticamente), será usado o caso 3.
 
 
e=0, mas como e precisa ser maior que zero, não é possível resolver pelo Método Mestre
Ex:
 
 
 
 
a=4 ; b=2 ; f(n)=n
 
Como (assintoticamente), será usado o caso 1.
 
 
 
Logo, e=1.
Isso foi possível por que polinomialmente
Por sim, conclui-se que:
 
 Página 20 de P.A.A. 
Ex:
 
 
 
 
a=3 ; b=2 ; f(n)=n
 
Como (assintoticamente), será usado o caso 1.
 
 
 
Logo, e=1,58.
Por fim, conclui-se que:
 
 Página 21 de P.A.A. 
Ciclo Euleriano: percorre todas as arestas do grafo uma única vez. (voltando ao vértice inicial)
Caminho Hamiltoniano: percorre todos os vértices do grafo uma única vez. (não há algortimo que o resolva)
Caixeiro Viajante: percorrer todos os vértices formando um ciclo de custo mínimo.
A quantidade de vértices de grau ímpar (quantidade de vértices incidentes ímpar) é par.-
Um ciclo Euleriano não possui vértices de grau ímpar.-
Afirmações:
Ciclos e Caminhos em Grafos
quarta-feira, 14 de abril de 2010
08:59
 Página 22 de P.A.A. 
Força Bruta: um algoritmo trivial para resolver o PCV consiste em simplesmente enumerar todas as 
n! permutações dos n vértices do grafo. Calcular os custos de cada viagem corresponde a cada uma 
das permutações e escolher uam viagem de custo mínimo.
Algoritmo Guloso:
G(V,A) grafo conexo, ponderado, orientado, representado por uma matriz de adjacências.-
Vértice inicial i (passa a ser o vértice corrente durante o algoritmo)-
Entrada:
Vetor cv[] com n vértices, one n = |v|.-
Saída:
cv[]: (os vértices são nomeados por números inteiros)-
j: ajuda a procurar a soluçãoótima local-
temp: vértice da solução ótima local (que forma caminho de menor custo a partir de i atual)-
vis: quantidade de vértices que já foram visitados-
Inteiro:
cv[1] <- i
vis = 1
temp <- i
j <- 1
j <- j+1
continue //irá testar novamente o laço mais interno
Se (j = i) então //não avalia um vértice para ele mesmo
Fim-Se
j <- j+1
continue
Se (visitado(j, cv, vis)) então //não considera se já houve visita em j
Fim-Se
temp <- j
Se (m[i][temp] > m[i][j]) então
Fim-Se
j <- j+1
Enquanto j <= n faça
Fim-Enquanto
cv[vis+1] <- temp // atualiza o proximo vértice da rota
vis <- vis+1
i <- temp
Enquanto (vis < n) faça //quando todos os vertices forem visitados
Fim-Enquanto
Retorne cv;
Inicio
Fim
Procedimento auxiliar: verifica se o "j" pertence ao vetor "cv"
visitado(inteiro: j, cv, vis)
Inteiro k <- 1
Retorne Verdadeiro
Se (cv[k] = j) então
Enquanto (k < vis) faça
Inicio
Caixeiro Viajante
segunda-feira, 19 de abril de 2010
10:08
 Página 23 de P.A.A. 
Retorne Verdadeiro
Fim-Se
k <- k+1
Fim-Enquanto
Retorne Falso
Fim
Exemplo:
OBS: vértices não adjacentes também terão seus pesos representados por ∞
De - Para 1 2 3 4
1 ∞ 2 10 3
2 20 ∞ 3 2
3 2 5 ∞ 15
4 7 1 4 ∞
n i j temp vis cv
4 1 1 1 1 [1][][][]
2 2
3
4
5 2 [1][2][][]
2 1
2
3 3
4 4
5 3 [1][2][4][]
4 1
2
3 3
4
5 4 [1][2][4][3]
3
Tempo de Execução Polinomial: n2
Programação Dinâmica:
Vértice inicial: 1
Grafo: G(V, A)
Seja f(i, C), o custo do caminho mínimo do vértice i até o vértice 1, e que visita todos os vértices do 
conjunto C:
f(1, V - {1}) = min (C1k + f(k, V-{1, K})), 2 <= k <= n) (1)
Cik, peso da aresta (i, k)
Se conhecermos os valores de f(k, V-{1, k}), (para todo k)(2 <= k <= n), então por (1), resolve-se o 
PCV.
Pode-se generalizar (1):
f(i, C) = min (Cij + f(j, C-{j})), j pertence a C (2)
 Página 24 de P.A.A. 
f(i, C) = min (Cij + f(j, C-{j})), j pertence a C (2)
Os valores de f necessários em (1) para resolver o PCV podem ser obtidos de (2) de uma forma 
iterativa ascendente:
1. Para |C|=0 , f(i, 0)=Cij , para 1 < i ≤ n
2. Para |C|=1 , f(i, {j})= Cij + f(j, 0) = Cij + Cj1 , para 1 < i,j ≤ n e i diferente de j
3. Para |C|= 2, 3, ..., n-2, determinam-se os valores de f(i, C) através de (2) utilizando-se os valores 
de f calculados nas iterações anteriores. Deve-se considerar 1 < i ≤ n e conjuntos C tais que C ∩{1, i} 
é vazio
Exemplo de Terada (1991):
. 1 2 3 4
1 0 2 10 7
2 20 0 20 1
3 1 5 0 15
4 7 12 3 0
f(2, {3}) = C23 + C31 = 20+1 = 21
f(2, {4}) = C24 + C41 = 1+7 = 8
f(3, {2}) = C32 + C21 = 5+20 = 25
f(3, {4}) = C34 + C41 =15+7 = 22
f(4, {2}) = C42 + C21 = 12+20 = 32
f(4, {3}) = C43 + C31 = 3+1 = 4 
f(2, {3,4}) = min(C23 + f(2, {4}), C24 + f(4, {3})) = min(20+22, 1+4) = 5 (2->4->3->1)
f(3, {2,4}) = min(C32 + f(2, {4}), C34 + f(4, {2})) = min(5+8, 15+32) = 13 (2->3->4->1)
f(4, {2,3}) = min(C42 + f(2, {3}), C43 + f(3, {2})) = min(12+21 , 3+25) = 28
f(1, {2,3,4}) = min(C12 + f(2, {3,4})), C13 + f(3, {2,4}), C14 + f(4, {2,3}) = min(2+5, 10+13, 7+28) = 7
O menor caminho é 1->2->4->3->1
Tempo de Execução: (n22n)
 Página 25 de P.A.A. 
vo pertence a V, vo vértice "fonte", G(V, A)
Grafo: não orientado, com custos não negativos
Cvw = 0 se v=w e custo ∞ quando (v, w) não pertence a A
Matriz de adjacência
Entrada:
(dist) é um vetor, onde dist(v) é a distância mínima de v para cada v petencente a V
Saída:
C <- {vo} ; dist(vo) <- 0
Dist(v) <- custo(vo, v)
Para cada v pertencente a V-{vo} faça
Fim-para
Escolhe w pertence a V-C | Dist(w) seja mínimo
Insere(w, C)
Dist(v) <- min(Dist(v) , Dist(w)+Custo(v, w))
Para cada w pertencente a V-C faça
Fim-Para
Enquanto c é diferente de V faça
Fim-Enquanto
Retorne Dist
Início
Fim
Exemplo:
v0 v1 v2 v3 v4
v0 0 3 ∞ ∞ 11
v1 ∞ 0 3 2 7
v2 ∞ ∞ 0 ∞ 2
v3 ∞ ∞ 5 0 ∞
v4 ∞ ∞ ∞ 6 0
Iteração C w Escolhido Dist
w v1 v2 v3 v4
- v0 - - 3 ∞ ∞ 11
1 v0, v1 v1 3 3 6 5 10
2 v0, v1, v3 v3 5 3 6 5 10
3 V-{v4} v2 6 3 6 5 8
4 V v4 8 3 6 5 8
Desempenho máximo: n2 .
Dijkstra
segunda-feira, 26 de abril de 2010
10:50
 Página 26 de P.A.A. 
Vértice "fonte" v-
G(V, E) grafo orientado, conexo, ponderado, n=|V| representado por matriz de adjacências M-
Entradas:
Dist[n]-
Rota[n]-
Saída:
Dist[v] <- 0
Rota[v] <- 0
Dist[c] <- ∞
Rota[c] <- 0
Para c<-1 até n, onde c ≠ v, faça
Fim-Para
Alterado <- verdadeiro
c <- 1
Alterado <- falso
Dist[i] <- Dist[j]+M[j][i]
Rota[i] <- j
Alterado <- verdadeiro
Se (Dist[i] > Dist[j]+M[j][i]) então
Fim-Se
Para cada aresta (j, i) pertencente a E e i≠v faça
Fim-Para
c <- c+1
Enquanto (alterado e c ≤ n) faça
Fim-Enquanto
retorne "ciclo negativo"
Se (alterado e c>n) então
retorne (dist, rota)
Senão
Fim-Se
Início
Fim
Exemplo:
1 2 3 4 5
1 0 1 ∞ 3 1
2 ∞ 0 1 2 ∞
3 ∞ ∞ 0 4 2
4 ∞ ∞ ∞ 0 ∞
5 2 ∞ ∞ 1 0
Lista de Arestas:
(j,i) : (1,2) - (1,5) - (1,4) - (2,3) - (2,4) - (3,4) - (3,5) - (5,1) - (5,4)
 
Dist / Rota
1 2 3 4 5 Alterado c j i
0/0 ∞/0 ∞/0 ∞/0 ∞/0 F 1 1
1/1 V 2
Bellman Ford
quarta-feira, 28 de abril de 2010
08:09
 Página 27 de P.A.A. 
1/1 V 2
1/1 V 5
3/1 V 4
2/2 V 2 3
(s/alt) 4
(s/alt) 3
(s/alt) 5
(ñ exec.) 5 1
2/5 4
F 2 1
(s/ alt) 2
(s/ alt) 5
(s/ alt) 4
(s/ alt) 2 3
(s/ alt) 4
(s/ alt) 3
(s/ alt) 5
(s/ alt) 5 4
3
No pior caso: n3
 Página 28 de P.A.A. 
Tipos de Algortimos
Classe P: são resolvidos com tempo de execução polinomial por algortimos determinístico.○
Algoritmos Eficientes: resolvidos com tempo de execução polinomial-
Classe NP: são verificados com tempo de execução polinomial (ver "Instâncias") e resolvidos com tempo de execução polinomial não-
determinístico.
○
Outros Algoritmos: não se conhece algoritmo que o resolva e não foi provado nenhum algoritmo polinomial.-
Intratáveis: são os problemas demonstrados que não têm solução por algoritmo polinomial. São resolvidos com tempo de execução exponencial.-
NP Completude
NP-Difícil: problema que foram gerados a partir da redutibilidade de problemas da classe NP. Esses problemas são, pelo menos, tão difíceis 
quanto os problemas da classe NP. 
-
Teorema de Cook: SAT pertence à classe NP Completo○
NP-Completo: são problemas que pertencem á classe NP e à classe NP-Difícil.-
SAT
SAT Conjuntiva: (a + b) . (c + d) . (... +...)○
SAT Disjuntiva: (a . b) + (c . d) + (... . ...)○
Pertence à classe NP-Difícil porque todo problema da classe NP pode ser reduzido para SAT, portanto SAT é pelo menos tão difícil quanto 
os problemas NP.
○
Problema da Satisfabilidade: encontrar os valores lógicos para todas as "n" variáveis para que a expressão seja verdadeira.-
Otimização: Qual o menor caminho no grafo?
Decisão: Existe um caminho no grafo menor que 5? E menor que 3?
Otimização e Decisão: problema de otimização podem ser convertidos para problemas de decisão através da verificação de instâncias para 
o problema.
○
O fato de um problema ser verificado em tempo polinomial, não implica que a busca da melhor solução também é executada em tempo 
polinomial . (Problemas NP)
○
Instância: um conjunto de dados específico a ser utilizado como entrada de um algoritmo.-
Ex:○
 
Se reduz "A" para "B", então "B" é pelo menos tão dificil quanto "A".
Se "B" pode ser resolvido em tempo polinomial, logo "A" também pode porque os elementos de "A" tem correspondentes em "B" 
Se "A" não pode resolvido em tempo polinomial, logo "B" também não pode, porque há elementos de "A" em "B".
Todo elemento de "A" deve constar em "B", o contrário não precisa acontecer.
Teorema de Cook: Qualquer problema pode ser reduzido para o problema SAT.○
Redução Polinomial:-
NP-Completude
segunda-feira, 24 de maio de 2010
10:26
 Página 29 de P.A.A. 
Clique: usa um grafo ~G com (|V|-k ) vértices-
Cobertura de Vértices: usa um grafo G com (V) vértices-
Problemas NP
quarta-feira, 16 de junho de 2010
08:35
 Página 30 de P.A.A.