A Atividade de Calculo
Por: Ramon Barbosa • 9/4/2022 • Trabalho acadêmico • 2.053 Palavras (9 Páginas) • 89 Visualizações
Data: 30/03/2022
Discente: Ramon Barbosa Pessoa
1 - Defina algoritmo, problema e instância.
Algoritmo: Na computação algoritmo é um conjunto de passos (instruções de máquina) lógicos que possuem o objetivo de manipular os valores de entrada, convertendo estes em uma saída.
O conceito de algoritmo independe da computação, como o caso de uma receita de bolo, que deve seguir um passo lógico, e transformar os produtos de entrada, como: farinha de trigo, ovo, manteiga, em uma saída, que neste caso seria o bolo.
[pic 1]
Os problemas: são os requisitos para transformar os valores de entrada em uma saída para aqueles valores. O problema deve ser sucinto e objetivo, evitando exceções, informando a maneira de converter os dados de entrada para um resultado. Para explicar melhor este conceito podemos utilizar um exemplo de problema bem definido.
- Encontrar o maior valor em uma lista de n elementos.
- Entrada: Uma sequência de n elementos [][pic 2]
- Saída: Um valor , tal que [pic 3][pic 4]
Podemos verificar que ainda que existem centenas de maneiras de formular uma resposta a este problema, entretanto o resultado deve ser equivalente para entradas iguais.
Instâncias: são os valores de entrada de um algoritmo. No exemplo anterior a instância do problema era a sequência de n elementos.
2 - Para cada problema da computação existe um algoritmo que é considerado sempre o melhor? Justifique.
Não. Geralmente existe um algoritmo que consegue se sobressair na maioria das instâncias, entretanto a depender destas um algoritmo que comumente possui menor desempenho consegue ser superior ou igual a outros algoritmos que em geral é mais eficiente.
Podemos utilizar como exemplo a ordenação de uma sequência de n números. Por este ser um problema fundamental possui várias possíveis soluções, para limitar o exemplo podemos considerar 2, são eles: Quick Sort e o Selection Sort.
O algoritmo Quick Sort é amplamente utilizado por apresentar o melhor desempenho na maioria dos casos, entretanto a depender das instâncias o Selection Sort poderá apresentar um resultado melhor.
A instâncias onde o Selection Sort apresentaria um desempenho superior ao Quick Sort, ocorre quando a sequência de elementos já está quase ordenada, o Selection Sort identificaria o elemento a ser ordenado e alteraria a sua posição, enquanto que o Quick Sort teria que dividir a sequência de elementos para assim conseguir ordenar.
3 - Pesquise como algoritmos computacionais podem ajudar a organizar mercadorias em um caminhão ou armazém, por exemplo. Que algoritmo clássico seria aplicado para esse fim?
Este algoritmo consiste em armazenar objetos de diferentes tamanhos na menor quantidade recipientes possíveis.
Para resolver este problema existem duas principais algoritmos: first-fit e o força bruta.
O algoritmo de first-fit consiste em selecionar arbitrariamente os itens e posicionar na primeira caixa que o elemento couber. Para exemplificar podemos utilizar um famoso quebra-cabeça, o tangram. No tangram existem 7 peças que se posicionadas corretamente formam 1 quadrado[pic 5][pic 6]
[pic 7][pic 8][pic 9][pic 10][pic 11]
[pic 12][pic 13][pic 14][pic 15][pic 16]
[pic 17]
O próximo menor elemento é entretanto este não possui espaço para ser adicionado neste pacote criando a necessidade de utilizar um novo pacote.
[pic 18][pic 19]
Para este algoritmo foram necessárias duas caixas. Vale ressaltar que ambas as caixas possuem espaços vazios que neste caso poderiam ser preenchidas com outras formas geométricas. A forma ótima do tangram consiste em utilizar completamente um pacote. Esta forma de ordenar só pode ser obtida utilizando o algoritmo de força bruta.
O algoritmo de força bruta consiste em tentar todas as possíveis formas de acomodar as caixas (ou formas geométricas, como no exemplo), e o caminho que conseguir obter a menor quantidade de pacotes é conhecido como a solução ótima.
O resultado ótimo do algoritmo de força bruta seria:
[pic 20]
4 - O que são estruturas de dados? Cite algumas estruturas clássicas e diga para qual propósito elas foram criadas.
No desenvolvimento do software é necessário a criação de algoritmos exclusivos para o funcionamento do programa, entretanto, algumas estruturas são amplamente utilizadas em quase qualquer algoritmo computacional, estas são chamadas estruturas de dados. As estruturas de dados são fundamentais para o funcionamento mais eficiente de um software, e devem aplicadas corretamente para cada uso. As estruturas da dados são atualmente usadas em grande escala, e são primordialmente necessárias no tratamento de grande quantidade de dados.
Uma estrutura clássica amplamente utilizada em bancos é a busca binária, nesta é utilizado uma árvore. Assim transformando buscas com complexidade exponencial para complexidade logarítmica, resultando na otimização de um software.
Podemos citar também o uso de grafos nas companhias aéreas, para minimizar o trecho e consequentemente o custo da viagem entre cidades.
5. O que são técnicas de projetos de algoritmos? Cite e descreva as principais técnicas de algoritmos.
As técnicas de algoritmos são uma classe de soluções, podem ser aplicados em problemas distintos. A ideia de resolução deve se persistir ainda que os resultados, instâncias e saídas sejam diferentes. São técnicas de projetos de algoritmos:
- Força Bruta: Esta técnica consiste em realizar todas as combinações possíveis, com o objetivo de encontrar a solução ótima. Esta técnica pode ser implementada no problema do caixeiro viajante. Por sua característica de enumerar todas as possíveis soluções, esta técnica demanda muito recurso computacional, tornando esta inviável para casos onde não é necessário a solução ótima.
- Divisão em conquista: Esta técnica consiste em dividir o problema geral, em problemas menores e fáceis computacionalmente de resolver, as soluções dos problemas menores são mescladas e tidas como a solução do problema geral. Este tipo de técnica é utilizado na busca binária, ordenação pelo método Quick Sort, etc.
- Algoritmo guloso: Esta técnica consiste em seguir aparentemente o melhor caminho no momento, ignorando as demais possibilidades. Normalmente este tipo de algoritmo é utilizado como uma variação da força bruta, entretanto, esta nem sempre retorna a solução ótima. Esta técnica pode ser utilizada no caixeiro viajante.
- Programação dinâmica: Esta técnica consiste em montar uma tabela com as soluções dos problemas já processados, e utilizar essas soluções para quando ocorrer o mesmo problema. Por exemplo: Multiplique , podemos dividir este problema em soluções menores, resultando em: , no primeiro problema é realizado a multiplicação entre , o resultado é adicionado em uma tabela.[pic 21][pic 22][pic 23]
[pic 24] | [pic 25] |
Agora temos que , o segundo problema, no caso, já foi resolvida e se encontra na tabela, logo será utilizado o resultado da tabela para evitar o reprocessamento dos dados. Logo [pic 26][pic 27][pic 28]
A última operação, no caso , ainda não foi processada, logo não é possível de encontrar o resultado na tabela e deverá ser executada. Logo .[pic 29][pic 30]
6 - Mostre em que situação um computador ultrapassado pode resolver um problema muito mais rápido que um computador de ponta.
Para exemplificar esta questão é possível utilizar um problema de ordenação, como já descrito anteriormente, esta é um problema fundamental de estrutura de dados, e por consequência possui dezenas de soluções possíveis. Para ficar mais simples o exemplo, podemos utilizar duas, seriam elas: Merge Sort e o Bubble Sort.
...