Boas noites pessoal...

Quarta feira (17 janeiro) tenho frequencia a Estrutura de Dados e Algoritmos, uma cadeira do 2º ano de Engenharia Informatica...
Ando Aki a estudar, e estou a ter dificuldade em resolver uma frequencia. nomeadamente na parte teorica.. curto mais a prática.

Então é assim, tenho 3 perguntas com resposta duvidosa, gostava k me ajudassem, e me dessem algumas luzes, voces sábios da arte de programar.. cá vai:

Pergunta 1: O que é a programação genérica e qual a sua importância no desenvolvimento de estruturas de dados?

Pergunta 2: Qual a importância do estudo das estruturas de dados e os algoritmos que as manipulam para o desenvolvimento de software e hardware?

Pergunta 3: Qual a importância de uma boa função de “hash” no desenvolvimento de hash tables (tabelas de dispersão)?

bem, só pra vos ilucidar um pouco, andamos o semestre a trabalhar com o NetBeans, desenvolvendo como trabalho final uma calculadora e um codificador/descodificador de textos...

Obrigadão desde já pelo tempo perdido na leitura da thread... :)

Pergunta 1: O que é a programação genérica e qual a sua importância no desenvolvimento de estruturas de dados?
Bem, isto é um dos trunfos do Java. Programação genérica, é aquele tipo de programação que não te restringe a tipos de dados, por exemplo, tu podes implementar uma lista que só admite strings mas se queres fazer uma lista que implementa inteiros estás a repetir TODO o código mudando só o tipo, porque não fazer uma lista genérica que aceita um tipo?

Em java custuma-se declarar da seguinte forma:

List<TIPO> var = new LinkedList<TIPO>();

Se fosse programação mais restrita nem sequer tinhas aqueles delimitadores de menor e maior ;) Este foi um dos avanços do Java 5.0

Pergunta 2: Qual a importância do estudo das estruturas de dados e os algoritmos que as manipulam para o desenvolvimento de software e hardware?
Esta não te sei responder com exactidão e certeza..., mas aqui vai uma tentativa..

A este tipo de perguntas é mais fácil pensares o que seria do desenvolvimento de software e hardware sem estas estruturas, que dificuldades irias enfrentar.

Imagina que queres a funcionalidade de uma lista, mas que não tens uma lista, como te irias safar? Andar a trabalhar com a pilha para trás e para a frente? Pushs e Pops atrás uns dos outros? Como irias garantir que não te irias baralhar todo e não começavas a trocar elementos?

Com uma estrutura de dados tens sempre referência para o elemento seguinte, um endereço de memória ou de disco. Poupas a larga escala a complexidade temporal em qualquer pesquisa, ou seja, melhoras significativamente o desempenho do teu software.

Pergunta 3: Qual a importância de uma boa função de “hash” no desenvolvimento de hash tables (tabelas de dispersão)?
Simples, garantia de não haver colisões e que utilizas a tabela de dispersão da melhor forma possível.

Agora tens de ter duas coisas em conta, tabelas de dispersão abertas e fechadas, quais queres tratar? Uma tabela de dispersão fechada é mais complicada de lidar, tens de encontrar uma função de hash de tal forma eficiente que evites a todo o custo colisões, senão a posição livre seguinte será ocupada..., para localizares esse objecto vai ser mesmo pain in the ass...
Uma tabela de dispersão aberta..., é a alegria, a função de hash de facto é importante, pois precisas de localizar com complexidade O(1) o elemento, mas não precisas de te preocupares com colisões, pois quando se dá uma colisão o elemento fica nessa posição também, mas dentro de uma lista.

Espero não ter sido confuso demais...

abraços, HecKel

thanks HecKel...

se ouver + opiniões... força ai...

Se fosse programação mais restrita nem sequer tinhas aqueles delimitadores de menor e maior ;) Este foi um dos avanços do Java 5.0

Só para elucidar, o C++ permite a definição de classes com base em Templates ou desde sempre ou à uns bons anos.

Nuno

só acrescentaria que na função de hash é necessário ter em conta a condensação dos dados..
dependendo da função implementada pode existir a tendência dos items ficarem localizados mais no inicio ou no fim da lista. o que aumentaria a probabilidade da existencia de colisões.

Apos uma tarde de estudo, e depois das vossas respostas, cheguei ás seguintes conclusoes...

Gostava k me corrigissem se tiver errado....

Quote:
Post Original de jtcgomes http://www.techzonept.com/images/styles/newtzstyle/buttons/viewpost.gif (http://www.techzonept.com/showthread.php?p=1377012#post1377012)
Pergunta 1: O que é a programação genérica e qual a sua importância no desenvolvimento de estruturas de dados?

Programação genérica é um paradigma da programação na qual os algoritmos são escritos de tal forma que apenas se tenham que adaptar às variaveis definidas pelo problema, ou seja, a programação genérica permite que um determinado parametro possa ter diferentes tipos de dados, evitando assim a repetição de código.


Quote:
Post Original de jtcgomes http://www.techzonept.com/images/styles/newtzstyle/buttons/viewpost.gif (http://www.techzonept.com/showthread.php?p=1377012#post1377012)
Pergunta 2: Qual a importância do estudo das estruturas de dados e os algoritmos que as manipulam para o desenvolvimento de software e hardwar

Um bom algoritmo é fundamental no desenvolvimento de software e hardware, uma vez que as estruturas de dados organizam de uma forma coerente os dados, tornando assim problemas complexos em soluções triviais.

Quote:

Post Original de jtcgomes http://www.techzonept.com/images/styles/newtzstyle/buttons/viewpost.gif (http://www.techzonept.com/showthread.php?p=1377012#post1377012)
Pergunta 3: Qual a importância de uma boa função de “hash” no desenvolvimento de hash tables (tabelas de dispersão)?

Uma boa função “hash” garante que não haja colisões de modo a utilizar a tabela de dispersão da melhor forma possivel.

Uma boa função hash evita colisões entre objectos, o que garante que as buscas sejam sempre O(1). Na existência de colisões, embora seja raro, as pesquisas posteriores são mais lentas, embora não seja uma perda significativa de velocidade.