Tabelas de Dispersão

Tabela de dispersão (também conhecida por ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores.
O  seu objetivo é:  a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado.

 Tabelas de dispersão são normalmente utilizadas para implementar vetores associativos, conjuntos e caches. 

complexidade: 
 O "ganho" com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme a quantidade de dados aumenta.

Função de espalhamento

O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. 

A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. 

Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão.

 

 

Método da divisão (método da congruência linear)

• Potências de dois devem ser evitadas para valores de .
• deve ser um número primo distante de pequenas potências de dois ( grande).

Exemplo:

José da Silva; 

Ricardo Sousa

Orlando Nogueira

 

Agora inserimos mais um nome:
Renato Porto
e temos uma colisão!

  Se inserirmos um outro nome começado com a letra R, teremos uma outra colisão na letra R. Se inserirmos "João Siqueira", a entrada estaria em conflito com o "José da Silva".

heap sort

The heapsort algorithm can be divided into two partes
- Step 1: a heap is built out of the data
- Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.

The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by chossing a min-heap or mar-heap in the step one.

Complexity: O(n.log n)

Design algoritmica

-> Divisão e conquista (divide and conquer)
->Atacar/resolver um problema algorítmico em que a dimensão dos dados de entrada é N através  da divisão dos dados de entrada em partes mais pequenas (duas ou mais partes), aplicar a resolução (geralmente de modo recursivo )a cada uma das partes e finalmente fazer a combinação dos resultados obtidos de modo a obter a solução final.

Etapas:

1) Divisão dos dados N => P1,P2...
2) Conquista/resolução a cada uma das partes Pi
3)Combinação dos resultados para obter solução final

 Processo de divisão e conquista/recursivo) aplicado em ordenação por partes(merge sort)

Grafo

O que é um grafo?

Grafo é uma abstracção matemática, mais genérica do que a árvore, que serve para descrever organizações e armazenar informação, e que se apresenta estruturada de forma complexa

Para que serve um grafo?

Os grafos são usados para simular sistema de redes. 

Ex: Nas redes de transporte, podem ser usados para calcular custos associados aos percursos e determinar percursos óptimos.

Nas redes de comunicação podem ser usados para determinar percursos alternativos de encaminhamento de informação ou para verificar se o desligamento de parte da rede não impede o encaminhamento da informação, ou seja determinar a conectividade  da rede.

Propriedades do Grafo

Um grafo é uma colecção de vértices ou nós que são os elementos  que contêm informação que se pretende armazenar e de arestas que são os elementos que ligam os vértices.Um grafo tem pelo menos um vértice, mas pode não ter qualquer aresta.Cada aresta esta associada a um par de vértices, chamando-se esses vértices por vértices adjacentes.

Um conjunto de vértices ligados entre si e desligados dos restantes vértices chama-se por componente conexa. Um grafo diz-se conexo se só possuir uma componente conexa, senão diz-se que é um grado desconexo.

Um grafo diz-se nulo se possuir apenas vértices e diz-se completo quando entre cada par de vértices existe uma aresta. Um grafo com V vértices tem no máximo V*(V-1)/2 arestas, quando é um grafo completo.

Um caminho num grafo é uma lista de vértices, que  os sucessivos vértices estão ligados por arestas. Os vértices e as arestas de um caminho podem não ser distintos, pelo que, ao contrário de um árvore, em que só pode existir mais de um caminho entre dois vértices. O número de arestas do caminho determina o seu comprimento.

Um caminho diz-se simples se não tiver arestas repetidas e diz-se elementar se todos os seus vértices forem distintos, Um circuito é um caminho que começa e acaba no mesmo vértice. Um circuito é simples se não possuir arestas repetidas e designa-se por ciclo se todos os seus vértices, com excepção inicial forem distintos. Assim sendo, um ciclo atravessa pelo menos três vértices distintos. 

Álgebra relacional

Álgebra relacional e uma linguagem procedimental que define operações sobre a base de dados, através de expressões algébricas. 

Operadores

Os cinco operadores básicas que definem a álgebra relacional, no sentido em que não podem ser definidos a partir de outros operadores, são os seguintes:

* Operadores sobre conjuntos:  Os operadores básicos sobre conjuntos são a união e a diferença;

* Selecção: Também chamado restrição, é um operador unário que produz o conjunto de tuplos (campos )de uma relação  R que satisfazem uma condição;

* Projecção: Operador unário que produz a mesma relação apenas com as colunas especificas, na ordem especificada;

* Produto:Operador unário binário que aplicado ás relações R e S, produz uma relação cujo o esquema é a união dos esquemas de R e S, e que combina cada tuplo de R com cada tuplo de S.

 # Selecção

A Selecção produz uma relação cujos  tuplos satisfazem a condição c. A condição c, é um predicado que pode envolver operadores aritméticos, operadores sobre texto, e conjunções, disjunções ou negações, actuando como um filtro da relação.

Exemplo:

Conclusão: Faz-se uma selecção de uma coluna com uma condição, que neste caso a condição é Ects > 4

O predicado é aplicado a cada linha individualmente, e o seu resultado determina a inclusão ou não da linha na relação resultante. Portanto, não é possível ter na condição de selecção operações sobre mais tuplos do que esta em causa .

#Projecção

A projecção (R) produz uma relação com os mesmo tuplos de R,mas apenas com as colunas constantes da lista L.
Esta lista pode não ter apenas nomes de colunas de R, mas também:
*Uma indicação para renomear colunas de esquema R;
* Uma expressão aritmética 

Exemplo:

π_{Nome,Ects   -->} Créditos

  

Nome	Créditos
Base de Dados	5
Programação	4

Conclusão: 

Com a projecção a coluna Ects, passou a chamar-se Créditos 

Outro exemplo:

π _{Nome, ECTS * 26  ->  Horas}

Nome	Horas
Base de Dados	130
Programação	104

#Produto

O produto permite combinar informação de relações diferentes.O produto de duas relações R e S - R X S resulta numa relação que é a união dos esquemas de R e S, alterando se necessário, colunas que tenham nomes iguais  e cujos tuplos sejam a combinação de cada tuplo de R  com cada tuplo de S.

Exemplo:

Nome                | Sigla         |ECTS    |                     |   Sala   |    Lugares   |
_____________ | _______ | _______ |                    | ______ | _________ |

Base de Dados  | BD            | 5           |                     | S1        | 30              |

Programação     | PG            |4            |                     | S2        | 40              |  

Produto:

Nome                | Sigla         |ECTS   |   Sala   |    Lugares   |
_____________ | ________ | ______ | _____ | _________

Base de Dados  | BD            | 5          | S1        | 30              |

Base de Dados   | BD           |5           | S2        | 30              |

Programação     | PG            |4           |S1          |30              |  

Programação     | PG            |4           | S2        | 40              |   

                   

Research sub-strings in strings: LSD radix sort

void lsd_sort(StringElementsArray * a, int N, int W, int R) {
    int i,r,d,c;
    int * count = newIntArray(R + 1);
    StringElementsArray aux; // aux Array
    createStringElementsArray(&aux,N); // create aux array

    for (d = W-1; d >= 0; d--) {

        // reset count[] array
        for (i = 0; i < R+1; i++)
            count[i]=0;

        // compute frequency counts
        for (i = 0; i < N; i++)
            count[a->str[i][d] + 1]++;

        // transform counts to indicies
        for (r = 0; r < R; r++)
            count[r+1] += count[r];

        // distribute
        for (i = 0; i < N; i++) {
            c = a->str[i][d];
            aux.str[count[c]] = a->str[i];
            aux.len[count[c]] = a->len[i];
            count[c]++;
        }

        // copy back
        for (i = 0; i < N; i++) {
            a->str[i] = aux.str[i];
            a->len[i] = aux.len[i];
        }

        // Trace of iterations for LSD string sort
        printf("\nLSD Sorted List (right to left) after sorting key %d:\n",d);
        for (i = 0; i < N; i++)
            printf("\t%s\n",a->str[i]);
    }

Research sub-strings in strings: KeY Index Counting

Key- indexed countig

  
void key_index_counting(StringKeyElementsArray * a, int N, int R) {

    int i,r,c;
    int * count = newIntArray(R + 1);
    // reset count[] array
    for (i = 0; i < R + 1; i++)
        count[i]=0;
    StringKeyElementsArray aux; // aux Array
    createStringKeyElementsArray(&aux,N); // create aux array

    // compute frequency counts
    for (i = 0; i < N; i++)
        count[a->keys[i]]++;

    // transform counts to indicies
    for (r = 0; r < R; r++)
        count[r+1] += count[r];//frequencias acumuladas

    // distribute
    for (i = 0; i < N; i++) {
        c = a->keys[i] - 1;
        aux.str[count[c]] = a->str[i];
        aux.len[count[c]] = a->len[i];
        aux.keys[count[c]] = a->keys[i];
        count[c]++;
    }

    // copy back
    for (i = 0; i < N; i++) {//4º passo
        a->str[i] = aux.str[i];
        a->len[i] = aux.len[i];
        a->keys[i] = aux.keys[i];
    }