Análise de algoritmos - UTEC.pdf

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


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


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


AALG - 2013


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


AALG - 2013


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


AALG - 2013


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Θ.

Documents

Análise de algoritmos - UTEC.pdf