{"id":712,"date":"2020-07-29T20:16:08","date_gmt":"2020-07-29T20:16:08","guid":{"rendered":"http:\/\/localhost\/?page_id=712"},"modified":"2022-04-05T07:30:45","modified_gmt":"2022-04-05T10:30:45","slug":"algoritmos-basicos","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/algoritmos-basicos\/","title":{"rendered":"Algoritmos b\u00e1sicos"},"content":{"rendered":"
\n

Ao analisarmos os algoritmos que ocorrem na disciplina, geralmente contamos quantas opera\u00e7\u00f5es precisamos\u00a0 para executar a computa\u00e7\u00e3o. Nosso objetivo aqui n\u00e3o \u00e9 fazer uma an\u00e1lise detalhada da complexidade dos algoritmos. N\u00f3s queremos apenas decidir se um algoritmo pode ser aplicado na pr\u00e1tica para resolver problemas com n\u00fameros grandes.Consideremos um exemplo f\u00e1cil. N\u00fameros ser\u00e3o escritos na base 10. Os algarismos de um n\u00famero $a$ ser\u00e3o denotados por $a_{n-1},a_{n-2},\\ldots,a_1,a_0$. Escrevemos que $a=[a_{n-1}a_{n-2}\\cdots a_1a_0]_{10}$. O comprimento do n\u00famero $a$ \u00e9 o n\u00famero $n$ de algarismos. O comprimento de $a$ ser\u00e1 denotado por $\\mbox{comp}(a)$.<\/p>\n

Assuma que temos dois n\u00fameros $a=[a_{m-1}\\cdots a_1a_0]_{10}$ e $b=[b_{n-1}\\cdots b_1b_0]_{10}$ dados por seus algarismos na base 10. O seguinte algoritmo simples vai calcular as algarismos da soma $c=[c_{m}c_{m-1}\\cdots c_1c_0]_{10}$.<\/p>\n
\nfunction adi\u00e7\u00e3o( list1, list2; base = 10 ) \n    \n    s = []; c = 0;\n    l1, l2 = length( list1 ), length( list2 )\n    for i in 1:max(l1,l2)\n        d = ( i<=l1 ? list1[i] : 0 ) + ( i<=l2 ? list2[i] : 0 ) + c\n        c = d >= base \n        push!( s, d % base )\n    end \n    if c == 1 push!( s, 1 ) end\n    return s\nend \n<\/code><\/pre>\n
Este algoritmo simples tem um la\u00e7o executado por max(l1,l2)<\/code> vezes e cada execu\u00e7\u00e3o do la\u00e7o precisa de um n\u00famero constante de opera\u00e7\u00f5es. Este \u00e9 um algoritmo cuja complexidade \u00e9 polinomial de primeiro grau em termos de $\\mbox{comp}(a)+\\mbox{comp}(b)$ onde $a$ e $b$ s\u00e3o os dois n\u00fameros no input.\n<\/div>\n
\u00c9 similarmente f\u00e1cil verificar que a diferen\u00e7a $a-b$ pode ser calculado usando um constante vezes $\\mbox{comp}(a)+\\mbox{comp}(b)$ opera\u00e7\u00f5es.<\/div>\n
\nConsidere a seguinte algoritmo para a multiplica\u00e7\u00e3o de dois n\u00fameros inteiros.<\/p>\n
\nfunction multiplica\u00e7\u00e3o( list1, list2; base = 10 )\n    res = []; \n    l1, l2 = length( list1 ), length( list2 )\n    for i in 1:l1 \n        pr = zeros( Int64, i-1 )\n        c = 0\n        for j in 1:l2\n            p = list1[i]*list2[j]+c\n            push!( pr, p % base )\n            c = p\u00f7base\n        end\n        if c != 0 push!( pr, c ) end \n        res = adi\u00e7\u00e3o( res, pr )\n    end\n    return res\nend\n<\/code><\/pre>\n
Aqui tem dois la\u00e7os e o n\u00facleo dos la\u00e7os precisa de um n\u00famero constante de opera\u00e7\u00f5es. Al\u00e9m disso, no la\u00e7o exterior fazemos uma chamada para a fun\u00e7\u00e3o adi\u00e7\u00e3o. Pode concluir que o n\u00famero das opera\u00e7\u00f5es que precisamos para executar este algoritmo \u00e9 constante vezes $\\mbox{comp}(a)\\cdot\\mbox{comp}(b)$ onde $a$ e $b$ s\u00e3o os dois n\u00fameros no input.<\/p>\n
Vale a pena mencionar que dois n\u00fameros naturais de comprimento menor ou igual a $n$ podem ser multiplicadas usando o Algoritmo Sch\u00f6nhage-Strassen<\/a> que precisa de constante vezes $n\\log n\\log\\log n$ opera\u00e7\u00f5es.\n<\/div>\n
Nos dois casos anteriores, o n\u00famero de opera\u00e7\u00f5es que precisamos para executar o algoritmo foi polinomial no comprimento do input. No primeiro caso, foi polinomial do primeiro grau, e no segundo caso foi polinomial do segundo grau. Algoritmos polinomiais de pequeno grau (menor ou igual a 3 ou 4) s\u00e3o considerados algoritmos pr\u00e1ticos. Quando o input do algoritmo \u00e9 um n\u00famero natural $n$, ent\u00e3o seu comprimento \u00e9 $\\log n$. <\/p>\n
\nConsidere a seguinte fun\u00e7\u00e3o para determinar se um n\u00famero \u00e9 primo ou n\u00e3o.<\/p>\n
\nfunction \u00e9_primo( n )\n    \n    for i in 2:floor(sqrt(n))\n        if n % i == 0 \n            return false\n        end\n    end \n    \n    return true\nend \n<\/code><\/pre>\n
Neste caso o comprimento do input\u00a0 \u00e9 $m\\sim \\log_{10}n$ mas o algoritmo precisa executar o la\u00e7o cerca de
\n\\[
\n\\sqrt n=(10^{\\log_{10}n})^{1\/2}\\sim 10^{m\/2}
\n\\]
\nvezes para verificar se um n\u00famero \u00e9 primo. Portanto este algoritmo \u00e9 um algoritmo exponencial e n\u00e3o pode ser considerado como um algoritmo pr\u00e1tico. De fato, o algoritmo n\u00e3o vai funcionar com n\u00fameros de 100-200 algarismos, enquanto n\u00fameros deste tamanho s\u00e3o comuns em problemas computacionais.<\/p>\n<\/div>\n
Um dos algoritmos mais importantes na nossa disciplina \u00e9 baseado no seguinte teorema.<\/p>\n
(Teorema de Divis\u00e3o de Euclides)\u00a0Sejam $a,b\\in\\mathbb Z$ e assuma que $b\\neq 0$. Ent\u00e3o existem unicamente n\u00fameros $q,r\\in \\mathbb Z$ tais que
\n\\[
\na=qb+r\\qquad\\mbox{e}\\qquad 0\\leq r<|b|.
\n\\]<\/div>\n
O n\u00fameros $q$ e $r$ s\u00e3o chamados de quociente<\/em> e resto<\/em>.<\/p>\n
\nAssumimos sem perder generalidade que $b>0$. Se $b$ for negativo, fazemos o argumento com $-b$ a trocaremos o sinal do quociente $q$.<\/p>\n
Exist\u00eancia.<\/strong> Seja $q$ o maior n\u00famero tal que $qb\\leq a$ e seja $r=a-qb$. Temos claramente que $a=qb+r$. Al\u00e9m disso, $r\\geq 0$. Se $r\\geq b$, ent\u00e3o $r-b\\geq 0$ e $r-b=a-(q+1)b\\geq 0$ que implica que $(q+1)b\\leq a$. Mas isso contradiz \u00e0 suposi\u00e7\u00e3o que $q$ foi escolhido maior poss\u00edvel. Portanto temos que $0\\leq r<b$.<\/p>\n
Unicidade.\u00a0<\/strong>Assuma que $a=q_1b+r_1=q_2b+r_2$\u00a0 com $0\\leq r_1,r_2<b$. Ent\u00e3o
\n\\[
\n(q_1-q_2)b=r_2-r_1.
\n\\]
\nTemos por um lado que o lado esquerdo da \u00faltima equa\u00e7\u00e3o \u00e9 um divisor de $b$. Por outro lado, o lado direito satisfaz $-b<r_2-r_1<b$. O \u00fanico divisor de $b$ que est\u00e1 no intervalo aberto $(-b,b)$ \u00e9 o zero, e assim obtemos que o n\u00famero representado pela equa\u00e7\u00e3o em cima precisa ser igual a zero. Isso implica que $r_1=r_2$ e que $(q_1-q_2)b=0$. Como $b\\neq 0$, obtemos\u00a0 que $q_1=q_2$. Portanto $q_1=q_2$ e\u00a0 $r_1=r_2$; ou seja, a decomposi\u00e7\u00e3o de $a$ na forma $qb+r$ \u00b4\u00e9 \u00fanica.<\/p>\n<\/div>\n
O quociente e o resto podem ser calculados com o seguinte algoritmo que deve ser familiar j\u00e1 do ensino fundamental.<\/p>\n
\nfunction div_resto( a, b )\n        \n    d = length( digits( a )) - length( digits( b ))\n    q = []\n    r = a\n    for i in d:-1:0\n        push!( q, floor( r\u00f7(10^i*b)))\n        r -= 10^i*q[end]*b\n        i -= 1\n    end\n    return q, r\nend \n<\/code><\/pre>\n
O algoritmo usado na fun\u00e7\u00e3o anterior \u00e9 pr\u00e1tico, pois o la\u00e7o \u00e9 executado length(a)-length(b)=length(q)<\/code> vezes. Al\u00e9m disso, dentro do la\u00e7o a opera\u00e7\u00e3o dominante \u00e9 computar 10^i*q[end]*b<\/code> que precisa de constante vezes length(b)<\/code> opera\u00e7\u00f5es. Portanto, o n\u00famero de opera\u00e7\u00f5es necess\u00e1rio para este algoritmo \u00e9 constante vezes length(b)*length(q)<\/code> (onde q<\/code> \u00e9 o quociente) e assim o algoritmo pode ser considerado pr\u00e1tico.<\/p>\n","protected":false},"excerpt":{"rendered":"
Ao analisarmos os algoritmos que ocorrem na disciplina, geralmente contamos quantas opera\u00e7\u00f5es precisamos\u00a0 para executar a computa\u00e7\u00e3o. Nosso objetivo aqui n\u00e3o \u00e9 fazer uma an\u00e1lise detalhada da complexidade dos algoritmos. N\u00f3s queremos apenas decidir se um algoritmo pode ser aplicado na pr\u00e1tica para resolver problemas com n\u00fameros grandes.Consideremos um exemplo f\u00e1cil. N\u00fameros ser\u00e3o escritos na … Continue reading Algoritmos b\u00e1sicos<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/712"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=712"}],"version-history":[{"count":16,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/712\/revisions"}],"predecessor-version":[{"id":1719,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/712\/revisions\/1719"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=712"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}