Slides - Complexidade de Algoritmos I

Prévia do material em texto

Linguagens Formais e Autômatos
(Complexidade de Algoritmos)
Profs. Júlio Silveira
e
Sérgio Monteiro
Apresentação
• Objetivos
– Dominar a utilização da complexidade assintótica como ferramenta 
para a avaliação de algoritmos computacionais. 
– Conhecer as principais técnicas utilizadas no projeto de algoritmos 
para produzir soluções corretas e eficientes. 
– Analisar e categorizar diversos problemas da área de comutação, 
relacionando-os com as principais técnicas algorítmicas estudadas. 
Apresentação
• Ementa
– Notação assintótica. Análise de algoritmos.
– Recorrências. Técnicas de Programação. Algoritmos de ordenação.
– Estruturas de Dados: Listas, Filas, Pilhas, Árvores, e suas aplicações.
– Grafos e algoritmos clássicos.
Bibliografia
• Básica
• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos – Teoria e 
Prática. Tradução da 3ª edição americana.
Rio de Janeiro: Elsevier, 2012.
• SZWARCFITER, J. L.; MARKENZON, L. Estrutura de Dados e seus Algoritmos. 
Rio de Janeiro: LTC, 1997.
• TOSCANI, L.V.; VELOSO, P.A.S. Complexidade de Algoritmos. Série Livros 
Didáticos, N°. 13. 2. ed. Porto Alegre: Sagra Luzzato, 2005. 
Bibliografia
• Complementar
• CELES, W. et al. Introdução a Estrutura de Dados. Rio de Janeiro: Campus, 
2004. 
• LOUDON, K. Mastering Algorithms with C. O'Reilly Media. 1st edition, 1999. 
• SHARRER, C.A. A Practical Introduction to Data Structures and Algorithm 
Analysis. 2nd Edition. Upper Saddle River,NJ: Prentice Hall, 2001. 
• TENENBAUM, A. M. et al. Estruturas de Dados Usando C. São Paulo: Pearson 
Makron Books, 1995. 
• ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2. ed. 
São Paulo: Pioneira Thomson Learning, 2004. 
Aula 1
• Conceitos básicos
– Problema computacional
• Definição
• Instância de um problema
• Tamanho da entrada
– Algoritmo
• Definição
• Revisão de algoritmos, Exemplos
• Noções intuitivas de melhor caso, pior caso, e caso médio
Problema Computacional
• Algoritmo
– Procedimento computacional bem definido
• Toma um conjunto de valores como entrada, e
• Produz um conjunto de valores como saída.
– Conjunto finito de instruções
• realizadas passo a passo, para a
• resolução de um problema computacional bem definido.
Definição de Problema Computacional
• Enunciado que especifica formalmente:
– Descrição genérica de uma entrada de um dado “tamanho”; e
– Descrição da saída correspondente à entrada fornecida
– Opcionalmente pode incluir o “nome” do problema
• O enunciado não especifica “como gerar” a saída
– O “como gerar” é solução do problema
– Solução do problema: um algoritmo
Definição de Problema Computacional
• Tamanho da entrada
– Parâmetro numérico que descreve sua magnitude
– Um valor n, ou a quantidade de dígitos binários ou decimais 
necessários para representá-lo.
• Exemplo: Encontrar o n-ésimo termo da sequência de Fibonacci
– Se a entrada for um conjunto de valores, o tamanho da entrada n
geralmente caracteriza a cardinalidade do conjunto.
• Exemplo: Ordenar um vetor com n elementos.
Instância de um Problema
• O problema computacional apenas descreve
– Caracteriza um par (entrada, saída), em termos genéricos
– Especifica o tamanho da entrada por um parâmetro numérico
• Instância de um problema
– Um caso particular do problema
– Exemplo específico de par entrada/saída específico
Problema Computacional
• Exemplo 1
– Nome: Calcular o n–ésimo termo da sequência de Fibonacci
– Entrada: n (valor natural: n ≥ 0)
– Tamanho: n ou log2 (n+1) (bits necessários para representar n)
– Saída: F(n)
F = 0, 1, 1, 2, 3, 5, 8, 13, 21,…
Problema Computacional
• Exemplo 1: calcular o n–ésimo termo da sequência de Fibonacci
• Instância do problema
– Entrada: 8 (1000)2
– Tamanho: 4 (bits)
– Saída: 21
F = 0, 1, 1, 2, 3, 5, 8, 13, 21,…
Problema Computacional
• Exemplo 2
– Nome: Ordenação (crescente) dos termos de uma sequência
– Tamanho: n
– Entrada: (vetor, n) { vetor[1..n] }
{ n: número de elementos }
– Saída: vetor ordenado { Permutação dos valores do 
vetor em ordem crescente }
Problema Computacional
• Exemplo 2: Ordenação
• Instância do problema
– Entrada: ( [13, 40, 8, 30, 9, 15, 2], 7 )
– Tamanho: 7
– Saída: [2, 8, 9, 13, 15, 30, 40]
Problema Computacional
• Exemplo 3
– Nome: Busca não-ordenada (em um vetor qualquer)
– Tamanho: n
– Entrada: (vetor, n, chave) { vetor[1..n] }
{ n: número de elementos }
{ chave: valor procurado }
– Saída: i Se vetor[i] = chave
0 caso chave ∉∉∉∉ vetor
Problema Computacional
• Exemplo 3: Busca não-ordenada
• Instâncias do problema
1. Entrada: ( [15, 3, 25, 40, 31, 2, 8], 7, 25) Tamanho: 7 Saída: 3
2. Entrada: ( [15, 3, 25, 40, 31, 2, 8], 7, 29) Tamanho: 7 Saída: 0
3. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 25) Tamanho: 7 Saída: 5
Problema Computacional
• Exemplo 4
– Nome: Busca ordenada (em um vetor ordenado )
– Tamanho: n
– Entrada: (vetor, n, chave) { vetor[1..n] , ordenado }
{ n: número de elementos }
{ chave: valor procurado }
– Saída: i Se vetor[i] = chave
0 caso chave ∉∉∉∉ vetor
Problema Computacional
• Exemplo 4: Busca ordenada
• Instâncias do problema
1. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 25) Tamanho: 7 Saída: 5
2. Entrada: ( [2, 3, 8, 15, 25, 31, 40], 7, 29) Tamanho: 7 Saída: 0
Problemas e Algoritmos
• Problema: Busca não ordenada
– Busca sequencial
• Problema: Busca ordenada
– Busca sequencial, Busca binária
• Problema: Ordenação
– Bolha, Seleção, Inserção, Quick, Merge, Heap, Counting, Radix
Análise de Algoritmos
• Analisando algoritmos
– Definição: T(I)
• Tempo para um algoritmo processar uma instância de entrada I, onde |I| = n
• Medido em instruções básicas de computação
• Função do tamanho da entrada: T(I) é função de n
• Exemplo
• Um algoritmo processa uma entrada I, de tamanho n, e executa 2n2
instruções (atribuições, comparações, …)
T(I) = 2n2
Análise de Algoritmos
• Para um algoritmo qualquer, definimos:
– Tempo de MELHOR CASO
• Dentre todas as entradas de tamanho n: f(n) = min |I|=n { T(I) }
– Tempo de PIOR CASO
• Dentre todas as entradas de tamanho n: f(n) = max |I|=n { T(I) }
– Tempo de CASO MÉDIO:
• Dentre todas as entradas de tamanho n: f(n) = |I|=n p(I) T(I)
p(I): probabilidade de ocorrência da entrada I,
dentre todas as entradas de tamanho n
Análise de Algoritmos
• Analisando algoritmos
– Exemplo
• Problema: Busca em vetor não ordenado
Entrada: (vetor, n, chave)
• Proposta: T(I) = número de COMPARAÇÕES com elementos
do vetor, efetuadas por um algoritmo qualquer
v[1] v[2] v[3] v[4] … v[n]
Análise de Algoritmos
• Exemplo (busca em vetor não ordenado)
– Algoritmo: busca sequencial
• Comparar chave com v[1], v[2], v[3], …, v[n]
• T(I) = número de COMPARAÇÕES com elementos
do vetor, efetuadas por um algoritmo qualquer
v[1] v[2] v[3] v[4] … v[n]
Análise de Algoritmos
• Algoritmo: busca sequencial
BUSCASEQNAOORD (v,n, chave)
1 Para i = 1 até n faça
2 Se chave = v[i] então
3 Retorne i
4 Retorne 0
i = 1,2,3,4,…………,n (n vezes)
Análise de Algoritmos
• Exemplo: Algoritmo de busca sequencial
– Tempo de MELHOR CASO f(n) = 1 comparação  f(n) = O(1)
– Tempo de PIOR CASO f(n) = n comparações  f(n) = O(n)
• O(1) e O(n)?
– O que é isso?
– Veremos depois.
Análise de Algoritmos
• Algoritmo de busca sequencial
– Comparações
• Se chave = v[i], são efetuadas i comparações
• Se chave ∉∉∉∉ v, são efetuadas n comparações
– Tempo de CASO MÉDIO
• f(n) = |I|=n p(I) T(I)
• Depende da distribuição de probabilidade das instâncias
• Ou seja, dependeda aplicação
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 1
• n = 5
• Probabilidades
– p1 = (chave=v[1]) = 
� �⁄ = 0.2
– p2 = (chave=v[2]) =
� �⁄ = 0.2
– p3 = (chave=v[3]) =
� �⁄ = 0.2
– p4 = (chave=v[4]) = 
� �⁄ = 0.2
– p5 = (chave=v[5]) =
� �⁄ = 0.2
v[1] v[2] v[3] v[4] v[5]
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 1 v[1] v[2] v[3] v[4] v[5]
� � =
� � = 3.0
� 15 × �
�
���
= 15��
�
���
= 15 1 + 2 + 3 + 4 + 5 = 
15
5
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 2
• n = 5
• Probabilidades
– p1 = (chave=v[1]) = 0.1
– p2 = (chave=v[2]) = 0.1
– p3 = (chave=v[3]) = 0.1
– p4 = (chave=v[4]) = 0.1
– p5 = (chave=v[5]) = 0.6
v[1] v[2] v[3] v[4] v[5]
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 2 v[1] v[2] v[3] v[4] v[5]
� � =
� � = 4.0
� �� × �
�
���
= �0.1 × �
�
���
 + 0.6 × 5 = 0.1 1 + 2 + 3 + 4 + 3
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 3
• n = 5
• Probabilidades
– p1 = (chave=v[1]) = 0.5
– p2 = (chave=v[2]) = 0.1
– p3 = (chave=v[3]) = 0.1
– p4 = (chave=v[4]) = 0.1
– p5 = (chave=v[5]) = 0.1
– pi = ( chave ∉∉∉∉ v ) = 0.1
v[1] v[2] v[3] v[4] v[5]
Análise de Algoritmos
• Algoritmo de busca sequencial
– Tempo de CASO MÉDIO: EXEMPLO 3 v[1] v[2] v[3] v[4] v[5]
� � =
� � = 2.4
� �� × � + 0.1 × 5
�
���
 = 0.5 × 1 +��� × �
�
���
 + 0.1 × 5
= 0.5 × 1 + 0.1 × 2 + 3 + 4 + 5 + 5 = 0.5 + 0.1 × 19
Análise de Algoritmos
• Tempo de CASO MÉDIO do algoritmo de busca sequencial
– EXEMPLO 4
• Sempre teremos chave ∈ vetor. Ou seja, p(chave ∈∈∈∈ vetor) = 100%
• Distribuição uniforme. Ou seja, pi = p(chave=vetor[i]) = 
�
�
� � =
� � = � + 12
� 1� × �
�
���
= 1���
�
���
= 1� 1 + 2 + 3 +⋯+ � = 
1
� 
(1 + �)�
2
Análise de Algoritmos
• Tempo de CASO MÉDIO do algoritmo de busca sequencial
– Exercício
• Insucesso (chave ∉ vetor)
– pi = p(insucesso) = 50%
– Número de comparações = n
• Sucesso
– Iguais probabilidades de encontrarmos o valor chave em qualquer posição.
– Ou seja, pi = pi , ꓯ i,j ∉ { 1, 2, ..., n }
Análise de Algoritmos
• Tempo de CASO MÉDIO do algoritmo de busca sequencial
– Exercício (cont.)
• Insucesso (chave ∉∉∉∉ vetor) :
– Com probabilidade = 
�
 ocorrerão n comparações
Análise de Algoritmos
• Tempo de CASO MÉDIO do algoritmo de busca sequencial
– Exercício (cont.)
• Sucesso (chave ∈ vetor) 
– Ocorrerão comparações conforme a posição da chave
– Probabilidade total = 
�
� , igualmente distribuída pelos elementos
– Logo, para um dado índice i específico:
pi = p(chave=vetor[i]) = 
Serão efetuadas 
!"%
� = 
�
 �
i comparações
Análise de Algoritmos
• Tempo de CASO MÉDIO do algoritmo de busca sequencial
– Exercício (cont.)
• Resposta:
� � = 12 × � + �
1
2� × �
�
���
= �� + 
�
�� 1 + 2 + 3 +⋯+ � =
�
2 + 
1
2� ∙
1 + � �
2
f(n) = %�&�� 
= �2 + 
� + 1
4 = ⋯ = 
3� + 1
4
 
Análise de Algoritmos
• Mas por que escolher uma instrução?
– No exemplo dado, escolhemos a comparação.
– E as demais instruções do algoritmo?
• Veremos nas próximas aulas.
Obrigado!