É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 10% da nota desta componente. Como existem 12 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de tipos abstratos de dados (TADs). Será por isso conveniente ver o que foi falado nas teóricas:
Exercício 1) TAD Conjunto - exemplo de implementação e utilização
Introdução e Conceitos Associados.
Nas teóricas 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 está explicada no vídeo Interfaces e TAD Conjunto (1h29m41s). 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 [ED247] TAD Conjunto (ArrayListIntSet) (Volume 2 - TADs)
Note que para ter aceite terá de implementar dois métodos novos: equals e intersection.
Deve submeter um ficheiro apenas com a classe que implementa o interface ArrayListIntSet
Para ambos os métodos a implementar, como recebe um IntSet s, apenas pode chamar os métodos do interface a esse objecto s.
Para fazer o equals(IntSet s) pode por exemplo verificar se o tamanho de ambos os objectos (this e s) são iguais e depois percorrer todos os elementos de this e verificar se estão em s (usando o método contains)
Para fazer o intersection(IntSet s) deve começar por criar um novo conjunto tmp (como criar? veja o código exemplo no enunciado... e deve ter espaço para quantos elementos?); depois pode percorrer todos os elementos de this e verificar se estão em s (usando o método contains); caso estejam, adicione-os a tmp.
Exercício 2) Medindo o tempo de execução do TAD Conjunto
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
No final, 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 3) 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 para os métodos contains, add e remove. Deverá por isso criar uma nova classe que implemente o interface IntSet (como definido no problema [ED247]):
classBooleanArrayIntSetimplements 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 no Mooshak o problema [ED248] TAD Conjunto (BooleanArrayIntSet) (Volume 2 - TADs)
Exercício de submissão extra para consolidação de conhecimentos
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).
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:
0
6
7
4
5
4
3
2
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
Mais exercícios extra para consolidação de conhecimentos
Algumas ideias para melhorar as suas implementações de IntSet:
Corrigir a limitação do número máximo de elementos no ArrayListIntSet: 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 e implemente-os. Por exemplo pode implementar união de conjuntos, verificar se um conjunto está contido noutro, etc.
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 (e é provavelmente o problema mais difícil que coloquei até agora - é normal demorar, precisarem de pensar bastante e terem dificuldades - o objectivo dos desafios é precisamente esse):
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".
