Marcus Ritt<\/a><\/span><\/p>\nS\u00daMULA
\n<\/strong>Algoritmos, estruturas de dados e t\u00e9cnicas algor\u00edtmicas avan\u00e7adas: algoritmos randomizados, algoritmos de aproxima\u00e7\u00e3o, algoritmos parametrizados.<\/p>\nOBJETIVOS<\/strong>
\nA disciplina objetiva combinar a teoria de algoritmos com a pr\u00e1tica de implementar e aplicar eles. Portanto, o conte\u00fado e apresentado em pares de aulas te\u00f3ricas e pr\u00e1ticas. Nas aulas te\u00f3ricas o funcionamento dos algoritmos \u00e9 explicado, a corretude \u00e9 demonstrada e a complexidade \u00e9 analisada. Nas aulas pr\u00e1ticas os algoritmos s\u00e3o implementados, testados e avaliados. Especialmente, o objetivo da disciplina \u00e9 que os alunos conhecem algoritmos avan\u00e7ados importantes e entendem o funcionamento deles; conhecem estruturas de dados avan\u00e7ados importantes e entendem o funcionamento delas; conhecem t\u00e9cnicas algor\u00edtmicas avan\u00e7adas importantes e sabem aplic\u00e1-las; sabem implementar as estruturas de dados e algoritmos apresentados e s\u00e3o capazes adaptar e aplicar elas a novos problemas.<\/p>\nPROGRAMA<\/strong><\/p>\n\n- Algoritmos avan\u00e7ados polinomiais
\na) Emparelhamento em grafos bi-partidos e grafos gerais
\nb) Fluxo em redes
\n2. Estruturas de dados avan\u00e7ados
\na) Fibonacci heaps e heaps binomiais
\nb) Hashing e filtros de Bloom
\nc) Filas de prioridade
\n3. T\u00e9cnicas algor\u00edtmicas avan\u00e7adas
\na) Algoritmos randomizados
\nb) Algoritmos de aproxima\u00e7\u00e3o
\nc) Algoritmos parametrizados.<\/li>\n<\/ol>\nCRIT\u00c9RIOS DE AVALIA\u00c7\u00c3O<\/strong>
\nO conte\u00fado te\u00f3rico \u00e9 avaliado atrav\u00e9s de uma prova escrita sobre toda mat\u00e9ria. A parte pr\u00e1tica \u00e9 avaliada atrav\u00e9s de trabalhos semanais realizados ao longo da disciplina. A nota final m resulta das notas da prova p e da nota m\u00e9dia de trabalhos t seguindo m = (4p + 6t) \/ 10.
\nO conceito final corresponde \u00e0 nota final e a frequ\u00eancia como segue:
\nA => 9 ? m ? 10 ? f ? 75%
\nB => 7.5 ? m < 9 ? f ? 75%
\nC => 6 ? m < 7.5 ? f ? 75%
\nD => m < 6 ? f ? 75%
\nFF => f < 75%
\nPara ser aprovado \u00e9 necess\u00e1rio obter um conceito final de A, B ou C. Um aluno com conceito final D pode realizar uma \u00fanica prova de recupera\u00e7\u00e3o.<\/p>\nBIBLIOGRAFIA<\/strong>
\n[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
\n[2] Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001.
\n[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation \u2013 Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
\n[4] Vijay V. Vazirani. Approximation algorithms. Springer, 2001.
\n[5] Jon Kleinberg and Eva Tardos. Algorithm design. Addison-Wesley, 2005.
\n[6] Rolf Niedermeier. Invitation to fixed-parameter algorithms. Habilitationsschrift, Universit\u00e4t T\u00fcbingen, WSI f\u00fcr Informatik, Germany, September 2002.
\n[7] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
\n[8] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
\n[9] Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Dover edition, 1982.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
T\u00f3picos Especiais em Computa\u00e7\u00e3o LXXXVIII: Algoritmos avan\u00e7ados Carga hor\u00e1ria \/ cr\u00e9ditos: 60 \/ 4 Pr\u00e9-requisitos: – Semestre oferecido: Primeiro Semestre Respons\u00e1vel: Prof. Dr. Marcus Ritt S\u00daMULA Algoritmos, estruturas de dados e t\u00e9cnicas algor\u00edtmicas avan\u00e7adas: algoritmos randomizados, algoritmos de aproxima\u00e7\u00e3o, algoritmos parametrizados. OBJETIVOS A disciplina objetiva combinar a teoria de algoritmos com a pr\u00e1tica de implementar […]<\/p>\n","protected":false},"author":14,"featured_media":0,"parent":462,"menu_order":588,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/pages\/2887"}],"collection":[{"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/comments?post=2887"}],"version-history":[{"count":3,"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/pages\/2887\/revisions"}],"predecessor-version":[{"id":2890,"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/pages\/2887\/revisions\/2890"}],"up":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/pages\/462"}],"wp:attachment":[{"href":"https:\/\/www.inf.ufrgs.br\/ppgc\/wp-json\/wp\/v2\/media?parent=2887"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}