{"id":10,"date":"2017-10-05T13:37:52","date_gmt":"2017-10-05T16:37:52","guid":{"rendered":"http:\/\/www.professores.uff.br\/dartigas\/?p=10"},"modified":"2020-09-02T12:15:02","modified_gmt":"2020-09-02T15:15:02","slug":"analise-e-projeto-de-algoritmos","status":"publish","type":"post","link":"https:\/\/www.professores.uff.br\/dartigas\/2017\/10\/05\/analise-e-projeto-de-algoritmos\/","title":{"rendered":"An\u00e1lise e Projeto de Algoritmos"},"content":{"rendered":"<hr \/>\n<p><strong>Provas<\/strong><\/p>\n<p><em>2014\/1<\/em><\/p>\n<ul>\n<li>P1 &#8211; 30\/04<\/li>\n<li>P2 &#8211; 30\/05<\/li>\n<li>VS &#8211; 06\/06<\/li>\n<\/ul>\n<hr \/>\n<p>Bibliografia<\/p>\n<p>Livro texto:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-11\" src=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/download.png\" alt=\"\" width=\"251\" height=\"250\" srcset=\"https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/download.png 251w, https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/download-150x150.png 150w\" sizes=\"auto, (max-width: 251px) 100vw, 251px\" \/><\/p>\n<p>Literatura complementar:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-12\" src=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/Screenshot-4.png\" alt=\"\" width=\"607\" height=\"415\" srcset=\"https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/Screenshot-4.png 607w, https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/Screenshot-4-300x205.png 300w\" sizes=\"auto, (max-width: 607px) 100vw, 607px\" \/><\/p>\n<p>Fundamentos<\/p>\n<p>Para aprender a tratar rela\u00e7\u00f5es de recorr\u00eancia recomendo a leitura do livro:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-13\" src=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/ArquivoExibir.jpg\" alt=\"\" width=\"292\" height=\"292\" srcset=\"https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/ArquivoExibir.jpg 292w, https:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/ArquivoExibir-150x150.jpg 150w\" sizes=\"auto, (max-width: 292px) 100vw, 292px\" \/><\/p>\n<hr \/>\n<p>Algumas rela\u00e7\u00f5es de recorr\u00eancia podem ser resolvidas utilizando o <a href=\"https:\/\/en.wikipedia.org\/wiki\/Master_theorem\" target=\"_blank\" rel=\"noopener noreferrer\">Teorema Mestre<\/a>.<\/p>\n<p>Uma ferramenta interessante para a solu\u00e7\u00e3o de rela\u00e7\u00f5es de recorr\u00eancia \u00e9 o Wolphram Alpha.<\/p>\n<p><iframe loading=\"lazy\" src=\"http:\/\/www.wolframalpha.com\/Calculate\/embed\/largeannot.jsp\" width=\"532\" height=\"56\" frameborder=\"0\" marginwidth=\"0\" data-mce-fragment=\"1\"><\/iframe><\/p>\n<p>Ne ferrramenta acima copie e cole a equa\u00e7\u00e3o: T(n) = 2*T(n\/2) + n, T(1) = 1<\/p>\n<p>Esta \u00e9 a rel\u00e7\u00e3o de recorr\u00eancia do n\u00famero de passos do merge sort e, como esperado, o resultado \u00e9 O(n.logn)<\/p>\n<p>De uma forma geral, \u00e9 necess\u00e1rio definir a rela\u00e7\u00e3o de recorr\u00eancia e os casos base, separados por v\u00edrgula.<\/p>\n<p>Na verdade, esta ferramenta \u00e9 extremamente poderosa e \u00e9 capaz de resolver v\u00e1rios outros tipos de problemas. Ainda no contexto deste curso, experimente as duas perguntas abaixo:<\/p>\n<p>is P in NP?<br \/>\nis NP in P?<\/p>\n<p>Os resultados foram os esperados?<\/p>\n<hr \/>\n<p><strong>Exerc\u00edcios<\/strong><\/p>\n<p><em>Listas de exerc\u00edcios<\/em>: <a id=\"APA-L1\" href=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/APA_L1.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">Lista 1<\/a>, <a id=\"APA-L2\" href=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/APA_L2.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">Lista 2<\/a>,<\/p>\n<p>Os exerc\u00edcios mencionados abaixo s\u00e3o dos sites UVa ou URI. Clique <a href=\"http:\/\/www.professores.uff.br\/dartigas\/iniciando-no-uri-e-no-uva\/\" target=\"_blank\" rel=\"noopener noreferrer\">aqui<\/a> para uma breve introdu\u00e7\u00e3o sobre como utilizar estes sites.<\/p>\n<div>\n<ul>\n<li>\u00a0\u00a0\u00a0 Divis\u00e3o e Conquista<\/li>\n<\/ul>\n<p>No UVa: <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1998\" target=\"_blank\" rel=\"noopener noreferrer\">11057<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1508\" target=\"_blank\" rel=\"noopener noreferrer\">10567<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=3344\" target=\"_blank\" rel=\"noopener noreferrer\">12192<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1282\" target=\"_blank\" rel=\"noopener noreferrer\">10341<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2408\" target=\"_blank\" rel=\"noopener noreferrer\">11413<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=3183\" target=\"_blank\" rel=\"noopener noreferrer\">12032<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=119\" target=\"_blank\" rel=\"noopener noreferrer\">183<\/a><\/p>\n<ul>\n<li>\u00a0\u00a0\u00a0\u00a0 Guloso<\/li>\n<\/ul>\n<p>No UVa: <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2231\" target=\"_blank\" rel=\"noopener noreferrer\">11264<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2384\" target=\"_blank\" rel=\"noopener noreferrer\">11389<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=3836\" target=\"_blank\" rel=\"noopener noreferrer\">12405<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2041\" target=\"_blank\" rel=\"noopener noreferrer\">11100<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2267\" target=\"_blank\" rel=\"noopener noreferrer\">11292<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=3362\" target=\"_blank\" rel=\"noopener noreferrer\">12210<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1597\" target=\"_blank\" rel=\"noopener noreferrer\">10656<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1659\" target=\"_blank\" rel=\"noopener noreferrer\">10718<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2098\" target=\"_blank\" rel=\"noopener noreferrer\">11157<\/a><\/p>\n<ul>\n<li>\u00a0\u00a0\u00a0\u00a0\u00a0 Programa\u00e7\u00e3o din\u00e2mica<\/li>\n<\/ul>\n<p>No UVa: <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=293\" target=\"_blank\" rel=\"noopener noreferrer\">357<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1247\" target=\"_blank\" rel=\"noopener noreferrer\">10306<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2512\" target=\"_blank\" rel=\"noopener noreferrer\">11517<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1557\" target=\"_blank\" rel=\"noopener noreferrer\">10616<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1760\" target=\"_blank\" rel=\"noopener noreferrer\">10819<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2613\">11566<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=422\" target=\"_blank\" rel=\"noopener noreferrer\">481<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2451\" target=\"_blank\" rel=\"noopener noreferrer\">11456<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=728\" target=\"_blank\" rel=\"noopener noreferrer\">787<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1625\" target=\"_blank\" rel=\"noopener noreferrer\">10684<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=44\">108<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1768\" target=\"_blank\" rel=\"noopener noreferrer\">10827<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=3102\">11591<\/a><\/p>\n<ul>\n<li>\u00a0\u00a0\u00a0\u00a0\u00a0 Backtracking<\/li>\n<\/ul>\n<p>No UVa:\u00a0<a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=565\" target=\"_blank\" rel=\"noopener noreferrer\">624<\/a>,\u00a0<a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1517\" target=\"_blank\" rel=\"noopener noreferrer\">10576<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=2026\" target=\"_blank\" rel=\"noopener noreferrer\">11085<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=465\" target=\"_blank\" rel=\"noopener noreferrer\">524<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=515\" target=\"_blank\" rel=\"noopener noreferrer\">574<\/a>, <a href=\"http:\/\/uva.onlinejudge.org\/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=24&amp;page=show_problem&amp;problem=1444\" target=\"_blank\" rel=\"noopener noreferrer\">10503<\/a><\/p>\n<hr \/>\n<p><strong>Trabalho<br \/>\n<\/strong><br \/>\nClique <a id=\"PD-code\" href=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/PD.zip\" target=\"_blank\" rel=\"noopener noreferrer\">aqui<\/a> para obter os c\u00f3digos das aulas de PD.<\/p>\n<p>O primeiro aluno que consertar o c\u00f3digo de mochila-bu.cpp ganhar\u00e1 um ponto na pr\u00f3xima prova. \u00c9 importante enviar o c\u00f3digo corrigido, com o erro comentado.<\/p>\n<p>Os alunos que entregarem os programas do <a id=\"trab-implementacao\" href=\"http:\/\/www.professores.uff.br\/dartigas\/wp-content\/uploads\/sites\/156\/2017\/10\/Trabalho-implementacao1401.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">trabalho de implementa\u00e7\u00e3o<\/a>, at\u00e9 \u00e0s 10:00hs do dia 30\/05, tamb\u00e9m ganham 1 ponto.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Provas 2014\/1 P1 &#8211; 30\/04 P2 &#8211; 30\/05 VS &#8211; 06\/06 Bibliografia Livro texto: Literatura complementar: Fundamentos Para aprender a tratar rela\u00e7\u00f5es de recorr\u00eancia recomendo a leitura do livro: Algumas rela\u00e7\u00f5es de recorr\u00eancia podem ser resolvidas utilizando o Teorema Mestre. Uma ferramenta interessante para a solu\u00e7\u00e3o de rela\u00e7\u00f5es de recorr\u00eancia \u00e9 o Wolphram Alpha. Ne [&hellip;]<\/p>\n","protected":false},"author":22,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-10","post","type-post","status-publish","format-standard","hentry","category-cursos"],"_links":{"self":[{"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/posts\/10","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":2,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":21,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/posts\/10\/revisions\/21"}],"wp:attachment":[{"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.professores.uff.br\/dartigas\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}