Análise de Algoritmos
Licenciatura em Eng.ª Informática
Prof. Lufialuiso Sampaio Velho
2º Ano - IIº Semestre 2013
Objectivos
• Abordar sobre os fundamentos da resolução de problemas usando algoritmos
• Analisar o crescimento de funções e a eficiência dos algoritmos
• Abordar sobre as diferentes técnicas de resolução de problemas existentes.
AALG - 2013
Metodologia e Avaliação
As aulas terão uma componente teórico – prática com um leque de exercícios a serem entregues após uma semana.
Avaliações contínuas – (30%)
• Prova parcelar
• Exercícios feitos em sala de aula ou em casa
Exame - (70%)
Aulas de Apoio: Terça e Quinta - Feira
AALG - 2013
contactos
Email da disciplina: [email protected]
Utilizar moderadamente para: • Dúvidas • Sugestões
Email do Docente: [email protected]
Obtenção de Material didáctico Acetatos entregues via • Partilha de ficheiros no Google Drive • Pendrive na sala de Aula
AALG - 2013
Programa da disciplina
Introdução aos Algoritmos
• Definição, porquê estudá-los?
• Fundamentos sobre a resolução de problemas utilizando algoritmos
• Tipos de problemas importantes: Ordenação, busca, grafos
Fundamentos da Análise da Eficiência do Algoritmo
• Estrutura da Análise de Algoritmos
• Notação assintótica e crescimento de funções
• Análise de Algoritmos não recursivos
• Análise de Algoritmos recursivos e recorrências
AALG - 2013
Programa da disciplina
Técnicas de Projecto de Algoritmo
• Força Bruta
• Dividir e conquistar
• Decrementar e conquistar
• Transformar e conquistar
• Estratégia Gulosa
AALG - 2013
Bibliografia Levitin, Anany – Introduction to The Design and Analysis of Algorithms – 3rd
Edition
ZIVIANI, Nivio. Projecto de Algoritmos com implementação em Pascal e C /
ou implementação com Java e C++.
H. Cormen,THOMAS; E. Leiserson, Charles; . ALGORITMOS – Tradução da 2ª
Edição Americana – Teoria e Prática – Editora Elsevier
Toscani, Laira Vieira - COMPLEXIDADE DE ALGORITMOS - VOL.13 - 3ª Edição –
Editora Bookman
AALG - 2013
AULA I Introdução aos Algoritmos
Licenciatura em Eng.ª Informática
O que é um algoritmo
Fundamentos sobre a resolução de problemas usando algoritmos
Tipos de problemas importantes
Introdução aos Algoritmos
AALG - 2013
Para a solução de qualquer problema associado ao nosso dia à dia em
diferentes áreas, fazemos o uso dos algoritmos.
Do ponto de vista prático, o profissional da área de computação precisa:
conhecer os algoritmos de diferentes áreas (ciências)
aprender a escrever excelentes algoritmos e analisar a sua eficiência
tanto do ponto de vista de tempo e espaço
usar os algoritmos para desenvolver a sua habilidade analítica
Em suma este conhecimento é muito mais do que escrever um bom
programa para computadores, pois serve como ferramenta para a
compreensão de temáticas associadas a química, música, física,
aeronáutica, etc.
Porquê o estudo de Algoritmos?
AALG - 2013
AALG - 2013
Um algoritmo, define uma sequência não ambígua de instruções que visam
solucionar um determinado problema; isto é, obtendo o resultado requerido
a partir de um conjunto de dados de entrada em tempo finito[1].
O que é um Algoritmo?
São considerados como algoritmos: uma receita, processo, técnica,
procedimento de rotina, com os seguintes requisitos: finitude, definitude,
entrada, saída, e eficácia.
AALG - 2013
Exemplo do problema computacional : Ordenação
Imagine que pretende ordenar uma sequencia não ordenada de inteiros.
Declaração do 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 sequência <5, 3, 2, 8, 3>
Algoritimos:
– Selection sort (selecção)
– Insertion sort (inserção)
– Merge sort (intercalação )
– Buble sort (bolha)
– (muito outros)
AALG - 2013
Algoritmo Euclidiano
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 seja zero (0), o que torna o problema trivial.
Exemplo: mdc(60,24) = mdc(24,12) = mdc(12,0) = 12
AALG - 2013
Descrição do algoritmo
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 o valor de r para n.
volta para o Passo1.
Em pseudocódigo
enquanto n ≠ 0 faça
r ← m mod n
m← n
n ← r
retorna m
AALG - 2013
Algoritmo Euclidiano
Caso prático
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
AALG - 2013
Outro método
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 Etapa 3; caso contrário, vá para a Etapa 4
Passo 3: Divide n por t. Se o resto for 0, retorna t e pára; caso contrário, vá para a Etapa 4
Passo 4: Reduz t por 1 e vá para a Etapa 2
Nota: Isto não funciona quando um dos números de entrada (m ou n) é zero.
AALG - 2013
Fundamentos para a solução de problemas Algorítmicos
Para a solução de um problema precisamos de:
Entender o problema
Determinar a capacidade do computador
Escolher a forma de resolução de problema (exacto ou aproximado)
Determinar a técnica de desenho do algoritmo
Escolher a estrutura de Dados
Método de especificação do algoritmo
Provar a exactidão do Algoritmo
Analisar o algoritmo
Codificar o algoritmo
AALG - 2013
Análise de Algoritmos
A análise de um algoritmo implica prever a quantidade de recursos que o
mesmo necessitará (memória, largura de banda).
Frequentemente o foco tem estado relacionado a medida do tempo que um
determinado algoritmo necessita para ser executado. Vimos no exemplo anterior
que para um determinado problema, vários algoritmos concorrem para a
solução do mesmo, permitindo assim a escolha do algoritmo mais eficiente,
descartando assim os de qualidade inferior.
Para analisar-mos o tempo de execução dos algoritmos utilizaremos o modelo
RAM (Random Access Machine).
Este modelo permite que as instruções sejam executadas sequencialmente uma
após outra, não permitindo instruções concorrentes (simultâneas) isto implica
que este modelo permite somente executar apenas algoritmos sequenciais, e
determinar o seu tempo de execução.
AALG - 2013
Questões a considerar
Podem existir inúmeros algoritmos para solucionar o mesmo problema,
mas com ideias diferentes e podem ser executados em velocidades
diferentes.
Um algoritmo pode ser representado de diversas formas: pseudocódigo,
fluxograma, narrativa, etc.
A construção eficiente dos algoritmos constitui uma base que distingue
os programadores qualificados dos iniciantes.
AULA 2 Fundamentos da Análise da Eficiência
do Algoritmo
Licenciatura em Eng.ª Informática
AALG - 2013
Análise de Algoritmos
Dado um algoritmo, podemos questionar-nos:
• Ele resolve o problema proposto?
• Quão eficiente é este algoritmo?
• É a única forma de resolver o problema?
• Como posso avaliar este ou aquele algoritmo?
Existem vários critérios pelos quais podermos avaliar os algoritmos. Estes critérios
são: Correcção (exactidão), Eficiência temporal, Eficiência Espacial, e a
Optimização.
Cada um dos critérios acima podem ser aplicados sobre as abordagens:
Experimental (empírica) e Teórica (analítica).
AALG - 2013
Abordagens de análise Abordagem experimental
Implementa o algoritmo e executa o programa para um conjunto de dados de
teste. Isto significa que sob esta abordagem, os resultados serão grandiosamente
influenciados pelo nível da máquina em que foi implementado (Hardware),
podendo assim variar a sua eficiência mediante a capacidade do processador
ou outro recurso.
Porém,
• Não podemos testar todas as possíveis entradas
• Podem ocorrer situações não previstas durante a criação do algoritmo,
podendo resultar em falha ou então uma boa ou má implementação.
Abordagem Analítica
Vê o algoritmo de uma forma generalizada, e tenta prever o seu
comportamento, procurando saber se ele resolve o problema, e o nível de
eficiência que o mesmo possui (custo de tempo e memória).
AALG - 2013
Estrutura da Análise
De que modo é analisado a eficiência de um Algoritmo?
Existem basicamente dois tipos de eficiência de algoritmos, nomeadamente:
• Eficiência Temporal: refere-se ao quão rápido um algoritmo é executado.
• Eficiência espacial: refere-se ao espaço extra que o algoritmo necessita.
Para o contexto desta disciplina, aprenderemos apenas a analisar o factor
tempo dos algoritmos, visto que o espaço não é uma variável bastante
influenciadora em comparação com o tempo.
Sendo assim para a eficiência temporal, é necessário considerar:
Tamanho de Entrada: a execução de qualquer algoritmo é influenciada
fortemente pelo sobre entradas maiores. Isto significa que é analisada a
eficiência temporal do algoritmo em função do parâmetro n (tamanho de
entrada).
AALG - 2013
Tempo de execução
Para medir o tempo de execução, baseamo-nos nas seguintes alternativas:
• Contar o número de vezes que cada operação do algoritmo é realizada
• Identificar a operação mais importante do algoritmo (operação básica). Esta
operação contribui bastante no tempo de execução total do algoritmo.
Isto implica que a eficiência do tempo é analisada pela determinação do
número de repetições da operação básica do algoritmo em função do
tamanho da entrada. tamanho de entrada
tempo de execução nº de vezes que a operação
básica é executada
AALG - 2013
Eficiência Temporal
• Entrada:
– Dados fornecidos
• Tamanho de entrada
– pode ser dado como número de valores num vector, o número de
registos num ficheiro, enfim, um certo número de elementos que
constituem a entrada de dados para o algoritmo; de modo que o tempo
de execução de um algoritmo pode ser dado como uma função T(n) do
tamanho n da sua entrada.
AALG - 2013
Exemplos de tamanho da entrada e operação básica
Problema medida de tamanho da entrada
Operação Básica
busca de chave em uma lista de n itens
número de itens da lista, i. e. n
comparação de chave
Multiplicação de duas matrizes
A dimensão da matriz ou o nº total dos elementos
Multiplicação de dois números
verificação de primalidade de um dado número inteiro n
Tamanho n = número de digitos (em representação binária)
divisão
problema de grafo típico Nº de vértice e/ou arcos Visita a vértice ou travessia nos arcos.
AALG - 2013
Eficiência Temporal: Melhor-caso, Caso médio e pior-caso
Para alguns algoritmos, a eficiência depende de dados fornecidos:
• Pior caso: Cpior(n) – máximo sobre as entradas de tamanho n
• Melhor caso: Cmelhor(n) – mínimo sobre as entradas de tamanho n
• Caso médio: Cmedio(n) – "Média" com entradas de tamanho n
• O caso médio não corresponde a:
– A média de pior e melhor casos.
Mas sim ao número de vezes que a operação básica será executada na
entrada típica,
ou ainda o número esperado de operações básicas consideradas como uma
variável aleatória sob alguma suposição sobre a distribuição de probabilidade
de todas as entradas possíveis
AALG - 2013
Crescimento de Funções
Vimos anteriormente que o custo (complexidade) de um algoritmo depende
maioritariamente do tamanho de entrada do problema. Sendo assim não é
aconselhável a escolha do melhor algoritmo num conjunto que solucionam o
mesmo problema, analisando-o sobre entradas menores.
Mas sim o custo de dois (2) ou mais algoritmos sobre grandes valores de n
(entrada).
Suponha dois (2) algoritmos que resolvam o mesmo problema:
Alg1 necessita de T(n)=n para solucionar o problema
Alg2 necessita de T(n)=n2 para solucionar o mesmo problema.
Para valores pequenos de n, não teremos grande diferença. Mas para grandes
valores, notaremos que o algoritmo com custo n2 cresce mais rapidamente.
Lembre sempre que para entradas grandes, os factores de menor influência
sobre o crescimento da função podem ser ignorados.
AALG - 2013
Crescimento de Funções
n log2 n n n log2 n n2 n3 2n n!
101 3,3 101 3,3*101 102 103 103 3,6*106
102 6,6 102 6,6*102 104 106 1,3*1030 9,3*10157
103 10 103 1,0*103 106 109
104 13 104 1,3*104 108 1012
105 17 105 1,7*105 1010 1015
106 20 106 2,0*106 1012 1018
Valores de algumas funções importantes quando n → ∞
AALG - 2013
Taxa de crescimento Assintótico / Notação Assintótica Uma maneira de comparar as funções que ignora factores constantes e
pequenos tamanhos de entrada é
• O(g(n)): classe de funções f (n), que não crescem mais rápido que g (n)
• Θ(g(n)): classe de funções f (n), que crescem a mesma ordem que g (n)
• Ω (g(n)): classe de funções f (n), que crescem, pelo menos, tão rápido quanto
g (n)
Notação O (Big-O) Definição: f (n)∈ O(g (n)), se existem duas constantes positivas c e n0 tal que f (n) ≤ cg (n) para todo n ≥ n0. Isto significa que a ordem de crescimento de f(n) é menor ou igual a ordem de crescimento de g(n). Exemplos:
1º Exemplo: 10n ∈ O(n2) 2º Exemplo: 5n+20 ∈ O(n)
AALG - 2013
Taxa de crescimento Assintótico / Notação Assintótica Exemplos: Em que situações podemos considerar que 10n ∈ O(n2) ou 10n = O(n2)
Solução Aplique primeiramente a fórmula: f(n) ≤ c. g(n), considerando f(n)=10n e g
(n) como n2.
Para pequenos valores positivos como para n0 =n<10 e c=1, podemos verificar
que a f(n) cresce mais rapidamente que g(n). E para n=10, os dois funcionam
de modo óptimo, ou seja atingem o mesmo ponto.
Mas para valores de n>10, f(n) comporta-se como Big-O de g(n). Isto é g(n)
cresce mais rapidamente.
Podemos analisar igualmente para uma constante C=10, para todo n>=1, a
afirmação que 10n = O(n2) é verdadeira.
cg(n)
t(n)
não importa
Fig. 2.1 A notação Big-‐oh t(n)∈ O(g(n))
AALG - 2013
Representação gráfica - Big - O
Nota: Não importa analisar o comportamento das funções para pequenos valores de n.
AALG - 2013
Taxa de crescimento Assintótico / Notação Assintótica
Notação Ω (Big-Omega) Definição: f (n)∈ Ω(g (n)), se existem duas constantes positivas c e n0 tal que f (n) ≥ cg (n) para todo n ≥ n0. Isto significa que a ordem de crescimento de f(n) é maior ou igual a ordem de crescimento de g(n).
Ex: n2 ∈ Ω(n) ou n2 = Ω(n) Para o exemplo acima, é possível notar que o crescimento da função f(n) é superior em relação a (c.g(n)) considerando c=1 para todo n ≥ 1.
cg(n)
t(n)
não importa
Fig. 2.2A notação Big-‐omega t(n)∈ Ω(g(n))
AALG - 2013
Representação gráfica - Big - Omega
Nota: Não importa analisar o comportamento das funções para pequenos valores de n.
AALG - 2013
Taxa de crescimento Assintótico / Notação Assintótica
Notação Θ (Big-Theta) Definição: f(n)∈ Θ(g (n)), se existem duas constantes positivas c e n0 tais que 0 ≤ c1.g(n) ≤ f (n) ≤ c2.g(n) para todo n ≥ n0. Isto significa que a ordem de crescimento de f(n) = ordem de crescimento de g(n).
Ex: n2/3-2n ∈ Θ(n2) ou n2/3-2n = Θ(n2) Para o exemplo acima, primeiramente, devemos provar em que situação é verificada que c1.g(n) ≤ f (n), isto é a notação Ω. Considere f(n)= n2/3 -2n, g(n)=n2, c=1/12 para todo n>=8. Em segundo lugar devemos provar em que situação é verificada f(n) ≤ c2.g(n)), isto é a notação O. Considere f(n)= n2/3 -2n, g(n)=n2, c=1/3 para n=8.
Resumimos que para provar que f(n) é Θ(g(n)) é necessário que f(n) seja O(g(n)) e f(n) seja Ω(g(n)).
c2g(n) t(n)
não importa
Fig. 2.3 A notação Big-‐theta t(n)∈ Θ(g(n))
c1g(n)
Representação gráfica - Big - Theta
AALG - 2013
Nota: Não importa analisar o comportamento das funções para pequenos valores de n.
AALG - 2013
Taxa de crescimento Assintótico / Notação Assintótica
Notação o (pequeno-O) Definição: f (n)∈ o(g (n)), se existem duas constantes positivas c e n0 tal que f (n) < cg (n) para todo n ≥ n0. Isto significa que a ordem de crescimento de f(n) é menor que a ordem de g(n).
Notação ω (pequeno-Omega)
Definição: f (n)∈ω(g (n)), se existem duas constantes positivas c e n0 tal que f (n) > cg (n) para todo n ≥ n0. Isto significa que a ordem de crescimento de f(n) é maior do que a ordem de crescimento de g(n).
Nota: Não se deve confundir a definição da notação (O e o) assim como a (Ω e ω), visto que apesar de serem semelhantes, são aplicadas em casos diferentes.
AALG - 2013
Estabelecendo ordem de crescimento usando limites
0 ordem de crescimento de T(n) < ordem de
crescimento de g(n)
c > 0 ordem de crescimento T(n) = ordem de
crescimento
de g(n)
∞ ordem de crescimento de T(n) > ordem de
crescimento de g(n)
Exemplos:
– 10n vs. n2
– n(n+1)/2 vs. n2
lim t(n)/g(n) =
AALG - 2013
Propriedades da Notação O
1. Se f(n) é O(g(n)) e g(n) é O(h(n)) então f(n) é O(h(n)).
Ex: n=O(n2) e n2 =O(n3) então n= O(n3)
2. Se f(n) é O(h(n)) e g(n) é O(h(n)) então f(n) + g(n) é O(h(n))
3. Se f(n) é O(h(n)) e g(n) é O(k(n)) então f(n) + g(n) é O(max(h(n), k(n))
Ex: n2 + 100n + logn= O(max(n2, 100n, logn))=O(n2)
4. ank é O(nk)
AALG - 2013
Classes de eficiência assintótica básicas
1 constante
log n logarítmica
n linear
n log n n-log-n
n2 Quadrática
n3 Cúbica
2n exponencial
n! factorial
Rápido
Lento Baixa Eficiência
Alta Eficiência
AALG - 2013
Exercícios
Dada as seguintes funções:
F1=n1/logn F2=loglogn F3=logn2 F4=n F5=2logn F6=nlogn F7=n!
F8=n2
Mostre que cada par de funções Fi e Fi+1 para 1≤ i ≤ 8 se são O, Ω ouΘ.