1 - Recursividade
1.1 Introdução......................................................................................................... 1
1.2 Cálculo do factorial............................................................................................ 3
1.3 Expansão em série de Taylor.............................................................................. 4
1.4 Números de Fibonacci........................................................................................ 7
1.5 Cálculo dos coeficientes binomiais....................................................................... 9
1.6 Cálculo das permutações.................................................................................. 12
1.7 Cálculo do determinante de uma matriz.............................................................. 14
1.8 Torres de Hanói............................................................................................... 16
1.9 Eliminação da recursividade.............................................................................. 21
1.10 Recursividade com retrocesso......................................................................... 23
1.11 Questões sobre a eficiência da recursividade.................................................... 30
Exercícios.............................................................................................................. 31
2 - Programação Orientada a Objectos
2.1 Introdução....................................................................................................... 35
2.2 Tipos de dados abstractos................................................................................. 40
2.3 Classes e objectos............................................................................................ 41
2.4 Classes de embrulho......................................................................................... 42
2.5 A classe Complex............................................................................................ 43
2.5.1 Construtores.............................................................................................. 44
2.5.2 Método de cópia........................................................................................ 47
2.5.3 Métodos selectores e modificadores............................................................ 49
2.5.4 Métodos comparadores.............................................................................. 50
2.5.5 Método de escrita...................................................................................... 52
2.5.6 Métodos operadores................................................................................... 52
2.5.7 Implementação da classe Complex.............................................................. 53
2.5.8 Métodos privados....................................................................................... 55
2.5.9 Programa de simulação.............................................................................. 56
2.6 A classe Record.............................................................................................. 57
2.6.1 A classe Time........................................................................................... 57
2.6.2 Implementação da classe Record............................................................... 60
2.7 A classe Memory............................................................................................ 67
2.7.1 Implementação concreta............................................................................ 68
2.7.2 Comunicação com o exterior...................................................................... 70
2.7.3 Implementação da classe IntMemory.......................................................... 72
2.7.4 Programa de simulação da memória de inteiros............................................ 73
2.7.5 Generalização da memória.......................................................................... 76
2.7.6 Programa de simulação da memória genérica............................................... 79
2.8 Controlo de erros.............................................................................................. 85
2.8.1 Programação defensiva.............................................................................. 85
2.8.1.1 Controlo centralizado de erro................................................................ 86
2.8.1.2 Nova implementação da classe Complex............................................... 88
2.8.1.3 Programa de simulação........................................................................ 91
2.8.2 Programação por contrato.......................................................................... 92
2.8.2.1 Asserções........................................................................................... 93
2.8.2.2 Nova implementação da classe Memory................................................ 94
2.9 Excepções........................................................................................................ 96
2.9.1 Implementação final da classe Memory.................................................... 99
2.9.2 Programa de simulação.......................................................................... 101
2.9.3 Implementação da classe Complex com excepções.................................. 105
2.9.4 Conclusões............................................................................................ 107
2.10 Interfaces...................................................................................................... 107
Exercícios.............................................................................................................. 110
Leituras Recomendadas.......................................................................................... 112
3 - Listas
3.1 Introdução....................................................................................................... 113
3.2 Listas simples.................................................................................................. 116
3.2.1 Algoritmos básicos.................................................................................... 117
3.2.2 Implementação genérica............................................................................ 122
3.2.3 Considerações finais sobre listas simples..................................................... 124
3.3 Listas biligadas................................................................................................ 125
3.3.1 Algoritmos básicos.................................................................................... 126
3.3.2 Implementação genérica............................................................................ 131
3.3.3 Considerações finais sobre listas biligadas................................................... 133
3.4 Listas skip...................................................................................................... 133
3.4.1 Algoritmos básicos.................................................................................... 136
3.4.2 Implementação genérica............................................................................ 142
3.4.3 Considerações finais sobre listas skip......................................................... 144
Exercícios.............................................................................................................. 145
Leituras Recomendadas......................................................................................... 147
4 - Árvores
4.1 Introdução...................................................................................................... 149
4.2 Árvore binária de pesquisa............................................................................... 152
4.2.1 Algoritmos básicos.................................................................................... 154
4.2.2 Algoritmos de pesquisa e de selecção......................................................... 156
4.2.3 Inserção e remoção de elementos............................................................... 159
4.2.4 Travessias................................................................................................ 164
4.2.5 Travessias não recursivas.......................................................................... 168
4.2.6 Balanceamento......................................................................................... 173
4.2.7 Implementação genérica............................................................................ 175
4.2.8 Implementação alternativa......................................................................... 180
4.3 Árvore de Adelson-Velskii Landis.................................................................... 185
4.3.1 Inserção de elementos............................................................................... 187
4.3.2 Remoção de elementos.............................................................................. 196
4.3.3 Implementação genérica............................................................................ 198
4.4 Árvore rubinegra............................................................................................. 203
4.4.1 Inserção de elementos............................................................................... 205
4.4.2 Remoção de elementos.............................................................................. 212
4.4.3 Implementação genérica............................................................................ 217
4.5 Árvore auto-equilibrada.................................................................................... 221
4.5.1 Abordagem recursiva (bottom-up)............................................................. 223
4.5.2 Abordagem repetitiva (top-down).............................................................. 223
4.5.3 Implementação genérica............................................................................ 230
4.6 Amontoado binário........................................................................................... 233
4.6.1 Inserção e remoção de elementos............................................................... 234
4.6.2 Promoção e despromoção de elementos...................................................... 238
4.6.3 Considerações finais sobre amontoados....................................................... 241
4.6.4 Implementação genérica............................................................................. 242
Exercícios............................................................................................................... 245
Leituras Recomendadas.......................................................................................... 248
5 - Pesquisa, Selecção e Ordenação
5.1 Introdução....................................................................................................... 249
5.2 Complexidade algorítmica................................................................................. 250
5.3 Pesquisa.......................................................................................................... 253
5.3.1 Pesquisa sequencial.................................................................................... 254
5.3.2 Pesquisa binária......................................................................................... 256
5.3.3 Pesquisa ternária........................................................................................ 262
5.3.4 Pesquisa por interpolação............................................................................ 267
5.3.5 Pesquisa por dispersão................................................................................ 269
5.3.5.1 Deslocamento da posição de colocação................................................. 271
5.3.5.2 Encadeamento de elementos................................................................. 279
5.3.5.3 Considerações finais sobre a pesquisa por dispersão............................... 285
5.3.6 Pesquisa por indexação............................................................................... 287
5.4 Selecção........................................................................................................... 288
5.4.1 Selecção do maior valor.............................................................................. 288
5.4.2 Selecção do menor valor............................................................................. 289
5.4.3 Selecção do primeiro valor que serve........................................................... 289
5.4.4 Selecção do melhor valor que serve............................................................. 290
5.4.5 Selecção do pior valor que serve................................................................. 290
5.4.6 Exemplificação dos algoritmos de selecção.................................................. 291
5.4.7 Selecção do k-ésimo menor valor................................................................ 292
5.5 Ordenação....................................................................................................... 293
5.5.1 Ordenação por selecção............................................................................. 294
5.5.2 Ordenação por troca.................................................................................. 297
5.5.3 Ordenação por inserção............................................................................. 304
5.5.4 Comparação dos algoritmos de ordenação................................................... 309
5.6 Ordenação por fusão........................................................................................ 310
5.7 Algoritmos de ordenação recursivos.................................................................. 313
5.7.1 Ordenação por fusão.................................................................................. 313
5.7.2 Ordenação por separação.......................................................................... 317
5.8 Algoritmo de ordenação Heap.......................................................................... 321
5.8.1 Construção do amontoado.......................................................................... 321
5.8.2 Implementação do algoritmo....................................................................... 323
5.9 Generalização dos algoritmos de ordenação....................................................... 328
Exercícios.............................................................................................................. 331
Leituras Recomendadas.......................................................................................... 332
6 - Memórias
6.1 Introdução....................................................................................................... 333
6.2 Caracterização da memória de acesso aleatório................................................. 334
6.3 Caracterização da memória fila......................................................................... 335
6.4 Caracterização da memória pilha....................................................................... 336
6.5 Caracterização da memória associativa............................................................. 337
6.6 Caracterização da memória fila com prioridade.................................................. 338
6.7 Tipos de implementação................................................................................... 340
6.8 Implementação da memória de acesso aleatório................................................. 341
6.9 Implementação da memória fila........................................................................ 342
6.10 Implementação da memória pilha.................................................................... 344
6.11 Implementação da memória associativa........................................................... 345
6.12 Implementação da memória fila com prioridade................................................ 351
6.13 Considerações finais sobre memórias.............................................................. 354
7 - Filas e Pilhas
7.1 Introdução...................................................................................................... 355
7.2 Memória fila................................................................................................... 356
7.2.1 Implementação estática............................................................................. 357
7.2.2 Implementação semiestática...................................................................... 362
7.2.3 Implementação dinâmica........................................................................... 364
7.3 Memória pilha................................................................................................. 367
7.3.1 Implementação estática............................................................................. 368
7.3.2 Implementação semiestática...................................................................... 371
7.3.3 Implementação dinâmica........................................................................... 372
7.4 Exemplos simples de aplicação de filas e pilhas................................................. 375
7.5 Exemplos complexos de aplicação de pilhas...................................................... 379
7.6 Torres de Hanói.............................................................................................. 385
7.7 Eliminação da recursividade............................................................................. 388
7.8 Memória fila dupla.......................................................................................... 390
Exercícios............................................................................................................. 390
8 - Memórias Associativas
8.1 Introdução..................................................................................................... 393
8.2 Configuração da memória............................................................................... 394
8.3 Implementação estática.................................................................................. 395
8.4 Implementação semiestática............................................................................ 401
8.5 Implementação dinâmica................................................................................. 404
8.5.1 Versão dinâmica linear............................................................................. 405
8.5.2 Versão dinâmica logarítmica..................................................................... 411
8.5.3 Versão dinâmica por dispersão................................................................. 418
8.5.4 Versão dinâmica hierárquica.................................................................... 426
8.6 Exemplo de utilização..................................................................................... 435
Exercícios............................................................................................................ 439
9 - Filas com Prioridade
9.1 Introdução..................................................................................................... 441
9.2 Implementação estática.................................................................................. 443
9.3 Implementação semiestática........................................................................... 449
9.4 Implementação dinâmica................................................................................ 451
9.5 Implementação com amontoado...................................................................... 456
9.6 Exemplo de utilização..................................................................................... 458
Exercícios............................................................................................................ 460
10 - Grafos
10.1 Introdução................................................................................................... 461
10.2 Propriedades do grafo.................................................................................. 462
10.3 Implementação do grafo............................................................................... 466
10.4 Caracterização do grafo............................................................................... 468
10.5 Dígrafo dinâmico......................................................................................... 469
10.6 Travessias................................................................................................... 478
10.7 Ordenação topológica................................................................................... 488
10.8 Componentes fortemente conexas................................................................. 496
10.9 Caminhos mais curtos................................................................................... 499
10.9.1 Vértices alcançáveis.............................................................................. 499
10.9.2 Caminho mais curto............................................................................... 501
10.9.3 Todos os pares de caminhos mais curtos................................................. 514
10.9.4 Os k caminhos mais curtos..................................................................... 517
10.10 Árvore abrangente de custo mínimo............................................................. 518
10.10.1 Algoritmo de Prim................................................................................ 518
10.10.2 Algoritmo de Kruskal........................................................................... 523
10.11 Fecho transitivo.......................................................................................... 527
10.12 Caminhos e circuitos hamiltonianos.............................................................. 528
10.13 Circuitos e caminhos eulerianos................................................................... 532
Exercícios............................................................................................................ 539
Leituras Recomendadas........................................................................................ 541
11 - Outros Tópicos de Programação
11.1 Conjunto disjunto.......................................................................................... 543
11.2 Pesquisa exaustiva....................................................................................... 546
11.2.1 Quadrado mágico.................................................................................. 546
11.2.2 Subconjuntos de um conjunto.................................................................. 549
11.2.3 Carregamento optimizado da mochila...................................................... 551
11.3 Algoritmos numéricos................................................................................... 553
11.3.1 Cálculo da potência................................................................................ 554
11.3.2 Avaliação do polinómio........................................................................... 554
11.3.3 Multiplicação de matrizes....................................................................... 555
Exercícios............................................................................................................ 560
Índice Remissivo