PUC-Rio
Departamento de Informática
Profs. Marcus Vinicius S. Poggi de Aragão
Período: 2008.2
Horário: 2as-feiras e 4as-feiras de 17-19
29 de agosto de 2008
Data da Entrega: 26 de setembro de 2008

ESTRUTURAS DISCRETAS (INF 1631)

1o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver códigos de algoritmos correspondentes a provas por indução matemática de teoremas associados a problemas sobre estruturas discretas.


Problema 1   Dada uma sequência de n números inteiros, determinar a subsequência crescente de tamanho máximo (com mais números inteiros).


Uma subsequência nesse problema não é necessariamente consecutiva. I.e., seja a seguinte sequência de números inteiros: 4,7,6,12,3,5,23. A subsequência crescente máxima é 4,6,12,23 com 4 inteiros.

Sejam os seguintes teoremas onde ik denota o k-ésimo inteiro da sequência In de n inteiros:


Teorema 1   Sabe-se determinar as subsequências crescentes de Ik = { i1, i2, ..., ik } com 1,2,...,k inteiros, quando existirem, que terminam com o menor inteiro.



Teorema 2   Sabe-se determinar a subsequência crescente máxima que termina no elemento ik de uma sequência de k inteiros Ik = { i1, i2, ..., ik }.


Responda às questões que se seguem.

  1. Prove os Teoremas 1 e 2 por indução matemática simples.

  2. Explique como conhecer as subsequências de tamanho 1,2,...,n que terminam com o menor inteiro resolve o problema 1.

  3. Mostre como conhecer a maior subsequência crescente que termina em cada elemento da sequência de inteiros permite encontrar a maior subsequência máxima.

  4. Descreva um algoritmo associado à sua prova do Teorema 1 em palavras. Em seguida apresente um pseudo-código para o algoritmo que você descreveu.

  5. Descreva um algoritmo associado à sua prova do Teorema 2 em palavras. Em seguida apresente um pseudo-código para o algoritmo que você descreveu.
Experimentação:

  1. Implemente os seus algoritmos em uma linguagem de programação.

  2. Execute os algoritmos para obter as maiores subsequências crescentes dos conjuntos de inteiros nos arquivos de teste (disponíveis na página web do curso). A especificação dos arquivo de entrada e as saídas desejadas encontram-se mais abaixo.

  3. Determine o tempo de CPU gasto para obter as subsequências crescentes máximas pelos algoritmos (utilize uma função oferecida no ambiente de desenvolvimento).

    Como haverá casos onde o tempo de CPU será muito pequeno, para uma maior precisão, execute o algoritmos tantas vezes quantas sejam necessárias para que o tempo de CPU ultrapasse 5 segundos. Registre o tempo em que o algoritmo terminou sua primeira execução após os 5 segundos de CPU e divida este tempo pelo número de execuções. O valor obtido será o tempo de CPU para ordenar o caso em teste.

    NÃO INCLUA O TEMPO PARA A LEITURA DO ARQUIVO NO TEMPO DE CPU, CONSIDERE SOMENTE O TEMPO PARA A OBTENÇÃO DAS SUBSEQUÊNCIAS MÁXIMAS !!

  4. Prepare uma tabela com os tempos de CPU obtidos para cada tamanho de sequência.
Conclusões

Escreva suas conclusões analisando as provas do teorema apresentadas, os algoritmos codificados e os resultados dos experimentos. Você considera que o algoritmo obtido é eficiente ?

ENTREGA DO TRABALHO

O trabalho pode ser feito em grupos de até 2 (dois) alunos. O trabalho entregue deve conter: Descrição do Arquivo de Entrada

A primeira linha contém um inteiro T contendo o número de inteiros na sequência. Cada um dos T conjuntos inicia com uma identificação I do conjunto na primeira linha, na linha seguinte está o número N de elementos no conjunto, enquanto que as N linhas seguintes contém os inteiros da sequência.

Descrição do Arquivo de Saída

O arquivo de saída contém as informações para a tabela pedida acima. Ou seja, ele possui T linhas, onde cada linha apresenta a identificação I do conjunto, o número N de inteiros no conjuntos e os tempos de CPU para os dois algoritmos.

This document was translated from LATEX by HEVEA.