Java Relatório Trabalho
Por: Fred Neves • 15/2/2019 • Ensaio • 2.496 Palavras (10 Páginas) • 385 Visualizações
[pic 1]
Algoritmos e Estruturas de Dados
Relatório do Projeto:
BikePickUp [pic 2]
Ano Letivo: 2018/2019
Docente: Prof. Bruno Anjos
Turno Prático: P1
Autor:
- Frederico Luz, nº 51162
Tipos Abstratos de Dados
User e UserReadOnly
A interface User e UserReadOnly representam o utilizador da aplicação que irá efetuar os “pick-ups”.
A interface User contém as operações relativas ao usuário que podem modificar os seus atributos exceto a getListPickUps() por razões de preferência.
Já a interface UserReadOnly possui as somente as operações de consulta de modo a proteger os dados, devido a sua exposição na classe principal (Main).
A estrutura de dados usada para guardar o objeto que implementa essas interfaces foi um Dicionário, implementando uma Tabela de Dispersão Aberta porque achei que seria melhor pois é uma estrutura simples de implementar e que não causaria muitos problemas em termos de complexidade temporal. Permitiria uma pesquisa através de uma chave em que as inserções e remoções possuíssem uma complexidade temporal constante no seu caso esperado.
Foi usado também uma Árvore Binária que trata de colisões com o objetivo de armazenar os utilizadores mais atrasados, devido a possibilidade de os ordená-los de forma decrescente pelo número de pontos de atraso.
Bike e BikeReadOnly
A interface Bike e BikeReadOnly representam as bicicletas do sistema.
A interface Bike contém as operações relativas as bicicletas que podem modificar os seus atributos exceto a getListPickUps() por razões de preferência.
Já a interface BikeReadOnly possui as somente as operações de consulta de modo a proteger os dados, devido a sua exposição na classe principal (Main).
A estrutura de dados usada para guardar o objeto que implementa essas interfaces foi um Dicionário, implementando uma Tabela de Dispersão Aberta porque achei que seria melhor pois é uma estrutura simples de implementar e que não causaria muitos problemas em termos de complexidade temporal. Permitiria uma pesquisa através de uma chave em que as inserções e remoções possuíssem uma complexidade temporal constante no seu caso esperado.
Park e ParkReadOnly
A interface Park e ParkReadOnly representam os parques do sistema.
A interface Park contém as operações relativas aos parques que podem modificar os seus atributos.
Já a interface ParkReadOnly possui somente as operações de consulta de modo a proteger os dados, devido a sua exposição na classe principal (Main).
A estrutura de dados usada para guardar o objeto que implementa essas interfaces foi um Dicionário, implementando uma Tabela de Dispersão Aberta porque achei que seria melhor pois é uma estrutura simples de implementar e que não causaria muitos problemas em termos de complexidade temporal. Permitiria uma pesquisa através de uma chave em que as inserções e remoções possuíssem uma complexidade temporal constante no seu caso esperado.
Também foi usada um Dicionário Ordenado onde se implementa uma OrderedDoubleList, de modo a guardar os parques com maior número de pick-ups máximo do sistema, tendo uma complexidade temporal linear no seu caso esperado.
PickUpReadOnly
Esta interface representa uma espécie de fatura apos o utilizador efetuar o PickDown(), onde este guarda todos os dados do determinado serviço concluído.
Possui somente métodos de consulta que irão ser úteis para operações como BikePickUps(), etc.
A estrutura de dados usada para guardar o objeto que implementa essa interface tanto no objeto UserClass como na BikeClass foi a DoubleLinkedList pois é de fácil manuseamento na hora de iterar os pick-ups efetuados.
BikeSystem
Esta é a interface que é implementada pela Classe topo, aonde todas as operações da aplicação são efetuadas.
Ela possui maioritariamente operações de modificação (void), com somente alguns “getters”.
Descrição das operações e Estudo das suas Complexidades Temporais
Legenda:
λu – Fator de ocupação da tabela de dispersão dos utilizadores.
λb - Fator de ocupação da tabela de dispersão das bicicletas.
λp – Fator de ocupação da tabela de dispersão dos parques.
λn – Somatório dos varios fatores de ocupação.
n – somatório dos vários elementos da tabela de dispersão.
nUser – número de elementos da tabela de dispersão dos utilizadores.
nBikes – número de elementos da tabela de dispersão das bicicletas.
nPark -- número de elementos da tabela de dispersão dos parques.
nBikesInPark -- número de elementos da tabela de dispersão das bicicletas nos parques.
- Inserir Utilizador ( addUser )
Esta operação consiste em adicionar um novo utilizador ao sistema, caso exista um utilizador com o mesmo ID o sistema retorna uma exceção. Caso não exista é criado um objeto UserClass e é inserido no Dicionário.
Complexidade Temporal
Ação | Melhor Caso | Pior Caso | Caso Esperado |
Procurar se existe um utilizador com o mesmo ID | O(1) | O(nUser) | O(1+λu) |
Inserir novo utilizador | O(1) | O(nUser) | O(1+λu) |
Total | O(1) | O(nUser) | O(1+λu) |
- Remover utilizador ( removeUser)
Esta operação consiste em remover um utilizador dado o seu ID, o processo é concluído com sucesso se o utilizador existe e ainda não efetuou nenhum pick-up.
Através do ID do utilizador este é pesquisado na tabela de dispersão.
Ação | Melhor Caso | Pior Caso | Caso Esperado |
Procurar se o utilizador existe na tabela de dispersão | O(1) | O(nUser) | O(1+λu) |
Verificar se o utilizador está em movimento | O(1) | O(1) | O(1) |
Verificar se a sua lista de pick-ups não está vazia | O(1) | O(1) | O(1) |
Remover o utilizador | O(1) | O(nUser) | O(1+λu) |
Total | O(1) | O(nUser) | O(1+λu) |
...