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.5 Árvores...............................................................................................................................................54
2.5.1 Árvore binária de pesquisa............................................................................................................59
2.5.2 Inserção e remoção de elementos..................................................................................................62
2.5.3 Travessias.....................................................................................................................................66
2.5.4 Travessias não recursivas...............................................................................................................69
2.5.5 Balanceamento de uma árvore binária de pesquisa..........................................................................73
Exercícios...................................................................................................................................................76
Leituras Recomendadas..............................................................................................................................78
3 - Programação Modular
3.1 Introdução...........................................................................................................................................79
3.2 Tipos abstractos de dados....................................................................................................................82
3.3 Módulos na linguagem C......................................................................................................................84
3.4 Abstracção de dados na linguagem C...................................................................................................85
3.5 Exemplo de um tipo abstracto de dados...............................................................................................87
Exercícios..................................................................................................................................................95
Leituras Recomendadas.............................................................................................................................96
4 - Memórias
4.1 Introdução...........................................................................................................................................97
4.2 Caracterização da memória de acesso aleatório....................................................................................98
4.3 Caracterização da memória fila.............................................................................................................99
4.4 Caracterização da memória pilha..........................................................................................................100
4.5 Caracterização da memória associativa.................................................................................................101
4.6 Tipos de implementação.......................................................................................................................103
4.7 Implementação da memória de acesso aleatório....................................................................................104
4.8 Implementação da memória fila.............................................................................................................105
4.9 Implementação da memória pilha..........................................................................................................107
4.10 Implementação da memória associativa...............................................................................................108
4.11 Considerações finais sobre memórias..................................................................................................112
5 - Memórias de Acesso Aleatório
5.1 Introdução............................................................................................................................................113
5.2 Memória de acesso aleatório concreta...................................................................................................114
5.3 Exemplo de utilização............................................................................................................................117
5.4 Memória de acesso aleatório configurada..............................................................................................119
5.5 Memória de acesso aleatório genérica...................................................................................................127
Exercícios...................................................................................................................................................132
6 - Pesquisa e Ordenação
6.1 Introdução............................................................................................................................................133
6.2 Complexidade algorítmica.....................................................................................................................134
6.3 Pesquisa...............................................................................................................................................136
6.3.1 Pesquisa sequencial........................................................................................................................138
6.3.1.1 Pesquisa sequencial.................................................................................................................138
6.3.1.2 Pesquisa do maior valor de uma sequência...............................................................................140
6.3.1.3 Pesquisa do menor valor de uma sequência..............................................................................140
6.3.1.4 Pesquisa do primeiro valor que serve.......................................................................................140
6.3.1.5 Pesquisa do melhor valor que serve.........................................................................................141
6.3.1.6 Pesquisa do pior valor que serve.............................................................................................142
6.3.1.7 Exemplificação dos algoritmos de pesquisa sequencial.............................................................142
6.3.2 Pesquisa binária.............................................................................................................................143
6.3.3 Pesquisa ternária............................................................................................................................147
6.3.4 Pesquisa por interpolação...............................................................................................................150
6.3.5 Pesquisa por dispersão...................................................................................................................152
6.3.5.1 Deslocamento da posição de colocação...................................................................................154
6.3.5.2 Encadeamento de elementos....................................................................................................159
6.3.5.3 Considerações finais sobre a pesquisa por dispersão................................................................162
6.3.6 Pesquisa por indexação..................................................................................................................164
6.4 Ordenação............................................................................................................................................165
6.4.1 Ordenação por selecção.................................................................................................................166
6.4.2 Ordenação por troca......................................................................................................................169
6.4.3 Ordenação por inserção..................................................................................................................177
6.4.4 Comparação dos algoritmos de ordenação simples..........................................................................180
6.5 Ordenação por fusão.............................................................................................................................181
6.6 Algoritmos de ordenação recursivos.......................................................................................................184
6.6.1 Ordenação por fusão......................................................................................................................184
6.6.2 Ordenação por separação..............................................................................................................186
6.7 Generalização dos algoritmos de ordenação...........................................................................................190
6.8 Avaliação do desempenho dos algoritmos..............................................................................................194
Exercícios....................................................................................................................................................196
Leituras Recomendadas...............................................................................................................................198
7 - Filas e Pilhas
7.1 Introdução............................................................................................................................................199
7.2 Memória fila.........................................................................................................................................200
7.2.1 Implementação estática.................................................................................................................201
7.2.2 Implementação semiestática..........................................................................................................207
7.2.3 Implementação dinâmica...............................................................................................................210
7.3 Memória pilha......................................................................................................................................214
7.3.1 Implementação estática.................................................................................................................215
7.3.2 Implementação semiestática..........................................................................................................219
7.3.3 Implementação dinâmica...............................................................................................................222
7.4 Exemplos simples de aplicação de filas e pilhas.....................................................................................226
7.5 Exemplos complexos de aplicação de pilhas.........................................................................................231
7.6 Implementações genéricas....................................................................................................................237
7.7 Torres de Hanói...................................................................................................................................243
7.8 Eliminação da recursividade..................................................................................................................246
Exercícios..................................................................................................................................................248
Leituras Recomendadas.............................................................................................................................250
8 - Memórias Associativas
8.1 Introdução...........................................................................................................................................251
8.2 Configuração da memória................................................................................................................... 252
8.3 Memória associativa estática................................................................................................................254
8.4 Memória associativa semiestática.........................................................................................................261
8.5 Memória associativa dinâmica..............................................................................................................266
8.5.1 Versão dinâmica linear..................................................................................................................266
8.5.2 Versão dinâmica por dispersão.....................................................................................................274
8.5.3 Versão dinâmica hierárquica.........................................................................................................284
8.6 Exemplo de utilização..........................................................................................................................295
8.7 Memória associativa genérica..............................................................................................................297
Exercícios.................................................................................................................................................303
9 - Filas com Prioridade
9.1 Introdução...........................................................................................................................................305
9.2 Caracterização da fila com prioridade...................................................................................................306
9.3 Implementação da fila com prioridade...................................................................................................306
9.4 Fila com prioridade estática..................................................................................................................308
9.5 Fila com prioridade dinâmica................................................................................................................317
9.6 Montes................................................................................................................................................323
9.6.1 Operações sobre montes..............................................................................................................324
9.7 Fila com prioridade com monte............................................................................................................327
9.8 Exemplo de utilização...........................................................................................................................331
9.9 Construção do monte...........................................................................................................................332
9.10 Algoritmo de ordenação Heap............................................................................................................334
9.11 Fila com prioridade genérica...............................................................................................................339
Exercícios...................................................................................................................................................343
Leituras Recomendadas..............................................................................................................................344
10 - Grafos
10.1 Introdução.........................................................................................................................................345
10.2 Propriedades do grafo........................................................................................................................346
10.3 Implementação do grafo.....................................................................................................................349
10.4 Caracterização do grafo.....................................................................................................................352
10.5 Digrafo dinâmico................................................................................................................................352
10.6 Travessias..........................................................................................................................................362
10.7 Ordenação topológica........................................................................................................................372
10.8 Componentes fortemente conexas......................................................................................................380
10.9 Caminhos mais curtos........................................................................................................................383
10.9.1 Vértices alcançáveis....................................................................................................................383
10.9.2 Caminho mais curto....................................................................................................................386
10.9.3 Todos os pares de caminhos mais curtos.....................................................................................397
10.9.4 Os k caminhos mais curtos..........................................................................................................400
10.10 Árvore abrangente de custo mínimo..................................................................................................401
10.10.1 Algoritmo de Prim.....................................................................................................................401
10.10.2 Algoritmo de Kruskal................................................................................................................405
10.11 Fecho transitivo................................................................................................................................409
Exercícios...................................................................................................................................................411
Leituras Recomendadas..............................................................................................................................414
11 - Outros Tópicos de Programação
11.1 Uniões...............................................................................................................................................415
11.2 Operadores bitwise...........................................................................................................................420
11.3 Sequências de ponteiros para funções.................................................................................................423
11.4 Lista de parâmetros com comprimento variável...................................................................................424
11.5 O pré-processador da linguagem C....................................................................................................426
11.5.1 Macros de substituição................................................................................................................427
11.5.2 Compilação condicional...............................................................................................................428
11.5.3 Asserções...................................................................................................................................429
11.6 Compilação automática......................................................................................................................430
11.7 Tratamento de sinais......................................................................................................................... 432
11.8 Controlo de erros..............................................................................................................................433
11.9 Conjunto disjunto..............................................................................................................................435
11.10 Acesso indexado a ficheiros.............................................................................................................439
Exercícios..................................................................................................................................................444
Leituras Recomendadas.............................................................................................................................444
Índice Remissivo