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];
    }