MO417 - Atas das Aulas (Conceitos Básicos)
Ata de Aula: 21/02/2003
Redator: Patrick Henrique
da Silva Brito
Tópicos:
- Problema de ordenação;
- Ordenação por inserção;
- Loops invariantes;
- Modelo RAM;
- Análise (Custo e nº de vezes que cada linha é executada);
- Pior caso e caso médio;
- Razão de crescimento;
- Divisão e conquista: Merge sort;
- Recorrência do Merge sort;
Problema de ordenação
Consiste em um problema
que possui:
Entrada: um
array de n elementos (a1, a2, ..., an);
Saída: um
array (b1, b2, ..., bn) com os mesmos
elementos da entrada, mas numa ordem tal que b1 <=
b2 <= ... <= bn.
Ordenação por inserção
É um algoritmo
de ordenação onde você percorre o array, sempre a partir
do primeiro índice desordenado (inicialmente o 2º elemento),
e em seguida procura inseri-lo na posição correta, comparando-o
com o seu anterior e trocando-os de lugar enquanto ele for menor que seu
precedente.
Loops invariantes
São as afirmações
/ propriedades que se mantém válidas no início de
cada iteração do loop.
Ex.: No
algoritmo de Insertion sort (veja abaixo), há uma invariante do
loop externo, poisno início de cada iteração, a
sub-array A[1]..A[j-1] consiste dos
mesmos elementos que tinham antes e está ordenada.
- Simplifica a análise e prova do algoritmo, uma vez que a análise se restringe às etapas antes, durante e após o loop, pois as propriedades essenciais são invariantes;
- O loop invariante depende do loop, e não do problema enunciado.
Foi
discutido sobre a questão 2.1-3, que propõe um problema de
busca seqüencial, que possua:
Entrada:um
array de vetores (A) e um valor (v) a ser encontrado em A.
Saída:
o índice (i) onde se encontra o item v no array A (em caso de repetição
de v, pode-se fornecer qualquer índice i tal que A[i]) = v.
Modelo RAM
É um modelo
de computação, isto é, é uma descrição
de onde o algoritmo vai ser executado (máquina). Possui as seguintes
características:
- É uma máquina;
- Possui instruções semelhantes às contidas nos computadores reais:
oAritméticas
(soma, subtração, multiplicação, divisão,
resto, piso e teto);
oDe
movimentação de dados (carregar, armazenar, copiar);
oDe
controle (desvio condicional e incondicional, chamada e retorno de sub-rotina);
oEssas
instruções são executadas em uma unidade de tempo,
uma aos a outra (sem concorrência);
oSuporta
os tipos de dados: Inteiro e de ponto flutuante;
oPossui
uma memória, que é representada por um vetor infinito que
provê acesso aleatório em uma unidade de tempo. Esse
acesso aleatório em uma unidade de tempo é a principal característica
desse modelo computacional.
- O modelo RAM é o modelo mais utilizado atualmente para análise de algoritmos.
RAM
(Random Access Machine) é uma máquina teórica, assim
como a máquina de Turing, porém o modelo RAM é mais
real, uma vez que provê o acesso aleatório à memória,
se assemelhando a um computador real.
Análise (Custo e nº de vezes que cada linha é executada)
Analisar
um algoritmo significa prever os recursos de que o algoritmo necessita.
Mas com freqüência é o tempo de computação
que desejamos medir.
Análise
do algoritmo Insert sort:
|
|
|
|
|
|
|
for
j <-- 2 to length[A]
|
|
|
|
key <-- A[j]
|
|
|
|
i <-- j-1
|
|
|
 |
while i>0 and A[i]>key
|
|
|
 |
A[i+1] <-- A[i]
|
|
|
 |
i <-- i-1
|
|
|
|
A[i+1] <-- key
|
* Como o tamanho do vetor de entrada (n) interfere diretamente no tempo de execução, o nº de ciclos do algoritmo foi estimado em função dele (n).
Resolução dos somatórios (Soma dos termos de uma PA):
O tempo de execução T(n)= soma de todos os custos, multiplicados pelo respectivo nº de vezes que foi executado.
T(n)= 5n2
+ 7n – 11, assim, o tempo de execução do algoritmo Insertion
sort é uma função quadrática de n, isto é,
o tempo de execução, no pior caso é ordem de n2,
representado por O(n2).
Pior caso e caso médio
Em geral, nos concentramos
apenas na descoberta do tempo de execução no pior caso; ou
seja, o tempo de execução mais longo para qualquer entrada
de tamanho n. Alguns comentários sobre essa escolha:
- Conhecer o tempo de execução no pior caso, nos dá uma garantia de que o algoritmo nunca irá demorar mais tempo do que o previsto;
- Para alguns algoritmos, como busca em um banco de dados, o pior caso ocorre com bastante freqüência;
- Muitas vezes, o caso médio é quase tão ruim quanto o pior caso;
- Além disso, normalmente o pior caso é mais fácil de encontrar, uma vez que para encontrar o caso médio é necessário ter uma distribuição de probabilidade nas entradas.
Porém há
algumas situações em que o caso médio é bastante
relevante, como por exemplo, o algoritmo Quick sort que possui um pior
caso O(n2), porém, na prática se mostra o melhor
algoritmo de ordenação conhecido, pois seu caso médio
é O(n lg n).
Razão de crescimento
Para saber a razão
de crescimento de um algoritmo, as constantes e os termos de menor ordem
devem ser ignorados, uma vez que o objetivo é ter uma idéia
geral da taxa de crescimento em função da variação
da entrada, o que é representado pelo termo mais significativo,
isto é, o de maior ordem.
A razão de crescimento
é o principal fator levado em consideração ao analisar
a adequação ou não de um algoritmo a um problema que
exija um determinado tamanho de entrada.
Ex.: Se
um problema exigisse a ordenação de um vetor de até
100 unidades, o algoritmo de Insertion sort se adequaria, porém,
para outro problema que exija a ordenação de vetores com
mais de 1.000.000 de de unidades, o Insertion sort seria inviável.
Divisão e conquista: Merge sort
Divisão e
conquista é uma técnica de resolução de
problemas que visa reduzir o esforço de resolução
dividindo o problema inicial em sub-problemas, que podem ser resolvidos
recursivamente, até encontrar um caso base resolvido de maneira
trivial. Essa técnica possui basicamente três passos:
- Dividir o problema em sub-problemas;
- Conquistar os sub-problemas;
- Combinar as soluções dos sub-problemas, apresentando a resolução do problema inicial.
O algoritmo Merge
Sort utiliza essa técnica para resolver o problema da ordenação:
- Divide o array em dois sub-arrays;
- Ordena cada sub-array de forma recursiva;
- Combina os sub-arrays ordenados, conservando a ordenação.
O Merge Sort é
recursivo e divide o vetor até que o sub-array tenha apenas um elemento,
o que caracteriza o caso base uma vez que um vetor unitário
sempre está ordenado.
Recorrência do Merge sort
A introdução
desse conceito foi apresentado através da análise do algoritmo
recursivo de Merge Sort:
|
|
|
|
|
Merge-Sort(A,p,r)
|
||
|
|
|
if p < r then
|
|
|
|
q <-- arredondaParaMenos[(p+r)/2]
|
|
|
|
Merge-Sort(A,p,q)
|
|
|
|
Merge-Sort(A,q+1,r)
|
|
|
|
Merge(A,p,q,r)
|
m= tamanho da entrada
= (r-p+1)
O procedimento Merge(A,p,q,r)
tem a função de combinar os dois sub-arrays (A[p..q] e A[q+1..r])
e seu tempo de execução é proporcional ao tamanho
desses dois sub-arrays, isto é O(m), para m=(r-p+1). Como os valores
do custo serão empregados numa equação, a ordem do
valor não deve ser empregada simplesmente, portanto, multiplicamos
m por uma constante apropriada c.
A complexidade do algoritmo
de ordenação de um vetor com m elementos é representada
por T(m):
T(m)=2T(m/2) + cm +
4
Essa
equação chama-se recorrência, pois ela estipula todos
os valores da função dependendo de valores menores da mesma
função (recursividade). Deve haver também o caso base:
neste caso, quando m=1 (p=r), T(1)=1.
… “não foi continuada a resolução dessa equação em sala, uma vez que o conhecimento necessário para esse fim (resolução de recorrência) será tratado em outra aula”.
A
solução é T(m) = O(m lg m). Para ordenar
um vetor de n elementos, temos T(n) = O(n lg n).
Conclusão: O
algoritmo de ordenação Merge Sort é mais rápido
que o algoritmo Insertion Sort, que tem razão de crescimento O(n2).