1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Perguntas de Frequencia

Discussão em 'Programação' iniciada por jtcgomes, 16 de Janeiro de 2007. (Respostas: 6; Visualizações: 1668)

  1. jtcgomes

    jtcgomes Power Member

    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... :)
     
  2. HecKel

    HecKel The WORM

    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

    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.

    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
     
  3. jtcgomes

    jtcgomes Power Member

    thanks HecKel...

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

    Slash Power Member

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

    Nuno
     
  5. acrobat

    acrobat Power Member

    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.
     
  6. jtcgomes

    jtcgomes Power Member

    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 [​IMG]
    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 [​IMG]
    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 [​IMG]
    Pergunta 3: Qual a importância de uma boa função de “hash” no desenvolvimento de hash tables (tabelas de dispersão)?

    [FONT=&quot]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.[/FONT]
     
  7. SHZR

    SHZR Power Member

    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.
     

Partilhar esta Página