Técnicas de Programação

Enunciado: 

 

 

Algoritmos são usados para resolver diversos problemas nos mais variados contextos. Em um comércio eletrônico, por exemplo, os dados (informações como nome, cpf, rg, senha, número de cartão de crédito, etc) das transações do usuário que está fazendo a compra trafegam pela internet, portanto é necessário algum tipo de mecanismo para garantir a privacidade.

Para resolver esse problema, um algoritmo de criptografia pode ser implementado para garantir a integridade e a confidencialidade dos dados (Ascencio; Araújo, 2010).

Segundo Cormem (2002, apud Ascencio; Araújo, 2010), um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor de saída.

Entretanto, nem sempre a escolha do algoritmo certo é uma tarefa simples, portanto a análise do algoritmo a ser utilizado é o primeiro passo do planejamento antes de implementá-lo.

Para Cormem (2002, apud Ascencio; Araújo,2010), a análise do algoritmo é prever os recursos necessários para sua implementação como memória, largura de banda, hardware e tempo.

Para Knuth, (1971, apud Ascencio; Araújo, 2010), calcular o custo de um algoritmo é determinar qual das alternativas contém a solução que resolve o problema em menos tempo.

 

Nesse contexto, simulações devem ser realizadas para que a escolha do algoritmo seja a mais assertiva possível.

Ascencio, A. F. G.; Araújo, G. S. Estruturas de Dados: algoritmos, análise da complexidade e implementações em JAVA e C/C++. São Paulo: Pearson, 2010.

 

Com base no texto a respeito da dificuldade de escolha do algoritmo certo a implementar, faça uma simulação de teste para determinar qual o melhor algoritmo para resolver o problema de colocar a sequência de letras ‘UMDOIS’ em ordem alfabética.

A) Mostre as etapas intermediárias de ordenação da implementação do algoritmo selection sort (por seleção).

B) Mostre as etapas intermediárias de ordenação da implementação do algoritmo quick sort (rápida), tendo o elemento à esquerda da partição com pivô.

C) Faça uma análise da complexidade de custo de ambas as implementações justificando o porquê da escolha.