Contagem de instruções Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Contagem de instruções– Teoria dos Grafos e Análise de Algoritmos
Exercícios
1. Por meio da contagem de instruções, é possível definir o tempo de execução de
um algoritmo, possibilitando a avaliação da sua eficácia. Considerando os
conhecimentos adquiridos a respeito da análise de algoritmos, leia as assertivas a
seguir:
I. O melhor caso do custo de tempo de execução de um algoritmo é quando a
maioria das instruções são executadas, percorrendo, assim, o algoritmo por inteiro.
II. A escolha de um algoritmo eficiente é considerada uma boa prática, pois impacta
a utilização sensata dos recursos computacionais disponíveis.
III. Um algoritmo pode ser definido como qualquer procedimento computacional
composto por regras, ambíguas e não ambíguas, que, dada uma entrada, produz
uma saída.
IV. Caso a entrada de um algoritmo dobre de tamanho e seu tempo de execução
aumente ao quadrado, será considerado um algoritmo de tempo de execução
exponencial.
Quais alternativas estão corretas?
Você acertou!
C. As afirmativas II e IV estão corretas. 
O melhor  caso do custo  de   tempo de  execução de  um algoritmo é quando o
menor número possível de instruções é executado, resultando em um tempo
de execução menor.
A   escolha   de   um   algoritmo   eficiente   é considerada uma boa prática,
impactando positivamente o desempenho de um sistema.
Um   algoritmo   poder   ser   definido   como   qualquer   procedimento
computacional composto por regras bem definidas e não ambíguas,   que,
dada uma entrada, produz uma saída.
Algoritmos com tempo de execução exponencial aumentam de forma drástica seu
tempo de execução de acordo com o aumento do tamanho da entrada. Caso o
valor do tamanho da entrada dobre, o tempo de execução será elevado ao
quadrado.
2. A contagem de instruções é um modelo matemático que serve para estimar o
custo de execução de um algoritmo. Esse modelo independe das especificações de
um computador, da linguagem de programação e do compilador
utilizado, permitindo, assim, uma comparação de desempenho mais justa entre os
algoritmos.
Utilizando a contagem de instruções, analise o algoritmo a seguir e calcule a função
de custo de tempo de execução.
Assinale a alternativa correta.
Resposta correta.
D. C(n) = (3n²+11n-4)/2.
3. Por meio da ordem de crescimento das funções de custo de tempo de execução,
é possível comparar a eficácia de dois ou mais algoritmos. Nas afirmações a seguir,
marque (V) para verdadeiro e (F) para falso:
( ) As funções de ordem quadrática e cúbica são recomendadas para grandes
conjuntos de entrada, mas não são aconselháveis para entradas muito pequenas.
( ) Algoritmos com tempo de execução e crescimento exponencial são
considerados impraticáveis.
( ) Dobrando o valor da entrada de uma função de ordem de crescimento nlog(n),
seu tempo de execução irá quadruplicar.
( ) Funções cúbicas aumentam em oito vezes o tempo de execução ao dobrar o
valor de sua entrada.
( ) Algoritmos com funções de crescimento logarítmico têm menor tempo de
execução do que as funções lineares, considerando o mesmo tamanho de entrada.
Sendo assim, analise a alternativa que apresenta a sequência correta.
Você acertou!
B. F – V – F – V – V.
As funções com ordem de crescimento quadrático e cúbico são
desaconselháveis para entradas muito grandes por impactarem de forma drástica
os   tempos   de   execuções   dos   algoritmos.   Seguindo   a   mesma   linha   de
raciocínio, algoritmos com funções de grandeza exponencial são   inviáveis:
enquanto   a   entrada   dobra   de   tamanho,   o   tempo   de   execução   é   elevado   ao
quadrado.
Quando as entradas das funções linearítmicas e cúbicas dobrarem, os tempos
de   execução   dos   algoritmos   aumentarão   um   pouco   mais   que   o   dobro   e   em
oito vezes, respectivamente.
Considerando   dois   algoritmos   cujas   funções   são   de ordens distintas,
logarítmicas e lineares,  dada uma mesma entrada,  o  tempo de execução da
função de grandeza logarítmica será menor que a linear.
4. Existem diferentes tipos de instruções. As instruções simples têm um custo de
execução fixo igual a um; já as instruções mais complexas, que envolvem a
utilização de comandos de operações com uma ou mais instruções simples, têm
custos variáveis, de acordo com o tamanho da entrada e a implementação
realizada. 
Considerando as informações a respeito da contagem de instruções, assinale a
alternativa correta.
Você acertou!
D. O comando for tem seu custo dobrado sempre que apresentar outras instruções em
conjunto; sozinho, seu custo é zero.
São consideradas instruções simples com custo igual a um: atribuição de valor,
comparação de valor, operações aritméticas básicas, incrementações, acesso ao
valor de um determinado elemento de um vetor e comandos de leitura e escrita.
Linhas de comentários não são consideradas instruções, ou seja, seu custo é igual
a   zero.   Comandos   de   operações,   como,   por   exemplo, if, for, while,   quando
sozinhos,   têm custo  igual  a zero também.Esses comandos só apresentarão um
custo   diferente   de   zero quando   estiverem   relacionados   a   alguma   instrução
simples. O comando for tem custo zero quando vazio, mas, quando
acompanhado de instruções de atribuição e comparação, apresenta um
custo dobrado. Após realizar a contagem do custo de instruções, são somados
todos os valores para obter o valor final de custo de tempo de execução de um
algoritmo.
5. É possível estimar a eficiência de um algoritmo de acordo com seu tempo de
execução. Para isso, o método de contagem de instruções é utilizado. Por ser um
método matemático, é eficaz e independe de especificações de máquina, não
precisando da real implementação do algoritmo, sendo possível utilizar
pseudocódigos.
Utilize o método de contagem de instruções para analisar o algoritmo a seguir,
calculando sua função de custo de tempo de execução. 
Assinale a alternativa correta.
Resposta correta.
A. C(n) = (3n²+7n+8)/2.
	Contagem de instruções– Teoria dos Grafos e Análise de Algoritmos
	Exercícios