Aula Prática #05 - Tipos Abstractos de Dados
(semana de 16/03 a 20/03)
Na passada terça-feira (dia 10 de Março), terminei a aula com um puzzle de programação. Aqui fica para todos os que quiserem tentar resolver. Podem enviar as vossas respostas por email para mim.
Pequeno Puzzle de Programação (não faz parte dos exercícios da aula)
Exercício 1) TAD Conjunto - exemplo de implementação e utilização
- Introdução e Conceitos Associados.
Nas teóricas (ver slides "3 - Tipos Abstractos de Dados") falamos de vários conceitos que devem rever. 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 será explicada no vídeo que publicarei brevemente (ainda durante o fim-de-semana). 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".