Análise de Algoritmos
AULA 1
Profa. Sandra de Amo
Disciplina: Análise de Algoritmos
Pós-graduação em Ciência da Computação
Objetivos Gerais
Conceitos Básicos
AULA 1 – Parte I
Profa. Sandra de Amo
Disciplina: Análise de Algoritmos
Pós-graduação em Ciência da Computação
“Problemas” e “Algoritmos”

O que é um problema ?

Função P: Input  Output

Instância do Problema = I ϵ Input

Exemplos de Problemas

Problema dos Primos

Primos: N  {Sim, Não}
Instância = número natural
Primos (n) = Sim, se n é primo; Não, caso contrário

Problema da Decomposição em primos

Decomposição:
N  {Seq | Seq = <(p1,n1),...,(pk,nk)>, pi primo}
Decomposição (n) = <(p1,n1), ..., (pk,nk)> se n = p1n1p2n2...pknk
Exemplo: Decomposição (10) = <(2,1), (5,1)>, pois 10 = 21.51
“Problemas” e “Algoritmos”


Problema do Circuito Hamiltoniano
 Hamilton: Grafos Dirigidos  {Sim, Não}
Instância = grafo dirigido G
Hamilton(G) = Sim, se G possui um caminho
passando por todos os vértices uma única vez;
= Não, caso contrário
Problemas de Decisão: output = {Sim, Não}
“Problemas” e “Algoritmos”

Solução de um Problema

Conjunto finito de instruções cuja execução sobre o input termina
depois de um tempo finito, produzindo no final o output.
Algoritmo que resolve o problema



Solução de um problema = algoritmo
Algoritmo : conjunto finito de instruções que transformam uma entrada
em uma saída depois de um tempo finito.
Todo Algoritmo está associado a um Problema
Perguntas
Função injetora ??
Conjunto dos Algoritmos
Conjunto dos Problemas
???
Não é função injetora: podem existir diferentes algoritmos para resolver um
mesmo problema
Não é função sobrejetora: Existem problemas que não têm solução
Problema de Correspondência de Post
(PCP)
Post: Dominós  {Sim,Não}
Instância= um conjunto de tipos de peças
de dominós
Post(D) = Sim, se existe um pareamento de
peças de tipos em D
= Não, caso contrário.
O problema PCP
Input = um conjunto finito de tipos de peças de dominós
g
abc
bcd
bcd
fg
eg
b
ef
1
2
3
…
4
ef
cde
n
Pergunta : É possivel encontrar um pareamento, isto é,
uma sequência de peças de tipos dados no input, tal que o string formado
na parte de cima e idêntico ao string formado na parte de baixo ?
bcdefg
bcdefg
Sequência : 3 n 1
Exemplos
b
a
ca
abc
ca
ab
a
c
1
2
3
4
abcaaabc
abcaaabc
Sequência de peças= 2 1 3 2 4
Exemplo
Input
abc
ca
acc
ab
a
ba
1
2
3
Resposta ??
Não
Justificativa : a parte de cima das peças é sempre
maior que a parte de baixo !
Formalização do Problema
Input genérico do Problema PCP
C={
t1
b1
,
t2
b2
,
t3
b3
, …
,
tn
bn
}
t1, t2, …, tn são strings sobre um alfabeto S
b1, b2, …, bn são strings sobre um alfabeto S
Um pareamento (match) = uma sequência <i1, i2, …, ik> de números em {1,…,n}
tal que
ti1 ti2 … tik = bi1 bi2 … bik
= string do pareamento
Pergunta : Existe um pareamento para o input C ?
Solução quando existe, não precisa ser
única
Problema da Ordenação
Ordena : SeqNat  SeqNat
Ordena(<a1,...,an>) = <b1,...,bn>
Onde: <b1,...,bn> é uma permutação de <a1,...,an>
b1 ≤ b2 ≤ ... ≤ bn
Algoritmos que o resolvem:
Insertion-Sort
Selection-Sort
Bubble-Sort
Eficiência em
Heap-Sort
Tempo cresce
Merge-Sort
Quick-Sort
Radix-Sort
Bucket-Sort
Insertion-Sort
Selection-Sort
Bubble-Sort
Heap-Sort
Merge-Sort
Quick-Sort
Radix-Sort
Bucket-Sort
Eficiência em
Espaço cresce
O que é um bom algoritmo ?



Correto ?
Eficiente em tempo ?
Eficiente em espaço ?
Soluções Aproximadas às vezes são
mais interessantes...
Problema do Vertex Cover (otimização)
Achar o menor subconjunto de vértices S tal que
cada aresta tem pelo menos uma d e suas extremidades
no conjunto S ?
Problema de Minimização de recursos
• Encontrar a solução ótima é difícil
• Problema NP-hard
• Encontrar solução aproximada é factível
Existem algoritmos que encontram soluções aproximadas em tempo polinomial
Para cada input G, o algoritmo dá uma solução com custo C(G) tal que:
C(G) ≥ α Opt(G)
Soluções Aproximadas nem sempre são
facilmente encontráveis
Problema do Caixeiro Viajante (otimização)
Achar o circuito hamiltoniano mais curto (passando por todas
as cidades uma única vez) ?
Problema de Minimização de recursos
• Encontrar a solução ótima é difícil
• Problema NP-hard
• Encontrar solução aproximada não é factível !
d3
d1
d2
d4
d6
d5
Tipos de Algoritmos
Problema P




P é decidível (tem solução ?)
Qual a complexidade de P ?
Se P for NP-completo: existem algoritmos aproximados ?
Como projetar um bom algoritmo para P, dentro das
limitações da complexidade inerente ao problema P ?
Tipos de Algoritmos:



Exatos versus Aproximativos
Iterativos versus Recursivos
Probabilísticos (ou Randômicos)
O que é um Algoritmo Probabilístico ?
Problema: Encontrar um elemento a em um array A de n elementos
Input: A, a , n
Output: posição m onde se encontra a ou ‘Não’
Algoritmo Exato
Begin
Para i = 1, ..., n faça
Se A[i] = a
Retorna i
Pára
Retorna ‘Não’
End
Se n é muito grande, algoritmo pode levar muito tempo para dar a
resposta .
O que é um Algoritmo Probabilístico ?
Problema: Encontrar um elemento a em um array A de n elementos
Input: A, a , n
Output: posição m onde se encontra a ou ‘Não’
Algoritmo Monte Carlo (não exato)
begin
i=1
repeat
Selecione aleatoriamente um número inteiro m em [1,n]
Se A[m] = a
Retorna m e pára
i=i+1
until i=k
Retorna ‘Não’
end
Monte Carlo encontra ‘a’ com Probabilidade (1 – (1/2)k)
Tempo de Execução de Monte Carlo é fixo
Análise de um Algoritmo
O que é analisar um algoritmo ?
Determinar sua eficiência
 quanto ao tempo de execução
 quanto à quantidade de memória utilizada para executar o
algoritmo
Modelo para a Análise da complexidade: Modelo RAM
(Random Access Machine)
 Operações executadas em sequência
 Não há execuções simultâneas
Análise de um Algoritmo
Que operações atômicas considerar no cálculo de custo ?
Operações atômicas = custo constante

Operações aritméticas


Movimentação de dados:


Soma, subtração, multiplicação, divisão, resto, piso, teto
Carregar, armazenar, copiar
Controle


Desvio condicional e incondicional
Chamada e retorno de subrotinas
Exemplo: Problema, Algoritmo, Análise do
Algoritmo
Problema: (Ordenação de uma sequência)
Input: sequência de n números A = <a1,...,an>
Output: B = <b1,...,bn>, onde B é uma
permutação de A e b1≤ b2 ≤ ... ≤ bn
Projeto de um Algoritmo
Algoritmo Insertion-Sort
Insertion-Sort (A)
1.
2.
3.
4.
5.
6.
7.
Entrada : A = array [a1,...,an]
For j  2 to n
do chave  A[j]
ij–1
% Procura lugar anterior onde inserir a chave
While i > 0 e A[i] > chave
do A[i+1]  A[i]
ii-1
A[i+1]  chave
Algoritmo é executado in place :
Espaço necessário = espaço da entrada + espaço das variáveis Chave, j, i
Complexidade em Espaço = constante (=3)
(não se conta o espaço ocupado pela entrada)
Algoritmo Insertion-Sort
Insertion-Sort (A)
1.
2.
3.
4.
5.
6.
7.
For j  2 to n
do chave  A[j]
ij–1
While i > 0 e A[i] > chave
do A[i+1]  A[i]
ii-1
A[i+1]  chave
Custo
c1
c2
c3
c4
c5
c6
c7
Vezes
n
n-1
n-1
Σnj=2 tj
Σnj=2 (tj-1)
Σnj=2 (tj-1)
n-1
tj = número de vezes que o teste do While em (4) é executado para cada valor j
do loop for
Algoritmo Insertion-Sort
T(n) = custo temporal do algoritmo em função do tamanho da
entrada (=n)
T(n) = c1.n + c2(n-1) + c3(n-1) + c4(Σnj=2 tj) + c5(Σnj=2 (tj-1)) + c6(Σnj=2 (tj-1)) + c7(n-1)
T(n) depende de tj
O valor de tj depende do “grau de desordenação” da entrada.
Algoritmo Insertion-Sort
Melhor caso: a entrada está corretamente em ordem crescente.

tj = 1, para j = 2,...,n
T(n) = c1.n + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1)
= (c1+c2+c3+c4+c7)n – (c2+c3+c4+c7)
Pior caso : a entrada está ordenada de forma reversa (descrescente)

tj = j, para j = 2,...,n
Σnj=2 j = [n(n+1)/2] – 1
T(n) = c1.n + c2(n-1) + c3(n-1) + c4([n(n+1)/2] – 1) + c5([n(n-1)/2]) +
+ c6([n(n-1)/2]) + c7(n-1) =
= (c4/2 + c5/2 + c6/2)n2 + (c1+c2+c3 - c4/2 - c5/2 - c6/2 + c7)n - (c2 + c3 + c4 + c7)
Algoritmo Insertion-Sort
Caso médio:
tj = j/2, para j = 2,...,n
Exercício: Determinar o valor de T(n) para o caso médio.
Notação O
Notação O é utilizada para ter uma estimativa superior
do tempo T(n) de execução, em termos de funções
do tipo nk, logn, 2n, cujas tendências de crescimento
seguem padrões distintos.

No melhor caso:


T(n) = O(n)
No pior caso:

T(n) = O(n2)
Apresentação Geral do Curso
AULA 1 – Parte II
Profa. Sandra de Amo
Disciplina: Análise de Algoritmos
Pós-graduação em Ciência da Computação
Apresentação Geral do Curso




Bibliografia
Material de Suporte
Conteúdo
Avaliação
Bibliografia Básica
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Introduction to Algorithms, MIT Press, 3ª Edição, 2009.
(Edição em portugues : “Algoritmos-Teoria e Prática”, Editora Campus 2003)
2. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. McGraw-Hill
Science/Engineering/Math; 1 edition (September 13, 2006). PDF disponível
online.
3. Donald E. Knuth. The Art of Computer Programming, Volume 4A:
Combinatorial Algorithms,Part 1. (Series in Computer Science & Information
Processing) Addison-Wesley Professional, 2011.
4. Vijay V. Vazirani. Approximation Algorithms. Addison-Wesley 2001
Bibliografia Complementar
1.
David Harel and Yishai Feldman. Algorithmics: The Spirit of
Computing, 3a Edição, Addison Wesley, 2004.
2. Steven S. Skiena: The Algorithm Design Manual. Springer, 2a
Edição., 2008.
3. Bernhard Korte, Jens Vygen. Combinatorial Optimization:
Theory and Algorithms (Algorithms
and Combinatorics), 4a Edição, 2010.
Material de Suporte
http://www.deamo.prof.ufu.br/CursoAA2013.html



Livro Texto
Slides
Artigos
Conteúdo do Curso
Parte I : Conceitos Básicos
 O que é um algoritmo ?
 Algoritmos Recursivos, Randômicos (Probabilísticos) ,
Aproximativos
 Análise e projeto de algoritmo
 Notação Assintótica
Parte II: Algoritmos de Ordenação:
 Tempo não linear: ocupação otimal de espaço
 Tempo linear : ocupação não otimal de espaço
Parte III : Estruturas de Dados
 Elementares: Pilhas, Filas, listas, árvores binárias, tabelas hash
estatísticas de ordem dinâmicas
 Avançadas: B-Tree, Heaps binomiais, Heaps de Fibonacci, estruturas
de dados para conjuntos
Conteúdo do Curso (cont.)
Parte IV : Técnicas Avançadas de Projeto e Análise
 Programação Dinâmica
 Algoritmos Gulosos
Parte V: Algoritmos de Grafos
 Algoritmos elementares
 Árvores Espalhadas
 Caminhos mais curtos
Parte VI : Tópicos Avançados
 Problemas NP-completos
 Algoritmos Combinatórios
 Algoritmos Aproximativos
Critério de Avaliação

Prova 1 : 23 de Abril
25 pontos

Prova 2: 10 de Junho
25 pontos

Prova 3 : 2 de Julho
30 pontos

Seminários : 8, 9 e 10 de Julho
20 pontos