TP4_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 4 - Erros de Portugueˆs
Introduc¸a˜o
Nas provas de questa˜o discursiva, o professor comec¸ou a perceber uma caracter´ıstica comum
nas respostas: erros de portugueˆs. Ele sempre defendeu que conhecer bem a l´ıngua materna era
algo important´ıssimo para a formac¸a˜o de seus alunos e, por isso, comec¸ou a pensar em formas
de valorizar este aspecto nos testes. Decidiu enta˜o que iria verificar as palavras onde erros eram
cometidos e penalizar o aluno de acordo com o “tamanho” desses erros de grafia. Para medir o
tamanho do erro cometido ele escolheu utilizar uma medida que relacionasse a palavra escrita pelo
aluno em relac¸a˜o a`quela escrita corretamente no diciona´rio, gerando penalizac¸o˜es maiores de acordo
com o quanto a palavra escrita pelo aluno diferisse da forma correta.
Definic¸a˜o do problema
O professor deseja ter um sistema capaz de comparar as respostas dos alunos com um diciona´rio
de palavras aceitas, e produzir com esse sistema uma resposta sem erros e uma pontuac¸a˜o que
quantifique esse erro. A quantificac¸a˜o desse erro dar-se-a´ com penalizac¸o˜es diferentes dependendo
da diferenc¸a entre a palavra escrita pelo aluno e a palavra no diciona´rio. Para medir essa diferenc¸a
o professor tem em mente quatro operac¸o˜es que podem ser realizadas sobre as palavras escritas
pelos alunos para transforma´-las nas palavras corretas:
1. Inserc¸a˜o(custo 1): operac¸a˜o em que um caracter e´ adicionado a` sequeˆncia. Por exemplo: se
a sequeˆncia e´ “calr” a palavra “calor” pode ser gerada por meio da adic¸a˜o do caracter “o” na
quarta posic¸a˜o da sequeˆncia;
2. Remoc¸a˜o(custo 1): operac¸a˜o em que um caracter e´ removido da sequeˆncia. Por exemplo:
se a sequeˆncia e´ “caloor” a palavra “calor” pode ser gerada por meio da remoc¸a˜o do caracter
“o” da quarta posic¸a˜o da sequeˆncia;
3. Substituic¸a˜o(custo 1.5): operac¸a˜o em que um determinado caracter da sequeˆncia e´ sub-
stitu´ıdo por outro. Por exemplo: se a sequeˆncia e´ “capor” a palavra “calor” pode ser gerada
por meio da substituic¸a˜o do caracter “p” pelo caracter “l”;
4. Troca(custo 2): operac¸a˜o em que dois caracteres subsequentes da sequeˆncia teˆm suas posic¸o˜es
trocadas. Por exemplo: se a sequeˆncia e´ “caolr” a palavra “calor” pode ser gerada ao fazer
uma transposic¸a˜o entre os caracteres das posic¸o˜es 3 e 4.
O algoritmo deve indicar qual o custo mı´nimo associado a um conjunto de operac¸o˜es capaz
de transformar as palavras incorretas nas palavras do diciona´rio. Este algoritmo deve ser imple-
mentado em treˆs formas distintas. A primeira de programac¸a˜o dinaˆmica sequencial, a segunda
de programac¸a˜o dinaˆmica com paralelizac¸a˜o de palavras e na terceira as computac¸o˜es dentro do
algoritmo de programac¸a˜o dinaˆmica sa˜o feitas paralelamente:
1
1. Programac¸a˜o Dinaˆmica Sequencial: implementac¸a˜o sequencial do algoritmo por meio do
uso de te´cnicas de programac¸a˜o dinaˆmica;
2. Programac¸a˜o Dinaˆmica com Paralelizac¸a˜o de Palavras: utilizar a mesma imple-
mentac¸a˜o do algoritmo anterior. No entanto, de forma que mais de um par de palavras
possa ser comparado ao mesmo simultaneamente.
3. Programac¸a˜o Dinaˆmica com Computac¸o˜es Paralelas Internas: utilizar paralelizac¸a˜o
em gra˜o fino, ou seja, para processar cada elemento da matriz gerada pelo algoritmo de
programac¸a˜o dinaˆmica. Voceˆ deve desenvolver o algoritmo de forma a executar em paralelo a
computac¸a˜o de todos os itens que sa˜o computa´veis ao mesmo tempo na matriz. Isso significa
que sempre que voceˆ encontrar duas ou mais ce´lulas da matriz que podem ser calculadas
ao mesmo tempo (que sa˜o independentes umas das outras) elas devera˜o ser computadas em
threads separadas.
Dicas:
• Foque em compreender as dependeˆncias de dados que existem para o ca´lculo de cada
um dos pesos propostos, ao compreender a evoluc¸a˜o dessas dependeˆncias voceˆ tera´ uma
noc¸a˜o de como o paralelismo pode ser feito;
• Fazer a paralelizac¸a˜o por linhas ou por colunas traz uma dificuldade intr´ınseca: ce´lulas
dentro de uma linha/coluna dependem de ce´lulas nesta mesma linha/coluna, portanto
este parece na˜o ser um bom caminho para a paralelizac¸a˜o.
E´ importante ressaltar que nesta opc¸a˜o a paralelizac¸a˜o deve ocorrer de qualquer maneira, ou
seja, mesmo que somente um par de palavras seja passado como entrada ela devera´ ter sua
computac¸a˜o paralelizada.
Entrada
A entrada consiste em dois arquivos separados. O primeiro arquivo conte´m um diciona´rio de
palavras escritas corretamente. Elas esta˜o dispostas no arquivo de forma que cada linha conte´m
uma palavra.
O segundo arquivo (chamado ”Respostas”) conte´m as palavras das respostas dos alunos. Cada
linha desse arquivo apresenta os termos na resposta de um aluno. Os termos do aluno esta˜o
separados entre si por um espac¸o em branco.
A seguir temos um exemplo de entrada do programa:
Diciona´rio:
aspecto
matematica
algebra
posicao
profissao
fourier
casa
calculo
dificil
2
Respostas:
aepscto caculo
matmatica augebra caza dificiu
posissao proficao furier cauculo
Cada linha do arquivo de respostas representa apenas um aluno, e pode conter um nu´mero indefinido
de termos. Os termos, tanto nas respostas quanto no diciona´rio, tambe´m podem ter um tamanho
varia´vel, podendo inclusive ser bem maiores que as palavras comumente empregadas em portugueˆs.
A soluc¸a˜o pode assumir que tanto o diciona´rio como um todo quanto cada uma das palavras
nas respostas cabem em memo´ria principal. Na˜o e´ preciso tratar casos com acentos ou cedilhas,
mas letras maiu´sculas devem ser consideradas como diferentes de letras minu´sculas.
Sa´ıda
Devera˜o ser impressas no arquivo de sa´ıda a diferenc¸a total entre as palavras escritas pelos alunos
e as palavras corretas no diciona´rio (considerando que a palavra correta e´ a palavra do diciona´rio
mais pro´xima, com menor custo das operac¸o˜es descritas anteriormente, da palavra escrita pelo
aluno), juntamente com sua distaˆncia para a palavra escrita originalmente, na ordem das palavras
na resposta.
Cada linha da sa´ıda deve apresentar primeiramente a soma dos custos das operac¸o˜es que trans-
formam as palavras da resposta desse aluno na linha correspondente (linha 1 da sa´ıda corresponde a`
linha 1 do arquivo de respostas). Esse valor deve separar-se do restante da linha por ”dois pontos” e
espac¸o. A seguir, nessa linha, devem ser apresentados os termos corretos encontrados no diciona´rio,
juntamente com o custo das operac¸o˜es que separam esse termo do termo dado na resposta; uma
v´ırgula, sem espac¸os, deve separar o termo correto de sua distaˆncia para a palavra na resposta.
Cada termo do diciona´rio e seu valor correspondente devem ser separados dos outros pares na linha
por um espac¸o em branco.
Veja a sa´ıda do exemplo anterior:
Sa´ıda:
4: aspecto,3 calculo,1
5.5: matematica,1 algebra,1.5 casa,1.5 dificil,1.5
7.5: posicao,2.5 profissao,2.5 fourier,1 calculo,1.5
Execuc¸a˜o
O programa gerado deve ter o nome tp4 e aceitar os seguintes argumentos:
./tp4 -a <algoritmo> -t <nu´mero threads> -r <respostas> -d <diciona´rio> -o <saı´da>
Cada flag especifica o argumento que a segue. Os argumentos consistem em:
algoritmo e´ um nu´mero do conjunto {1, 2, 3} onde cada elemento representa o nu´mero do al-
goritmo citado na Sec¸a˜o de Definic¸a˜o do Problema (sequencial, paralelizac¸a˜o de palavras e
paralelizac¸a˜o interna).
3
nu´mero threads Define o nu´mero ma´ximo de threads que o programa pode utilizar simultanea-
mente nos algoritmos paralelos. (esse argumento e´ facultativo quando e´ pedido o algoritmo
sequencial).
respostas Arquivo contendo as respostas do aluno, conforme descrito na Sec¸a˜o Entrada.diciona´rio Arquivo contendo um diciona´rio de termos, conforme descrito na Sec¸a˜o Entrada.
sa´ıda Arquivo em que o programa devera´ escrever a sa´ıda, conforme descrito na Sec¸a˜o Sa´ıda.
4
Entrega
• A data de entrega desse trabalho e´ 24/05/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.
– Na ana´lise do algoritmo paralelo espera-se gra´ficos que apresentem o desempenho em
func¸a˜o do nu´mero de threads, com pelo menos um gra´fico mostrando a variac¸a˜o do
tempo de execuc¸a˜o em func¸a˜o do nu´mero de threads, por exemplo.
• Especificac¸a˜o da(s) ma´quina(s) utilizada(s) nos experimentos realizados.
• Uma breve conclusa˜o do trabalho implementado.
5
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´rio make deve ser utilizado para auxiliar a compilac¸a˜o. Um arquivo Makefile deve
gerar um executa´vel do programa que aceite os comandos e arquivos de entrada discutido
nas sec¸o˜es anteriores. O comando para executar as soluc¸o˜es devera´ seguir o exemplo abaixo,
conforme especificado na Sec¸a˜o Execuc¸a˜o:
./tp4 -a <algoritmo> -t <nu´mero de threads> -r <arquivo de respostas> -d <arquivo de
diciona´rio> -o <arquivo de sa´ıda>
• 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´ obri-
gato´ria a utilizac¸a˜o de me´todos de programac¸a˜o dinaˆmica e paralela.
6