Lista de exercício - UNIBH

Prévia do material em texto

Curso: Ciência da Computação Disciplina: Análise de Algoritmo
Professor(a): Rafaela Moreira e Samara Leal 2a Lista de Exerćıcios (A1)
Aluno(a):
Turma: Data de Entrega: Valor: Nota:
27/05/19 10 pontos
1. (1 PONTO) Dado que existe necessidade de ordenar arquivos de tamanhos diver-
sos, podendo também variar o tamanho dos registros de um arquivo para outro,
apresente uma discussão sobre quais algoritmos de ordenação (Seleção, Inserção,
Shellsort e Quicksort) você escolheria diante das diversas situações posśıveis. Justi-
fique.
O método de ordenação por Seleção é um método simples e vantajoso quanto ao número de
movimentos, que é O(n). É indicado para arquivos com registros muito grandes, desde que o
tamanho do arquivo não exceda 1000 elementos.
O método de ordenação por Inserção é efeciente para arquivo com até 20 elementos. Sua im-
plementação é tão simples quanto à implementação do método de ordenação por Seleção e para
arquivos já ordenados o custo é O(n).
O método de ordenação Shellsort é muito utilizado por ser eficiente para arquivos moderados.
O pior caso desse método não é tão ruim e quando o arquivo está parcialmente ordenado o
programa executa menos comparações. Este método é uma extensão do algoritmo por inserção
e contorna o problema que há quando o menor item está mais a direita do vetor.
O método de ordenação Quicksort é o mais eficiente em várias situações, porém pode ser dif́ıcil
detectar qualquer erro de implementação.
2. (2 PONTOS) Para os seguintes algoritmos de ordenação interna: Inserção, Seleção,
Shellsort e Quicksort: Determine experimentalmente o número esperado de (i) com-
parações e (ii) movimento-de-registros para cada um dos quatro métodos de or-
denação. Utilize a classe PermutacaoRandomica abaixo para obter uma permutação
randômica dos valores de um vetor A de n elementos. Utilize arquivos de diferentes
tamanhos com chaves geradas randomicamente. Repita cada experimento algumas
vezes e obtenha a média para cada medida de complexidade. Dê sua interpretação
dos dados obtidos, comparando-os com resultados anaĺıticos.
1 public class PermutacaoRandomica {
2 public stat ic double rand0a1 (Random rand ) {
3 // u t i l i z a o tempo como semente para o metodo setSeed ( )
4 rand . setSeed ( System . cur r entT imeMi l l i s ( ) ) ;
5 // s e l e c i o n a a l ea to r i amente um nuumero no i n t e r v a l o [ 0 , 1)
6 return rand . nextDouble ( ) ;
7 }
8 public stat ic void permut ( Item v [ ] , int n) {
9 Random rand = new Random ( ) ;
10 for ( int i = n − 1 ; i > 0 ; i−−) {
11 int j = ( int ) ( ( ( double ) i ∗ rand0a1 ( rand ) ) + 1 . 0 ) ;
12 Item b = v [ i ] ; v [ i ] = v [ j ] ; v [ j ] = b ;
13 }
14 }
15 }
Tabela 1: Tabela de Comparações Ordenação - 10 execuções
Algoritmo Tipo 500 registros 2000 registros 10000 registros
Seleção Comparações 177113.0 2824983.0 7.0619901E7
Movimentações 374250.0 5997000.0 1.49985E8
Inserção Comparações 61637.0 1001011.0 2.4978124E7
Movimentações 62635.0 1005009.0 2.4998122E7
ShellSort Comparações 6168.0 33919.0 238887.0
Movimentações 8406.0 45340.0 309748.0
QuickSort Comparações 5008.0 20004.0 100000.0
Movimentações 2711.0 10087.0 57817.0
Para cada algoritmo foram realizadas dez execuções, sendo os valores apresentados na tabela
a média dessas execuções. Pode-se observar através da Tabela 1 que o algoritmo com menor
comparações e movimentações foi o QuickSort.
1 public class Exe r c i c i o2 {
2
3 /∗∗
4 ∗ @param args the command l i n e arguments
5 ∗/
6 public stat ic void main ( St r ing [ ] a rgs ) {
7
8 int tam = 500 ;
9 MeuItem v [ ] = new MeuItem [ tam ] ;
10 int n = v . l ength ;
11 Random rand = new Random( ) ;
12 Ordenacao o = new Ordenacao ( ) ;
13 int [ ] ordena ;
14 double mediaComparacao ;
15 double mediaMovimentacao ;
16 int execucao = 10 ;
17 int comparacao = 0 ;
18 int movimentacao = 0 ;
19
20 for ( int k = 0 ; k < execucao ; k++) {
21
22 for ( int i = 0 ; i < n ; i++) {
23 int r = rand . next Int (n) ;
24 v [ i ] = new MeuItem( i ) ;
25 v [ i ] . chave = r ;
26
27 }
28 ordena = o . qu ickSort (v , 0 , n−1) ;
29 comparacao += ordena [ 0 ] ;
30 movimentacao += ordena [ 1 ] ;
31
32 }
33 mediaComparacao = comparacao / execucao ;
34 mediaMovimentacao = movimentacao / execucao ;
35
36 System . out . p r i n t ( ”Media da Comparacao : ” + mediaComparacao + ”
\n” + ”Media da Movimentacao : ” + mediaMovimentacao + ”\n” )
;
37
38 }
39
40 }
41 public interface Item {
42 public int compara ( Item i t ) ;
2
43 public void alteraChave ( Object chave ) ;
44 public Object recuperaChave ( ) ;
45 }
46
47 public class MeuItem implements Item {
48 int chave ;
49 // outros componentes do r e g i s t r o
50
51 public MeuItem ( int chave ) { this . chave = chave ; }
52
53 public int compara ( Item i t ) {
54 MeuItem item = (MeuItem) i t ;
55 i f ( this . chave < item . chave ) return −1;
56 else i f ( this . chave > item . chave ) return 1 ;
57 return 0 ;
58 }
59
60 public void alteraChave ( Object chave ) {
61 I n t eg e r ch = ( In t eg e r ) chave ; this . chave = ch . intValue ( ) ;
62 }
63
64 public Object recuperaChave ( ) { return new I n t eg e r ( this . chave ) ; }
65
66 public St r ing toS t r i ng ( ) { return ”” + this . chave ; }
67
68 public void gravaArq ( RandomAccessFile arq ) throws IOException {
69 arq . w r i t e In t ( this . chave ) ;
70 }
71
72 public void leArq ( RandomAccessFile arq ) throws IOException {
73 this . chave = arq . r eadInt ( ) ;
74 }
75
76 public stat ic int tamanho ( ) { return 4 ; /∗ 4 bytes ∗/ }
77 }
78
79 public class Ordenacao {
80
81 public int [ ] s e l e c a o (MeuItem A[ ] ) {
82
83 int n = A. l ength ;
84 int min ;
85 MeuItem x ;
86 int comparacao = 0 , movimentacao = 0 ;
87
88 for ( int i = 0 ; i < n ; i++) {
89 comparacao++;
90 min = i ;
91 for ( int j = i + 1 ; j < n ; j++) {
92 comparacao++;
93 i f (A[ j ] . chave < A[min ] . chave ) {
94 comparacao++;
95 min = j ;
96 }
97 x = A[min ] ;
98 movimentacao++;
99 A[min ] = A[ i ] ;
100 movimentacao++;
101 A[ i ] = x ;
102 movimentacao++;
103 }
104 }
105 int comMov [ ] = new int [ 2 ] ;
3
106 comMov [ 0 ] = comparacao ;
107 comMov [ 1 ] = movimentacao ;
108 return comMov ;
109 }
110
111 public int [ ] i n s e r c ao (MeuItem A[ ] ) {
112
113 int n = A. l ength ;
114 int j ;
115 int movimentacao = 0 , comparacao = 0 ;
116 MeuItem x ;
117
118 for ( int i = 1 ; i < n ; i++) {
119 comparacao++;
120 x = A[ i ] ;
121 movimentacao++;
122 j = i − 1 ;
123 A[ 0 ] = x ;
124 movimentacao++;
125 while ( x . chave < A[ j ] . chave ) {
126 comparacao++;
127 A[ j + 1 ] = A[ j ] ;
128 movimentacao++;
129 j−−;
130 }
131 A[ j + 1 ] = x ;
132 movimentacao++;
133 }
134
135 int comMov [ ] = new int [ 2 ] ;
136 comMov [ 0 ] = comparacao ;
137 comMov [ 1 ] = movimentacao ;
138 return comMov ;
139
140 }
141
142 public int [ ] s h e l l S o r t (MeuItem A[ ] ) {
143
144 int n = A. l ength ;
145 int h = 1 , j ;
146 int movimentacao = 0 , comparacao = 0 ;
147 MeuItem x ;
148 do {
149 comparacao++;
150 h = h ∗ 3 + 1 ;
151 } while (h < n) ;
152 do {
153 comparacao++;
154 h /= 3 ;
155 for ( int i = h ; i < n ; i++) {
156 comparacao++;
157 x = A[ i ] ;
158 movimentacao++;
159 j = i ;
160
161 while (A[ j − h ] . chave > x . chave ) {
162 comparacao++;
163 A[ j ] = A[ j − h ] ;
164 movimentacao++;
165 j −= h ;
166 i f ( j <= h) {
167 comparacao++;
168 break ;
4
169 }
170 }
171 A[ j ] = x ;
172 movimentacao++;
173 }
174 } while (h != 1) ;
175
176 int comMov [ ] = new int [ 2 ] ;
177 comMov [ 0 ] = comparacao ;
178 comMov [ 1 ] = movimentacao ;
179 return comMov ;
180 }
181
182 int [ ] p a r t i c ao (MeuItem A[ ] , int l e f t , int r i g h t ) {
183 int i = l e f t , j = r i gh t ;
184 int movimentacao = 0 , comparacao = 0 ;
185 MeuItem tmp ;
186 MeuItem pivot = A[ ( l e f t + r i gh t ) / 2 ] ;
187
188 while ( i <= j ) {
189 comparacao++;
190 while (A[ i ] . chave < pivot . chave ){
191 comparacao++;
192 i++;
193 }
194 while (A[ j ] . chave > pivot . chave ) {
195 comparacao++;
196 j−−;
197 }
198 i f ( i <= j ) {
199 comparacao++;
200 tmp = A[ i ] ;
201 movimentacao++;
202 A[ i ] = A[ j ] ;
203 movimentacao++;
204 A[ j ] = tmp ;
205 movimentacao++;
206 i++;
207 j−−;
208 }
209 } ;
210
211 int comMov [ ] = new int [ 3 ] ;
212 comMov [ 0 ] = comparacao ;
213 comMov [ 1 ] = movimentacao ;
214 comMov [ 2 ] = i ;
215 return comMov ;
216
217 }
218
219 public int [ ] qu i ckSort (MeuItem A[ ] , int l e f t , int r i g h t ) {
220 int [ ] r = pa r t i c ao (A, l e f t , r i g h t ) ;
221 int index = r [ 2 ] ;
222
223 i f ( l e f t < index − 1) {
224 quickSort (A, l e f t , index − 1) ;
225 }
226 i f ( index < r i g h t ) {
227 quickSort (A, index , r i g h t ) ;
228 }
229
230 int comMov [ ] = new int [ 2 ] ;
5
231 comMov [ 0 ] = r [ 0 ] ;
232 comMov [ 1 ] = r [ 1 ] ;
233 return comMov ;
234 }
235 }
3. (1 PONTO) Considere as técnicas de pesquisa sequencial, binária e a pesquisa
baseada em hashing.
(a) Descreva as vantagens e desvantagens de cada uma das técnicas acima, colo-
cando em que situações você usaria cada uma delas.
Pesquisa Sequencial: é a técnica mais simples, onde a partir do primeiro registro, pesquisa
seqüencialmente até encontrar a chave procurada. Cada registro contém um campo chave
que identifica o registro. Vantagens: é um método simples, o arranjo não precisa estar
ordenado. Desvantagens: se o elemento estiver na última posição ou não for encontrado,
faz n comparações e não é indicado para arranjos grandes. Usado para arranjos com no
máximo 25 registros e não ordenado.
Pesquisa Binária: registros devem estar ordenados. Compara a chave com o registro que
está na posição do meio da tabela. Se a chave é menor, então o registro procurado está na
primeira metade da tabela, se a chave é maior, então o registro procurado está na segunda
metade da tabela. O processo é repetido até que a chave seja encontrada. Vantagens: mais
eficiente, pois a busca utiliza a técnica de divisão e conquista, sendo a comparação log n.
Desvantagens: alto custo para manter a tabela ordenada, não deve ser usada para tabelas
muito dinâmicas. Usado com registros ordenados e não dinâmicos.
Pesquisa em Hashing: os registros armazenados em uma tabela são diretamente en-
dereçados a par- tir de uma transformação aritmética sobre a chave de pesquisa. Primeiro
é necessário computar o valor da função de hashing, a qual transforma a chave de pesquisa
em um endereço da tabela, depois é necessário existir um método para lidar com colisões,
pois duas ou mais chaves podem ser transformadas em um mesmo endereço de tabela. Van-
tagens: simples, eficiente para tamanhos grandes, escalabilidade da tabela. Desvantagens:
tratamento de colisões, tempo médio de acesso é ótimo somente em uma faixa, dependência
da escolha da função.
(b) Dê a ordem do pior caso e do caso esperado de tempo de execução para cada
método.
Pesquisa Sequencial:
Pior caso: C(n) = n Caso esperado: C(n) = (n + 1)/2
Pesquisa Binária:
Pior caso: C(n) = O(n) Caso esperado: C(n) = O((log n)
Pesquisa em Hashing:
Pior caso: C(n) = O(n) Caso esperado: C(n) = O(1)
4. (2 PONTOS) Árvore Binária de Pesquisa
(a) (1 PONTO) Desenhe a árvore binária de pesquisa que resulta da inserção su-
cessiva das chaves Q U E S T A O F C I L em uma árvore inicialmente vazia.
6
(b) (1 PONTO) Desenhe as árvores resultantes das retiradas dos elementos E depois
U da a árvore obtida no item anterior.
7
8
9
10
5. (2 PONTOS) Substitua XXXXXXXXXXXX pelas 12 primeiras letras do seu nome,
desprezando brancos e letras repetidas, nas duas partes desta questão. Para quem
não tiver doze letras diferentes no nome, completar com as letras PQRSTUVWXYZ,
nesta ordem, até completar 12 letras. Por exemplo, eu deveria escolher RAFELPIS-
CUZM. A segunda letra A de RAFAELA não entra porque ela já apareceu antes,
e assim por diante. Desenhe o conteúdo da tabela hash resultante da inserção de
registros com as chaves XXXXXXXXXXXX, nesta ordem, em uma tabela inicial-
mente vazia de tamanho 7 (sete), usando listas encadeadas. Use a função hash: h(k)
= k % 7 para a k-ésima letra do alfabeto.
LETRA R A F E L P I S C U Z M
ASCII 82 65 70 69 76 80 73 83 67 85 90 77
Tabela 2: Código ASCII das letras do alfabeto
6. (2 PONTOS) Árvore Patŕıcia
Considere o seguinte trecho do poema “Quadrilha”, de Carlos Drummond de An-
drade: “João amava Teresa que amava Raimundo que amava Maria que amava
Joaquim que amava Lili que não amava ninguém.” Construa uma árvore Patricia
para indexar o texto acima. Considere a seguinte codificação para as palavras do
texto:
João 01001011 Maria 01100101
amava 00011101 Joaquim 00101110
Teresa 11101011 Lili 01010011
que 10100101 não 10011100
Raimundo 11011010 ninguém 10110010
11
12