Laboratório 5 - Semana de 24 a 28 Mar

Neste laboratório propõe-se a execução dum programa que implementa um conjunto de algoritmos simples, estudados nas aulas teóricas, sobre o Problema da Conectividade. Pretende-se que os alunos façam uma análise cuidadosa destes programas, a nível semântico e sintáctico. Através desta análise, deverão ser capazes de identificar o que cada algoritmo faz, introduzindo código pertinente para obter a informação sobre o funcionamento do programa em termos de complexidade. Assuma que a complexidade dos algoritmos é função do número de operações elementares associadas aos procedimentos de procura e de união. Considere como operações  elementares apenas os acessos aos elementos das tabelas de dados (número de vezes que a tabela id é lida e/ou escrita).

Os dados são inicialmente lidos do terminal (standard input) que pode ser redirecionado para ler de um ficheiro de entrada.  A sintaxe deste ficheiro é muito simples: na primeira linha do ficheiro é indicado algoritmo a executar depois o número de objectos/nós do problema. Nas linhas seguintes são indicados os pares de ligações.  O programa deve ler todo o ficheiro até esgotar os dados.

  1. O ficheiro executa.c, abre e lê o ficheiro de entrada fornecido como argumento na linha de comando. O programa contém um diálogo que permite a escolha entre várias opções de algoritmos para efectuar o teste de conectividade. Analise o código dos algoritmo para o problema da conectividade que se apresenta de seguida. O código do algoritmo de Procura Rápida - Quick Find (QF)  União Rápida - Quick Union (QU) e dos restantes algoritmos encontra-se no ficheiro conectividade.c. Pretende-se analisar o desempenho dos diversos algoritmos num conjunto de problemas cujos pares de ligações se encontram nos ficheiros de dados fornecidos. Adicione código para contabilizar o número de operações elementares (leituras e escritas das tabelas de dados) associados aos procedimentos de procura e de união efectuadas. Nos algoritmos de União Rápida Equilibrada (WQU) e União Rápida com Compressão de Caminhos (CWQU) contabilize as operações associadas aos procedimentos de equilíbrio e de compressão como operações de união.  No final da execução do programa, deve escrever estes valores para o terminal (stdout). Apresente os resultados obtidos na tabela (imprima o ficheiro  tabela.pdf), indicando para cada ficheiro e algoritmo os valores contabilizados de nós, pares de entrada, ligações e acessos à memoria realizados nas procuras e de uniões.

  2. Verifique se os resultados obtidos experimentalmente estão de acordo com os resultados teórico.

Attachments