Projeto E Análise De Algoritmos

Sumário

1. Conceitos de Algoritmo 3

2. Conceitos de Estrutura de Dados 3

3. Conceitos de programa 3

4. Medidas de tempo e de execução 3

5.1. Recursividade; 4

5.2. Algoritmos tentativa e erro (backtracking); 4

5.3. Divisão e conquista; 4

5.4. Programação dinâmica; 5

5.5. Algoritmos gulosos; 5

5.6. Algoritmos aproximados; 5

6. ESTRUTURA DE DADOS BASICAS 7

 

1. CONCEITOS

1.1. Conceitos de Algoritmo

Algoritmo consiste em uma sequência ordenada de passos que deve ser seguida para solução de um problema ou para a realização de uma tarefa, garantindo a sua repetibilidade, é um conjunto de passos executáveis não ambíguos. Pode ser representados de diversas formas

Descrição narrativa, fluxograma convencional e pseudocódigo, também conhecido como linguagem estruturada.

1.2. Conceitos de Estrutura de Dados

Estrutura de Dados é um método particular de se implementar um Tipo Abstrato de Dados. Elas são formas de distribuir e relacionar os dados disponíveis, de modo a tornar mais eficientes os algoritmos que manipulam esses dados.

Cada Estrutura de Dados é construída dos tipos básicos (int, real, char) ou dos tipos estruturados (array, record) de uma linguagem de programação.

1.3. Conceitos de programa

Programas são formulações concretas de algoritmos abstratos, baseados em representações e estruturas específicas de dados. Em outras palavras, programas representam uma classe especial de algoritmos capazes de serem seguidos por computadores.

2. PARADIGMAS DE PROJETO DE ALGORITMOS

3. MEDIDAS DE TEMPO E DE EXECUÇÃO

Uma das características mais importantes em projeto e analise de algoritmos é o da escolha das estruturas adequadas para uma dada aplicação. Para um problema pequeno, não é muito importante a solução escolhida, desde que esteja correta, mas para problemas de grande porte, é fundamental que a escolha seja bem feita.

Uma forma de implementação pode ser boa para alguns casos e ruim para outros, e pode ser difícil decidir quais são os melhores e os piores casos.

3.1. Recursividade;

Um procedimento que chama a si mesmo, direta ou indiretamente, é chamado de recursivo. Recursividade permite descrever algoritmos de forma mais clara e concisa, especialmente problemas recursivos por natureza ou que utilizam estruturas recursivas.

Na implementação usa-se uma pilha para armazenar os dados usados em cada chamada de um procedimento que ainda não terminou. Todos os dados não globais vão para a pilha, registrando o estado corrente da computação. Quando uma ativação anterior prossegue, os dados da pilha são recuperados.

No caso do caminhamento central:

Para cada chamada recursiva, o valor de p e o endereço de retorno da chamada recursiva são armazenados na pilha. Quando encontra p=nil o procedimento retorna para quem chamou utilizando o endereço de retorno que está no topo da pilha.

3.2. Algoritmos tentativa e erro (backtracking);

Tentativa e erro: decompor o processo em um número finito de sub-tarefas parciais que devem ser exploradas exaustivamente.

O processo de tentativa gradualmente constrói e percorre uma árvore de sub-tarefas. Algoritmos tentativa e erro não seguem uma regra fixa de computação:

– Passos em direção à solução final são tentados e registrados e caso esses passos tomados não levem à solução final, eles podem ser retirados e apagados do registro.

Técnica usada quando não se sabe exatamente que caminho seguir para encontrar uma solução. Não garante a solução ótima, essa técnica pode ser vista ainda como uma variante da recursividade ao se fazer a análise de um algoritmo que usa backtracking, deve-se também analisar o crescimento do espaço de soluções.

3.3. Divisão e conquista;

Os Passos básicos dividir o problema a ser resolvido em subproblemas menores e independentes, encontrar soluções para as partes, combinar as soluções obtidas em uma solução global. Os algoritmos podem utilizar recursão para dividir e combinar.

Dividir o problema em partes menores, encontrar soluções para essas partes (supostamente mais fácil). Geralmente leva a soluções eficientes e elegantes, principalmente se forem recursivas.

3.4. Programação dinâmica;

Método de solução baseado em tabela, dividindo e resolvendo todos os subproblemas menores, más somente utiliza as soluções ótimas.

A programação dinâmica calcula a solução para todos os subproblemas, partindo dos subproblemas menores para os maiores, armazenando os resultados em uma tabela. A vantagem é que uma vez que um subproblema é resolvido, a resposta é armazenada em uma tabela e nunca mais é recalculado.

3.5. Algoritmos gulosos;

São tipicamente usados para resolver problemas de otimização, por exemplo, o algoritmo para encontrar o caminho mais curto entre duas cidades. Um algoritmo guloso escolhe a estrada que parece mais promissora no instante atual e nunca muda essa decisão, independentemente do que possa acontecer depois.

Para chegar à solução ótima existe uma lista de caminhos possíveis e outros inviáveis. Uma função verifica um conjunto particular de caminhos e produz uma solução (sem considerar se é a melhor opção).

Uma função indica qual dos caminhos é o mais promissor e outra fornece o valor da solução encontrada.

Quando funciona corretamente, a primeira solução encontrada é sempre ótima.

3.6. Algoritmos aproximados;

Gera soluções aproximadas, que podem não ser ótimas, mas são próximas delas faz-se necessária uma medida de qualidade.

COMPLEXIDADE