Ciencia_Da_Computacao_Eng_Software

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Análise de algoritmos
Algoritmos: Introdução
Dado um problema, como encontrar um algoritmo eficiente para sua solução? 
Encontrado um algoritmo, como comparar este algoritmo com outros algoritmos que oferecem soluções similares para o mesmo problema? 
Como avaliar a qualidade de um algoritmo? 
Qual é o algoritmo de menor custo computacional possível para solucionar um problema particular?
Questões como essas são relevantes para programadores e cientistas da computação. 
Algoritmos: Introdução
No domínio da Ciência da Computação algoritmos podem ser avaliados sob diversos aspectos. 
Todos os aspectos levam em consideração o crescimento do tempo de execução do algoritmo ou espaço necessário (memória) para a solução de grandes problemas.
Algoritmos: Definição
Um algoritmo pode ser definido como uma sequência de ações executáveis para a obtenção de uma solução para um determinado problema (Parreira Jr, 2014). 
Também pode ser visto com sendo uma descrição de um padrão de comportamento, expresso em termos de conjuntos finitos de ações (Dijkstra, 1994). 
Ou ainda, uma descrição finita, passo a passo, de como um problema é solucionável (Terada, 1991).
Os referidos passos devem ser bem definidos, sem ambiguidades e executáveis em computadores (Parreira Jr, 2014). 
Algoritmos: Complexidade
Vários critérios podem ser utilizados para escolher o algoritmo, quais sejam: situações que manipulam poucos dados, problemas que exige o processamento de muitos dados(multimídia, inteligência artificial, redes sociais), etc. 
Todos os critérios consideram o tempo de execução do algoritmo e o espaço(memória) necessário ao armazenamento dos dados do problema.
Calcular o tempo de execução e o espaço exigido por um algoritmo para uma determinada entrada de dados é um estudo da complexidade de algoritmos (Parreira Jr, 2014). 
Algoritmos: Complexidade
Como avaliar (calcular) a complexidade de um algoritmo?
No cálculo da complexidade, pode-se medir o número de passos de execução de uma máquina de Turing ao processar o algoritmo;
Ou medir o tempo gasto na execução do algoritmo em um computador específico. 
Contudo, a maioria das análises no domínio da Ciência da Computação conta apenas o número de operações “elementares” executadas. 
A medida da complexidade é o crescimento assintótico dessa contagem de operações (Parreira Jr, 2014). 
Algoritmos: Complexidade
Por exemplo, em um algoritmo para encontra o maior número entre “n” números lidos, a operação elementar seria a comparação dos valores numéricos, e a complexidade seria uma função em “n” do número de comparações efetuadas pelo algoritmo, para valores elevados de “n” (crescimento assintótico)
(Parreira Jr, 2014). 
A complexidade assintótica de um algoritmo determina o tamanho de problemas que podem ser solucionados pelo algoritmo (Parreira Jr, 2014). 
Por exemplo, se um algoritmo processa entradas de tamanho “n” (n dados) no tempo c*n2, para alguma constante c, então a complexidade de tempo do algoritmo é O(n2), lê-se big O de ordem n2 ou complexidade de ordem 2, ou seja:
Algoritmos: Complexidade
	Entrada (n)	Complexidade tempo (O(n2))
	1	1
	2	4
	4	16
	8	64
	16	256
	32	1024
	64	4096
Algoritmos: Complexidade - operações
Para t = 1s
T(n) = n * UT
1 = n * 10-3
n = 1000
Cálculos para A1
Para t = 1min 
T(n) = n * UT
60 = n * 10-3
n = 60000
Para t = 1hora 
T(n) = n * UT
3600 = n * 10-3
n = 3,6 * 106
Algoritmos: Complexidade - operações
Para t = 1s
T(n) = n2 * UT
1 =  n2 * 10-3
n2 = 1/10-3
n2 = 103 
n = 31,6
Cálculos para A3
Para t = 1min
T(n) = n2 * UT
60 =  n2 * 10-3
n2 = 60/10-3
n2 = 60000 
n = 244,9
Para t = 1hora
T(n) = n2 * UT
3600 =  n2 * 10-3
n2 = 3600/10-3
n2 = 3,6*106 
n = 1897,4
Algoritmos: Complexidade  - operações
Para t = 1s
T(n) = 2n * UT
1 =  2n * 10-3
2n = 1/10-3
2n = 103 
log22n = log2103
nlog22 = 3log210
n =  3x3,32 = 9.96
Cálculos para A5
Para t = 1min
T(n) = n2 * UT
60 =  2n * 10-3
2n = 60/10-3
2n = 60000 
log22n = log260000
nlog22 = log260000
n = 15,87
Para t = 1hora
T(n) = n2 * UT
3600 =  2n * 10-3
2n = 3600/10-3
2n = 3,6*106 
log22n = log2 3,6*106
nlog22 = log2 3,6*106
n = 21,78
Algoritmos: Complexidade - operações
Observa-se que algoritmos de complexidade linear (O(n)) resolvem problemas cada vez maiores com o aumento do tempo. 
Observa-se, contudo, que nos algoritmos de complexidade exponencial O((2n)) poucos aumentos no tamanho dos problemas resolvidos (operações feitas). 
Nos algoritmos de complexidade quadrática (O(n2)) o aumento no tamanho do problema (em termos de operações) no tempo é discreto, mas "aceitável".
Algoritmos: Complexidade - operações
Nota-se que um aumento de 10 vezes na velocidade de computação permite: Algoritmos de complexidade linear O(n) resolver problemas 10 vezes maiores;
Algoritmos de complexidade quadrática O(n2) solucionar problemas 3 vezes maiores;
enquanto que os algoritmos de complexidade exponencial O(2n) não aumentam significativamente a capacidade de solucionar problemas maiores. 
os
13
Algoritmos: Complexidade
Cálculos
Para A1:
Atual: T(n) = S1 * 1 UT
Futuro: T´(n) = ( n * 1UT) / 10
T(n) = T´(n)
S1*1UT = (n*1UT)/10
n = 10*S1
Para A3:
Atual: T(n) = S32 * 1 UT
Futuro: T´(n) = ( n2 * 1UT) / 10
T(n) = T´(n)
S32*1UT = (n2*1UT)/10
S32 = n2/10
n2  = 10*S32
n  = 3* S3
Para A5:
Atual: T(n) = 2S5 * 1 UT
Futuro: T´(n) = ( 2n * 1UT) / 10
T(n) = T´(n)
2S5*1UT = (2n*1UT)/10
2S5 = 2n/10
2n  = 10*2S5
log22n  = log2( 10* 2S5)
nlog22 = log210 + log22S5 
n =  3,3 + S5
image1.jpeg