Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica, Algoritmos aleatórios, Algoritmos numéricos - Coggle…
Programação dinâmica
A recomputação de subproblemas surge em muitos algoritmos. Assim, existem
muitas vezes onde armazenar uma tabela completa de subresultados será útil.
Essa abordagem para projetar um algoritmo que funciona armazenando uma tabela de resultados para subproblemas é chamada de programação dinâmica. O nome é um pouco arcano, porque não tem muita semelhança óbvia com o processo que está ocorrendo ao armazenar subproblemas em uma tabela.
A programação dinâmica é uma alternativa poderosa ao princípio padrão de dividir e conquistar. Em dividir e conquistar, um problema é dividido em subproblemas, os subproblemas são resolvidos (independentemente) e, em seguida, recombinados em uma solução para o problema que está sendo resolvido.
g. Os algoritmos de programação dinâmica geralmente não são implementados simplesmente usando uma tabela para armazenar subproblemas para chamadas recursivas (ou seja, retrocedendo como é feito pelo Fibrt). Em vez disso, esses algoritmos são tipicamente implementados construindo a tabela de subproblemas de baixo para cima. Assim, o Fibi representa melhor a forma mais comum de programação dinâmica do que o Fibrt, mesmo que não use a tabela completa.
Algoritmos aleatórios
Considere como a introdução da aleatoriedade em nossos algoritmos pode acelerar as coisas, embora talvez às custas da precisão. Mas muitas vezes podemos reduzir a possibilidade de o erro ser tão baixo quanto quisermos, enquanto ainda aceleramos o algoritmo.
-
Algoritmos numéricos
Algoritmos relacionados a cálculos matemáticos em números. Exemplos são atividades como multiplicar dois números ou elevar um número a uma determinada potência. Em particular, estamos preocupados com situações em que operações internas de inteiro ou ponto flutuante não podem ser usadas porque os valores que estão sendo operados são muito grandes. Preocupações semelhantes surgem para operações em polinômios ou matrizes.
Como não podemos confiar no hardware para processar as entradas em uma única operação de tempo constante, estamos preocupados em como implementar a operação de forma mais eficaz para minimizar o custo do tempo. Isto levanta uma questão sobre a forma como devemos aplicar as nossas medidas normais de custo assintótico em termos de taxas de crescimento sobre a dimensão dos factores de produção.
Primeiro, o que é uma instância de adição ou multiplicação? Cada valor dos operandos produz uma instância de problema diferente. E qual é o tamanho da entrada ao multiplicar dois números? Se olharmos o tamanho de entrada como dois (uma vez que dois números são de entrada), então qualquer algoritmo de tempo não constante tem uma taxa de crescimento que é infinitamente alta em comparação com ao crescimento do insumo.
Isso não faz sentido, especialmente à luz do fato de que sabemos pela aritmética da escola primária que adicionar ou multiplicar números faz
parecem ficar mais difíceis à medida que o valor dos números envolvidos aumenta
De fato, sabemos a partir de algoritmos padrão da escola primária que o custo da adição padrão é linear no número de dígitos que estão sendo adicionados, e a multiplicação custou n × m ao multiplicar um número de m-dígito por um número de n dígitos
O número de dígitos para os operandos parece ser uma consideração fundamental quando estamos executando um algoritmo numérico que é sensível ao tamanho da entrada. O número de dígitos é simplesmente o log do valor, para uma base adequada do log. Assim, para fins de cálculo das taxas de crescimento assintótico de algoritmos, consideraremos o "tamanho" de um valor de entrada como sendo o log desse valor. Dada essa visão, há uma série de características que parecem relacionar tais operações.
-
-
-
-
• O custo de um determinado algoritmo pode diminuir quando n aumenta de valor (digamos quando se passa de um valor de 2k − 1 para 2k para 2k + 1), mas geralmente
-