TP3_2014_1

Prévia do material em texto

Universidade Federal de Minas Gerais
Departamento de Cieˆncia da Computac¸a˜o
Algoritmos e Estruturas de Dados III
Primeiro Semestre de 2014
Trabalho Pra´tico 3 - Facilitando a Correc¸a˜o
Introduc¸a˜o
Apo´s aplicar a prova surpresa (descrita no TP2), o professor decidiu punir aqueles alunos que
participavam de um grupo de troca de respostas. Para isso, ele aplicou uma prova com o objetivo
de substituir a primeira prova da disciplina.
Essa prova era composta apenas de uma questa˜o discursiva. Nessa questa˜o, o aluno deveria
escrever um texto extenso e detalhado para responder o que era pedido. Apo´s a aplicac¸a˜o da prova,
o professor digitalizou as respostas dos alunos para facilitar a correc¸a˜o, removendo os acentos,
pontuac¸o˜es, artigos e preposic¸o˜es.
Ele decidiu ordenar as palavras das respostas de todos os alunos em um u´nico arquivo, com
o nu´mero da chamada de cada aluno que utilizou aquela palavra em sua resposta. Entretanto,
ao abrir os arquivos com as respostas, o professor percebeu que essa ordenac¸a˜o na˜o poderia ser
realizada internamente, pois os arquivos eram maiores do que sua memo´ria interna.
Definic¸a˜o do problema
O que o professor pretende realizar e´ um ı´ndice invertido dos termos nas respostas dos alunos.
Um ı´ndice invertido e´ uma estrutura de dados para indexar uma colec¸a˜o de documentos, semelhante
ao ı´ndice remissivo encontrado em muitos livros dida´ticos, em que tem-se para cada palavra uma
lista de pa´ginas que cobrem aquele assunto.
Para o presente trabalho os termos nas respostas de cada aluno formam um documento da, em
que a e´ um identificador do documento, referente ao aluno. A colec¸a˜o D e´ o conjunto de documentos
passados como entrada ao algoritmo.
Para produzir o ı´ndice invertido e´ preciso saber quais sa˜o os termos no conjunto de documentos,
o vocabula´rio, e ordena´-los. E e´ preciso saber para quais alunos as respostas conte´m os termos
desejados, as ocorreˆncias.
Para gerar essas informac¸o˜es basta produzir uma representac¸a˜o intermedia´ria do conjunto de
documentos. Essa representac¸a˜o intermedia´ria e´ formada por tuplas < t, a >, em que t ∈ da e´ um
termo pertencente a uma resposta do aluno a. Essas tuplas esta˜o ordenadas por t e, em caso de
empate, por a. Uma vez que se tem essa lista ordenada de tuplas basta percorreˆ-la uma vez para
produzir um ı´ndice invertido dos termos.
O algoritmo para produzir o ı´ndice invertido a partir de uma colec¸a˜o de documentos e´ descrito
no Algoritmo 1.
Esse algoritmo resolve o problema da construc¸a˜o do ı´ndice invertido. No entanto, e´ importante
que se note que no presente trabalho, e na maioria das vezes em que se enfrenta esse problema nos
casos reais, a lista L e´ grande demais para se ter em memo´ria, o que impossibilita sua ordenac¸a˜o
utilizando apenas a memo´ria interna. Nesse trabalho sera´ preciso enta˜o utilizar um algoritmo de
ordenac¸a˜o externa para ordenar essa lista e assim produzir o ı´ndice invertido.
1
Algorithm 1: Construc¸a˜o do I´ndice Invertido
Input: colec¸a˜o de documentos D
Output: ı´ndice invertido I
L← inicializa lista;
for da ∈ D do
for t ∈ da do
adiciona < t, a > no final de L
end
end
ordena L; for < t, a >∈ L, na ordem do
if < t, a > diferente da tupla anterior na lista then
if t na˜o pertence ao vocabula´rio do ı´ndice invertido then
escreve t no ı´ndice invertido I;
end
escreve a no ı´ndice invertido I;
end
end
Repare que o Algoritmo 1 tambe´m garante que as ocorreˆncias no ı´ndice tambe´m estara˜o orde-
nadas e que um aluno na˜o aparece como ocorreˆncia de um termo mais de uma vez, mesmo que um
termo se repita na resposta desse aluno.
Entrada
O arquivo de testes conte´m apenas uma instaˆncia. Em cada linha do arquivo estara´ o nu´mero
de chamada do aluno e o texto da sua resposta em seguida, separados por um espac¸o em branco.
Ou seja, em uma determinada linha estara´ o nu´mero a, que representa o aluno a e o texto de sua
resposta.
A seguir temos um exemplo de entrada do programa:
Entrada:
1 livro precederam
1 quadros verdadeira
2 historia verdadeira
3 ignoro confidencia livro
4 quadros sombrear
5 quadros fantasias
Nesse exemplo o aluno 1 respondeu: livro precederam quadros verdadeira. O aluno 2 respondeu:
historia verdadeira, e assim por diante.
Repare que nada impede que um arquivo de entrada contenha duas ou mais linhas com termos
diferentes e um mesmo nu´mero de chamada do aluno que as identifica, este caso na˜o representa
nenhum caso especial para o algoritmo descrito na Sec¸a˜o anterior.
Sa´ıda
Devera˜o ser impressas no arquivo de sa´ıda as palavras ordenadas e separadas por uma quebra
de linha. Ale´m disso, na frente de cada palavra devera´ aparecer o nu´mero de chamada de cada
aluno que utilizou aquela palavra em sua resposta.
2
Veja a sa´ıda do exemplo anterior:
Sa´ıda:
confidencia 3
fantasias 5
historia 2
ignoro 3
livro 1 3
precederam 1
quadros 1 4 5
sombrear 4
verdadeira 1 2
Execuc¸a˜o
O programa gerado deve ter o nome tp3 e aceitar os seguintes argumentos:
./tp3 -o <arquivo de saı´da> -m <tamanho da memo´ria> <arquivo(s) de entrada>...
O arquivo de sa´ıda contera´ o ı´ndice invertido como descrito na Sec¸a˜o anterior. O tamanho da
memo´ria e´ a quantidade de memo´ria principal, em bytes, dispon´ıvel para o programa como um
todo. Tanto o arquivo de sa´ıda quanto o tamanho de memo´ria devem vir logo depois de suas flags
identificadoras na linha de comando, -o e -m, respectivamente.
O programa deve ainda receber um ou mais arquivos de entrada. Os arquivos de entrada na˜o
sa˜o precedidos por nenhuma flag na linha de comando.
A colec¸a˜o D e´ formada por todos os arquivos de entrada. O motivo pelo qual o programa deve
aceitar mu´ltiplos arquivos de entrada e´ que a entrada pode ser grande demais para ser eficientemente
manipulada em um arquivo u´nico.
3
Entrega
• A data de entrega desse trabalho e´ 29/04/2014.
• A penalizac¸a˜o por atraso obedece a` seguinte fo´rmula 2d−1/0.32%, onde d sa˜o os dias u´teis de
atraso.
• Submeta apenas um arquivo chamado <numero matricula> <nome>.zip. Na˜o utilize espac¸os
no nome do arquivo. Ao inve´s disso utilize o caractere ‘ ’.
• Na˜o inclua arquivos compilados ou gerados por IDEs. Apenas os arquivos abaixo devem
estar presentes no arquivo zip.
– Makefile
– Arquivos fonte (*.c e *.h)
– Documentacao.pdf
• Na˜o inclua nenhuma pasta. Coloque todos os arquivos na raiz do zip.
• Siga rigorosamente o formato do arquivo de sa´ıda descrito na especificac¸a˜o. Tome cuidado
com whitespaces e formatac¸a˜o dos dados de sa´ıda
• NA˜O SERA´ NECESSA´RIO ENTREGAR DOCUMENTAC¸A˜O IMPRESSA!
• Sera´ adotada me´dia harmoˆnica entre as notas da documentac¸a˜o e da execuc¸a˜o, o que
implica que a nota final sera´ 0 se uma das partes na˜o for apresentada.
Documentac¸a˜o
A documentac¸a˜o na˜o deve exceder 10 pa´ginas e deve conter pelo menos os seguintes itens:
• Uma introduc¸a˜o do problema em questa˜o.
• Modelagem e soluc¸a˜o proposta para o problema. O algoritmo deve ser explicado de
forma clara, possivelmente atrave´s de pseudo-co´digo e esquemas ilustrativos.
• Ana´lise de complexidade de tempo e espac¸o da soluc¸o implementada.
• Experimentos variando-se o tamanho da entrada e quaisquer outros paraˆmetros que afetem
significativamente a execuc¸a˜o.
– Espera-se a utilizac¸a˜o de tabelas e gra´ficos, com suas respectivas ana´lises.
– Espera-se ao menos um gra´fico de tamanho de entrada X numero de acessos ao disco e
tempo de sistema.
• Especificac¸a˜o da(s) ma´quina(s) utilizada(s) nos experimentos realizados.
• Uma breve conclusa˜o do trabalho implementado.
4
Co´digo
• O co´digo deve ser obrigatoriamente escrito na linguagem C. Ele deve compilar e executar
corretamente nas ma´quinas Linux dos laborato´rios de graduac¸a˜o.
• O utilita´riomake deve ser utilizado para auxiliar a compilac¸a˜o, um arquivo Makefile deve
gerar um executa´vel que devera´ obrigatoriamente ser capaz de receber o nome do arquivo
de sa´ıda e a quantidade principal dispon´ıvel para a execuc¸a˜o do programa, bem como uma
lista de arquivos de entrada. O comando para executar as soluc¸o˜es devera˜o seguir o exemplo
abaixo:
./tp3 -o <arquivo de saı´da> -m <tamanho da memo´ria> <arquivo(s) de entrada>...
• As estruturas de dados devem ser alocadas dinamicamente e o co´digo deve ser modular-
izado (divisa˜o em mu´ltiplos arquivos fonte e uso de arquivos cabec¸alho .h)
• Varia´veis globais devem ser evitadas.
• Parte da correc¸a˜o podera´ ser feita de forma automatizada, portanto siga rigorosamente os
padro˜es de sa´ıda especificados, caso contra´rio sua nota pode ser prejudicada.
• Legibilidade e boas pra´ticas de programac¸a˜o sera˜o avaliadas.
• Para este trabalho e´ obrigato´ria a utilizac¸a˜o de me´todos de ordenac¸a˜o externa.
• Para a correc¸a˜o deste trabalho, ale´m da ana´lise do co´digo, o comando Ulimit sera´ utilizado
para verificar a utilizac¸a˜o de memo´ria.
5