6-output

Prévia do material em texto

E-Book - Apostila
6-Boas ferramentas trazem eficiência (DL)
E-Book - Apostila
Esse arquivoé uma versão estática. Para melhor experiência, acesse esse conteúdo pela m ídia interativa.
Boa
e
E-Book - Apostila
ntas
Esta unidade de estudos focará em boas ferramentas. Leia com atençãoo trechoa seguir:
Reflexão
Thiago era um programador muito perfeccionista em seus códigos. Criar estruturas
organizadase eficientes não erao suficiente para ele: era precisa buscar uma otimização
extrema. Em geral, Thiago utilizava arrays de tamanho fixo para buscar maior otimização
e velocidade, sempre com as posições necessárias para operaro seu código. Por vezes
Thiago ficava extremamente estressadoe tinha dificuldades em trabalhar em equipe,
justamente por não utilizar estruturas dinâmicas. Para determinados problemas, mesmo
perdendo um pouco de otimização, utilizar estruturas como listas seria mais proveitoso
parao desenvolvimento do projeto.
Vamos refletir sobrea utilização de estruturas estáticase dinâmicas para as melhores
abordagens na implementação de soluções computacionais?
2-13
E-Book - Apostila
Ao final deste conteúdo, você será capaz de:
^ Diferenciar arrayse listas, compreendendo asaplicabilidades de estruturas
estáticase dinâmicas;
• Propora utilização de métodos de ordenação paraa resoluções de problemas
específicos;
• Implementar soluções que utilizem tipos abstratos de dados como pilhase filas.
FIGURA1 -O que estudaremos?
3-13
ELABORA$ÃO DOAUTOR,2020.
Vetores (Arrays)
E-Book - Apostila
Um dos primeiros problemas que surgem, quando estamos programando,é a necessidade de
processar listas de valores. Sea lista for pequenao bastante, você declara algumas variáveise
resolve como temos feito até agora. Mas,e sea lista for muito grande? Como fazer?
Vetores (ou arrays) são usados para armazenar vários valores em uma única variável, ao invés de
declarar variáveis separadas para cada valor.É a forma mais simples de organizar listas de dados na
memória, pois são armazenados em sequência, um apóso outro,o que permite que qualquer valor
de qualquer posição seja acessado livremente.
Estudo Guiado
Ü/ ATENÇÃO
Dizemos que os vetores são variáveis compostas homogêneas, pois seus elementos
4 - 13
devem sertodos do mesmo tipo.
E-Book - Apostila
Para entender como declarar um vetor unidimensional na
linguagem Javae acessar cada uma de suas posições, leia
atentamente as páginas 190a 192 desta referência.
Clique no linke leiao livro
DEITEL, H.; DE IT EL, P.J ava: como programar. 8. ed. São Paulo: Pearson, 2010.
Até agora, falamos sobre listas de variáveis, mas não é raro termos necessidade de estruturas com
mais dimensões, como uma tabela, por exemplo. Nesse caso, precisaríamos que nosso vetor tivesse
linhase colunas, tal qual uma tabela do banco de dados, ou seja, um vetor de dimensão 2, que
muitas vezesé chamado matriz.
Quando definimos as dimensões de um vetor, podemos definir tamanhosdiferentes para cada uma
delas.
Estudo Guiado
Nada como um exemplo para esclarecer esse conceito. Dê uma
espiada nas páginas 109a 112. Elas mostram detalhadamente
como definire acessar elementos de uma matrize finalizam com
um estudo de caso muito rico, na linguagem Java.
Clique no linke leiao livro
5-13
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1142
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1142
E-Book - Apostila
DEITEL, H.; DE IT EL, P.J ava: como programar. 8. ed. São Paulo: Pearson, 2010.
ATENÇÃO
Podemos tervetores de quantas dimensões forem necessárias,e cada dimensão pode
tertamanhos distintos.
FIGURA2 - Exemplo
ELABORAÇÃO DO AUTOR, 201O.
Porqueutilizar vetores? Simples! Porque, às vezes, precisamos realizar tarefas sobre uma massa de
dados, como ordená-la para facilitar buscas sobre ela.E os vetores (não importa de quantas
dimensões) permitem realizar esses algoritmos de maneira muito eficiente, pois, como visto nos
exemplos, são utilizados índices para acessoa cada um de seus elementos,o que favorece
algoritmos iterativos.
Métodos fundamentais de ordenação
Alguns algoritmos utilizam técnicas bem simples, como condiçõese laços. Outros exigem técnicas
mais elaboradas. Vamos estudar agora alguns fundamentos dos algoritmos chamados elementares.
São três:
6-13
E-Book - Apostila
• Ordenação por Inserção - lnsertion Sort
• Ordenação porSeleção - Selection Sort
• Ordenção pelo Método da Bolha - Bubble Sort
Como exemplo, temoso método de Ordenação por Inserção. Trata-se de um algoritmo intuitivo.
Funciona como seestivéssemos ordenando um conjunto de cartas na mão:
Considere um vetorv com n posições. Tome um elemento do vetor numa posição i, i»=1e
insira-o na sequência jáordenada v[0.. i-1] na posição adequada.A posição 0, se
considerada sozinha, está naturalmente ordenada.O segredoé encontrara posição
adequada.
A figura,a seguir, ilustraa dinâmica.
FIGURA3 - Dinâmica do algoritmo de Ordenação por Inserção
7-13
v inicial
i = 1
i z 2
i =3
i = 4
ELABORAÇÃO DO AUTOR, 2020.
E-Book - Apostila
Nadaa fazer
Veja agorao algoritmo. Perceba que as técnicas são simples.
Ordenação por Inserção (vetor v, inteiro n)
para j de 1 até n-1
x v[j]
i j-l
enquanto i > 0 e v[i] > x
v[i+l] = v[i]
i i-l
V[i+1] x
8- 13
Ordenação	por	Inserção	(vetor	v,		inteiro	n)
						para	j	de	1	até	n-1
												x	=	v[j]
												i	=	j−1
												enquanto	i	≥	0	e	v[i]	>	x
																		v[i+1]	=	v[i]
																		i	=	i−1
												v[i+1]	=	x
E-Book - Apostila
Zl Saiba Mais
Você pode encontrar detalhes dessee dos outros algoritmos elementares em https://plata
forma.bvirtual.com.br/Leitor/Publicacao/1995
As páginas 21a 52 trazem explicações minuciosas, além de um estudo comparativo sobre
o desempenho de cada um deles.
Será que existem algoritmos mais eficientes para ordenação de dados? Pode apostar que sim!
Entretanto,a implementação desses algoritmos necessita de técnicas mais elaboradas, entre elasa
recursão.
Recursãoe algoritmos mais eficientes de ordenação
A recursão caracteriza-se pela chamada de uma sub-rotina no próprio corpo da sub-rotina, ou
seja, ela faz uma chamada para ela mesma. Cada linguagem tem um nome diferente para as
sub-rotinas: funções em C e Python, métodos em Java, entre outros.
A recursão pode serobservada na natureza. Existem muitos exemplos de objetos em que suas
partes separadas repetem as características do todo. Vejaa Figura 4.
FIGURA4 - Exemplo de fractal na natureza
9 - 13
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf/0?code=TBT5q6WfaiGPZvTpb93Ij0wfbKkysq+cBtC96oSQ1wyurSNNoX4Q6NK8R4j8gbIZlVegSsxnFojjXKym9LN0EQ==
E-Book - Apostila
Entre os algoritmos que utilizama recursão para sua implementação, temoso Quick Sorte o Merge
Sort. Ambos utilizama estratégia "divisãoe conquista".
Existem ainda outros algoritmos que permitema ordenação de dados que não se baseiam em
comparação. São baseados na contagem dos elementos: Counting Sort.
Saiba Mais
Quer saber mais sobre esses algoritmose sua eficiência? Veja as páginas 53a 73 de https:/
/plataforma.bvirtual.com.br/Leitor/Publicacao/1995
10-13
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995
E-Book - Apostila
Nem tudoé vetor, quase tudo
Vimos que osvetores são estruturas muito eficientes, pois alocam-se em espaços contíguos de
memória. lsso permite acessar qualquer posiçãoa partir do seu endereço inicial, ou seja, podemos
fazer acesso randômico aos seus elementos.
No entanto, vetores não são flexíveis quantoà definição do seu tamanho. Na maioria das vezes, ele
é dimensionado para suportaro número máximo previsível de elementos paraa resolução de um
problema.
Vetores dinâmicos amenizam esse problema, pois realocam novos espaços de memória.
Saiba Mais
Quer saber como sãoosvetores dinâmicos?A linguagem Java fornece uma classe, dentro
da Java Collections, chamada ArrayList. Veja as páginas 221a 223 de https://plataforma.b
virtual.com.br/Leitor/Loader/1142
Você vaiperceber quantacoisa legalé possível fazer com essa estrutura.
Existe também uma alternativa bem interessante de estrutura que cresce ou diminui, conformea
necessidade da aplicação: as listas ligadas. Essas estruturas fazema alocação oua desalocação de
memória para cada elemento que precisa ser inserido ou removido da lista de dadosa ser
processada.
Tipos abstratos
Um tipo abstrato de dados (TAD) trata-se de um conjunto de dados estruturadose um conjunto de
operações que podem serexecutadas sobre esses dados.
Alguns tipos são muito utilizados em computação: pilhae fila. Nesses tipos,a inserçãoe a retirada
de elementos seguem regras bem definidas.A pilha segue LIFO (last in, first out):o último elemento
a serinseridoé o primeiro disponível para remoção. Jáa fila segue FIFO (first in, first out):o
primeiro queé inserido deve sero primeiro queé removido.
11-13
https://plataforma.bvirtual.com.br/Leitor/Loader/1142/pdf
E-Book - Apostila
Importante dizer que esses tipos podem serimplementados, utilizando tanto vetores
quanto listas ligadas.
Além desses tipos, temos outros ainda mais elaborados. Cada um servea propósitos específicos
dentro do desenvolvimento de software: temos árvores, grafos, tabelas hash entre outros.
Qual seriao propósito dessas estruturas? Tanto as estruturas quanto os algoritmos estudados
permitem eficiência no processamento. Tudo está ligadoà necessidade de processamento cada
vez mais rápido das informações. Por exemplo: quando temos uma lista de valores ordenados,
podemos realizar um algoritmo de busca mais eficiente do que a força bruta. Um exemploé a
busca binária.
Estudo Guiado
Para ver um pouquinho mais sobre esses conteúdos, acesseo linke
leia as páginas 90a 102. Você vaigostar de colocar esses elementos
no seu projeto.
Clique no linke leiao livro
ASCENCIO, A.F. G.; ARAÚJO, G.S.de.Estrutura de dados:a Igoritmos, aná lise da complexidadee
implementações em JAVAe C/C++. São Paulo: Pearson Prentice Ha Il, 2010.
12-13
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995
E-Book - Apostila
Quanto maioro leque de ferramentase recursos de desenvolvimento de soluções computacionais
dominados pelo desenvolvedor, maiores as possibilidades de criar soluções eficientes. Estudamos
diversos conceitos essenciais para essa evolução, dentre eles:
Refe
i li
ASCENCIO, A.F. G.; ARAÚJO, G.S. de. Estrutura de dados: algoritmos, análise da complexidadee
implementações em Javae C/C++. São Paulo: Pearson, 2010.
DEITEL, P.; DEITEL, H. Java: Como Programar. 8. ed. São Paulo: Pearson Eduacation do Brasil. 2010.
FORBELLONE, A.L. V.; EBERSPACHER, H.F. Lógica de programação:a construção de algoritmose
estruturas de dados. 3. ed. São Paulo: Prentice Hall, 2005.
13 - 13