1 - Recursividade
1.1 Introdução ............................................................................. 1
1.2 Cálculo do fatorial .................................................................... 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
Leituras Recomendadas ...................................................................... 34
2 - Programação modular
2.1 Introdução ............................................................................. 35
2.2 Tipos de dados abstratos ............................................................... 38
2.3 Módulos na linguagem C ................................................................. 40
2.4 Abstração de dados na linguagem C ...................................................... 42
2.5 Gestão da memória dinâmica ............................................................. 43
2.6 Controlo de erros ...................................................................... 46
2.6.1 Programação defensiva .............................................................. 46
2.6.1.1 Controlo centralizado de erro .................................................. 47
2.6.1.2 Devolução sistemática de um código de erro pelas operações ..................... 47
2.6.2 Programação por contrato ........................................................... 48
2.6.2.1 Asserções ...................................................................... 49
2.6.3 Conclusões ......................................................................... 50
2.7 Exemplo de um tipo de dados elemento matemático ........................................ 50
2.8 Exemplo de um tipo de dados memória .................................................... 58
2.8.1 Implementação concreta ............................................................. 58
2.8.2 Implementação configurada .......................................................... 65
2.8.2.1 Elemento constituinte da memória ............................................... 66
2.8.2.2 Implementação da memória ....................................................... 69
2.8.2.3 Exemplo de utilização .......................................................... 73
2.8.3 Implementação genérica ............................................................. 75
Exercícios ................................................................................. 80
Leituras Recomendadas ...................................................................... 83
3 - Listas
3.1 Introdução ............................................................................. 85
3.2 Listas simples ......................................................................... 87
3.2.1 Algoritmos básicos ................................................................. 89
3.2.2 Simulação das operações básicas da lista ........................................... 95
3.2.3 Considerações finais sobre listas simples .......................................... 96
3.3 Listas biligadas ....................................................................... 96
3.4 Listas skip ............................................................................ 102
Exercícios ................................................................................. 111
Leituras Recomendadas ...................................................................... 114
4 - Árvores
4.1 Introdução ............................................................................. 115
4.2 Árvore binária de pesquisa ............................................................. 118
4.2.1 Algoritmos básicos ................................................................. 120
4.2.2 Algoritmos de pesquisa e de seleção ................................................ 121
4.2.3 Inserção e remoção de elementos .................................................... 124
4.2.4 Travessias ......................................................................... 130
4.2.5 Travessias não recursivas .......................................................... 132
4.2.6 Balanceamento ...................................................................... 138
4.2.7 Visualização ....................................................................... 140
4.2.8 Simulação da árvore binária de pesquisa ............................................ 142
4.2.9 Implementação alternativa .......................................................... 143
4.3 Árvore de Adelson-Velskii Landis ....................................................... 147
4.3.1 Inserção de elementos .............................................................. 149
4.3.2 Remoção de elementos ............................................................... 158
4.4 Árvore rubinegra ....................................................................... 160
4.4.1 Inserção de elementos .............................................................. 163
4.4.2 Remoção de elementos ............................................................... 169
4.5 Árvore autoequilibrada ................................................................. 175
4.5.1 Estrutura do nó .................................................................... 176
4.5.2 Abordagem recursiva (bottom-up) .................................................... 177
4.5.3 Abordagem repetitiva (top-down) .................................................... 177
4.6 Amontoado binário ...................................................................... 185
4.6.1 Inserção e remoção de elementos .................................................... 186
4.6.2 Promoção e despromoção de elementos ................................................ 189
4.6.3 Considerações finais sobre amontoados .............................................. 192
4.6.4 Simulação do amontoado ............................................................. 193
Exercícios ................................................................................. 194
Leituras Recomendadas ...................................................................... 198
5 - Pesquisa, Seleção e Ordenação
5.1 Introdução ............................................................................. 199
5.2 Complexidade algorítmica ............................................................... 200
5.3 Pesquisa ............................................................................... 203
5.3.1 Pesquisa sequencial ................................................................ 204
5.3.2 Pesquisa binária ................................................................... 206
5.3.3 Pesquisa ternária .................................................................. 212
5.3.4 Pesquisa por interpolação .......................................................... 217
5.3.5 Pesquisa por dispersão ............................................................. 219
5.3.5.1 Deslocamento da posição de colocação ........................................... 221
5.3.5.2 Encadeamento de elementos ...................................................... 226
5.3.5.3 Considerações finais sobre a pesquisa por dispersão ............................ 229
5.3.6 Pesquisa por indexação ............................................................. 231
5.4 Seleção ................................................................................ 232
5.4.1 Seleção do maior valor ............................................................. 233
5.4.2 Seleção do menor valor ............................................................. 234
5.4.3 Seleção simultânea do maior e do menor valores ..................................... 234
5.4.4 Seleção do primeiro valor que serve ................................................ 235
5.4.5 Seleção do melhor valor que serve .................................................. 236
5.4.6 Seleção do pior valor que serve .................................................... 236
5.4.7 Exemplificação dos algoritmos de seleção ........................................... 237
5.4.8 Selecção do K-ésimo menor valor .................................................... 238
5.5 Ordenação .............................................................................. 239
5.5.1 Ordenação por seleção .............................................................. 240
5.5.2 Ordenação por troca ................................................................ 243
5.5.3 Ordenação por inserção ............................................................. 250
5.5.4 Comparação dos algoritmos de ordenação simples ..................................... 255
5.6 Ordenação por fusão .................................................................... 256
5.7 Algoritmos de ordenação recursivos ..................................................... 259
5.7.1 Ordenação por fusão ................................................................ 259
5.7.2 Ordenação por separação ............................................................ 263
5.8 Algoritmo de ordenação Heap ............................................................ 267
5.8.1 Construção do amontoado ............................................................ 267
5.8.2 Implementação do algoritmo ......................................................... 269
5.9 Generalização dos algoritmos de ordenação .............................................. 274
5.10 Avaliação do desempenho dos algoritmos ................................................ 277
Exercícios ................................................................................. 279
Leituras Recomendadas ...................................................................... 282
6 - Memórias
6.1 Introdução ............................................................................. 283
6.2 Caracterização da memória de acesso aleatório .......................................... 284
6.3 Caracterização da memória fila ......................................................... 285
6.4 Caracterização da memória pilha ........................................................ 287
6.5 Caracterização da memória associativa .................................................. 288
6.6 Caracterização da memória fila com prioridade .......................................... 290
6.7 Tipos de implementação ................................................................. 291
6.8 Implementação da memória de acesso aleatório ........................................... 293
6.9 Implementação da memória fila .......................................................... 294
6.10 Implementação da memória pilha ........................................................ 295
6.11 Implementação da memória associativa .................................................. 297
6.12 Implementação da memória fila com prioridade .......................................... 302
6.13 Considerações finais sobre memórias ................................................... 305
7 - Filas e Pilhas
7.1 Introdução ............................................................................. 307
7.2 Memória fila ........................................................................... 308
7.2.1 Implementação estática ............................................................. 309
7.2.2 Implementação semiestática ......................................................... 316
7.2.3 Implementação dinâmica ............................................................. 318
7.3 Memória pilha .......................................................................... 322
7.3.1 Implementação estática ............................................................. 324
7.3.2 Implementação semiestática ......................................................... 328
7.3.3 Implementação dinâmica ............................................................. 330
7.4 Exemplos simples de aplicação de filas e pilhas ........................................ 334
7.5 Exemplos complexos de aplicação de pilhas .............................................. 340
7.6 Implementações genéricas ............................................................... 345
7.7 Torres de Hanói ........................................................................ 351
7.8 Eliminação da recursividade ............................................................ 354
7.9 Memória fila dupla ..................................................................... 356
Exercícios ................................................................................. 357
Leituras Recomendadas ...................................................................... 358
8 - Memórias Associativas
8.1 Introdução ............................................................................. 359
8.2 Configuração da memória ................................................................ 360
8.3 Memória associativa estática ........................................................... 362
8.4 Memória associativa semiestática ....................................................... 370
8.5 Memória associativa dinâmica ........................................................... 374
8.5.1 Versão dinâmica linear ............................................................. 374
8.5.2 Versão dinâmica logarítmica ........................................................ 382
8.5.3 Versão dinâmica por dispersão ...................................................... 392
8.5.4 Versão dinâmica hierárquica ........................................................ 401
8.6 Exemplo de utilização .................................................................. 411
8.7 Memória associativa genérica ........................................................... 414
Exercícios ................................................................................. 419
9 - Filas com Prioridade
9.1 Introdução ............................................................................. 421
9.2 Fila com prioridade estática ........................................................... 423
9.3 Fila com prioridade dinâmica ........................................................... 432
9.4 Implementação com amontoado ............................................................ 439
9.5 Exemplo de utilização .................................................................. 443
9.6 Fila com prioridade genérica ........................................................... 444
Exercícios ................................................................................. 449
Leituras Recomendadas ...................................................................... 450
10 - Grafos
10.1 Introdução ............................................................................ 451
10.2 Propriedades do grafo ................................................................. 452
10.3 Implementação do grafo ................................................................ 456
10.4 Caracterização do grafo ............................................................... 458
10.5 Dígrafo/Grafo dinâmico ................................................................ 459
10.6 Travessias ............................................................................ 471
10.7 Ordenação topológica .................................................................. 481
10.8 Componentes fortemente conexas ........................................................ 489
10.9 Caminhos mais curtos .................................................................. 492
10.9.1 Vértices alcançáveis .............................................................. 492
10.9.2 Caminho mais curto ................................................................ 495
10.9.3 Todos os pares de caminhos mais curtos ............................................ 507
10.9.4 Os K caminhos mais curtos ......................................................... 510
10.10 Árvore abrangente de custo mínimo .................................................... 511
10.10.1 Algoritmo de Prim ................................................................ 511
10.10.2 Algoritmo de Kruskal ............................................................. 516
10.11 Fecho transitivo ..................................................................... 520
10.12 Caminhos e circuitos hamiltonianos ................................................... 521
10.13 Circuitos e caminhos eulerianos ...................................................... 525
Exercícios ................................................................................. 533
Leituras Recomendadas ...................................................................... 536
11 - Outros Tópicos de Programação
11.1 Uniões ................................................................................ 537
11.2 Operadores bitwise .................................................................... 542
11.3 Sequências de ponteiros para funções .................................................. 545
11.4 Lista de parâmetros com comprimento variável .......................................... 546
11.5 Pré-processador da linguagem C ........................................................ 548
11.5.1 Macros de substituição ............................................................ 549
11.5.2 Compilação condicional ............................................................ 550
11.5.3 Asserções ......................................................................... 551
11.6 Compilação automática ................................................................. 552
11.7 Tratamento de sinais .................................................................. 554
11.8 Controlo de erros ..................................................................... 555
11.9 Conjunto disjunto ..................................................................... 557
11.10 Acesso indexado a ficheiros .......................................................... 560
11.11 Pesquisa exaustiva ................................................................... 565
11.11.1 Quadrado mágico .................................................................. 565
11.11.2 Subconjuntos de um conjunto ...................................................... 570
11.11.3 Carregamento otimizado da mochila ................................................ 574
11.12 Algoritmos numéricos ................................................................. 576
11.12.1 Cálculo da potência .............................................................. 576
11.12.2 Avaliação do polinómio ........................................................... 577
11.12.3 Multiplicação de polinómios ...................................................... 578
11.12.4 Multiplicação de matrizes ........................................................ 580
Exercícios ................................................................................. 585
Leituras Recomendadas ...................................................................... 586
Glossário de Termos - Português Europeu/Português do Brasil
Índice Remissivo