Estruturas de Dados e Algoritmos

Publish in

Documents

33 views

Please download to get full document.

View again

of 237
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Estruturas de Dados e Algoritmos.  2001, Claudio Esperança. Introdução. O que é um algoritmo? Processo sistemático para computar um resultado a partir de dados de entrada O que são estruturas de dados? Maneira de organizar dados e operar sobre eles
Transcript
Estruturas de Dados e Algoritmos  2001, Claudio Esperança Introdução
  • O que é um algoritmo?
  • Processo sistemático para computar um resultado a partir de dados de entrada
  • O que são estruturas de dados?
  • Maneira de organizar dados e operar sobre eles
  • Algoritmos + estruturas de dados = programas
  • Um programa é a expressão em linguagem formal (inteligível por um computador) de um algoritmo.
  • Projeto de Algoritmos
  • Entender a entrada
  • Entender o que se espera na saída
  • Repetir:
  • Bolar um método,
  • Se o método é correto, então
  • Analisar a complexidade do método,
  • Se complexidade é aceitável, terminar.
  • Implementar (programar)
  • Projeto de Estruturas de Dados
  • Uma modelagem abstrata dos objetos a serem manipulados e das operações sobre eles
  • Tipo de Dados Abstrato (“Abstract Data Type”)
  • Ex.: Uma “pilha”, com operações “push”, “pop” etc.
  • Uma modelagem concreta do TDA, isto é, como armazenar o TDA em memória/disco e que algoritmos devem ser usados para implementar as operações
  • Ex.: Pilha armazenada como lista encadeada ou vetor ...
  • Projeto versus Implementação
  • Um bom projeto leva a uma boa implementação
  • Todas as idéias principais já foram estudadas
  • A tradução do projeto em programa é quase mecânica
  • (ou não)
  • Programar é uma arte
  • Um algoritmo inferior bem programado pode ser mais útil que um algoritmo eficiente mal programado
  • Há considerações práticas quase tão importantes quanto um bom projeto, como por exemplo,
  • Interfaces
  • Manutenibilidade
  • Documentação
  • Algoritmos e Complexidade
  • Eficiênciade um algoritmo
  • Complexidade de tempo: quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n
  • Pior caso: Considera-se a instância que faz o algoritmo funcionar mais lentamente
  • Caso médio: Considera-se todas as possíveis instâncias e mede-se o tempo médio
  • Eficiência de uma estrutura de dados
  • Complexidade de espaço: quanto “espaço de memória/disco” é preciso para armazenar a estrutura (pior caso e caso médio)
  • Complexidade de espaço e tempo estão freqüentemente relacionadas
  • Algoritmos e Complexidade
  • Eficiência medida objetivamente depende de:
  • Como o programador implementou o algoritmo/ED
  • Características do computador usado para fazer experimentos:
  • Velocidade da CPU
  • Capacidade e velocidade de acesso à memória primária / secundária
  • Etc
  • Linguagem / Compilador / Sistema Operacional / etc
  • Portanto, a medição formal de complexidade tem que ser subjetiva, porém matematicamente consistente
  • Complexidade assintótica
  • Complexidade Assintótica
  • Tempo / espaço medidos em número de “passos” do algoritmo / “palavras” de memória ao invés de segundos ou bytes
  • Análise do algoritmo / e.d. permite estimar uma função que depende do tamanho da entrada / número de dados armazenados (n).
  • Ex.:
  • Percebe-se que à medida que n aumenta, o termo cúbico começa a dominar
  • A constante que multiplica o termo cúbico tem relativamente a mesma importância que a velocidade da CPU / memória
  • Diz-se que T(n)  O(n3)
  • Complexidade Assintótica
  • Definição: T(n)  O( f (n)) se existem constantes c e n0 tais que T(n)  cf (n) para todo n  n0
  • Alternativamente, T(n)  O( f (n)) se lim n T(n) / f (n) é constante (mas não infinito)
  • Exemplo:
  • Limite Superior e Limite Inferior
  • Notação O é usada para estabelecer limites superiores de complexidade
  • Para estabelecer limites inferiores de complexidade usa-se a notação 
  • Definição T(n)   ( f (n)) se existem constantes c e n0 tais que cf (n)  T(n) para todo n  n0
  • Alternativamente, T(n)   ( f (n)) se lim n T(n) / f (n) > 0 para todo n  n0(pode ser, inclusive, infinito)
  • Limites Justos
  • Observe que se T (n)  O (n3) então, T (n)  O (n4), T (n)  O (n5), etc
  • Analogamente, se T (n)  (n3) então, T (n)   (n2), T (n)  (n), etc
  • Se uma função T (n) tem como limites superior e inferior a mesma função f (n), então diz-se que f (n) é um limite justo de T (n), ou T (n)  (f (n))
  • Definição
  • T (n)  (f (n))  T (n)  O (f (n))  T (n)  (f (n))
  • Inventário de funções de complexidade
  • T (n)  O (1) : constante – mais rápido, impossível
  • T (n)  O (log log n) : super-rápido
  • T (n)  O (log n) : logarítmico – muito bom
  • T (n)  O (n) : linear – é o melhor que se pode esperar se algo não pode ser determinado sem examinar toda a entrada
  • T (n)  O (n log n) : limite de muitos problemas práticos, ex.: ordenar uma coleção de números
  • T (n)  O (n2) : quadrático
  • T (n)  O (nk) : polinomial – ok para n pequeno
  • T (n)  O (kn), O (n!), O (nn) : exponencial – evite!
  • Exemplo: Pontos máximos em 2D
  • Um ponto máximo de uma coleção é um que não é dominado por nenhum outro (da coleção)
  • Diz-se que um ponto (x1, y1) domina um ponto (x2, y2) se x1x2 e y1 y2
  • Exemplo – Algoritmo Força Bruta
  • Basta testar todos os pontos e verificar se são máximos: procmaximos(Inteiron,Pontop[1..n]){ paraidesde1aténfazer{ dominado¬falso j¬1 enquantoØdominadoÙj£nfazer{ sei¹jÙdomina(p[j],p[i])então dominado¬verdadeiro j¬j+1 } seØdominadoentãoreportar(p[i]) } }
  • Observações sobre pseudo-código
  • É uma descrição do algoritmo para humanos
  • Não precisa conter detalhes desnecessários
  • Ex.: Assumimos que p não contém pontos duplicados, mas este pode ser um detalhe importante para o implementador
  • Precisa ser inteligível
  • Se o algoritmo usa outro algoritmo, este deve ser óbvio ou deve ser explicitado.
  • Ex.: função domina deve ser explicitada? procdomina(Pontop,Pontoq){ retornarp.x ³ q.xÙp.y ³ q.y }
  • Correção do algoritmo
  • Se o algoritmo não é óbvio, deve-se dar uma justificativa de sua correção
  • Em particular:
  • Enumere restrições sobre a entrada admitida pelo algoritmo
  • Diga porque cada resultado computado satisfaz o que é pedido
  • Diga porque nenhum resultado correto é omitido
  • Análise de complexidade (pior caso)
  • O pior caso acontece quando todos os pontos são máximos
  • O interior do laço mais interno tem complexidade constante, digamos 2 (o comando “se” e a atribuição a “j”)
  • O laço mais interno tem complexidade
  • O interior do laço mais externo tem complexidade
  • O algoritmo tem complexidade
  • Somatórios
  • Propriedades
  • Alguns somatórios notáveis Resolvendo somatórios
  • O que faríamos se não soubéssemos que
  • Usar limites aproximados
  • Aproximar por integrais
  • Justificando a aproximação por integral Resolvendo somatórios por indução
  • Formula-se um palpite e tenta-se prová-lo. Ex.:
  • Prova do caso base:
  • Para n = 0, o somatório é 0
  • Trivialmente verdadeiro se admitirmos d = 0
  • Prova do caso genérico
  • Resolvendo somatórios por indução
  • Prova do caso genérico:
  • Coeficientes de potências iguais têm “bater”
  • Resolvendo temos a = 1/3, b = 1/2 e c = 1/6
  • D0 D1 D2 D3 … DN A0 A1 A2 A3 … AN Array (vetores, matrizes)
  • Organiza dados de mesma natureza (mesmo tamanho) em posições sucessivas da memória
  • Cada dado é identificado por um índice
  • Dado um índice i é possível computar o endereço de memória correspondente em tempo constante
  • Se o array é alocado a partir do endereço A0 e cada dado ocupa k posições, então o i-ésimo elemento está no endereço Ai= A0 + i.k
  • Matrizes são construídas analogamente como vetores de vetores
  • Array
  • Estrutura de dados fundamental
  • Diversas outras estruturas são implementadas usando arrays
  • Em última análise, a própria memória é um array
  • Problemas:
  • Alocação de memória
  • Quantas posições deve ter o array para uma dada aplicação?
  • O que fazer se precisarmos mais?
  • Como inserir um novo dado entre o k-ésimo e o (k+1)-ésimo elemento?
  • Como remover o k-ésimo elemento?
  • Busca em Arrays
  • Dado um array A contendo n valores nas posições A[0] .. A[n-1] e um valor v, descobrir:
  • Se v pertence ao array (problema + simples)
  • Qual ou quais posições de A contêm v (normalmente assume-se que todos os dados em A são distintos)
  • Algoritmo trivial: busca sequencial procbuscasequencial(v,n,A[0..n-1]){ achei¬falso i¬0 enquantoi<nenãoacheifazer{ seA[i]=ventãoachei¬verdadeiro senãoi¬i+1 } seacheientãoreportar(i)senãoreportar(-1) }
  • Busca em Arrays
  • Busca seqüencial simples testa três condições dentro do laço.
  • É possível alterar o algoritmo para empregar apenas um teste no laço de repetição
  • Busca com Sentinela:
  • Usa-se uma posição a mais no final do array (A[n]) que é carregada com uma cópia do dado sendo buscado (v)
  • Como é garantido que v será encontrado, não é preciso se precaver contra o acesso de uma posição i não existente
  • Busca Seqüencial com Sentinela procbusca_com_sentinela(v,n,A[0..n]){ A[n]¬v i¬0 enquantoA[i]¹vfazer{ i¬i+1 } sei<nentão reportar(i)% encontrado senão reportar(-1)% não encontrado } Busca Seqüencial – Análise
  • A análise de pior caso de ambos os algoritmos para busca seqüencial são obviamente O(n), embora a busca com sentinela seja mais rápida
  • A análise de caso médio requer que estipulemos um modelo probabilístico para as entradas. Sejam:
  • E0 , E1 , … En-1 as entradas v correspondentes às situações onde v=A[0], v=A[1], … v=A[n-1]
  • En entradas v tais que vnão pertence ao array A
  • p(Ei) a probabilidade da entrada Eiocorrer
  • t (Ei) a complexidade do algoritmo quando recebe a entrada Ei
  • Assumimos:
  • p(Ei) = q/npara i < n
  • p(En) = 1-q
  • Busca Seqüencial – Análise de Caso Médio
  • Se admitirmos t (Ei) = i+1, então temos como complexidade média:
  • Para q=1/2, temos complexidade média  3n/4
  • Para q=0, temos complexidade média  n
  • Para q=1, temos complexidade média  n/2
  • Arrays Ordenados
  • Se os dados se encontram ordenados (em ordem crescente ou decrescente), a busca pode ser feita mais eficientemente
  • Ordenação toma tempo (n log n)
  • Útil se a coleção não é alterada ou se é alterada pouco freqüentemente
  • Busca seqüencial ordenada tem complexidade média = n/2
  • Busca binária tem complexidade pior caso O(log n)
  • Busca Seqüencial Ordenada procbusca_ordenada(v,n,A [0 .. n]){ A[n]¬v i¬0 enquantoA [i]<vfazeri¬i+1 sei < neA [i] = ventão reportar(i)% encontrado senão reportar (-1)% não encontrado } Busca Binária procbusca_binária(v,n,A [0 .. n–1]){ inf¬0% limite inferior sup¬n-1% limite superior enquantoinf£supfazer{ meio¬(inf + sup)div2 seA [meio]<ventão inf¬meio + 1 senãoseA[meio]>ventão sup¬meio – 1 senão retornar(meio)% Valor encontrado } retornar(-1)% Valor não encontrado } Busca Binária - Análise de Complexidade
  • O algoritmo funciona examinando as posições A[inf], A[inf+1],… A[sup]
  • Cada iteração do laço elimina aproximadamente metade das posições ainda não examinadas. No pior caso:
  • Inicialmente: n
  • Após a 1a iteração: ~ n/2
  • Após a 2a iteração: ~ n/4 …
  • Após a k-ésima iteração: ~ n/2k = 1
  • Logo, no pior caso, o algoritmo faz ~ log2 n iterações, ou seja, o algoritmo tem complexidade O(log n)
  • Arrays - Inserção e Remoção de Elementos
  • É preciso empregar algoritmos de busca se:
  • A posição do elemento a ser removido não é conhecida
  • O array não pode conter elementos repetidos
  • Se o array é ordenado, deseja-se preservar a ordem
  • Deslocar elementos para criar / fechar posições
  • Se o array não é ordenado,
  • Inserção: Adicionar elemento no final do array
  • Remoção: Utilizar o elemento do final do array para ocupar a posição removida
  • Se todas as posições estão preenchidas, inserção ocasiona overflow
  • Realocar o array
  • Reportar erro
  • Exemplo: Inserção em Array Ordenado
  • Assume-se que o array A pode conter elementos iguais
  • Expressões lógicas são avaliadas em curto-circuito procinserção_ordenada (v, n, max, A [0 .. max – 1]) { sen < maxentão { i¬n enquantoi > 0 eA [i–1] > vfazer { A [i] ¬A [i–1] i¬i–1 } A [i] ¬v n¬n + 1 } senãoreportar ("Overflow") }
  • Exemplo: Remoção em Array Ordenado
  • Algoritmo remove o elemento A [i]
  • Pressupõe-se que i foi obtido por uma operação de busca procremoção_ordenada (i, n, A [0 .. n–1]) { sei < nentão { n¬n–1 enquantoi < nfazer { A [i] ¬A [i+1] i¬i+1 } } senãoreportar ("Erro") }
  • Complexidade de Inserção e Remoção
  • Os dois algoritmos para arrays ordenados têm complexidade de pior caso O(n)
  • É possível realizar inserção e remoção em O(1) se não for necessário preservar ordem entre os elementos
  • Observe que:
  • Array ordenado
  • Busca (binária) = O(log n)
  • Inserção/Remoção = O(n)
  • Array não ordenado
  • Busca (seqüencial) = O(n)
  • Inserção/Remoção = O(1)
  • Pilhas, Filas e Deques
  • Arrays, assim como listas*, são freqüentemente usados para implementar coleções seqüenciais de dados onde as alterações (inserção/remoção) são efetuadas apenas no início ou no final da seqüência:
  • Pilha: inserção e remoção na mesma extremidade
  • Fila: inserção numa extremidade e remoção na outra
  • Deque (double-ended queue): inserção e remoção em ambas extremidades * OBS.: Lembre que estamos empregando o termo “array”para denotar coleções de dados de mesmo tamanho armazenados contiguamente em memória. Falaremos de listas mais tarde.
  • Pilhas
  • Dada uma pilha P, podemos definir as seguintes operações:
  • Empilha (dado v,pilha P): acrescenta o dado v no topo da pilha. Pode ocasionar overflow
  • Desempilha (pilha P): descarta o dado mais recentemente empilhado (no topo da pilha). Pode ocasionar underflow
  • Altura (pilha P): retorna o número de elementos de P
  • Topo (pilha P): retorna o dado mais recentemente empilhado. Definida apenas se Altura (P) > 0
  • A política de inserção e remoção à maneira de uma pilha é também conheciada como “LIFO”: Last In, First Out
  • Implementando Pilhas com Arrays
  • Assumimos que uma pilha P tem os seguintes campos/componentes:
  • P.max = número máximo de dados comportado pela pilha
  • P.A [0 .. P.max – 1] = array com P.max elementos
  • P.n = número de elementos presentes na pilha (inicialmente 0)
  • Nossa implementação armazena os dados na pilha em P.A [0 .. P.n – 1], na mesma ordem em que foram empilhados:
  • P.A [0] é o dado mais antigo
  • P.A [P.n – 1] é o dado mais recente
  • Implementando Pilhas com Arrays procempilha (dado v, pilha P) { seP.n < P.maxentão { P.A [P.n] ¬v P.n¬P.n + 1 } senãoreportar ("Overflow") } procdesempilha (pilha P) { seP.n > 0 entãoP.n¬P.n – 1 senãoreportar ("Underflow") } procaltura (pilha P) { retornar (P.n) } proctopo (pilha P) { retornar (P.A [P.n – 1]) } Complexidade da Implementação de Pilha
  • Todas as operações são O(1)
  • Se for necessário tratar overflow com realocação, inserção pode ter complexidade de pior caso O(n)
  • Um novo array de comprimento maior (ex.: 2 max) é alocado
  • Todos os elementos são copiados para o novo array
  • Filas
  • São comumente definidas as seguintes operações sobre filas:
  • Enfileira (dado v, fila F) : o dado v é posto na fila F
  • Desenfileira (fila F) : descarta o dado mais antigo (menos recentemente enfileirado) da fila F
  • Comprimento (fila F) : retorna o número de elementos na fila F
  • Próximo (fila F) : retorna o dado mais antigo da fila F
  • A política de inserção e remoção de dados à maneira de uma fila é conhecida como “FIFO” – First In First Out
  • Filas Implementadas com Arrays
  • Uma fila F pode ser implementada usando uma estrutura com os seguintes campos
  • F.max = número máximo de dados
  • F.A [0 .. F.max–1] = array onde os dados são postos
  • F.início = índice do 1o elemento da fila (inicialmente 0)
  • F.n = número de elementos da fila
  • Os elementos da fila são armazenados consecutivamente a partir de F.A [F.início] podendo “dar a volta” e continuar a partir de F.A [0]. Exemplo:
  • 0 1 2 3 4 5 6 7 8 9 max = 10início = 7 n = 5 A Último elemento Primeiro elemento Filas Implementadas com Arrays procenfileira (dado v, fila F) { seF.n < F.maxentão { F.A [(F.início + F.n) mod F.max] ¬v F.n¬F.n + 1 } senãoreportar ("Overflow") } procdesenfileira (fila F) { seF.n > 0 então { F.início¬ (F.início + 1) mod F.max F.n¬F.n – 1 } senãoreportar ("Underflow") } proccomprimento (fila F) { retornarF.n } procpróximo (fila F) { retornarF.A [F.início] } Ordenação de Arrays
  • Operação de grande importância teórica e prática
  • Muitos algoritmos conhecidos com complexidade O(n log n):
  • HeapSort
  • QuickSort
  • MergeSort
  • Freqüentemente, algoritmos com complexidade assintótica pior – tipicamente O(n2) – acabam sendo mais eficientes para n pequeno:
  • BubbleSort
  • InsertionSort
  • Dividir para Conquistar
  • Vamos estudar o MergeSort, um algoritmo sob o princípio “Dividir para Conquistar” ou “Divide and Conquer”
  • Consiste de:
  • Dividir a tarefa em pequenas subtarefas
  • “Conquistar” – resolver cada subtarefa aplicando o algoritmo recursivamente a cada uma
  • Combinar as soluções das subtarefas construindo assim a solução do problema como um todo
  • Tipicamente, algoritmos do tipo “Dividir para Conquistar” são recursivos
  • Na análise de algoritmos recursivos os limites de complexidade precisam ser determinados resolvendo recorrências
  • MergeSort
  • Considere um array A[1..n]. O algoritmo consiste das seguintes fases
  • DividirA em 2 sub-coleções de tamanho  n/2
  • Conquistar: ordenar cada sub-coleção chamando MergeSort recursivamente
  • Combinar as sub-coleções ordenadas formando uma única coleção ordenada
  • Se uma sub-coleção tem apenas um elemento, ela já está ordenada e configura o caso base do algoritmo
  • entrada 7 5 2 4 1 6 3 0 7 5 2 4 1 6 3 0 Dividir 7 5 2 4 1 6 3 0 7 5 2 4 1 6 3 0 MergeSort saída 0 1 2 3 4 5 6 7 2 4 5 7 0 1 3 6 Combinar 5 7 2 4 1 6 0 3 7 5 2 4 1 6 3 0 MergeSort
  • A rotina MergeSort abaixo ordena as posições i, i+1, … i+n–1 do array A[]
  • A rotina Merge é dada a seguir procMergeSort (A [], i, n) { sen > 1 então { m¬n div 2 MergeSort (A, i, m) MergeSort (A, i + m, n – m) Merge (A, i, i + m, n) } }
  • MergeSort procMerge (A [], i1, i2, n) { array B [] i, j, k¬i1, i2, i1 enquantoi < i2 ej < i1 + nfazer { seA [i] £A[j] então { B [k] ¬A [i] k, i¬k + 1, i + 1 } senão { B [k] ¬A [j] k, j¬k + 1, j + 1 } } enquantoi < i2 fazer { B [k] ¬A [i] i, k¬i + 1, k + 1 } paraidesdei1 atéj–1 fazer { A [i] ¬B [i] } } MergeSort - Considerações
  • MergeSort é um algoritmo de ordenação estável
  • Se dois elementos são iguais eles nunca são trocados de ordem
  • Importante, por exemplo, se os elementos já estão ordenados segundo alguma chave secundária
  • O array auxiliar B não pode ser evitado sem piorar a performance do algoritmo
  • O “overhead” da recursão pode ser aliviado empregando-se um algoritmo mais simples quando os arrays forem pequenos (algumas dezenas)
  • MergeSort - Considerações
  • Pode-se aliviar a situação evitando a cópia dos elementos de B de volta para A
  • Usa-se 2 arrays A e B de mesmo comprimento
  • Em níveis pares da recursão, Merge opera em A usando B para armazenar o resultado
  • Em níveis ímpares a situação é invertida
  • Ao final pode ser necessário copiar de B para A novamente (se o número de níveis de recursão for ímpar)
  • MergeSort - Análise
  • Análise da rotina Merge:
  • Cada chamada mescla um total de n elementos
  • Há três laços de repetição, sendo que cada iteração executa um
  • Related Search

    Previous Document

    LATIHAN 1.docx

    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks