Trabalho Prático 3

Universidade Federal de Minas Gerais
ˆ
Departamento de Ciencia da Computacao
¸˜
Algoritmos e Estruturas de Dados III
Primeiro Semestre de 2014

Trabalho Pr´tico 3 - Facilitando a Corre¸˜o a ca

Introdu¸˜o ca Ap´s aplicar a prova surpresa (descrita no TP2), o professor decidiu punir aqueles alunos que o 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 quest˜o discursiva. Nessa quest˜o, o aluno deveria a a escrever um texto extenso e detalhado para responder o que era pedido. Ap´s a aplica¸˜o da prova, o ca o professor digitalizou as respostas dos alunos para facilitar a corre¸˜o, removendo os acentos, ca pontua¸˜es, artigos e preposi¸˜es. co co
Ele decidiu ordenar as palavras das respostas de todos os alunos em um unico arquivo, com
´
o n´mero da chamada de cada aluno que utilizou aquela palavra em sua resposta. Entretanto, u ao abrir os arquivos com as respostas, o professor percebeu que essa ordena¸˜o n˜o poderia ser ca a realizada internamente, pois os arquivos eram maiores do que sua mem´ria interna. o Defini¸˜o do problema ca O que o professor pretende realizar ´ um ´ e ındice invertido dos termos nas respostas dos alunos.
Um ´ ındice invertido ´ uma estrutura de dados para indexar uma cole¸˜o de documentos, semelhante e ca ao ´ ındice remissivo encontrado em muitos livros did´ticos, em que tem-se para cada palavra uma a lista de p´ginas que cobrem aquele assunto. a Para o presente trabalho os termos nas respostas de cada aluno formam um documento da , em que a ´ um identificador do documento, referente ao aluno. A cole¸˜o D ´ o conjunto de documentos e ca e passados como entrada ao algoritmo.
Para produzir o ´ ındice invertido ´ preciso saber quais s˜o os termos no conjunto de documentos, e a o vocabul´rio, e orden´-los. E ´ preciso saber para quais alunos as respostas