Análise e Técnicas de Algoritmos
Período 2003.1

Introdução aos Algoritmos

Introdução aos Algoritmos

Conceitos Básicos

O nosso curso é sobre projeto e análise de algoritmos.




Algoritmo. Informalmente, um algoritmo pode ser definido como uma receita de bolo que provê um método passo-a-passo para a solução de um determinado problema. O conceito de algoritmo é bastante abrangente. Em nosso curso estamos interessados em algoritmos computacionais. Um algoritmo é um procedimento computacional que toma algum valor ou conjunto de valores como entrada e produz um valor ou conjunto de valores como saída. Um algoritmo transforma a entrada em saída, através da execução de uma seqüência de passos computacionais.

Um algoritmo não é um programa, embora quase sempre seja especificado de forma semelhante. Um algoritmo pode, em geral, ser implementado de diferentes formas.

Neste curso, vamos estudar métodos, técnicas, idéias, dicas para desenvolver algoritmos (eficientes). Vamos ainda aprender como analisar/comparar algoritmos sem necessitar implementá-los. Qual o melhor algoritmo? Aquele que leva o menor tempo para ser executado? Aquele que ocupa menor espaço em memória? Ou aquele que é mais fácil de ser codificado?



Problemas computacionais. Algoritmos são ferramentas para resolver problemas computacionais. Um problema computacional especifica a relação entre a entrada e a saída desejada. Por exemplo:

Ordenação

Entrada: Uma seqüência de $n$ números $\langle a_1, a_2, ..., a_n \rangle$.

Saída: Uma reordenação da seqüência de entrada $\langle a'_1, a'_2, ..., a'_n \rangle$, onde $a'_1 \leq a'_2 \leq ... \leq a'_n$.

Número Primo

Entrada: Um número natural $q$.

Saída: Sim ou não, dependendo se o $q$ é ou não um número primo.



Instância. Uma instância de um problema computacional é um possível valor para a entrada. Por exemplo, $\langle 7, 23, 45, 2, 13 \rangle$ é uma instância para o problema da ordenação. O número $29$, por sua vez, é uma instância para o problema dos números primos.

Um algoritmo está correto para um certo problema se, para qualquer instância, ele termina e retorna como saída o valor esperado. No exemplo da ordenação, um algoritmo correto sempre terminaria, retornando a seqüência ordenada dos números da entrada. Um algoritmo é dito incorreto se ele não pára em algumas instâncias ou se produz uma saída errada.



Pseudo-código. Aspectos como precisão e facilidade de expressão são importantes na descrição de um algoritmo. Um algoritmo pode ser descrito de 3 formas: i) Linguagem natural (português ou inglês), ii) Pseudo-código e, iii) Linguagem de programação como pascal ou C.

Em geral, uma notação baseada em pseudo-código é utilizada para a descrição de algoritmos, pois garante um balanceamento nos quesitos precisão e facilidade de expressão.

Para escrever algoritmos vamos utilizar as convenções definidas pelo Prof. Dalton Serey (http://www.dsc.ufpb.br/dalton/edados/convencoes) para a disciplina de estruturas de dados.

Alguns Exemplos de Algoritmos

Ordenação

Talvez, o algoritmo mais simples para o problema da ordenação é o Insertion Sort. A idéia deste algoritmo de ordenação consiste em incrementalmente inserir os elementos $a_1, a_2, ..., a_n$, de forma que a seqüência se mantenha ordenada.

A idéia do Insertion Sort pode ser ilustrada da seguinte forma:

\epsffile{insertionsort.eps}







Uma possível descrição em pseudo-código para este algoritmo é:


\begin{algorithmic} \STATE {\bf InsertionSort(A)} \FOR{$j \leftarrow 2$ to $tam... ...\ENDWHILE \par\STATE $A[i + 1] \leftarrow marca$\ENDFOR \STATE \end{algorithmic}

Números Primos

Um número natural é primo, se e somente se ele só é divisível por $1$ e por ele mesmo. Uma forma simples de resolver este problema é:




\begin{algorithmic} \STATE {\bf Primo1(q)} \FOR{$i \leftarrow 2$ to $q - 1$} \... ...$} \STATE return NO \ENDIF \ENDFOR \STATE return YES \STATE \end{algorithmic}


Se analisarmos com mais atenção, é possível perceber que o algoritmo acima executa pelo menos duas vezes mais o número de testes necessários. Uma nova solução possível seria:




\begin{algorithmic} \STATE {\bf Primo2(q)} \FOR{$i \leftarrow 2$ to $q/2$} \IF... ...$} \STATE return NO \ENDIF \ENDFOR \STATE return YES \STATE \end{algorithmic}


Se uma análise detalhada for feita, o limite superior para potenciais divisores de $q$ é $\sqrt{q}$. Essa solução é 100 vezes mais rápida do que $Primo1$, quando $q$ é um número primo de 5 dígitos.

Análise de Algoritmos

Uma análise simples do algoritmo $Primo1$ possibilitou produzir um algoritmo que é 100 vezes mais eficiente. Na maioria das vezes, entretanto, uma análise mais complexa é necessária.

Dois aspectos importantes são importantes na análise de algoritmos:

Corretude

Invariante de Laço. Garantir corretude não é trivial. Em geral, utilizamos o conceito de indução matemática para verificar a corretude de algoritmos. Em muitos casos a indução é realizada através de uma propriedade que chamamos de invariante de laço.

Para introduzir o conceito de invariante de laço, vamos voltar ao exemplo do Insertion Sort. Observando o algoritmo, é possível perceber que no início de cada iteração do laço (for), os elementos $A[1..j-1]$ estão ordenados. Essa propriedade se repete em cada iteração.

Para provar através de um invariante de laço que um algoritmo está correto, é necessário verificar três detalhes:

  1. Inicialização: o invariante é verdadeiro antes da primeira iteração.
  2. Manutenção: se for verdadeiro antes de uma iteração, ele permanecerá verdadeiro antes da próxima iteração.
  3. Término: Quando o laço termina, o invariante nos fornece uma propriedade que ajuda a garantir a corretude do algoritmo.

Eficiência - Tempo de Execução

Eficiência de um algoritmo pode ser definida através de diferentes tipos de análise: tempo de execução, memória utilizada, etc. Em geral, a análise de um algoritmo está relacionado ao seu tempo de execução.

Para comparar os diferentes algoritmos, é necessário definir um modelo abstrato de uma máquina onde os algoritmos serão executados. Um modelo bem aceito denominado Máquina de Acesso Aleatório (RAM) assume um único processador genérico e apresenta as seguintes características:

O tempo de execução de um algoritmo é o número de instruções RAM que ele executa. De fato, o modelo RAM não é um modelo realístico:

Ainda assim, o modelo RAM nos permite obter resultados realísticos.

O que influencia o tempo de execução de um algoritmo? O tamanho da entrada? A configuração da entrada? No caso do problema de ordenação, o tamanho da entrada é a quantidade de números a serem ordenados. A configuração pode indicar como os números estão ordenados inicialmente.

Em geral, o tempo de execução é definido em função do tamanho da entrada. Uma possível alternativa para definir o tempo de execução é contar o número de vezes que cada instrução foi executada. Na prática, em algoritmos para problemas reais, não é interessante realizar essa contagem. Utilizamos uma abordagem que estuda a ordem de crescimento de funções que identificam o algoritmo. A análise assintótica considera o comportamento de funções no limite, para valores suficientemente grandes de seus parâmetros. Em alguns casos é necessário resolver uma relação de recorrência. Existem diferentes notações (big-oh, $\Omega$, $\Theta$).

Existem vários tipos de análise:

No exemplo do Insertion Sort, temos:

Razões para Estudar Algoritmos

  1. Evitar reinventar a roda.
  2. Para ajudar quando do desenvolvimento de seus algoritmos.
  3. Ajudar a entender ferramentas que usam algoritmos particulares. Por exemplo, ferramentas de compressão de dados:
  4. Útil conhecer técnicas empregadas para resolver problemas de determinados tipos.

O Que Estudar?

  1. Como criar algoritmos.
  2. Como analisar algoritmos.
  3. Como validar algoritmos.
  4. Como expressar algoritmos.


Jorge C. A. de Figueiredo 2003-05-05