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. É uma ferramenta para resolver um
problema computacional bem especificado.
Uma instância de um problema consiste na entrada que satisfaz a quaisquer restrições impostas no enunciado do problema necessária para se calcular uma solução para o problema.
Um algoritmo é dito correto se para cada instância de entrada, ele para com a saída correta.
Diz-se que um algoritmo correto resolve o problema computacional dado.
Os algoritmos incorretos podem ser úteis, se sua taxa de erros pode ser controlada.
O único requisito é que a especificação deve fornecer uma descrição precisa do procedimento computacional a ser seguido.
Estrutura de dados é um meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações. Nenhuma estrutura de dados única funciona bem para todos os propósitos, e assim é importante conhecer os pontos fracos e as limitações de várias delas.
Problemas NP-Completos
- embora ainda não tenha sido encontrado nenhum algoritmo eficiente para um problema NP completo, ninguém jamais provou que não é possível existir um algoritmo eficiente para este fim. Desconhece-se se existem ou não algoritmos eficiente para problemas NP completos.
- Se existe um algoritmo eficiente para qualquer um deles, então existem algoritmos eficientes para todos.
- Vários problemas NP Completos são semelhantes, mas não idênticos, a problemas para os quais conhecemos algoritmos eficientes. Uma pequena mudança no enunciado do problema pode provocar uma grande alteração na eficiência do melhor algoritmo conhecido.
Exemplo de um problema NP Completo é "problema do caixeiro viajante". Não tem nenhum algoritmo eficiente conhecido. "Algoritmos de aproximação".
Exercício:
1.1-1 Forneça um exemplo real no qual apareça um dos problemas computacionais a seguir:
ordenação:
Listagem de alunos ou produtos por nome, ou código ou sobrenome, ou fabricante
determinação da melhor ordem para multiplicação de matrizes:
Para solução sistema de equações lineares, utilizando método de Gauss
localização da envoltória convexa:
topografia, determinar o terreno que envolve os pontos levantados, Curvas de nível
1.1-2 Além da velocidade, que outras medidas de eficiência poderiam ser usadas em configuração real?
Espaço utilizado para solução, custo financeiro dos recursos utilizados, por exemplo: banda de conexão, tempo de processamento.
1.1-3 Selecione uma estrutura de dados que você já tenha visto antes e discuta seus pontos fortes e suas limitações.
Vetor
Pontos fortes: rapidez no seu acesso. pode-se acessar qualquer posição do vetor diretamente
Pontos fracos: alocação em geral é estática, necessita de uma engenharia para alocar mais espaço, desde que esteja utilizando alocação estática.
1.1-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?
Aspectos semelhantes: a dificuldade para encontrar a solução mais eficiente esta no tamanho da quantidade de pontos, cidades que se queira analisar, quanto maior o número de cidades, pontos do problema mais difícil fica a solução do problema.
o problema do caminho mais curto pertence a classe P
o problema do caixeiro viajante pertence a classe NP Completo
1.1-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: Quantidade de dinheiro necessária para quitar as dívidas do dia (contas a pagar)
Solução Aproximada: Encontrar o zero de uma função utilizando o método das secantes.
https://meitcher.wordpress.com/2015/01/27/1-1-algoritmos/
O estudo do algoritmo é necessário para demonstrar que o método da solução adotada termina e obtém a resposta correta.
Boa prática da engenharia de software - bem documentada e projetada.
1.2-1 Forneça um exemplo de aplicação que exige conteúdo algorítmico no nível da aplicação e discuta a função dos algoritmos envolvidos
A solução de classificação multivariável, por exemplo aplicação do algoritmo de PROMETHEE, tem que aplicar algoritmo de ordenação, classificação, comparação entre os critérios selecionados.
1.2-2 Vamos supor que estamos comparando implementações de ordenação por inserção e ordenação por intercalação na mesma máquina. Para entradas de tamanho
n, a ordenação por inserção é executada em 8n^
2 etapas, enquanto a ordenação por intercalação é executada em 64n lg (n) etapas. Para que valores de n a ordenação por inserção supera a ordenação por intercalação?
Elaborando uma tabela com três colunas, n, tempo para o algoritmo por inserção e o tempo para o algoritmo por intercalação tem-se a tabela abaixo. O algoritmo por inserção tem menos etapas para n variando de 1 a 31, depois disso, ou seja, para n>26 o algoritmo por intercalação tem menos etapas. Foi utilizado lg = log na base 2.
| n |
8*n^2 |
64*n*ln(n) |
| 1 |
8.00 |
0.00 |
| 2 |
32.00 |
88.72 |
| 3 |
72.00 |
210.93 |
| 4 |
128.00 |
354.89 |
| 5 |
200.00 |
515.02 |
| 6 |
288.00 |
688.04 |
| 7 |
392.00 |
871.77 |
| 8 |
512.00 |
1,064.67 |
| 9 |
648.00 |
1,265.60 |
| 10 |
800.00 |
1,473.65 |
| 11 |
968.00 |
1,688.12 |
| 12 |
1,152.00 |
1,908.41 |
| 13 |
1,352.00 |
2,134.04 |
| 14 |
1,568.00 |
2,364.60 |
| 15 |
1,800.00 |
2,599.73 |
| 16 |
2,048.00 |
2,839.13 |
| 17 |
2,312.00 |
3,082.54 |
| 18 |
2,592.00 |
3,329.71 |
| 19 |
2,888.00 |
3,580.44 |
| 20 |
3,200.00 |
3,834.54 |
| 21 |
3,528.00 |
4,091.84 |
| 22 |
3,872.00 |
4,352.19 |
| 23 |
4,232.00 |
4,615.45 |
| 24 |
4,608.00 |
4,881.49 |
| 25 |
5,000.00 |
5,150.20 |
| 26 |
5,408.00 |
5,421.47 |
| 27 |
5,832.00 |
5,695.21 |
| 28 |
6,272.00 |
5,971.31 |
| 29 |
6,728.00 |
6,249.70 |
| 30 |
7,200.00 |
6,530.30 |
| 31 |
7,688.00 |
6,813.03 |
1.2-3 Qual o menor valor de n tal que um algoritmo cujo tempo de execução é 100n^2 funciona mais rápido que um algoritmo cujo tempo de execução é 2^n na mesma máquina.
Elaborando uma tabela com três colunas, n, tempo para o algoritmo 1 e o tempo para o algoritmo 2 tem-se a tabela abaixo. O algoritmo 2 é melhor até n=14, a partir de n=15 o algoritmo 1 tem melhor desempenho.
| n |
100^n |
2^n |
| 0 |
0 |
1 |
| 1 |
100 |
2 |
| 10 |
10000 |
1024 |
| 14 |
19600 |
16384 |
| 15 |
22500 |
32768 |
https://meitcher.wordpress.com/2015/01/27/1-2-algoritmos-como-tecnologia/
http://clrs.skanev.com/
