ATPS - Análise e Complexidade de Algoritmos

[pic 1]

ANHANGUERA EDUCACIONAL – LEME

CENTRO UNIVERSITÁRIO ANHANGUERA UNIDADE LEME

CIÊNCIA DA COMPUTAÇÃO

ATPS - ATIVIDADES PRÁTICAS SUPERVISIONADAS

ANÁLISE E COMPLEXIDADE DE ALGORITMOS

ANÁLISE E COMPLEXIDADE DE ALGORITMOS

Trabalho apresentado ao Centro Universitário Anhanguera, unidade Leme, como requisito parcial para obtenção de nota nas Atividades Práticas Supervisionadas da disciplina Complexidade de Algoritmos, do curso de Bacharel em Ciências da Computação.

SUMÁRIO

1.        Introdução        

2.        Objetivo do Desafio        

3.        Introdução à Análise de Complexidade de Algoritmos        

3.1.        Medida de Complexidade de Algoritmo Ômicron        

3.2.        Implementação do Algoritmo        

4.        Algoritmos de Ordenação        

4.1.        Ordenação por Seleção        

4.2.        Ordenação por Inserção        

5.        Algoritmos Iterativos e Recursivos        

5.1.        Implementação de um Algoritmo Recursivo        

6.        Algoritmos Gulosos        

6.1.        Implementação de Algoritmo Guloso        

7.        Referências Bibliográficas        

1. Introdução

A Atividade Prática Supervisionada (ATPS) é um procedimento metodológico de ensino-aprendizagem desenvolvido por meio de etapas, acompanhadas pelo professor, e que tem por objetivos:

• Favorecer a autoaprendizagem do aluno;
• Estimular a corresponsabilidade do aluno pelo aprendizado;
• Promover o estudo, a convivência e o trabalho em grupo;
• Auxiliar no desenvolvimento das competências requeridas para o exercício profissional;
• Promover a aplicação da teoria na solução de situações que simulam a realidade;
• Oferecer diferenciados ambientes de aprendizagem.

Para atingir esses objetivos, a ATPS propõe um desafio e indica os passos a serem percorridos ao longo do semestre para sua solução.

1. Objetivo do Desafio

Esse desafio propõe aos alunos fazerem um estudo sobre análise de classes distintas de algoritmos, sendo elas: algoritmos de ordenação, algoritmos em grafos, algoritmos iterativos e recursivos e algoritmos gulosos, fazendo uso dos conceitos de medidas de complexidade vistos na disciplina de Análise e Complexidade de Algoritmos. Essas análises serão feitas para que o aluno possa aplicá-las em situações de decisão entre dois ou mais algoritmos que resolvem certos tipos de problemas.

O objetivo do desafio é mostrar ao aluno o funcionamento das classes de algoritmos citadas acima e, ao final conhecer uma ferramenta que o ajudará na análise de complexidade.

1. Introdução à Análise de Complexidade de Algoritmos

Conforme Ziviani (2004), todo projeto de algoritmo é influenciado pelo estudo dr seus comportamentos.

Após um problema ser levantado, analisado e decisões de projeto são tomadas, os algoritmos devem ser implementados por um desenvolvedor. Neste momento, um projetista pode se deparar com inúmeros algoritmos que resolvem o dado problema, custo de tempo de execução e espaço de alocação em memória são aspectos importantes que devem ser considerados ao determinar qual algoritmo implementado.

Na área de análise de algoritmos existem dois tipos de problemas bem distintos, conforme apontou Knuth (1971):

• Análise de um algoritmo particular; e
• Análise de uma classe de algoritmo.

Quando determinamos que o custo de um algoritmo é igual ao menor custo possível, então é possível concluir que o algoritmo é ótimo para a medida de custo considerada.

1. Medida de Complexidade de Algoritmo Ômicron

A complexidade de um algoritmo depende da quantidade de vezes que será executado sua operação elementar, tais quais podem variam de acordo com a entrada de tamanho n.

Sugerido por Knuth (1968) uma notação para dominação assintótica, O (ômicron) é utilizado para expressar comparativamente o crescimento assintótico e representa a velocidade com que a função tende ao infinito. Representar a medida do pior caso possível, ou o mais demorado, baseando-se no tempo de execução sobre todas as entradas de tamanho n. É o método mais fácil de se obter.

Dado um arquivo com n registros, sendo cada registro uma chave única, e dado um problema localizar uma chave qualquer no arquivo, podemos considerar que o pior caso é f(n) ou O(n) (chave é igual ao último registro ou é inexistente).

1. Implementação do Algoritmo

Algoritmo desenvolvido em C++ que realiza o tratamento de uma dada variável do tipo string, removendo alguns caracteres específicos que estão acentuados.

O algoritmo implementa declarações e declarações simples, laços e laços aninhados e expressões condicionais if-then-else.

...