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.
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/
Um comentário:
A questão 1.2-2 está com um erro. Utilizou-se ln(x) ao invés de log2(n).
Postar um comentário