Download Projeto e Analise de Algoritmos - Nivio Ziviani PDF

TitleProjeto e Analise de Algoritmos - Nivio Ziviani
Tags Class (Computer Programming) Computational Complexity Theory Data Type
File Size2.3 MB
Total Pages808
Document Text Contents
Page 1

Introdução�

Última alteração: 10 de Outubro de 2006

∗Transparências elaboradas por Charles Ornelas, Leonardo Rocha, Leonardo
Mata e Nivio Ziviani

Page 2

Projeto de Algoritmos – Cap.1 Introdução – Seção 1.1 1

Algoritmos, Estruturas de Dados e
Programas

� Os algoritmos fazem parte do dia-a-dia das
pessoas. Exemplos de algoritmos:

� instruções para o uso de medicamentos,

� indicações de como montar um aparelho,

� uma receita de culinária.

� Seqüência de ações executáveis para a
obtenção de uma solução para um
determinado tipo de problema.

� Segundo Dijkstra, um algoritmo corresponde
a uma descrição de um padrão de
comportamento, expresso em termos de um
conjunto finito de ações.

� Executando a operação a + b percebemos
um padrão de comportamento, mesmo
que a operação seja realizada para
valores diferentes de a e b.

Page 404

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária –Seção 5.5.2 80

Estrutura e operações do dicionário
para listas encadeadas

public Object pesquisa ( String chave) {

int i = this .h (chave, this .pesos) ;

i f ( this . tabela [ i ] . vazia ( ) ) return null ; / / pesquisa
sem sucesso

else {

Celula cel=(Celula) this . tabela [ i ] . pesquisa(

new Celula(chave, null ) ) ;

i f ( cel == null ) return null ; / / pesquisa sem sucesso

else return cel . item;

}

}

public void insere ( String chave, Object item ) {

i f ( this .pesquisa (chave) == null ) {

int i = this .h (chave, this .pesos) ;

this . tabela [ i ] . insere (new Celula (chave, item ) ) ;

}

else System.out . print ln ( "Registro ja esta presente" ) ;

}

public void ret i ra ( String chave) throws Exception {

int i = this .h (chave, this .pesos) ;

Celula cel = (Celula) this . tabela [ i ] . ret i ra (

new Celula (chave, null ) ) ;

i f ( cel == null )

System.out . print ln ( "Registro nao esta presente" ) ;

} }

Page 405

Projeto de Algoritmos - Cap.5 Pesquisa em Memória Primária –Seção 5.5.2 81

Análise

� Assumindo que qualquer item do conjunto
tem igual probabilidade de ser endereçado
para qualquer entrada da tabela, então o
comprimento esperado de cada lista
encadeada é N/M , em que N representa o
número de registros na tabela e M o tamanho
da tabela.

� Logo: as operações pesquisa, insere e retira
custam O(1 + N/M) operações em média,
sendo que a constante 1 representa o tempo
para encontrar a entrada na tabela, e N/M , o
tempo para percorrer a lista. Para valores de
M próximos de N , o tempo torna-se
constante, isto é, independente de N .

Page 807

Projeto de Algoritmos – Cap.9 ProblemasNP-Completo e Algoritmos Aproximados – Seção 9.2.372

Casamento Mínimo com Pesos -
Algoritmo de Christophides

• Os principais passos do algoritmo de
Christophides são:

1. Obtenha a AGM T para o conjunto de n
cidades, com custo O(n2).

2. Construa um casamento mínimo M para o
conjunto de vértices de grau ímpar em T ,
com custo O(n3).

3. Encontre um caminho de Euler para o
grafo Euleriano obtido com a união de T e
M , e converta o caminho de Euler em um
caminho do caixeiro-viajante usando
curto-circuitos, com um custo de O(N).

• Assim obtivemos um algoritmo polinomial de
custo O(n3), com uma razão de aproximação
garantida para o pior caso de RA < 3/2.

Page 808

Projeto de Algoritmos – Cap.9 ProblemasNP-Completo e Algoritmos Aproximados – Seção 9.2.373

Algoritmo de Christophides - Pior
Caso

• Exemplo de pior caso do algoritmo de
Christofides:

5

1 1 1 1 11 1 1 1 1

1 1 1 1

1 1 1 1 1

• A AGM e o caminho ótimo são:

AGM

Ótimo

1 1 1 1

1 1 1 1 1

1

1 1 1 1 11 1 1 1 1

• Neste caso, para uma instância I:

C(I) =
3

2
[Otimo(I)− 1],

em que o Otimo(I) = 11, C(I) = 15, e
AGM = 10.

Similer Documents