Aula Prática #05 - Tipos Abstractos de Dados
(semana de 18/03 a 22/03)
Exercício 1) TAD Conjunto - exemplo de implementação e utilização
- Introdução e Conceitos Associados.
Nas aulas teóricas da semana passada (ver slides "3 - Tipos Abstractos de Dados") foram explicado alguns conceitos que deve rever caso não tenha ido às aulas. Em particular, num "resumo resumido":
- Interface: definição dos métodos de um TAD (em abstracto, sem indicar implementação)
- Implementação de um interface: uma classe X que implementa um interface Y é declarada como class X implements Y e tem de implementar todos os métodos definidos no interface.
- TAD Conjunto: um tipo abstracto de dados que implementa um conjunto (foi usado como exemplo um conjunto de números inteiros e operações como adicionar, remover ou verificar se um número está contido no conjunto)
- Testando a implementação dada como exemplo (usando um array como lista).
A página desta unidade curricular contém secção de exemplos de código. Em particular, deve ir à parte do TAD IntSet, fazer download dos ficheiros IntSet.java, ArrayListIntSet.java e TestSet.java, compilar e executar a classe TestSet.
Esta implementação foi explicada na aula teórica. Certifique-se que percebe toda a implementação e o output obtido na execução.
- Submetendo no Mooshak.
Usando o código disponibilizado como base, submeta e resolva com sucesso no Mooshak o problema [ED184] TAD Conjunto (IntSet) (Volume 2 - TADs)
Dicas:
- Deve submeter um ficheiro apenas com a classe que implementa o interface IntSet
- O código está quase pronto a submeter, sendo apenas necessário mudar o nome da classe (qual o nome pedido no enunciado?) e criar um construtor padrão (sabendo que no máximo vão existir 100 números diferentes no input dado, o que pode fazer?).
- Descobrindo a quantidade de números únicos.
Use a implementação de conjunto para descobrir a quantidade de números únicos (não repetidos) no input. O algoritmo a usar deverá ser algo como:
- Criar um conjunto s vazio
- Enquanto houver um número x para ler, adicionar x ao conjunto s
- Escrever a quantidade de elementos em s
Teste o seu programa com os seguintes ficheiros N.txt, cada um contendo N números entre 1 e N (se precisar, pode parar a execução com ctrl + C):
Meça o tempo de execução para cada um destes casos de teste. Por exemplo, para medir o tempo para o caso de 1000 números execute, e supondo que o seu programa está numa classe Unique, pode fazer o seguinte:
$ time java Unique < 1000.txt
Como foi crescendo o tempo? Esperava que demorasse mais ou que demorasse menos?
Exercício 2) Um TAD conjunto mais eficiente
O objectivo deste exercício é criar uma nova implementação do TAD conjunto que seja mais eficiente do ponto de vista do tempo de execução. Deverá por isso criar uma nova classe que implemente o interface IntSet:
class BooleanArrayIntSet implements IntSet {
// Deverá colocar aqui os atributos e métodos
}
A ideia é usar um array de valores booleanos para dizer se um número está ou não num conjunto:
- Manter um array isElem[] de valores booleanos (verdadeiro ou falso)
- isElem[i] diz-nos se o número i está ou não no conjunto
- O tamanho do array determina o tamanho do número máximo
- Manter numa outra variável size o número de elementos
Por exemplo, o conjunto {1,5,7} seria representado por:
- isElem[]={F,T,F,F,F,T,F,T,F,F,F} e size=3
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
- Criando o código.
Crie um ficheiro BooleanArrayIntSet.java implementando a ideia para o TAD conjunto atrás descrita (como poderá ser um construtor da classe?). Teste os seus métodos (usando por exemplo a classe TestSet que já tem definida - tem de mudar a declaração da variável s para passar a usar esta nova implementação)
- Verificação da eficiência.
Modifique o código anterior para verificar a quantidade de números únicos para passar a usar a sua nova implementação de IntSet. Teste o funcionamento, medindo o tempo de execução. É melhor ou pior que a anterior implementação? Deverá conseguir agora executar em muito menos tempo o caso de 1 milhão de números.
- Vantagens e desvantagens.
Sabendo que esta nova implementação é mais eficiente na inserção de números, que outra vantagens e desvantagens vê em relação à anterior implementação de uma lista de números usando arrays?
- Submissão no Mooshak.
Para uma verificação final de que o seu TAD foi bem implementado, submeta e resolva com sucesso (novamente) no Mooshak o problema [ED184] TAD Conjunto (IntSet) (Volume 2 - TADs), desta vez com a sua nova implementação de arrays de booleanos.
Exercício 3) TAD BigNumber - Números arbitrariamente grandes
Os tipos de dados primitivos do Java têm limites para os números que conseguem representar. O objectivo deste exercício é a implementação de um TAD destinado a representar números inteiros positivos arbitrariamente grandes, ou seja, com suporte para o número de dígitos que desejarmos (o Java já contém uma classe para representar números com precisão arbitrária, mas aqui a ideia é serem vocês a implementarem uma).
Deve por isso submeter e resolver com sucesso no Mooshak o problema [ED185] TAD Números Arbitrariamente Grandes (BigNumber) (Volume 2 - TADs)
Dicas:
Armazenar o número
Uma sugestão (simples) é usar um array contendo em cada posição um dígito, o que lhe vai simplificar a vida depois para somar e multiplicar. Deve colocar o digito menos significativo na posição zero e por ai adiante.
Por exemplo, o número "23454760" ficaria guardado num array como o que se segue:
Se optar pelo array de digitos, pode simplesmente declará-lo com o tamanho máximo permitido (1000 dígitos) e guardar o número de dígitos significativos actualmente armazenados numa outra variável size, por exemplo.
Para converter um caracter no dígito correspondente, basta subtrair-lhe '0' (por exemplo, char c = '2'; int d = c - '0'; colocaria um 2 no inteiro d).
Somar dois números
Ainda se recordam como somar manualmente dois números? Exemplo:
123
+ 789
-----
912
Multiplicar dois números
Ainda se recordam como multiplicar manualmente dois números? Exemplo:
123
x 789
------
1107
984
861
------
97047
Exercícios extra para consolidação de conhecimentos
- Algumas ideias para melhorar a implementação ArrayListIntSet:
- Corrigir a limitação do número máximo de elementos: no caso de não haver espaço criar novo array pelo menos com o dobro do tamanho necessário e copiar para lá os elementos do conjunto
- Acrescente métodos ao TAD IntSet para calcular a união e a intersecção de dois conjuntos, e implemente-os.
- Crie um TAD IntMultiSet (incluindo o interface e pelo menos uma implementação possível) para representar conjuntos onde podem existir várias cópias do mesmo elemento. Faça as alterações necessárias nos vários métodos que tinha e imagine novos métodos possíveis (ex: um método para devolver a quantidade de elementos de um dado tipo no multiset)
- Algumas ideias para melhorar o TAD BigNumber:
- Adicionar possibilidade de trabalhar também com números negativos
- Adicionar operações de subtração e de divisão
Exercício de Desafio
Para esta semana vou colocar um novo exercício ad-hoc de eficiência algorítmica, envolvendo também padrões a duas dimensões. É novamente um problema da minha autoria que que foi usado nas Olimpíadas de Informática:
O limite de tempo de execução para cada caso de teste é de 2 segundos, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for eficiente.
Para estes problemas de desafios não vou dar logo dicas, para vos deixar pensar, mas se quiserem mesmo resolver o problema e não estejam a conseguir (mesmo depois de terem realmente tentado), podem falar comigo para obter pistas, ou ter uma ideia de como os "atacar".