prova1 ed2

Prévia do material em texto

PROVA 1 ED2 - 2012
1) [4.5] Implemente uma sub-rotina que recebe por parâmetro um arquivo já existente e cria um índice secundário estruturado como lista invertida. Para tanto, considere a chave nome. O arquivo existente é de registros de tamanho variável e contém os seguintes campos: código (chave primária), nome e idade. Existe um inteiro no início do registro indicando seu respectivo tamanho. Os campos estão separados por “|”.
Ao final responda:
- Qual a importância de se utilizar indexação? Cite pelo menos duas vantagens.
Índices são utilizados para facilitar a localização de informações, principalmente quando precisamos organizar um arquivo para ser pesquisado por chaves.
O arquivo índice é mais fácil de trabalhar, pois usa registros de tamanho fixo e pode ser pesquisado com busca binária (em memória principal), além de ser muito menor que o arquivo de dados. O índice pode estar ordenado apesar do arquivo de dados não estar e a partir da chave e do offset, um único seek é necessário para recuperar o registro correspondente.
Portanto melhora o tempo de busca por um registro e possibilitar múltiplas visões dos registros em um arquivo de dados.
- Porque os índices secundários apontam para os índices primários ao invés de apontarem para o arquivo principal?
Porque o índice secundário pode ter várias ocorrências iguais, mas de registros diferentes, portanto ao invés de gravar várias vezes o mesmo filme, por exemplo, basta gravar o nome do filme uma única vez apontando pra todas as chaves primárias existentes do nome daquele filme. Também é redundante manter duas listas que levam ao mesmo dado, já que o índice primário leva ao offset do arquivo, é conveniente que o índice secundário leve ao primário do que gravar o mesmo dado novamente. 
Programa:
/* Função que insere um novo elemento (nome, ra) nos vetores de índice secundário 1 e 2. Primeiro, faz um laço para posicionar o nome na posição correta do primeiro vetor, que deve ser ordenado. Depois verifica se o nome é igual ao nome onde está posicionado ou diferente. Se for igual, então não insere o nome no vetor de índice secundário 1, apenas insere o RA no vetor de índice secundário 2, fazendo as alterações necessárias dos offsets que estão nesse vetor. Se for diferente, insere o nome no vetor de índice secundário 1 e o RA no vetor de índice secundario 2, com offset igual a -1. */
void insereindsec(char novonome[10],int novora)
{
    int i=0,off=0,k=0,b,c,j=0;
    // compara o novo nome com os nomes do vetor, para achar a posicao correta para inserir.
    while ((strcmp(novonome,secprim[i].nome) > 0) && (i<tamindsec1))
    {
        i++;
    }
    // se for mesmo nome, apenas insere o RA no segundo arquivo de indice secundario.
    if (strcmp(novonome,secprim[i].nome) == 0)
    {
        off = secprim[i].off1;
        while (off <= tamindsec2)
        {
            if (secsec[off].off2 == -1)
            {
                secsec[off].off2 = tamindsec2;
                secsec[tamindsec2].ra = novora;
                secsec[tamindsec2].off2 = -1;
                tamindsec2++;
                break;
            }
            else
            {
                off = secsec[off].off2;
            }
        }
    }
    // se for diferente, atualiza o novo nome no primeiro e no segundo arquivos
    // de indice secundario.
    if (strcmp(novonome,secprim[i].nome) != 0)
    {
        k=tamindsec1;
        c=strlen(novonome);
        while (k>i)
        {
            for(b=0;b<10;b++)
                secprim[k].nome[b] = secprim[k-1].nome[b];
            secprim[k].off1=secprim[k-1].off1;
            k--;
        }
        for (j=0;j<10;j++)
        {
            secprim[i].nome[j]=' ';
        }
        for(b=0;b<=c;b++)
            secprim[i].nome[b] = novonome[b];
        secprim[i].off1=tamindsec2;
        secsec[tamindsec2].ra = novora;
        secsec[tamindsec2].off2 = -1;
        tamindsec1++;
        tamindsec2++;
    }
}
2) [1.5] Joãozinho é um excelente matemático, mas entende pouco de computação. Ele criou um excelente método de compressão de dados, mas está com dificuldades de propor um formato de arquivo que armazene um conjunto de arquivos comprimidos. Faça uma sugestão a Joãozinho considerando que as seguintes funcionalidades são muito utilizadas:
a- Descomprimir todos os arquivos comprimidos.
b- Listar todos os arquivos que estão dentro do arquivo comprimido.
c- Descomprimir um arquivo dado o seu nome.
Faça uma sugestão de formato de arquivo e discuta como os itens a, b e c seriam implementados no formato proposto.
O formato ZIP é muito utilizado e descomprime todos os arquivos sem perdas, ou seja, os dados obtidos após a descompressão são idênticos aos dados originais.
Poderia usar a idéia da codificação de Huffman: usar menor número de bits para representar caracteres com maior frequencia. Essa técnica pode ser implementada usando uma árvore binária que armazena caracteres nas folhas, e cujos caminhos da raiz até as folhas provêm a sequência de bits que são usados para codificar os respectivos caracteres.
A maioria dos arquivos de computador possui a mesma informação registrada repetidas vezes. Os programas de compressão de dados simplesmente se livram dessa redundância. Em vez de registrarem uma parte da informação várias vezes, um programa de compressão de arquivo lista esta informação uma vez, fazendo nova referência a ela sempre que volta a aparecer no programa original.
Quanto mais a informação for comprimida, maior a quantidade de informação pode ser armazenada e transmitidas mais rapidamente daquelas que não estão.
3) [1.0] O custo de acesso ao disco é uma combinação de quais fatores? Qual desses fatores é o que mais influencia no custo?
É uma combinação de 3 fatores:  
- Tempo de busca (seek): tempo para posicionar o braço de acesso no cilindro correto.
- Delay de rotação: tempo para o disco rodar de forma que a cabeça de L/E esteja posicionada sobre o setor desejado.
- Tempo de transferência: tempo para transferir os bytes. 
O fator mais expressivo é o tempo de seek, porque ele depende de quanto o braço tem que se movimentar e geralmente é mais caro em ambientes multiusuários.
4. [3.0] Quais as maneiras existentes para se organizar os arquivos visando a melhora do desempenho? Qual a vantagem e desvantagem de cada uma?
	Seqüencial
	Registros dispostos ordenadamente obedecendo a uma sequência determinada por uma chave primária
Acessos seqüenciais mais eficientes
	Operações de modificações não são simples
	Seqüencial Indexado
	Utilizam índices que determinam o endereço de um registro no arquivo e agilizam a consulta por estarem na RAM
	Necessidades de áreas de extensão que precisam ser reorganizadas
	Indexado
	Não existem áreas de extensão e os registros não tem compromisso com armazenamento físico
	Atualização do índice quando ocorre inserção de um registro.
	Direto
	Acesso direto, sem necessidade do índice
Não é necessário percorrer uma estrutura auxiliar.
	Determinar funções que gerem menor número de colisões
	Invertido
	Acesso direto ao registro após localização da lista invertida
	As listas invertidas valem apenas para aquela disposição física do arquivo