Trabalho Algoritmos I - Modelo de Grafos para Alocação de Vagas de Emprego e Redução do Desemprego

TP2 Desemprego Algoritmos I Data de entrega 02062023 1 Objetivo do trabalho O objetivo deste trabalho e modelar o problema computacional descrito a seguir utilizando estru turas de dados e algoritmos em particular aqueles vistos na disciplina que permitam resolvˆelo de forma eficiente Serao fornecidos alguns casos de teste bem como a resposta esperada dos casos fornecidos para que o aluno possa testar a corretude de seu algoritmo Nao obstante recomendase que o aluno crie casos de teste adicionais a fim de validar sua propria implementacao A sua solucao deve obrigatoriamente ser desenvolvida utilizando algoritmos em grafos e algoritmos gulosos O codigofonte da solucao e uma documentacao sucinta relatorio contendo nao mais do que 5 paginas deverao ser submetidos via Moodle ate a data limite de 02062023 A especificacao do conteudo do relatorio e linguagens de programacao aceitas serao detalhadas nas secoes subsequentes 2 Definicao do problema Willie Gates e o CEO de uma grande rede social chamada LinkOut No entanto a rede esta enfrentando uma grande crise e ele esta buscando maneiras de aumentar o engajamento dos usuarios O principal objetivo da LinkOut e conectar seus usuarios as vagas de emprego ideais Infelizmente Willie esta recebendo muitas reclamacoes de usuarios que nao estao sendo recomendados para nenhuma vaga enquanto seus colegas com qualificacoes semelhantes estao sendo bombardeados com novas vagas Desesperado Willie contatou vocˆe um especialista em algoritmos para desenvolver uma solucao que pudesse garantir vagas para o maximo de usuarios possıvel a fim de evitar os problemas relatados pelos usuarios da rede Felizmente Willie possui um algoritmo muito eficaz que indica se um usuario e apto ou nao para determinada vaga Esses dados podem ser representados como um grafo bipartido onde uma aresta candidatovaga existe se o candidato atende aos requisitos da vaga Preocupado com a rapida queda de usuarios da LinkOut vocˆe sugeriu utilizar uma especie de Proof of Concept para o problema propondo uma abordagem gulosa de baixa complexidade que encontra uma solucao rapidamente Willie aprovou a ideia desde que assim que a solucao gulosa estiver pronta vocˆe tambem implemente um outro algoritmo que sempre encontre a melhor solucao possıvel Sua missao e implementar dois algoritmos que encontrem pares unicos de usuarios e vagas para o maior numero possıvel de usuarios em uma rede Note que a solucao gulosa muitas vezes e subotima e Willie gostaria que vocˆe comparasse ambas solucoes apontando para ele as vantagens e desvantagens de cada algoritmo Pedro André RD CFO CTO SWE CEO Bruno Maria Paulo Figura 1 Wille em busca do aumento de engajamento na sua rede social 1 3 Exemplo do problema 31 Modelagem do problema Este trabalho pratico aborda a parte de grafos e algoritmos gulosos da ementa desta disciplina Para a resolucao do problema a sua modelagem precisa usar ambas tecnicas e deve ser descrita sucintamente no relatorio apresentado 32 Formato da entrada esperada O seu programa devera processar um caso de teste em cada execucao A primeira linha de um cenario de teste e composta de trˆes numero inteiros U J e E representando respectivamente o numero de usuarios 2 U 10000 o numero de ofertas de emprego 1 J 10000 e o numero de qualificacoes usuarioemprego 1 E U J Cada uma das proximas E linhas descreve uma qualificacao usuariovaga representadas pelo nome do usuario seguido pelo nome da vaga obrigatoriamente nessa ordem Os dois identificadores sao representados por strings separados por um espaco simples 33 Formato da saıda esperada Para cada caso de teste seu programa deve imprimir duas linhas A primeira linha deve imprimir o resultado do algoritmo guloso enquanto a segunda linha deve imprimir o resultado do algoritmo exato O output deve usar a saıda padrao e utilizar o seguinte formato Guloso RESULT GREEDY Exato RESULT EXACT 34 Casos de teste Entrada 5 5 9 Andre CFO Bruno RED Bruno SWE Maria CEO Maria CFO Maria CTO Paulo CFO Paulo CTO Pedro RED Saıda Guloso 4 Exato 5 Entrada 5 4 9 Anna software engineer Edsel electrical engineer Edsel senior php developer Edsel software engineer Elisha senior php developer Ethelbert c programmer Ethelbert electrical engineer Santo c programmer Santo electrical engineer Saıda Guloso 4 Exato 4 IMPORTANTE Nos casos de teste o resultado do algoritmo guloso pode variar bastante de acordo com a estrategia adotada Por outro lado a solucao otima exata sera sempre a mesma Serao disponibilizados comandos no Makefile proxima secao para avaliar tanto o algoritmo exato quanto a 2 solucao gulosa proximidade do otimo Encorajamos o estudante a encontrar a melhor aproximacao gulosa possıvel Junto com a descricao do problema disponibilizaremos um conjunto de casos de teste e as solucoes exatas para cada caso de teste 4 Implementacao O seu programa devera ser implementado na linguagem C ou C e devera fazer uso apenas de funcoes da biblioteca padrao da linguagem Nao serao aceitos trabalhos que utilizem qualquer outra linguagem de programacao eou que facam uso de bibliotecas que nao a padrao O aluno pode implementar seu programa em qualquer ambiente Windows Linux MacOS etc no entanto deve garantir que seu codigo compile e rode nas maquinas do DCC tigredccufmgbr ou jaguardccufmgbr ou logindccufmgbr pois sera neste ambiente que o TP sera corrigido Note que essas maquinas sao acessıveis a todos os alunos do DCC com seu login e senha podendo inclusive ser realizado acesso remoto via SSH O aluno pode buscar informacoes no site do CRC Centro de Recursos Computacionais do DCC httpswwwcrcdccufmgbr Para facilitar o desenvolvimento vamos fornecer uma estrutura base de arquivos com Makefile ja configurado A pasta TP02TemplateCPPzip disponıvel para download na tarefa do Moodle contem 2 arquivos maincpp e Makefile O ponto de entrada do seu programa esta no arquivo maincpp Fique a vontade para criar novos arquivos hpp e cpp conforme sua preferˆencia Para compilar seu programa basta executar o comando make no mesmo diretorio que o Makefile esta Ao final deste comando se a compilacao for bem sucedida sera criado um arquivo executavel chamado tp02 Esse arquivo pode ser executado pela linha de comando usando tp02 O arquivo da entrada deve ser passado ao seu programa como entrada padrao atraves da linha de comando eg tp02 casoTeste01txt e gerar o resultado tambem na saıda padrao nao gerar saıda em arquivo Para avaliar automaticamente sua solucao em todos os casos de teste disponibilizados disponibli zamos dois comandos make eval avalia apenas os resultados referentes ao algoritmo exato make eval greedy avalia o quanto o resultado guloso e proximo do otimo Nota Esses comandos foram testados apenas em ambientes Linux 5 O que deve ser entregue Devera ser submetido um arquivo zip contendo apenas uma pasta chamada tp2 esta pasta devera conter i Documentacao em formato PDF e ii Implementacao 51 Documentacao A documentacao deve ser sucinta e nao ultrapassar 5 paginas Vocˆe deve descrever cada solucao do problema de maneira clara e precisa detalhando e justificando os algoritmos e estruturas de dados utilizados Para tal artifıcios como pseudocodigos exemplos ou diagramas podem ser uteis Note que documentar uma solucao nao e o mesmo que documentar seu codigo Nao e necessario incluir trechos de codigo em sua documentacao nem mostrar detalhes de sua implementacao exceto quando estes influenciem o seu algoritmo principal o que se torna interessante E essencial que a documentacao contenha ao menos 1 Identificacao Nome e Matrıcula 2 Introducao Breve resumo do problema com suas palavras 3 Modelagem Modelos adotados bem como detalhamento e justificativa dos algoritmos e estru turas de dados escolhidos E necessario tambem realizar uma analise comparativa dos resultados dos dois algoritmos 3 Observacoes E necessario que vocˆe realize a analise de complexidade do seu codigo no relatorio Solucoes muito lentas eg que executem com tempo superior a 1 segundo por entrada nao serao consideradas uma vez que terao complexidades muito acima da adequada para este problema 52 Implementacao O codigo fonte submetido deve conter todos os arquivos fonte e o Makefile usado para compilar o projeto Lembre que seu codigo deve ser legıvel entao evite variaveis com nomes nao descritivos int a aa aaa e lembrese de comentar seu codigo Ja estamos fornecendo uma implementacao base com os arquivos necessarios entao indicamos que vocˆe so o altere se for necessario 53 Atrasos Trabalhos poderao ser entregues apos o prazo estabelecido porem sujeitos a uma penalizacao regida pela seguinte formula p 2d1 032 1 Nesta formula d representa dias de atraso Por exemplo se a nota dada pelo corretor for 70 e vocˆe entregou o TP com 4 dias corridos de atraso sua penalizacao sera de p 25 e portanto a sua nota final sera Nf 701 p 522 Note que a penalizacao e exponencial e 6 dias de atraso resultam em uma penalizacao de 100 6 Consideracoes finais Assim como em todos os trabalhos desta disciplina e estritamente proibida a copia parcial ou integral de codigos seja da internet ou de colegas Utilizaremos o algoritmo MOSS para deteccao de plagio em trabalhos seja honesto Vocˆe nao aprende nada copiando codigo de terceiros nem pedindo a outra pessoa que faca o trabalho por vocˆe Se a copia for detectada sua nota sera zerada e os professores serao informados para que as devidas providˆencias sejam tomadas 4