Esta obra tem como objectivo fornecer uma competência sólida no desenvolvimento de programas de média e elevada complexidade e um conhecimento profundo sobre estruturas de dados avançadas e algoritmos complexos, usando a linguagem de programação Java e aplicando o paradigma da programação orientada a objectos. Inclui exemplos, exercícios, programas e leituras recomendadas, com vista a facilitar a aprendizagem dos alunos.
O livro está organizado em cinco grandes temas:
•Estudo do paradigma da programação orientada a objectos na linguagem Java, apresentando os aspectos fundamentais para implementar tipos de dados abstractos concretos e genéricos paramétricos;
•Estudo das principais estruturas de dados dinâmicas: listas simplesmente ligadas (singly linked lists), listas duplamente ligadas (doubly linked lists), listas ligadas com atalhos (skip lists), árvores binárias de pesquisa (binary search trees), árvores de Adelson-Velskii Landis (AVL trees), árvores rubinegras (red black trees), árvores auto-equilibradas (splay trees) e amontoados binários (binary heaps);
•Estudo das principais classes de algoritmos: recursivos, pesquisa, selecção, ordenação, pesquisa exaustiva e numéricos;
•Estudo da implementação dos diferentes tipos de memórias: fila (Queue), pilha (Stack), associativa (Content Access Memory) e fila com prioridade (Priority Queue);
•Estudo do tipo de dados abstracto grafo/dígrafo e seus algoritmos mais importantes: travessias em largura e em profundidade, ordenação topológica, detecção de componentes fortemente conexas, caminhos mais curtos, árvore abrangente de custo mínimo, fecho transitivo, e caminhos e circuitos hamiltonianos e eulerianos.
1 - Recursividade
1.1 Introdução
1.2 Cálculo do factorial
1.3 Expansão em série de Taylor
1.4 Números de Fibonacci
1.5 Cálculo dos coeficientes binomiais
1.6 Cálculo das permutações
1.7 Cálculo do determinante de uma matriz
1.8 Torres de Hanói
1.9 Eliminação da recursividade
1.10 Recursividade com retrocesso
1.11 Questões sobre a eficiência da recursividade
Exercícios
2 - Programação Orientada a Objectos
2.1 Introdução
2.2 Tipos de dados abstractos
2.3 Classes e objectos
2.4 Classes de embrulho
2.5 A classe Complex
2.6 A classe Record
2.7 A classe Memory
2.8 Controlo de erros
2.9 Excepções
2.10 Interfaces
Exercícios
3 - Listas
3.1 Introdução
3.2 Listas simples
3.3 Listas biligadas
3.4 Listas skip
Exercícios
4 - Árvores
4.1 Introdução
4.2 Árvore binária de pesquisa
4.3 Árvore de Adelson-Velskii Landis
4.4 Árvore Rubinegra
4.5 Árvore auto-equilibrada
4.6 Amontoado binário
Exercícios
5 - Pesquisa, Selecção e Ordenação
5.1 Introdução
5.2 Complexidade algorítmica
5.3 Pesquisa
5.4 Selecção
5.5 Ordenação
5.6 Ordenação por fusão
5.7 Algoritmos de ordenação recursivos
5.8 Algoritmo de ordenação Heap
5.9 Generalização dos algoritmos de ordenação
Exercícios
6 - Memórias
6.1 Introdução
6.2 Caracterização da memória de acesso aleatório6.3 Caracterização da memória fila
6.4 Caracterização da memória pilha
6.5 Caracterização da memória associativa
6.6 Caracterização da memória fila com prioridade
6.7 Tipos de implementação
6.8 Implementação da memória de acesso aleatório
6.9 Implementação da memória fila
6.10 Implementação da memória pilha
6.11 Implementação da memória associativa
6.12 Implementação da memória fila com prioridade
6.13 Considerações finais sobre memórias
7 - Filas e Pilhas
7.1 Introdução
7.2 Memória fila
7.3 Memória pilha
7.4 Exemplos simples de aplicação de filas e pilhas
7.5 Exemplos complexos de aplicação de pilhas
7.6 Torres de Hanói
7.7 Eliminação da recursividade
7.8 Memória fila dupla
Exercícios
8 - Memórias Associativas
8.1 Introdução
8.2 Configuração da memória
8.3 Implementação estática
8.4 Implementação semiestática
8.5 Implementação dinâmica
8.6 Exemplo de utilização
Exercícios
9 - Filas com Prioridade
9.1 Introdução
9.2 Implementação estática
9.3 Implementação semiestática
9.4 Implementação dinâmica
9.5 Implementação com amontoado
9.6 Exemplo de utilização
Exercícios
10 - Grafos
10.1 Introdução
10.2 Propriedades do grafo
10.3 Implementação do grafo
10.4 Caracterização do grafo
10.5 Dígrafo dinâmico
10.6 Travessias
10.7 Ordenação topológica
10.8 Componentes fortemente conexas
10.9 Caminhos mais curtos
10.10 Árvore abrangente de custo mínimo
10.11 Fecho transitivo
10.12 Caminhos e circuitos hamiltonianos
10.13 Circuitos e caminhos eulerianos
Exercícios
11 - Outros Tópicos de Programação
11.1 Conjunto disjunto
11.2 Pesquisa exaustiva
11.3 Algoritmos numéricos
Exercícios
António Adrego da Rocha
Professor Auxiliar no Departamento de Electrónica, Telecomunicações e Informática da Universidade de Aveiro. A sua actividade de investigação, tem sido dedicada à simulação e análise de algoritmos em linguagem C, na modelação e simulação em VHDL de arquitecturas de máquinas de estados finitas hierárquicas e na sua síntese em C++. No decurso da sua actividade pedagógica, tem leccionado Programação em Pascal, Sistemas Operativos, Sistemas Digitais, Programação em VHDL, Programação em linguagem C, Programação em linguagem Java, Algoritmos e Estruturas de Dados Avançadas e Programação em Assembly. É autor dos livros Introdução à Programação Usando C, Estruturas de Dados e Algoritmos em C e co-autor de Introdução à Programação em Java, publicados pela FCA.