Baixe o app para aproveitar ainda mais
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
Compartilhar