Filas prioritária( Algoritmos e estruturas de dados 1)

filas prioritárias
->estrutura de dados linear
->tipo de dados
    abstracto (ADT) com as seguintes prioridades:
* supostas operações de - inserção( de um novo elemento na fila)
                -remoção do elemento que esta na cabeça  da fila isto é, o elemento maior  prioridade,tipicamente o elemento com maior de chave

API da fila prioritária(PG-Priority Queue)

void insert QP(PQueu *pq,int elemento)
int DelMaxPQ(PQueu*pq)


exemplo: os seguintes n=8, a chegar por esta ordem á fila
5,2,7,3,1,8,6,4



3 Implementações de possíveis PQ:
a)Usar um vector não ordenado
    - quando chega um elemento é colocado no final do vector(custo 1-constante)
    - quando queremos remover o maior elemento temos fazer n comparações para determinar o maior elemento

b)Usar um vector ordenado
- quando chega um novo elemento é feita a fusão ordenada com o vector ordenado já  existente(inserção tem custo linear)
- remoção com custo, constante-1

c)Binary Heap
- implementar uma árvore binária balanceado usando um vector

ex: árvore binária
- estrutura de dados não linear em que casa elemento tem: 0,1, ou 2 filhos
-existe uma só raiz na árvore
-> A árvore binária satisfaz as seguintes condições
   - todos os niveis estão completamente preenchido excepto o ultimo nível que pode estar parcialmente preenchido

-> Para uma Binary Heap
que implemente uma fila prioritária(PQ) sem elementos repetidos, dado qualquer elemento da árvore binária ele tem que ser sempre maior que os seus filhos (0,1, ou 2 filhos)

->nuance de implementação vamos deixar a posição 0 do vector da raiz aparece na posição 1
-> Dado um elemento da posição(índice) k o seu pai esta na posição k/2(divisão inteiro)
->os filhos do elemento de índice k estão nas posições 2*k e 2*k+1

Algoritmo de Pesquisa Binária

Para a implementação da pesquisa binária num vector V de N valores inteiros ordenados de uma forma crescente, adopta-se o seguinte algoritmo:

Função  Pesquisa_Binária(V,N,X)
{   
  1.Inicializar a  pesquisa e inicializar variáveis
        ini=1;
        fim=N;
2. Percorrer o vector para encontrar o elemento
      Do While   ini <= fim
                meio= INT((ini+fim)/2)

                 if  X <V[meio]
                    then fim= meio-1
                 else   if x> V[meio]
                        then ini= meio+1;
                                 else   write("elemento encontrado")
                                       return (meio)
3. Percorreu todo o vector e não encontrou o elemento
  return (0)

Pesquisa Binária

Pesquisa Binária

A estratégia a adoptar neste algoritmo passa por comparar o elemento que procuramos com o valor do elemento armazenado no meio do vector.

* Se esse elemento for menor que o elemento do meio, então conclui-se que, se o elemento estiver presente no  vector , ele estará na primeira parte do mesmo.

* Se o elemento a pesquisar for maior, então estará na segunda parte do vector. Logicamente que se for igual, estará encontrado o elemento do vector e a pesquisa ficará concluída.

*  Se o elemento estiver estiver num das partes do vector, repete-se o procedimento considerando apenas a parte que restou e compara-se o elemento a procurar com o elemento de armazenado no meio dessa parte.

Em suma:
Há 3 tipos de comparações entre o elemento X a pesquisar e o valor v[i] que representa o valor posicionado no meio da estrutura de dados:


     -> Se o X= V[i] então a pesquisa é bem sucedida. A pesquisa termina.

     -> Se o X <V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que procedem V[i], ou seja na primeira metade da lista.

     -> Se X> V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que sucedem V[i], ou seja na segunda metade da lista

Uma ajuda extra

Para ajudar no estudo !!
 Vejam os vídeos do canal ,engloba os algoritmos que abordamos nas aulas 
http://youtu.be/OM8ZHrySAj4

Algoritmo Quick Find

Pseudo-C

função connected(P,Q)
{
   retorna quick_find_ID[P]==quick_find_ID[Q];
}

Função Union(P,Q)
{
    Inicializar a variavel i, , count_comp e vec_size

      Pid=quick_find_ID[P];
      Qid=quick_find_ID[Q];

           Se Pid==Qid
                    retorna
               count_comp--;
    
    For   i=0 to vec_size
            Se quick_find_ID[i]==Pid
                     então
                              quick_find_ID[i]=Qid;
}

Quick Sort (em c)

Quicksort is a very efficient sorting algorithm. It has two phases:
- the partition phase and
-the sort phase,
Most of the work is done in the partition phase. it works out where to divide the work.
The sort phase simply sorts the two smaller problems that are generated in the partition phase.
Complexity: O(n.log n)

void quick_sort(int n, int* v)
{
    if(n<=1)
        return;
    else
    {
        int x=v[0];
        int e=1;
        int d=n-1;

        do
        {
            while(e<n && v[e] <=x) e++;
            while(v[d]>x)d--;
            if(e<d)//faz a troca
            {
                int temp=v[e];
                v[e]=v[d];
                v[d]=temp;
                e++;
                d--;
            }
        }
        while(e<=d); //troca o pivot
        v[0]=v[d];
        v[d]=x;
        //ordena sub vectores restantes
        quick_sort(d,v);
        quick_sort(n-e,&v[e]);
    }

}

Bubble Recrusivo (em C)

O próximo exemplo apresenta uma  implementação recrusica em C do algoritmo bubble sort. Lembrar que o algoritmo recursivo de ordenação posiciona o elemento maior valor e chama, recursivamente, o algoritmo para ordenar o vector vec restante com n-1 elementos

void Bubble_rec(int n, int* vec)
{
    int troca=0;
    int j=0;

    for(j=0; j<n-1; j++)
    {
        if(vec[j]>vec[j+1])
        {
            int temp=vec[j];
            vec[j]=vec[j+1];
            vec[j+1]=temp;
            troca=1;
        }
        if(troca!=0)
            Bubble_rec(n-1,vec);
    }

}

Bubble Sort- Algoritmo (em c)

Uma função que implementa o algoritmo bubble sort e que considera a ordenação de um vector de valores inteiros é apresentada a seguir.Neste programa considera-se que a função recebe como parâmetros o numero de elementos e o ponteiro do primeiro elemento do vector que se deseja ordenar.

void  Bubble_sort(int n, int* vec)
{
    int i;
    int j;

    for(i=n-1; i>=1; i--)
    {

        for(j=0; j<i; j++)
        {
            //printf("vec: %d",vec[i]);
            if(vec[j]>vec[j+1])
            {
                int  temp=vec[j];
                vec[j]=vec[j+1];
                vec[j+1]=temp;
            }
        }

    }
}

Sistemas Digitais (Introdução)

1. Sistemas (Digitais)
2. Dispositivos
3. Componentes


Sistema: Circuitos complexo que resulta da associação de dispositivos e componentes; possui entradas e saídas e  funciona com base em 3 fases distintas:

Dispositivos: Circuito electrónico digital que é constituído por vários componentes e desempenho um função especifico e bem determinado

Exemplo: contador, codificador, etc...

Componentes ou elementos : Cada uma das partes que são utilizados por construir circuitos electrónicos

Circuito integrado (chip) "pastilha"

Integra na mesma "pastilha" vários circuitos; vários dispositivos

Propriedades do Sinal analógico 

a)contínuos no tempo e/ou espaço

b) contínuos em amplitude

Como faço a conversão de um sinal analógico para o sinal digital?

Discretizo no tempo e/ou espaço

Discretizo na amplitude ou quantificar

Conversão A/D 

1. Amostragem 

2. Quantificação

    codificação em binário

Vantagens dos Sistemas Digitais (face aos analógicos):

1. maior imunidade ao ruído eléctrico 

2. elevada densidade de integração de circuitos (diminuir o peso)

3. facilidade de interligação entre dispositivos digitais (blocos)

Arquitectura continuação I

Operações aritméticas 

Arquitectura

Sistemas de numeração/ Representação Numérica 

Sistema Decimal
(alfabeto de símbolos)   : 10 símbolos (0,1,2,.....,9)

Sistema Binário: 2 símbolos (0,1)

Quantidade numérica pode ser representada recorrendo a um alfabeto K símbolos 

Exemplo decimal:
base=2

2 3 5 = 2*10^2 + 2*10^1 + 2*10^0
|   |   |
|   |    unidades (posição 0)
|    dezenas  (posição 1)
centenas (posição 2)

Exemplo binário

base=2
1 1 1 0 1 = 1*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0= 16+8+4+1=29

exercicio:
- Colocar em decimal
16        4    2    1
1 0 1 1 1= 16+4+2+1= 23

Processos

• Consiste num método de descrição das actividades de um sistema operativo;
• Todo o software incluído no sistema operativo é organizado num grupo de programas executáveis. Cada um destes programas quando activo forma um processo juntamente com o ambiente de execução associado;
• Cada processo pode "correr" num processador diferente, mas na prática é utilizada a multi-programação (cada processador "corre" vários processos), logo o sistema operativo deve fazer o escalonamento de processos de forma a ser efectuada a comutação de processos;
• Os sistemas operativos baseados neste modelo, fornecem primitivas para a criação e destruição de processos;
• Cada processo pode criar por sua vez processos filho independentes, podendo este continuar a sua execução concorrentemente com eles, ou então bloquear até à sua conclusão.

Contexto de um Processo

É toda a informação necessária à descrição completa do estado actual de um processo:

• PCB (Bloco de Controlo do Processo)
  • Identificação do processo, grupo, etc;
  • Informação sobre o escalonamento: estado, prioridade, etc;
  • Localização e tamanho dos contextos de memória, de dados, de stack, ficheiros e código;
  • Registos de controlo;
  • Código;
  • Dados do programa;
  • Stack;
  • Descritores de ficheiros.

Funcionamento de Algumas System Calls

 Como funciona a função fork(), exit(),wait() ?

Fork()

fork ( int pid = fork() )

 1- Verifica se há lugar na Tabela de Processos
 2- Tenta alocar memória para o filho
 3- Altera o mapa de memória e copia para a Tabela
 4- Copia a imagem do Pai para o Filho
 5- Copia para a tabela de processos a informação do processo Pai(pid,propriedades,estado,etc)
 6- Atribui um Pid ao Pai
 7- Informa o Kernel (Núcleo do Sistema Operativo) e o sistema de ficheiros que foi criado um novo processo

Exit()

exit (exit(int estado) )

O  funcionamento depende do pai estar á espera ou não.
  * Se o pai esta á espera, então a entrada na tabela é limpa e o espaço de memória  é desalocado(o processo termina definitivamente)
 * Se o pai não está á espera, o processo fica adormecido, activando um bit na entrada correspondente da tabela, o scheduler(o responsável pelo escalonamento dos processos) recebe uma mensagem de modo a evitar o processo
 * Se o processo pai morre antes do filho fazer exit e de modo a evitar que o processo fique adormecido eternamente, este é adoptado pelo processo ttv(processo que "lê" o login) correspondente, já que este está a sempre a fazer wait
  
wait()

wait (int pid=wait(int *estado) )

Obriga o processo a esperar pelo fim de um filho de modo a libertar o espaço correspondente na tabela e originar uma eliminação definitiva.

• Obriga a uma pesquisa da tabela de processos, para descobrir se existe algum processo filho;
• Se existir um processo filho adormecido, ele é limpo da tabela de processos e o seu pid é retornado para o wait, assim como o argumento do exit do processo adormecido;
• Se não houver nenhum filho adormecido, e existir algum filho no scheduler, então o processo é bloqueado até o filho executar o exit;
• Se não existir nenhum filho na tabela de processos, o wait retorna um valor de erro.