TP3-Algoritmos-I-Otimizacao-de-Distribuição-de-Ligas-Metálicas-com-Programacao-Dinâmica

TP3 Centro de distribuicao Algoritmos I Data de entrega 02072023 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 programacao dinˆamica 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 02072023 A especificacao do conteudo do relatorio e linguagens de programacao aceitas serao detalhadas nas secoes subsequentes 2 Definicao do problema Parte 1 Programacao dinˆamica Vocˆe trabalha em um centro de distribuicao de uma fabrica de ligas metalicas e com seu conhe cimento em algoritmos esta pensando em otimizar o processo de distribuicao Cada fabrica produz ligas metalicas de diferentes tamanhos em metros e os clientes tambem fazem a solicitacao de ligas em metros ex 1000 metros em ligas O papel do centro de distribuicao e separar as encomendas de cada cliente para o despache da transportadora Para otimizar tempo e recursos e interessante que o numero de ligas usadas para suprir uma demanda seja a mınima possıvel levando em conta os tamanhos de liga disponıveis no momento Por exemplo se um cliente precisa de 40 metros de ligas e o centro de distribuicao contem os tamanhos 1 5 10 20 25 o numero mınimo de ligas que podem ser usadas e 2 Figura 1 Caminhao saindo do centro de distribuicao com 2 ligas metalicas de 20 metros para atender o pedido do cliente de 40 metros de ligas 1 Parte 2 NPCompletude Apos alcancar sucesso com o seu algoritmo no centro de distribuicao regional vocˆe tornouse amplamente reconhecido dentro da empresa e a sua solucao inovadora chegou aos ouvidos do presidente da companhia que ficou encantado com o algoritmo desenvolvido Agora ele quer que vocˆe teste o mesmo algoritmo em uma escala muito maior o centro de distribuicao global onde as demandas dos clientes sao significativamente maiores e os tipos de produtos sao mais diversos Ao receber uma amostra das demandas dos clientes para teste vocˆe percebeu que o algoritmo estava levando consideravelmente mais tempo para ser executado Apos realizar algumas pesquisas descobriuse que o problema em questao e classificado como NPcompleto Vocˆe deve escrever um relatorio ressaltando a complexidade do algoritmo fornecido no item anterior em funcao do tamanho da entrada em bits e provando que o problema em questao se trata de um problema NPcompleto 3 Exemplo do problema 31 Modelagem do problema Este trabalho pratico aborda a parte de programacao dinˆamica e NPcompletude da ementa desta disciplina Para a resolucao do problema a sua modelagem precisa usar usar programacao dinˆamica e a solucao deve ser descrita sucintamente no relatorio apresentado 32 Formato da entrada esperada O seu programa devera processar varios casos de teste em uma execucao A primeira linha de um cenario de teste e composta por um inteiro T que representa o numero de casos de teste no arquivo Cada caso de teste possui duas linhas de informacoes A primeira linha e composta por dois numero inteiros N e W representando respectivamente o numero de tipos de ligas metalicas disponıvel 1 N 1000 e a demanda do cliente em metros 1 W 1000000 A segunda linha de um caso de teste contem N inteiros representando o tamanho li de cada liga metalica disponıvel 1 li 1000 Vocˆe pode assumir que sempre havera estoque de ligas metalicas de tamanho 1 33 Formato da saıda esperada Para cada caso de teste seu programa deve o numero mınimo de ligas metalicas para suprir uma demanda de tamanho W 34 Casos de teste Entrada 3 6 126 1 5 10 15 25 50 5 40 1 5 10 20 25 2 103 1 5 Saıda 4 2 23 Junto com a descricao do problema disponibilizaremos um conjunto de casos de teste e as solucoes exatas para cada caso de teste 2 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 TP03TemplateCPPzip 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 tp03 Esse arquivo pode ser executado pela linha de comando usando tp03 O arquivo da entrada deve ser passado ao seu programa como entrada padrao atraves da linha de comando eg tp03 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 disponibili zamos o comando make eval que avalia seu algoritmo em todos os casos de teste disponibilizados Nota o comando de avaliacao foi testado apenas em ambientes Linux 5 O que deve ser entregue Devera ser submetido um arquivo zip contendo apenas uma pasta chamada tp3 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 Detalhamento da implementacao do problema usando programacao dinˆamica 4 Analise de Complexidade e NPCompletude Analise de complexidade do problema e reducao de um problema NPCompleto dica esse e um problema pseudopolinomial em que o seu tempo de execucao e polinomial no valor numerico da entrada mas e exponencial no comprimento da entrada o numero de bits necessarios para representalo Observacoes Solucoes muito lentas nao serao consideradas uma vez que terao complexidades muito acima da adequada para este problema 3 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