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