View
117
Download
0
Category
Preview:
Citation preview
Módulo 9
4 Algoritmos4.1 Definição e Características4.2 Fatoração4.3 Pesquisa4.3.1 Pesquisa Sequencial4.3.2 Pesquisa Binária
DCC 001Programação de Computadores
2° Semestre de 2011Prof. Osvaldo Carvalho
DCC001 - 2011-2 1
Algoritmos e Programas
DCC001 - 2011-2 2
Algoritmos e Programas
Algoritmo Prescrição de passos para transformar uma
informação de entrada em outra informação de saída
Cada passo prescrito deve ser uma operação garantidamente realizável
seja por operações elementares seja por outro algoritmo
Programa Um programa é a concretização de um algoritmo
em uma linguagem executávelDCC001 - 2011-2 3
Questões sobre Algoritmos e Problemas
Especificação: Para qual problema precisamos de um
algoritmo? Correção:
O algoritmo resolve mesmo o problema proposto?
Eficiência: Qual é o consumo de recursos computacionais
(tempo e memória, essencialmente) para se resolver o problema?
DCC001 - 2011-2 4
Especificação
Surge de um processo de análise de um problema de transformação de informação
Não é estática; muitas vezes uma especificação é modificada durante o processo de desenvolvimento, ou mesmo durante o uso de um programa Ex. O caso de equações de 2º grau com o primeiro
coeficiente igual a zero não foi previsto em nossos exemplos Em problemas reais muitas vezes a especificação é a
etapa mais demorada
DCC001 - 2011-2 5
Correção
Podemos verificar se um algoritmo atende a uma especificação por um exame de sua estrutura – uma prova formal de sua correção
Na prática somente algoritmos pequenos têm uma prova de correção viável
Testes são usados para ganhar convicção do bom funcionamento de um algoritmo
Testes podem descobrir erros, mas quase nunca garantir sua ausência
DCC001 - 2011-2 6
DCC001 - 2011-2
Somador em Cascata
Entrada b
Entrada a
SCSCSC SC
7
SomadorTestes ou Prova Formal?
Para testar completamente um somador de 32 bits são necessários 264 testes!
Se estamos convencidos da correção de um circuito de soma completa, não temos problemas em aceitar a correção do somador
É da compreensão da estrutura do somador que vem a nossa convicção; testes viáveis cobrem uma fração ínfima do espaço de entradasDCC001 - 2011-2 8
Eficiência
Algoritmos com a mesma funcionalidade podem diferir muito em sua eficiência
O termo complexidade é usado para designar uma função que descreve como o uso de recursos computacionais cresce com o tamanho da entrada de um algoritmo
Procura-se determinar a complexidade de um algoritmo de forma independente da velocidade de um computador específico e de outros fatores que afetam o tempo de execução de um programa
DCC001 - 2011-2 9
Fatoração
DCC001 - 2011-2 10
Fatoração de Inteiros
Consiste em descobrir o menor divisor > 1 de um número inteiro n >= 2 dado (se este fator for igual a n, n é primo)
Uma boa parte da segurança da informação em uso hoje em dia depende da dificuldade computacional de se fatorar um número Chaves criptográficas podem ser quebradas por
fatoração Estas chaves são produtos de dois primos
grandes, com 1024 ou 2048 bits cadaDCC001 - 2011-2 11
A função MenorFator
DCC001 - 2011-2
function p = MenorFator(n) p = 2; while modulo(n,p) <> 0 p = p + 1; endendfunction
function ehPrimo = Primo(n) ehPrimo = (n == MenorFator(n));endfunction
12
O programa Fatora.sce
exec("MenorFator.sci");n = input("n = ");while n >= 2 timer(); p = MenorFator(n) ; tempoGasto = timer(); // Imprime o resultado printf("\nTempo = %8.6fs, %6d é divisível por %6d",... tempoGasto,n,p); if n == p then printf(" **PRIMO**") end n = input("n = ");end
DCC001 - 2011-2 13
Dois Casos de Fatoração
Para 131101, primo, são feitas 131101 chamadas da função modulo
Para 131103, somente 3 chamadas! Conclusão: o tempo de execução pode
depender da instância específica do problema
Para a fatoração, primos são o pior caso
DCC001 - 2011-2
Tempo = 3.062500s, 131101 é divisível por 131101 **PRIMO**n = 131103 Tempo = 0.000000s, 131103 é divisível por 3
14
Variações no Tempo de Execução
Um mesmo programa pode apresentar variações no tempo de execução de uma mesma instância de um problema
O principal motivo é o compartilhamento do computador
DCC001 - 2011-2
n = 131101Tempo = 2.984375s, 131101 é divisível por 131101 **PRIMO** n = 131101Tempo = 3.078125s, 131101 é divisível por 131101 **PRIMO** n = 131101Tempo = 3.015625s, 131101 é divisível por 131101 **PRIMO**
15
Tempos do Programa Fatora.sce em dois computadores
DCC001 - 2011-2 16
Somente números primos
Função de Complexidade
n é o tamanho de uma instância de um problema
Uma função caracteriza a complexidade de um algoritmo quando o seu tempo de execução é limitado por multiplicado por uma constante
A idéia é absorver na constante diferenças de desempenho entre computadores específicos
Escreve-se (“big O notation”)
DCC001 - 2011-2 17
ng
ng
ngOnT
Complexidade da função MenorFator em função do número de bits na entrada
DCC001 - 2011-2 18
nOnT 2
Melhorando a Fatoração
Se d é um divisor de n, existe d’ tal que
d*d’ = n Temos ou d <= sqrt(n), ou d’
<= sqrt(n) Portanto, ao fatorar só
precisamos testar os divisores menores ou iguais à raiz de n
P.ex., sqrt(12) = 3,464, e só precisamos testar divisores menores ou iguais a 3
DCC001 - 2011-2
d d'1 122 63 44 36 212 1
19
A FunçãoMenorFator2.sce
function p = MenorFator2(n) limite = int(sqrt(n)); p = 2; while modulo(n,p) <> 0 & p <= limite p = p + 1; end if modulo(n,p) <> 0 then p = n; endendfunction
DCC001 - 2011-2 20
2/22 nn OOnT
Complexidade O(2^n) versus O(2^(n/2))
Quando n = 10 bits a função modulo é chamada ~1024 vezes com o primeiro algoritmo, e ~32 com o segundo.
Quando dobramos o tamanho do problema, com n = 20 bits, a função modulo é chamada ~1048576 vezes com o primeiro algoritmo, ou
seja, 1024 vezes o tempo para n = 10 ~1024 vezes com o segundo algoritmo, ou seja,
32 vezes o tempo para n = 10!DCC001 - 2011-2 21
Pesquisa
DCC001 - 2011-2 22
Pesquisa em Tabelas
Localizar um elemento em uma tabela é um problema clássico da computação
Vamos ver dois algoritmos para isto: Pesquisa Sequencial Pesquisa Binária
DCC001 - 2011-2 23
Pesquisa por um Número Primo
Vamos utilizar algoritmos de pesquisa para testar se um número é primo
Obviamente isto só funciona para números menores ou iguais ao maior número presente na tabela
DCC001 - 2011-2 24
Tabela de Números Primos
Números primos têm propriedades matemáticas interessantes, e por isso são muito estudados
Na internet é possível encontrar arquivos com os primeiros muitos números primos
O arquivo 200000primos.txt contém os 200.000 primeiros números primosDCC001 - 2011-2 25
Início e Final do Arquivo 200000primos.txt
DCC001 - 2011-2 26
Especificação
Faça um programa que Leia o arquivo 200000primos.txt que
contém os primeiros 200000 números primos
Leia repetidamente números inteiros e, para cada número lido, verifique se o número é primo utilizando a tabela lida.
O programa deve parar quando o número lido for 0 (zero).
DCC001 - 2011-2 27
Pesquisa Sequencial
DCC001 - 2011-2 28
Pesquisa Sequencial
function p = seqSearch(key,table) i = 1; // A chave nunca está à esquerda de i while i <= length(table) & table(i) ~= key i = i+1; end if i <= length(table) then p = i; else p = -1; endendfunction
DCC001 - 2011-2
Convenção para valor retornado quando a
pesquisa falha
29
O Programa VerificaPrimos3.sce
arqTab = xgetfile("*.txt",pwd(),"Arquivo com Tabela");tabPrimos = fscanfMat(arqTab);
n = input("n = ");while n >= 2 timer();eh_Primo = Primo3(n,tabPrimos); tempoGasto = timer(); // Imprime o resultado printf("\nTempo gasto = %g segundos", tempoGasto); if eh_Primo then printf("\nO número %d é primo!\n\n",n); else printf("\nO número %d não é primo!\n\n", n) end n = input("n = ");end
DCC001 - 2011-2 30
A Função Primo3.sce
function ePrimo = Primo3(n,tabela) ePrimo = seqSearch(n,tabela) ~= -1;endfunction
DCC001 - 2011-2 31
Complexidade da Pesquisa Sequencial
Não é difícil ver que se n é o tamanho da tabela, o número de comparações feito em uma pesquisa por um elemento presente na tabela varia entre 1 e n
Se considerarmos todas as chaves presentes na tabela como tendo a mesma probabilidade de serem pesquisadas, o algoritmo fará em média n/2 comparações
O pior caso ocorre com pesquisas por chaves que não constam da tabela, quando são feitas n comparações
Nós dizemos que a complexidade da pesquisa sequencial é O(n), ou seja, cresce linearmente com o tamanho da tabela
DCC001 - 2011-2 32
Pesquisa Binária
DCC001 - 2011-2 33
Pesquisa Binária
Quando a tabela tem suas entradas em ordem crescente (ou decrescente), podemos utilizar um algoritmo muito mais eficiente para a pesquisa
A chave é comparada com o elemento no meio da tabela. Se a chave for Igual a este elemento: sucesso Menor: a pesquisa é reaplicada à metade inferior
da tabela Maior: a pesquisa é reaplicada à metade superior
da tabelaDCC001 - 2011-2 34
Procurando por 71
DCC001 - 2011-2 35
1 202 353 464 485 586 68 6 68 6 687 71 7 71 7 71 7 718 74 8 749 87 9 8710 98 10 98
Procurando por 37
DCC001 - 2011-2 36
1 20 1 202 35 2 353 46 3 46 3 464 48 4 48 4 485 586 687 718 749 8710 98
Pesquisa Binária
DCC001 - 2011-2 37
function p = BinarySearch(key,table,low,high) printf("\nlength(table) = %d",high-low); //extra if high < low then p = -1; else m = int((low+high)/2); if key == table(m) then p = m; else if key < table(m) then p = BinarySearch(key,table,low,m-1); else p = BinarySearch(key,table,m+1,high); end end endendfunction
O Programa VerificaPrimos5.sce// Programa para deteção de números primosexec("Primo5.sci")exec("BinarySearch.sci")
arqTab = uigetfile("*.txt",pwd(),"Arquivo com Tabela");tabPrimos = fscanfMat(arqTab);
n = input("n = ");while n >= 2 timer(); eh_Primo = Primo5(n,tabPrimos); tempoGasto = timer(); // Imprime o resultado printf("\nTempo gasto = %g segundos", tempoGasto); if eh_Primo then printf("\nO número %d é primo!\n\n",n); else printf("\nO número %d não é primo!\n\n", n) end n = input("n = ");end
DCC001 - 2011-2 38
A Função Primo5.sci
function ePrimo = Primo5(n,tabela) posicao = BinarySearch( n,tabela,1,length(tabela)); ePrimo = (posicao <> -1);endfunction
DCC001 - 2011-2 39
Pesquisa BináriaPassos para n = 16
DCC001 - 2011-2 40
20
21
22
23
24
São 4 passos no pior caso
Pesquisa BináriaQual é a maior tabela pesquisável com p passos?
DCC001 - 2011-2 41
Com p passos uma pesquisa é completada em uma tabela de tamanho <= 2p
20
21
22
…2p
…
Complexidade da Pesquisa Binária
A cada passo o tamanho da porção da tabela é dividido por 2
No pior caso, o algoritmo termina quando o tamanho dessa porção é igual a 1
Com p passos, reduzimos a 1 o tamanho da porção examinada de uma tabela com n =~ 2p
elementos Temos no máximo log2(n) passos Ou seja, a complexidade da pesquisa binária é
logarítimica
DCC001 - 2011-2 42
Complexidade linear x complexidade logarítmica
Para pesquisar em uma tabela de 200.000 elementos, a pesquisa binária faz no máximo log2(200.000) =~ 18 comparações
Para a mesma tabela, a pesquisa sequencial pode necessitar de 200.000 comparações;
Se dobrarmos o tamanho da tabela, a pesquisa binária fará no máximo 19 comparações (uma a mais), enquanto que a pesquisa sequencial poderá fazer 400.000 comparações!DCC001 - 2011-2 43
Resumo
Aspectos fundamentais do estudo de algoritmos são especificação, correção e complexidade
Algoritmos podem ter desempenhos distintos para instâncias distintas de um mesmo problema
Procuramos caracterizar a complexidade de forma independente do desempenho de máquinas específicasDCC001 - 2011-2 44
Resumo
Muitas vezes podemos encontrar melhores algoritmos estudando propriedades do problema de transformação de informação
Algumas funções de complexidade indicam que poderíamos esperar milênios pela execução de um programa
DCC001 - 2011-2 45
Recommended