Algoritmos e Estrutura de Dados

Um algoritmo é uma sequência de passos que transformam entrada em saída. De acordo com o autor renomado na área, Thomas Cormen, “um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída”.

O algoritmo correto para uma aplicação é aquele que finaliza quando encontra a saída correta, ou seja, quando resolve o problema. O algoritmo incorreto para uma aplicação é aquele que pode não parar em alguma resposta ou pode parar na resposta errada.

Ainda segundo Cormen, uma estrutura de dados “é um meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações”. Cada estrutura possui suas características e aplicações, de acordo com a necessidade em questão.

Problemas NP-Completos são problemas para os quais não se conhece uma solução eficiente.

Exercícios (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Forneça um exemplo real no qual apareça um dos problemas computacionais a seguir: ordenação, determinação da melhor ordem para multiplicação de matrizes ou localização da envoltória convexa.

Listagem de alunos de um curso por nome; encontrar o número dos transistores encomendados em determinado mês, de acordo com a tabela de venda de vários modelos de aparelhos por mês, mais a tabela de peças necessárias para montar cada modelo de aparelho.

2-     Além da velocidade, que outras medidas de eficiência poderiam ser usadas em uma configuração real?

Custo financeiro de recursos utilizados na execução, largura de banda.

3-     Selecione uma estrutura de dados que você já tenha visto antes e discuta seus pontos fortes e suas limitações.

Vetor. Vantagem: rapidez no acesso a qualquer posição da estrutura. Desvantagem: difícil de alocar espaço novo, dada a sua estrutura estática.

4-     Em que aspectos os problemas do caminho mais curto e do caixeiro-viajante anteriores são semelhantes? Em que aspectos eles são diferentes?

São semelhantes na visão de que ambos se tornam complexos com o aumento do número de cidades envolvidas no problema. São diferentes porque o problema do caminho mais curto possui uma solução eficiente, enquanto que o problema do caixeiro-viajante não possui, já que se trata de um problema NP-Complexo.

5-     Mostre um problema real no qual apenas a melhor solução servirá. Em seguida, apresente um problema em que baste uma solução que seja "aproximadamente” a melhor.

Solução ótima: calcular a quantidade de combustível necessária para atravessar uma ponte. Solução aproximada: encontrar o posto de combustível mais próximo de casa.