Cap. 1 Introdução

Prévia do material em texto

INTRODUÇÃO
Complemento de Algoritmia e Complexidade
Capítulo I
 Corpo docente:
◦ Dikiefu Fabiano, Msc.
 Monitores:
◦ Bongo Cahisso (4º Ano)
◦ Hélio Sbantana (4º Ano)
 Avaliação
◦ 2 provas parcelares (PP1 e PP2)
◦ Um projecto (continuação do projecto da cadeira de AED + Análise da 
complexidade do código do projecto) Proj
◦ 1 Exame de Época Normal
 Nota final
◦ Época Normal: [(PP1+PP2+Proj)/3]*0,4 + EXN*0,6
◦ Época de Recurso: [(PP1+PP2+Proj)/3]*0,4 + REC*0,6
Nota
EXN: Exame Normal 
REC: Exame de Recurso
◦ bbbbb
Complemento de Algoritmo e Complexidade
Índice
1. Introdução
2. Fundamentos da análise da eficiência do algoritmo
2.1 Mecanismos de análise
2.1.1 Medição de tamanho de entrada
2.1.2 Unidades para medição de tempo de execução
2.1.3 Ordens de crescimento
2.1.4 Eficiências de pior caso, melhor caso e caso médio.
2.1.5 Sumário
2.2 Notação Assintótica e classes de eficiências básicas.
2.2.1 Definição Informal
2.2.2 Notações O,  e 
2.2.3 Propriedades de notações assintótica
2.2.4 Uso de limites para comparação de ordens de crescimento
2.2.5 Classes de eficiências básicas
2.3 Análise matemática de algoritmos não recursivos
2.4 Análise matemática de algoritmos recursivos
2.5 Exemplo: Números de Fibonacci
3. Força bruta
3.1 Ordenação por selecção e bolhas
3.2 Busca sequencial
3.3 Problemas de closest-pair e convex-hull
3.4 Busca exaustiva
3.4.1 Problema de comerciante viajante
3.4.2 Problema Knapsack
4. Divide e Conquista
4.1 Ordenação por Mergesort
4.2 Ordenação por Quicksort
4.3 Pesquisa Binária
4.4 Arvore binária transversal. Propriedades
Cont.
5. Reduz e conquista
5.1 Ordenação por inserção
5.2 Pesquisa em Depth-first e Breadth-first
5.3 Ordenação por topologia
5.4 Algoritmos do tipo Redução pelo factor constante
5.4.1 Problema de Fake-Coin (Moeda falsa)
5.4.2 Multiplicação à la Russe
5.4.3 Problema de Josephus
6. Transformar e conquistar
6.1 Pre-Ordenação
6.2 Eliminação de Gauss
6.3 Pesquisa balanceada de arvore
6.4 Heaps e Heapsort
6.5 Problemas de redução
O que é um algoritmo?
Um algoritmo é uma sequência de instruções 
inequívocas para resolver um problema, ou seja, 
para a obtenção de uma saída requerida para 
qualquer entrada legítimo em uma quantidade 
finita de tempo.
Computador
Problema
Algoritmo
Entrada Saida
Porquê Estudo Algoritmos?
 Todos programas do computador dependem de 
algoritimos
◦ Todas as empresas e muitas facetas da vida 
diária dependem de programas de computador
◦ Computadores e Telescópios
 Aprender a escrever Excelente Algoritmos 
significa aprender a usar Excelente Técnicas 
Resolução de Problemas
Porquê estudar algoritmos? (parte 2)
 Importância teórica
◦ o núcleo da ciência da computação
 Importância prática
◦ Conjunto de ferramentas de algoritmos 
conhecidos de um praticante
◦ Estrutura para desenhar e analisar algoritmos 
para novos problemas
Citação de Donald Knuth
Uma pessoa bem treinada em ciência da
computação sabe como lidar com algoritmos: como
construí-los, manipulá-los, compreendê-los, analisá-
los. Este conhecimento é a preparação para muito
mais do que escrever bons programas de
computador, é uma ferramenta mental, de propósito
geral, que será uma ajuda definitiva para a
compreensão de outras disciplinas, sejam eles
química, linguística, ou música, etc.
O que é um algoritmo?
 Receita, processo, método, técnica, 
procedimento de rotina, ... com os seguintes 
requisitos:
◦ Finitude
 termina depois de um número finito de passos
◦ Definitude
 rigorosamente e sem ambiguidades especificada
◦ Entrada
 As entradas válidas são claramente especificados
◦ Saída
 pode ser provado para produzir a saída correcta dada uma 
entrada válida
◦ Eficácia
 passos são suficientemente simples e básico
Pontos importantes de algoritmos a considerar
 Cada passo de um algoritmo deve ser não-ambígua.
Nota: isto não significa necessariamente – “deve ser 
discreto”
 A gama de inputs para um algoritmo tem de ser 
especificado com cuidado.
 O mesmo algoritmo pode ser representado de diversas 
maneiras.
 Podem existir vários algoritmos para resolver o mesmo 
problema.
◦ Algoritmos para o mesmo problema pode ser baseada em 
idéias muito diferentes e pode resolver o problema com 
velocidades dramaticamente diferentes (também, que as suas 
necessidades de recursos podem ser dramaticamente 
diferentes - geralmente estes são considerações opostas) 
 Suscita a noção de qual algoritmo é "melhor" (assumindo que ambos 
os algoritmos são "corretas"
Alguns problemas computacionais bem 
conhecidos. 
 Ordenação
 Busca
 Caminhos mais curtos no grafo
 Árvore Geradora Mínima (Minimum spanning 
tree)
 Testes de primalidade
 Problema do caixeiro viajante
 Problema da mochila
 Torres de Hanoi
Exemplo do problema computacional : Ordenação
 Declaração de problema:
◦ Entrada: Uma sequencia de n números <a1, a2, …, an>
◦ Saída: Uma sequencia de entrada reordenada 
<a1´, a2´, …, an´> tal que ai´≤ aj´ onde i < j
 Exemplo: A sequencia <5, 3, 2, 8, 3>
◦ Entrada: 5, 3, 2, 8, 3
◦ Saída : 2, 3, 3, 5, 8
 Algoritimos:
◦ Ordenação por Selecção
◦ Ordenação por Inserção
◦ Ordenação por intercalação (Mergesort)
◦ (muito outros)
Ordenação por Selecção
 Entrada: vector a[1],…,a[n]
 Saída: vector ordenada em ordem decrescente
 Algoritmo:
para i=1 até n
troca a[i] com menor de a[1],…a[n]
Questões básicas relacionadas aos Algoritmos
 Como projectar algoritmos
◦ Sua compreensão do domínio do problema (o que é um pré-requisito para 
resolver esse tipo de problema em geral), e compreensão da forma de 
representação das soluções irão necessariamente crescer e evoluir em 
paralelo.
 Como expressar algoritmos
◦ Pseudocódigo.
◦ Além disso, o nível de complexidade e expressividade será necessário. 
 Provando correção
◦ Fortes provas matemáticas de correção, às vezes é possível. 
 Eficiência
◦ A análise teórica
◦ A análise empírica
 Optimalidade
◦ Matematicamente, o que representa o melhor desempenho absoluto de 
qualquer algoritmo que possa surgir.
◦ Se o nosso algoritmo tem esse desempenho, então ele deve ser o ideal.
Análise de Algoritmos
 Como é bom o algoritmo?
◦ Correcto
◦ Eficiência de tempo
◦ Eficiência de espaço
 Será que não existe um algoritmo melhor?
◦ limites inferiores
◦ Optimalidade
Algoritmo de Euclide
Problema: 
Encontra o mdc(m,n), o máximo divisor comum de dois 
inteiros não negativo, não ambos zero m e n
Exemplos: mdc(60,24) = 12, mdc(60,0) = 60, mdc(0,0) = ?
Algoritmo de Euclides é baseado na aplicação repetida de 
igualdade
mdc(m,n) = mdc(n, m mod n)
até que o segundo número é 0, o que torna o problema 
trivial.
Exemplo: mdc(60,24) = mdc(24,12) = mdc(12,0) = 12
Não impressionado?
Qual é o máximo divisor comum entre 3885 e 1736?
mdc(3885, 1736)= mdc(1736,413)
= mdc(413,84)
= mdc(84,77)
= mdc(77,7)
= mdc(7,0) 
= 7
Duas descrições de algoritmo de Euclides
Euclide de Alexandria – 3rd Century B.C.
Passo 1 Se n = 0, retorna m e pára; 
Senão vá para o passo 2
Passo 2 Divide m por n e atribui o valor do resto para r
Passo 3 Atribui o valor de n para m e valor de r para n. 
Va para Passo1.
enquanto n ≠ 0 faça
r ← m mod n
m← n
n ← r
retorna m
Outro método para o cálculo de mdc(m,n)
 Algoritmo de verificação inteiro consecutivo
Passo 1 Atribuir o valor de min {m, n} para t
Passo 2 Divide m por t. Se o resto for 0, vá para a passo 3; 
caso contrário, vá para a passo 4
Passo 3 Divide n port. Se o resto for 0, retorna t e pára; caso 
contrário, vá para a passo 4
Passo 4 Reduz t por 1 e vá para a passo 2
Nota: Isto não funciona quando um dos números de 
entrada (m ou n) é zero.
Outro método para o cálculo de mdc(m,n)
 Procedimento do ensino médio
(Parafraseando a partir do seu professor de ensino médio, 
século 20):
Passo 1 Encontre os factores primos de m
Passo 2 Encontre a factores primos de n
Etapa 3 Encontre todos os factores primos comuns
Passo 4 Calcule o produto de todos os factores primos 
comuns e retorná-lo como mdc (m, n)
 É este um algoritmo?
Isso foi um algoritmo?
 Podes usar o algoritmo para encontrar mdc 
(23458222, 3423333)?
◦ Como encontrar as listas de factores primos?
◦ Como classifica estas listas para encontrar os 
factores em comum?
 O procedimento anterior, não é um algoritmo pois 
não é definitivamente inequívoca.
◦ além: encontrar a lista de factores principais para 
um grande número acaba por ser difícil
Crivo de Eratóstenes
O Crivo de Eratóstenes é um algoritmo e um método simples e prático para 
encontrar números primos até um certo valor limite. Segundo a tradição, foi criado 
pelo matemático grego Eratóstenes (a.c. 285-194 a.C.).
Para exemplificá-lo, vamos determinar a lista de números entre 1 e 20.
Inicialmente, determina-se o maior número a ser checado. Ele corresponde à raiz 
quadrada do valor limite, arredondado para baixo. No caso, a raiz de 20, 
arredondada para baixo, é 4.
Crie uma lista de todos os números inteiros de 2 até o valor limite: 
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 e 20.
O primeiro número da lista 2 é um número primo.
Remova da lista todos os múltiplos do número primo encontrado. 
Neste caso temos: 2, 3, 5, 7, 9, 11, 13, 15, 17 e 19.
O próximo número da lista é primo. Repita o procedimento. No caso, o próximo 
número da lista é 3. 
Removendo seus múltiplos, a lista fica: 2, 3, 5, 7, 11, 13, 17 e19. 
3 é o último número a ser verificado pois que o 4 fora eliminado em virtude de 
ser multiplo de 2, conforme determinado inicialmente. Assim, a lista encontrada 
contém somente números primos.
Vide http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes
Crivo Erastótenes (Simulação)
Algoritmo
Entrada: inteiro n ≥ 2
Saida Lista de números primos menor ou igual que n
para p ← 2 até n faça 
A[p] ← p
para p ← 2 até n faça
Se A[p] ≠ 0 // p não tiver sido previamente eliminadas
// da lista
j ← p* p
enquanto j ≤ n faça
A[j] ← 0 // marca o elemento como eliminado
j ← j + p
Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Vide http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes
Duas questões principais relacionadas com 
algoritmos
 Como desenhar algoritmos
 Como analisar a eficência do algoritmo
Estratégias de desenho de algoritmos
 A força bruta
 Dividir para conquistar
 Diminuir para conquistar
 Transformar e conquistar
 Abordagem gulosa
 Retrocesso(Backtracking) e Branch and bound
 Programação Dinamica
 Compensações de Espaço e Tempo (Space and time 
tradeoffs)
Estruturas de dados fundamentais
 lista
◦ Sequencial
◦ Ligadas
◦ Pilha
◦ Fila
◦ Fila de prioridade,
◦ etc
 Grafo
 Árvore
 Conjuntos e dicionário