2011_1_ciencia_da_computacao_7_analise_e_complexidade_de_algoritmos-1

5/10/2018 2011_1_ciencia_da_computacao_7_analise_e_complexidade_de_algoritmos-1 - ...

http://slidepdf.com/reader/full/20111cienciadacomputacao7analiseecomplexidadedealgoritmos-1

ATIVIDADES PRÁTICASSUPERVISIONADAS

Ciência da Computação7ª Série

Análise e Complexidade de Algoritmos

A atividade prática supervisionada (ATPS) é um método de ensino-

aprendizagem desenvolvido por meio de um conjunto de atividades

programadas e supervisionadas e que tem por objetivos:

Favorecer a aprendizagem.

Estimular a corresponsabilidade do aluno pelo aprendizado eficiente e

eficaz.

Promover o estudo, a convivência e o trabalho em grupo.

Desenvolver os estudos independentes, sistemáticos e o autoaprendizado.

Oferecer diferenciados ambientes de aprendizagem.

Auxiliar no desenvolvimento das competências requeridas pelas DiretrizesCurriculares Nacionais dos Cursos de Graduação.

Promover a aplicação da teoria e conceitos para a solução de problemas

relativos à profissão.

Direcionar o estudante para a emancipação intelectual.

Para atingir esses objetivos, as atividades foram organizadas na forma de

um desafio, que será solucionado por etapas ao longo do semestre letivo.

Participar ativamente desse desafio é essencial para o desenvolvimento das

competências e habilidades requeridas na sua atuação, no mercado de trabalho.

Aproveite essa oportunidade de estudar e aprender com desafios da vida

profissional.

AUTORIA:

Marcela Cristiani Ferreira

Faculdade Anhanguera de Limeira



Ciência da Computação – 7ª Série – Análise e Complexidade de Algoritmos


Pág. 2 de 7

COMPETÊNCIAS E HABILIDADES

Ao concluir as etapas propostas neste desafio, você terá desenvolvido as competênciase habilidades descritas a seguir:

Competência para identificar, analisar, documentar e solucionar problemas enecessidades passíveis de solução via computação.

Capacidade de desenvolvimento para a pesquisa científica e tecnológica. Aplicação eficiente dos princípios de gerenciamento, organização e busca de

informações. Analisar, organizar, abstrair e relacionar dados e informações.

DESAFIO

De acordo com Ziviani (2005), um algoritmo pode ser visto como uma sequência deações executáveis a fim de obter uma solução para um determinado tipo de problema. Oobjetivo da disciplina de Análise e Complexidade de Algoritmos é atribuir ferramentas queauxiliem na decisão de escolha entre dois ou mais algoritmos, qual é o melhor para resolverdeterminado problema, levando em consideração o tempo gasto para executar todas as açõese a quantidade de memória utilizada para armazenamento das informações. O estudo dacomplexidade é feita através de classes assintóticas.

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

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

Produção AcadêmicaSerão produzidos relatórios parciais referentes a cada uma das etapas.

ParticipaçãoPara a elaboração dessa atividade, os alunos deverão previamente organizar-se em

equipes de 1 a 4 participantes e entregar seus nomes, RAs e e-mails ao professor da disciplina.Essas equipes serão mantidas durante todas as etapas.

PadronizaçãoO material escrito solicitado nessa atividade deve ser produzido de acordo com as

normas da ABNT1, com o seguinte padrão:• em papel branco, formato A4;• com margens esquerda e superior de 3cm, direita e inferior de 2cm;•

fonte Times New Roman tamanho 12, cor preta;1

Consulte o Manual para Elaboração de Trabalhos Acadêmicos. Unianhanguera. Disponível em:

<http://www.unianhanguera.edu.br/anhanguera/bibliotecas/normas_bibliograficas/index.html>.





Pág. 3 de 7

• espaçamento duplo entre linhas;• se houver citações com mais de três linhas, devem ser em fonte tamanho 10, com

um recuo de 4cm da margem esquerda e espaçamento simples entre linhas;• com capa, contendo:

• nome de sua Unidade de Ensino, Curso e Disciplina;

• nome e RA de cada participante;• título da atividade;• nome do professor da disciplina;• cidade e data da entrega, apresentação ou publicação.

ETAPA 1

Aula-tema: Medidas de Complexidade, análise assintótica de limites decomplexidade.

Essa atividade é importante para que você conheça as medidas assintóticas decomplexidade, considerando que os algoritmos são representados, muitas vezes, por funçõesmatemáticas, assim, faz-se um estudo sobre o comportamento assintótico dessas funções.

Para realizá-la, é importante seguir os passos descritos.

PASSOS

Passo 1

Ler o Capítulo 1 – “Introdução”: Seção 1.3; subseções 1.3.1, 1.3.2, do livro do Ziviani (2005).

Passo 2

Definir, de acordo com o texto lido no passo 1, as medidas de complexidade Ômicron (Ο ),Ômega (Ω ) e Theta (Θ ).

Passo 3

Usar as medidas de complexidade descritas acima e fazer as seguintes atividades:1. Comparar uma função linear f(n) com uma função quadrática g(n) e mostre que f(n) é

Ômicron (g(n)), determinando constantes n0 natural e c real positivo;

2. Comparar uma função exponencial f(n) com uma função cúbica g(n) e mostre que f(n) éÔmega (g(n)), determinando constantes n0 natural e d real positivo;

3. Comparar duas funções quadráticas f(n) e g(n) e mostre que f(n) é Theta (g(n)),determinando constantes c, d reais positivos e n0 natural.

Passo 4

Criar um algoritmo que tenha pelo menos dois elementos que sejam comuns a maioria dosalgoritmos como, por exemplo, atribuições simples, declarações, laços, laços aninhados,If-Then-Else. Entregar ao professor o Relatório 1 com todos os passos descritos nessa etapa.





Pág. 4 de 7

ETAPA 2

Aula-tema: Análise de desempenho de alguns algoritmos clássicos de busca,ordenação e sobre grafos.

Essa atividade é importante para que você aprenda a analisar algoritmos de ordenaçãopor seleção e por inserção.Para realizá-la, é importante seguir os passos descritos.

PASSOS

Passo 1

Citar as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenaçãopor inserção. Explicar o funcionamento de cada um deles.

Passo 2

Criar um algoritmo de ordenação por inserção e um de ordenação por seleção para ordenarum vetor de tamanho n.

Passo 3

Explicar o funcionamento, passo a passo, dos algoritmos criados no passo 2 dessa etapa.

Passo 4Escrever a complexidade, linha a linha, de cada um dos algoritmos criados no passo 2 dessaetapa. Entregar ao professor o Relatório 2 com todos os passos descritos nessa etapa.

ETAPA 3

Aula-tema: Análise de desempenho de alguns algoritmos clássicos de busca,ordenação e sobre grafos.

Essa atividade é importante para que você aprenda a representar grafos através delistas de adjacência e matriz de adjacência.


PASSOS

Passo 1

Criar um grafo com no mínimo 5 vértices, represente-o através da matriz de adjacência eatravés da lista de adjacência e faça um algoritmo que dê o grau de cada um de seus vértices,usando as duas maneiras representadas. Apresentar a complexidade dos algoritmos criados.





Pág. 5 de 7

Passo 2

Desenhar o grafo ponderado que representa a seguinte situação: Suponha que umfuncionário encarregado de verificar o estado das estradas, deseja planejar a sua rota deinspeção nas estradas que existem entre as cidades A, B, C, D e E. A rota deve se iniciar nacidade A. O custo de cada estrada é:

Estrada ligando a cidade A à cidade B = 3;Estrada ligando a cidade A à cidade E = 12;Estrada ligando a cidade B à cidade C = 3;Estrada ligando a cidade B à cidade D = 2;Estrada ligando a cidade B à cidade E = 7;Estrada ligando a cidade C à cidade D = 2;Estrada ligando a cidade E à cidade D = 6.

Passo 3

Fazer a matriz de custos que representa o grafo do passo 2 dessa etapa.

Passo 4

Calcular o caminho de custo mínimo para o inspetor percorrer. Entregue ao professor todosos passos da etapa descritos no Relatório 3.

ETAPA 4

Aula-tema: Introdução aos principais paradigmas do projeto de algoritmos –recursividade.

Essa atividade é importante para que você perceba a diferença entre as análises de umalgoritmo recursivo e um algoritmo iterativo.


PASSOS

Passo 1

Pesquisar em Ziviani (2005) ou em Cormen (2002) as diferenças entre os dois tipos dealgoritmos: iterativo e recursivo, dando pelo menos um exemplo de cada um deles.

Passo 2

Pesquisar no livro do Cormen (2002), os métodos de resolução de uma equação derecorrência. Apresente a equação de recorrência que representa o algoritmo recursivoextraído do livro do Ziviani (2005), capítulo 1, página 22:





Pág. 6 de 7

Pesquisa (n);(1) if n <= 1(2) then ‘inspecione elemento’ e termine

else begin(3) para cada um dos n elementos ‘inspecione elemento’;(4) Pesquisa (n/3);

end;

Em seguida, resolva a seguinte equação de recorrência: T(n) = n + T(n/2); T(1) = 0.

Passo 3

Apresentar a equação de recorrência, resolvê-la e escrever a ordem de complexidade doalgoritmo a seguir:

int soma(int n)

int (n == 1)return(1);

elsereturn (n + soma(n - 1));

main ( )

int n = 4;printf (“%d”, soma (n));

Passo 4

Descrever a ordem de complexidade do algoritmo a seguir, explicando o seu raciocínio.Entregar ao professor todos os passos da etapa descritos no Relatório 4.

funct subsequênciaSomaMáxima(v: array Z, n : N) : Z ≡ var soma, somaMáxima: Z

i, j, k : Nendbegin

somaMáxima ←v[1]for i = 1 to n step 1 do

for j = i to n step 1 dosoma ← 0for k = i to j step 1 do

soma ← soma + v[k]odif soma > somaMáxima then somaMáxima ← soma fl

odod

result←

somaMáximaend

Fonte: DÉHABE, DAVID (2003, p. 8)





Pág. 7 de 7

ETAPA 5

Aula-tema: Introdução aos principais paradigmas do projeto de algoritmos:Algoritmos Gulosos e Algoritmos de aproximação.

Essa atividade é importante para que você entenda o funcionamento de um algoritmoguloso.Para realizá-la, é importante seguir os passos descritos.

PASSOS

Passo 1

Pesquisar no livro do Cormen (2002), explicar como é o funcionamento do algoritmo guloso ecomo é calculada sua complexidade.

Passo 2

Escolher três listas de tamanhos diferentes e faça a intercalação segundo o algoritmo guloso.Explicar de que forma a ordem da escolha das listas de tamanhos m1, m2 e m3 influencia nacomplexidade do algoritmo.

Passo 3

Ler o artigo: Sistema para Análise Automática da Complexidade de Algoritmos NãoRecursivos no Pior Caso de Marco Antonio de Castro Barbosa que se encontrar emhttps://docs.google.com/fileview?id=0B-Sl6Nl-2puCNDAzOTM1MGYtZDllYy00ZmRlLWFhNjctNjQzMThhMWRkY2M5&h (Acessado em27/ 10/ 2010) e fazer uma análise crítica do mesmo.

Passo 4

Fazer o Relatório 5 com as informações referentes a essa etapa e entregar ao professor.

Bibliografia

ZIVIANI, N. Projeto de Algoritmos com implementações em Pascal e C. 2ª edição. SãoPaulo: Pioneira Thomson Learning, 2005. 552 p.

CORMEN, T. H.; LEISERSON, C . E.; RIVEST, R. L.; STEIN, C. Algoritmos: Teoria e Prática.Tradução da 2ª edição Americana. Rio de Janeiro, Elsevier, 2002. 916 p.

Documents

2011_1_ciencia_da_computacao_7_analise_e_complexidade_de_algoritmos-1