contagem de operações e medição do tempo de execução

Prévia do material em texto

<p>PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS</p><p>Instituto de Ciências Exatas e Informática</p><p>Exercícios sobre Contagem de Operações e Medição do Tempo de</p><p>Execução de Algoritmos</p><p>Curso : Engenharia de Software</p><p>Disciplina : Algoritmos e Estruturas de Dados II</p><p>Professores : Eveline Alonso Veloso</p><p>João Caram</p><p>Regras Básicas:</p><p>• Exercício prático individual.</p><p>• Sua entrega será realizada exclusivamente pelo Canvas, em tarefa própria, na turma prática.</p><p>• Entregas do exercício em cópia, mesmo que parcialmente, seja de código ou estrutura lógica, de</p><p>outros alunos, da Web ou de quaisquer outras fontes externas, acarretarão atribuição de nota 0 aos</p><p>alunos envolvidos e encaminhamento do caso ao Colegiado de Coordenação Didática do Curso.</p><p>Descrição:</p><p>Neste exercício, praticaremos a contagem de operações de algoritmos e a medição de</p><p>desempenho computacional. O exercício prático é composto das seguintes partes: (1) instrumentação</p><p>dos algoritmos propostos a fim de contar o número de operações executadas por cada um deles e medir</p><p>seus respectivos tempos de execução; (2) execução dos algoritmos e coleta de dados; (3) comparação</p><p>entre a contagem de operações e o desempenho dos algoritmos implementados.</p><p>Implementação:</p><p>A primeira parte do exercício consiste na instrumentação dos algoritmos abaixo a fim de contar o número</p><p>de operações executadas por cada um deles e medir seus respectivos tempos de execução:</p><p>Algoritmo A</p><p>public	static	int	codigoA(int	n){</p><p>int	b=0;</p><p>for(int	i	=	0;	i	<=	n;	i+=2){</p><p>b	+=	3;</p><p>}</p><p>return	b;</p><p>}</p><p>Algoritmo B</p><p>public	static	void	codigoB(int[]	vet){</p><p>for	(int	i	=	0;	i	<	vet.length;	i+=2){</p><p>for(int	j	=	i;	j	<	(vet.length/2);	j++){</p><p>vet[i]	+=	vet[j];</p><p>}</p><p>}</p><p>}</p><p>Essas implementações serão utilizadas na fase seguinte.</p><p>Experimentação:</p><p>Nesta etapa, o tempo de execução de cada algoritmo implementado deve ser medido, em uma</p><p>determinada máquina; assim como o número de operações executadas pelo algoritmo. É importante</p><p>observar que todos os experimentos deverão ser executados na mesma máquina, com a mesma</p><p>configuração de hardware e sistema operacional. Essa configuração deve constar no início do relatório a</p><p>ser entregue por você na finalização do trabalho.</p><p>Para realizar os experimentos, considere “n” como o tamanho da entrada de dados. Iniciando-se “n” em</p><p>15.625, devem ser utilizados valores crescentes, dobrando o valor de “n” em cada passo. Para cada valor</p><p>de “n”, registre a quantidade de operações realizadas pelo algoritmo e seu tempo gasto, em</p><p>nanossegundos.</p><p>Deverão ser realizadas 5 medições em cada cenário e o tempo de execução será dado pela média</p><p>aritmética das 3 medições intermediárias, ou seja, desconsiderando-se o maior e o menor valores medidos.</p><p>Seu teste irá até “n” superar 2 bilhões ou até o tempo médio de execução do algoritmo ultrapassar 50</p><p>segundos – o que ocorrer primeiro em cada algoritmo.</p><p>Comparação e Análise dos Resultados Analíticos e Experimentais:</p><p>Nesta parte, deve-se utilizar as informações de tempo de execução coletadas experimentalmente</p><p>anteriormente e compará-las com a contagem de operações de cada algoritmo implementado, apontando</p><p>semelhanças e possíveis diferenças entre a contagem de operações dos algoritmos, a análise experimental</p><p>e a complexidade esperada para o algoritmo.</p><p>A tabela a seguir apresenta um exemplo do que está sendo pedido, com dados fictícios.</p><p>Algoritmo X</p><p>N Operações Tempo</p><p>(nanossegundos)</p><p>15.625	 3.825	 385.330</p><p>31.250	 5.735	 550.127</p><p>62.500	 8.320	 912.615</p><p>125.000	 11.647	 1.235.042</p><p>250.000	 19.220	 1.755.934</p><p>...	 ...	 ...</p><p>Para isso, com base nos dados coletados, crie um gráfico para cada algoritmo implementado considerando</p><p>as médias dos tempos de execução medidos para cada valor de “n” e apresente suas conclusões.</p>