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
Leituras Recomendadas .................................................................................................. 34
2 - Estruturas de Dados Dinâmicas
2.1 Introdução ................................................................................................................. 35
2.2 Gestão da memória dinâmica ...................................................................................... 36
2.3 Exemplos ................................................................................................................... 37
2.4 Listas ligadas .............................................................................................................. 40
2.4.1 Listas simples ...................................................................................................... 41
2.4.2 Listas biligadas .................................................................................................... 48
2.4.3 Listas skip .......................................................................................................... 54
2.5 Árvores ..................................................................................................................... 62
2.5.1 Árvore binária de pesquisa .................................................................................. 67
2.5.1.1 Inserção e remoção de elementos ................................................................. 70
2.5.1.2 Travessias .................................................................................................... 74
2.5.1.3 Travessias não recursivas ............................................................................. 77
2.5.1.4 Balanceamento ............................................................................................. 81
2.5.1.5 Visualização ................................................................................................. 84
2.5.2 Árvore de Adelson-Velskii Landis ........................................................................ 85
Exercícios ........................................................................................................................ 96
Leituras Recomendadas ................................................................................................... 98
3 - Programação Modular
3.1 Introdução ................................................................................................................. 99
3.2 Tipos abstractos de dados .......................................................................................... 102
3.3 Módulos na linguagem C ............................................................................................ 104
3.4 Abstracção de dados na linguagem C ......................................................................... 105
3.5 Exemplo de um tipo abstracto de dados ..................................................................... 107
Exercícios ........................................................................................................................ 115
Leituras Recomendadas ................................................................................................... 118
4 - Memórias
4.1 Introdução ................................................................................................................. 119
4.2 Caracterização da memória de acesso aleatório .......................................................... 120
4.3 Caracterização da memória fila ................................................................................... 121
4.4 Caracterização da memória pilha ................................................................................ 122
4.5 Caracterização da memória associativa ....................................................................... 123
4.6 Caracterização da memória fila com prioridade ........................................................... 125
4.7 Tipos de implementação ............................................................................................. 126
4.8 Implementação da memória de acesso aleatório .......................................................... 128
4.9 Implementação da memória fila ................................................................................... 129
4.10 Implementação da memória pilha .............................................................................. 130
4.11 Implementação da memória associativa ..................................................................... 131
4.12 Implementação da memória fila com prioridade ......................................................... 137
4.13 Considerações finais sobre memórias ........................................................................ 140
5 - Memórias de Acesso Aleatório
5.1 Introdução .................................................................................................................. 141
5.2 Memória de acesso aleatório concreta ......................................................................... 142
5.3 Exemplo de utilização .................................................................................................. 145
5.4 Memória de acesso aleatório configurada .................................................................... 147
5.5 Memória de acesso aleatório genérica ......................................................................... 155
Exercícios ......................................................................................................................... 160
6 - Pesquisa, Selecção e Ordenação
6.1 Introdução .................................................................................................................. 161
6.2 Complexidade algorítmica ........................................................................................... 162
6.3 Pesquisa ..................................................................................................................... 165
6.3.1 Pesquisa sequencial .............................................................................................. 166
6.3.2 Pesquisa binária ................................................................................................... 168
6.3.3 Pesquisa ternária .................................................................................................. 174
6.3.4 Pesquisa por interpolação ..................................................................................... 179
6.3.5 Pesquisa por dispersão ......................................................................................... 181
6.3.5.1 Deslocamento da posição de colocação ......................................................... 183
6.3.5.2 Encadeamento de elementos .......................................................................... 189
6.3.5.3 Considerações finais sobre a pesquisa por dispersão ...................................... 191
6.3.6 Pesquisa por indexação ........................................................................................ 193
6.4 Selecção ..................................................................................................................... 194
6.4.1 Selecção do maior valor ................................................................................... 195
6.4.2 Selecção do menor valor .................................................................................. 195
6.4.3 Selecção simultânea do maior e do menor valores ............................................. 196
6.4.4 Selecção do primeiro valor que serve ................................................................ 197
6.4.5 Selecção do melhor valor que serve .................................................................. 197
6.4.6 Selecção do pior valor que serve ...................................................................... 198
6.4.7 Exemplificação dos algoritmos de selecção ....................................................... 199
6.4.8 Selecção do k-ésimo menor valor ..................................................................... 199
6.5 Ordenação .................................................................................................................. 201
6.5.1 Ordenação por selecção ....................................................................................... 202
6.5.2 Ordenação por troca ............................................................................................ 206
6.5.3 Ordenação por inserção ........................................................................................ 212
6.5.4 Comparação dos algoritmos de ordenação simples ................................................ 216
6.6 Ordenação por fusão ................................................................................................... 217
6.7 Algoritmos de ordenação recursivos ............................................................................. 220
6.7.1 Ordenação por fusão ............................................................................................ 220
6.7.2 Ordenação por separação .................................................................................... 224
6.8 Generalização dos algoritmos de ordenação ................................................................. 228
6.9 Avaliação do desempenho dos algoritmos .................................................................... 231
Exercícios .......................................................................................................................... 233
Leituras Recomendadas ..................................................................................................... 235
7 - Filas e Pilhas
7.1 Introdução .................................................................................................................. 237
7.2 Memória fila ............................................................................................................... 238
7.2.1 Implementação estática ........................................................................................ 239
7.2.2 Implementação semiestática ................................................................................. 245
7.2.3 Implementação dinâmica ...................................................................................... 248
7.3 Memória pilha ............................................................................................................ 252
7.3.1 Implementação estática ........................................................................................ 253
7.3.2 Implementação semiestática ................................................................................. 257
7.3.3 Implementação dinâmica ...................................................................................... 260
7.4 Exemplos simples de aplicação de filas e pilhas ............................................................ 264
7.5 Exemplos complexos de aplicação de pilhas ................................................................ 269
7.6 Implementações genéricas .......................................................................................... 275
7.7 Torres de Hanói ......................................................................................................... 281
7.8 Eliminação da recursividade ........................................................................................ 284
Exercícios ........................................................................................................................ 286
Leituras Recomendadas .................................................................................................... 288
8 - Memórias Associativas
8.1 Introdução ................................................................................................................. 289
8.2 Configuração da memória .......................................................................................... 290
8.3 Memória associativa estática ...................................................................................... 292
8.4 Memória associativa semiestática ............................................................................... 299
8.5 Memória associativa dinâmica .................................................................................... 304
8.5.1 Versão dinâmica linear ........................................................................................ 304
8.5.2 Versão dinâmica logarítmica ................................................................................ 312
8.5.3 Versão dinâmica por dispersão ........................................................................... 322
8.5.4 Versão dinâmica hierárquica ............................................................................... 332
8.6 Exemplo de utilização ................................................................................................ 343
8.7 Memória associativa genérica .................................................................................... 346
Exercícios ....................................................................................................................... 351
9 - Filas com Prioridade
9.1 Introdução ................................................................................................................. 353
9.2 Fila com prioridade estática ........................................................................................ 354
9.3 Fila com prioridade dinâmica ...................................................................................... 364
9.4 Amontoados .............................................................................................................. 370
9.4.1 Operações sobre amontoados ............................................................................. 371
9.5 Fila com prioridade com amontoado ........................................................................... 374
9.6 Exemplo de utilização ................................................................................................. 377
9.7 Construção do amontoado ......................................................................................... 379
9.8 Algoritmo de ordenação Heap ................................................................................... 381
9.9 Fila com prioridade genérica ...................................................................................... 386
Exercícios ........................................................................................................................ 390
Leituras Recomendadas ................................................................................................... 391
10 - Grafos
10.1 Introdução ............................................................................................................... 393
10.2 Propriedades do grafo .............................................................................................. 394
10.3 Implementação do grafo ........................................................................................... 397
10.4 Caracterização do grafo ........................................................................................... 400
10.5 Digrafo dinâmico ...................................................................................................... 400
10.6 Travessias ................................................................................................................ 411
10.7 Ordenação topológica .............................................................................................. 421
10.8 Componentes fortemente conexas ............................................................................ 429
10.9 Caminhos mais curtos .............................................................................................. 432
10.9.1 Vértices alcançáveis .......................................................................................... 432
10.9.2 Caminho mais curto .......................................................................................... 435
10.9.3 Todos os pares de caminhos mais curtos ........................................................... 447
10.9.4 Os k caminhos mais curtos ................................................................................ 450
10.10 Árvore abrangente de custo mínimo ........................................................................ 451
10.10.1 Algoritmo de Prim ........................................................................................... 451
10.10.2 Algoritmo de Kruskal ...................................................................................... 455
10.11 Fecho transitivo ...................................................................................................... 459
Exercícios ......................................................................................................................... 461
Leituras Recomendadas .................................................................................................... 464
11 - Outros Tópicos de Programação
11.1 Uniões ..................................................................................................................... 465
11.2 Operadores bitwise ................................................................................................. 470
11.3 Sequências de ponteiros para funções ....................................................................... 473
11.4 Lista de parâmetros com comprimento variável ......................................................... 474
11.5 O pré-processador da linguagem C .......................................................................... 476
11.5.1 Macros de substituição ...................................................................................... 477
11.5.2 Compilação condicional ..................................................................................... 478
11.5.3 Asserções ......................................................................................................... 479
11.6 Compilação automática ............................................................................................. 480
11.7 Tratamento de sinais ................................................................................................. 482
11.8 Controlo de erros ..................................................................................................... 483
11.9 Conjunto disjunto ..................................................................................................... 485
11.10 Acesso indexado a ficheiros ................................................................................... 489
Exercícios ........................................................................................................................ 494
Leituras Recomendadas ................................................................................................... 494
Índice Remissivo