{"id":4104,"date":"2019-07-08T10:36:36","date_gmt":"2019-07-08T13:36:36","guid":{"rendered":"http:\/\/www.inf.ufrgs.br\/profcomp\/?page_id=4104"},"modified":"2019-12-13T15:40:38","modified_gmt":"2019-12-13T18:40:38","slug":"cmp605","status":"publish","type":"page","link":"https:\/\/www.inf.ufrgs.br\/profcomp\/lista-de-disciplinas\/cmp605\/","title":{"rendered":"CMP605"},"content":{"rendered":"

T\u00f3picos Especiais em Computa\u00e7\u00e3o DCV – T\u00f3picos selecionados em Otimiza\u00e7\u00e3o Combinat\u00f3ria<\/strong><\/p>\n

Professor respons\u00e1vel: Marcus Ritt
\nCarga Hor\u00e1ria: 30 horas
\n2 cr\u00e9ditos
\nOferecimento: Segundo Semestre
\nMatr\u00edcula de Graduandos: INF05504<\/p>\n

* S\u00famula
\nT\u00f3picos selecionados em otimiza\u00e7\u00e3o combinat\u00f3ria focando no volume 4B do livro “The Art of Computer Programming” incluindo algoritmos de backtracking, estruturas de dados eficientes para backtracking, busca combinatorial para problemas de cobertura simples, e com cores e multiplicidade, t\u00e9cnicas de pr\u00e9-processamente, e t\u00e9cnicas para resolver de satisfatibilidade. (Mais informa\u00e7\u00f5es em http:\/\/www.inf.ufrgs.br\/~mrpritt\/doku.php?id=inf5504:homepage ).<\/p>\n

* Objetivos
\nAo final da disciplina espera-se que o aluno
\n– conhe\u00e7a m\u00e9todos e algoritmos de estado de arte em t\u00f3picos selecionados em busca combinat\u00f3ria em otimiza\u00e7\u00e3o combinat\u00f3ria.
\n– saiba aplicar as t\u00e9cnicas a problemas pr\u00e1ticos.
\n* Conte\u00fado Program\u00e1tico<\/p>\n

** Semana 1: Introdu\u00e7\u00e3o: Contextualiza\u00e7\u00e3o e vis\u00e3o geral de m\u00e9todos e algoritmos de estado de arte em otimiza\u00e7\u00e3o combinat\u00f3ria.<\/p>\n

** Semanas 2 e 3: Contextualiza\u00e7\u00e3o<\/p>\n

    \n
  1. Revis\u00e3o de conceitos matem\u00e1ticos: vari\u00e1veis aleat\u00f3rias, probabilidades, probabilidades condicionais, desigualdades de Markov, Chernoff, Jensen, martingales, coeficientes binomiais, n\u00fameros harm\u00f4nicas de Fibonacci.<\/li>\n<\/ol>\n
      \n
    1. Revis\u00e3o de conceitos de an\u00e1lise e projeto de algoritmos: t\u00e9cnicas de an\u00e1lise, solu\u00e7\u00e3o de recorr\u00eancias e fun\u00e7\u00f5es geradoras, nota\u00e7\u00e3o assint\u00f3tica, programa\u00e7\u00e3o din\u00e2mica.<\/li>\n<\/ol>\n
        \n
      1. Revis\u00e3o de conceitos de otimiza\u00e7\u00e3o combinat\u00f3ria: programa\u00e7\u00e3o linear e inteira, dualidade.<\/li>\n<\/ol>\n

        ** Semana 4: Semi\u00e1rio 1: algoritmos de backtracking<\/p>\n

          \n
        1. O algoritmo b\u00e1sico de backtracking.<\/li>\n
        2. Estruturas de dados.<\/li>\n
        3. Algoritmo para gerar pares de Langford.<\/li>\n
        4. C\u00f3digos “commafree”.<\/li>\n
        5. Estimar o tempo de execu\u00e7\u00e3o.<\/li>\n<\/ol>\n

          ** Semana 5: Semin\u00e1rio 2: Busca combinatorial 1<\/p>\n

            \n
          1. Opera\u00e7\u00e3o elementar de liga\u00e7\u00f5es dan\u00e7antes.<\/li>\n
          2. Problemas de cobertura exata.<\/li>\n
          3. Algoritmo para resolver problemas de cobertura exata com liga\u00e7\u00f5es dan\u00e7antes.<\/li>\n<\/ol>\n

            ** Semana 6: Semin\u00e1rio 3: Busca combinatorial 2<\/p>\n

              \n
            1. Itens secund\u00e1rios em problemas de cobertura exata.<\/li>\n
            2. Solu\u00e7\u00e3o de Sudokus.<\/li>\n
            3. Probemas com polyominoes.<\/li>\n
            4. A fatora\u00e7\u00e3o de um problema de cobertura exata.<\/li>\n<\/ol>\n

              ** Semana 7: Semin\u00e1rio 4: Busca combinatorial 3<\/p>\n

                \n
              1. Cobertura exata com cores.<\/li>\n
              2. Multiplicidade em problemas de cobertura.<\/li>\n
              3. Cobertura exata com cores e multiplicidades.<\/li>\n<\/ol>\n

                ** Semana 8: Semin\u00e1rio 5: Busca combinatorial 4<\/p>\n

                  \n
                1. An\u00e1lise de algoritmo para problemas de cobertura exata com cores e multiplicidades.<\/li>\n
                2. T\u00e9cnicas para focar em problemas de busca.<\/li>\n
                3. T\u00e9cnicas para aproveitar equival\u00eancias locais.<\/li>\n
                4. T\u00e9cnicas de pr\u00e9-processamento.<\/li>\n<\/ol>\n

                  ** Semana 9: Semin\u00e1rio 6: Busca combinatorial 5<\/p>\n

                    \n
                  1. M\u00e9todos para encontrar solu\u00e7\u00f5es de menor custo.<\/li>\n
                  2. Implementa\u00e7\u00e3o de cortes de menor custo.<\/li>\n
                  3. Liga\u00e7\u00f5es dan\u00e7antes com ZDDs (zero-suppressed decision diagram).<\/li>\n<\/ol>\n

                    ** Semana 10: Semin\u00e1rio 7: Satisfatibilidade 1<\/p>\n

                      \n
                    1. Introdu\u00e7\u00e3o \u00e0 satisfatibilidade.<\/li>\n
                    2. Problemas de cobertura e colora\u00e7\u00e3o.<\/li>\n
                    3. Aplica\u00e7\u00f5es: fatora\u00e7\u00e3o, teste, aprendizagem de fun\u00e7\u00f5es booleanas, verifica\u00e7\u00e3o de modelos (model checking), tomografia digital.<\/li>\n<\/ol>\n

                      ** Semana 11: Semin\u00e1rio 8: Satisfatibilidade 2<\/p>\n

                        \n
                      1. Solu\u00e7\u00e3o de SAT bom backtracking.<\/li>\n
                      2. Estuturas de dados pregui\u00e7osas.<\/li>\n
                      3. Satisfatibilidade por observa\u00e7\u00e3o.<\/li>\n
                      4. Satisfatibilidade com DPLL.<\/li>\n<\/ol>\n

                        * Metodologia<\/p>\n

                        Aulas te\u00f3ricas-expositivas, exerc\u00edcios individuais e em classe, trabalhos individuais com apresenta\u00e7\u00e3o e discuss\u00e3o em aula.<\/p>\n

                        Carga Hor\u00e1ria
                        \n– Te\u00f3rica: 25 horas
                        \n– Pr\u00e1tica: 5 horas
                        \n* Experi\u00eancias de Aprendizagem<\/p>\n

                        Aulas te\u00f3ricas-expositivas, exerc\u00edcios individuais e em classe, trabalhos individuais com apresenta\u00e7\u00e3o e discuss\u00e3o em aula. Est\u00e3o previstas Atividades Aut\u00f4nomas do Aluno com uma carga hor\u00e1ria de 5 (cinco) horas-aula a serem desenvolvidas ao longo do semestre. As atividades previstas podem incluir: realiza\u00e7\u00e3o de temas e trabalhos, leitura de texto (cap\u00edtulos de livros ou artigos), resolu\u00e7\u00e3o de listas de exerc\u00edcios entre outras.<\/p>\n

                        * Crit\u00e9rios de Avalia\u00e7\u00e3o
                        \nOs estudantes ser\u00e3o avaliados pela apresenta\u00e7\u00e3o de um t\u00f3pico selecionado em um dos semin\u00e1rios (nota S) e a solu\u00e7\u00e3o de uma lista de exerc\u00edcios correspondentes ao t\u00f3pico (nota T).
                        \nA m\u00e9dia final \u00e9 M=(S+T)\/2.
                        \nO conceito final corresponde com a nota final e a frequ\u00eancia f como segue:
                        \nConceito final=
                        \nA, caso 9<=m<=10 e f>=75%
                        \nB, caso 7.5<=m<9 e f>=75%
                        \nC, caso 6<=m<7.5 e f>=75%
                        \nD, caso m<6 e f>=75%
                        \nFF, caso f<75%
                        \nPara ser aprovado \u00e9 necess\u00e1rio obter um conceito final de A,B ou C.<\/p>\n

                        * Atividades de Recupera\u00e7\u00e3o Previstas
                        \nAlunos que receberam um conceito D podem recuperar a nota atrav\u00e9s de uma prova oral sobre o conte\u00fado do t\u00f3pico selecionado.
                        \nUm aluno com conceito final D pode realizar uma \u00fanica prova oral de recupera\u00e7\u00e3o sobre a mat\u00e9ria do t\u00f3pico selecionado. Pr\u00e9-requisito para realiza\u00e7\u00e3o da prova de recupera\u00e7\u00e3o \u00e9 uma frequ\u00eancia de 75% ou maior e ter apresentando o t\u00f3pico selecionado em aula.
                        \nN\u00e3o h\u00e1 recupera\u00e7\u00e3o das provas e nem dos trabalhos por n\u00e3o comparecimento\/entrega, exceto nos casos previstos na legisla\u00e7\u00e3o (sa\u00fade, parto, servi\u00e7o militar, convoca\u00e7\u00e3o judicial, luto, etc.), sendo necess\u00e1ria a devida comprova\u00e7\u00e3o por parte do aluno e a aprova\u00e7\u00e3o pela inst\u00e2ncia respons\u00e1vel dentro da universidade.
                        \n* Prazo para Divulga\u00e7\u00e3o dos Resultados das Avalia\u00e7\u00f5es
                        \nO resultado de cada avalia\u00e7\u00e3o ser\u00e1 disponibilizado 15 dias \u00fateis ap\u00f3s do prazo de entrega.<\/p>\n","protected":false},"excerpt":{"rendered":"

                        T\u00f3picos Especiais em Computa\u00e7\u00e3o DCV – T\u00f3picos selecionados em Otimiza\u00e7\u00e3o Combinat\u00f3ria Professor respons\u00e1vel: Marcus Ritt Carga Hor\u00e1ria: 30 horas 2 cr\u00e9ditos Oferecimento: Segundo Semestre Matr\u00edcula de Graduandos: INF05504 * S\u00famula T\u00f3picos selecionados em otimiza\u00e7\u00e3o combinat\u00f3ria focando no volume 4B do livro “The Art of Computer Programming” incluindo algoritmos de backtracking, estruturas de dados eficientes para […]<\/p>\n","protected":false},"author":14,"featured_media":0,"parent":462,"menu_order":605,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4104"}],"collection":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/comments?post=4104"}],"version-history":[{"count":1,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4104\/revisions"}],"predecessor-version":[{"id":4105,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4104\/revisions\/4105"}],"up":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/462"}],"wp:attachment":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/media?parent=4104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}