Análise e técnica de projeto de algoritmos
Por Igor Cruz
(igor.cruz@ccc.ufcg.eu.br)
programação de computadores, estamos sempre resolvendo problemas por meio de diversos tipos de algoritmos. Muitas vezes alguns desses algoritmos não são ideais para determinada situação e é essencial sabermos quais algoritmos se adaptam melhor para o domínio que estamos trabalhando. Então, vamos relembrar relembrar alguns tipos de algoritmos e como funcionam de forma geral.

Algoritmos são receitas que mostram os passos e os procedimentos necessários para a resolução de uma tarefa ou problema. Eles mostram o “como fazer” para atingir um determinado objetivo. Existem diversos tipos de algoritmos que nos ajudam a resolver problemas em diversas áreas. Segue, abaixo, alguns exemplos de algoritmos importantes na área da computação.

  • Tentativa e erro: Determina que devemos testar todas as possibilidades de resultados em um problema para descobrir qual a melhor resposta. Geralmente são algoritmos simples, porém, na maioria dos casos, com pouca eficiência.

  • Divisão e conquista: Caracteriza-se pela divisão do problema em dois ou mais subproblemas, o qual Cada instância menor é resolvida usando o próprio algoritmo. Por fim, a solução dos subproblemas é combinada para a solução global. Geralmente tem bastante eficiência, com tendência a complexidade logarítmica.

  • Programação dinâmica: Assim como o divisão e conquista, cada instância do problema é resolvida a partir da solução de instâncias menores. A característica distintiva da programação dinâmica é que ele armazena as soluções das várias subinstâncias para reuso caso o subproblema se repita.

Veja algumas video aulas sobre os tipos de algoritmos descritos acima:

Dynamic Programming I: Fibonacci, Shortest Paths (MIT 6.006 Introduction to Algorithms, Fall 2011/ View the complete course: http://ocw.mit.edu/6-006F11/ Instructor: Erik Demaine

Lecture 03: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication/ View the complete course: http://ocw.mit.edu/6-006F11/ Instructor: Erik Demaine

Resolvendo a questão:

  • O item I corresponde à letra D, já que, como explicado anteriormente, testam-se todas as possibilidades possíveis para a resolução do problema e usa-se a mais adequada.

  • O item II corresponde à letra E, pois divisão e conquista é um algoritmo que divide o problema maior em subproblemas e depois combinam-se as respostas para alcançar a solução global.

  • O item III relaciona-se ao item B. O algoritmo de Balanceamento, assim como o divisão e conquista, divide o problema maior em subproblemas, porém esses são de tamanhos uniformes.

  • O item IV tem como resposta a letra A, já que são algoritmos usados para encontrar soluções aproximadas em problemas de otimização. Esses podem não nos dar a melhor solução mas uma aproximação dela, mas priorizam a distância ótima.

  • O item V relaciona-se com a letra C, pois a programação dinâmica divide o problema maior em instancias menores e seus resultados são armazenados para um possível reuso.

Logo a resposta para a questão é a letra “e”.

Referências:

Jornal PETNews - Edição: Rafael Rêgo - Revisão: Tiaraju Smaneoto e Lívia Sampaio
Grupo PET Computação UFCG, 2013. All rights reserved.