Algoritmos básicos

Ao analisarmos os algoritmos que ocorrem na disciplina, geralmente contamos quantas operações precisamos  para executar a computação. Nosso objetivo aqui não é fazer uma análise detalhada da complexidade dos algoritmos. Nós queremos apenas decidir se um algoritmo pode ser aplicado na prática para resolver problemas com números grandes.Consideremos um exemplo fácil. Números serão escritos na base 10. Os algarismos de um número $a$ serão 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úmero $a$ é o número $n$ de algarismos. O comprimento de $a$ será denotado por $\mbox{comp}(a)$.

Assuma que temos dois números $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}$. 

function adição( list1, list2; base = 10 ) 
    
    s = []; c = 0;
    l1, l2 = length( list1 ), length( list2 )
    for i in 1:max(l1,l2)
        d = ( i<=l1 ? list1[i] : 0 ) + ( i<=l2 ? list2[i] : 0 ) + c
        c = d >= base 
        push!( s, d % base )
    end 
    if c == 1 push!( s, 1 ) end
    return s
end

Este algoritmo simples tem um laço executado por max(l1,l2) vezes e cada execução do laço precisa de um número constante de operações. Este é um algoritmo cuja complexidade é polinomial de primeiro grau em termos de $\mbox{comp}(a)+\mbox{comp}(b)$ onde $a$ e $b$ são os dois números no input.

É similarmente fácil verificar que a diferença $a-b$ pode ser calculado usando um constante vezes $\mbox{comp}(a)+\mbox{comp}(b)$ operações.
Considere a seguinte algoritmo para a multiplicação de dois números inteiros. 

function multiplicação( list1, list2; base = 10 )
    res = []; 
    l1, l2 = length( list1 ), length( list2 )
    for i in 1:l1 
        pr = zeros( Int64, i-1 )
        c = 0
        for j in 1:l2
            p = list1[i]*list2[j]+c
            push!( pr, p % base )
            c = p÷base
        end
        if c != 0 push!( pr, c ) end 
        res = adição( res, pr )
    end
    return res
end

Aqui tem dois laços e o núcleo dos laços precisa de um número constante de operações. Além disso, no laço exterior fazemos uma chamada para a função adição. Pode concluir que o número das operações que precisamos para executar este algoritmo é constante vezes $\mbox{comp}(a)\cdot\mbox{comp}(b)$ onde $a$ e $b$ são os dois números no input.

Vale a pena mencionar que dois números naturais de comprimento menor ou igual a $n$ podem ser multiplicadas usando o Algoritmo Schönhage-Strassen que precisa de constante vezes $n\log n\log\log n$ operações.

Nos dois casos anteriores, o número de operações 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ão considerados algoritmos práticos. Quando o input do algoritmo é um número natural $n$, então seu comprimento é $\log n$.

Considere a seguinte função para determinar se um número é primo ou não. 

function é_primo( n )
    
    for i in 2:floor(sqrt(n))
        if n % i == 0 
            return false
        end
    end 
    
    return true
end

Neste caso o comprimento do input  é $m\sim \log_{10}n$ mas o algoritmo precisa executar o laço cerca de
\[
\sqrt n=(10^{\log_{10}n})^{1/2}\sim 10^{m/2}
\]
vezes para verificar se um número é primo. Portanto este algoritmo é um algoritmo exponencial e não pode ser considerado como um algoritmo prático. De fato, o algoritmo não vai funcionar com números de 100-200 algarismos, enquanto números deste tamanho são comuns em problemas computacionais.

Um dos algoritmos mais importantes na nossa disciplina é baseado no seguinte teorema.

(Teorema de Divisão de Euclides) Sejam $a,b\in\mathbb Z$ e assuma que $b\neq 0$. Então existem unicamente números $q,r\in \mathbb Z$ tais que
\[
a=qb+r\qquad\mbox{e}\qquad 0\leq r<|b|.
\]

O números $q$ e $r$ são chamados de quociente e resto.

Assumimos sem perder generalidade que $b>0$. Se $b$ for negativo, fazemos o argumento com $-b$ a trocaremos o sinal do quociente $q$.

Existência. Seja $q$ o maior número tal que $qb\leq a$ e seja $r=a-qb$. Temos claramente que $a=qb+r$. Além disso, $r\geq 0$. Se $r\geq b$, então $r-b\geq 0$ e $r-b=a-(q+1)b\geq 0$ que implica que $(q+1)b\leq a$. Mas isso contradiz à suposição que $q$ foi escolhido maior possível. Portanto temos que $0\leq r<b$.

Unicidade. Assuma que $a=q_1b+r_1=q_2b+r_2$  com $0\leq r_1,r_2<b$. Então
\[
(q_1-q_2)b=r_2-r_1.
\]
Temos por um lado que o lado esquerdo da última equação é um divisor de $b$. Por outro lado, o lado direito satisfaz $-b<r_2-r_1<b$. O único divisor de $b$ que está no intervalo aberto $(-b,b)$ é o zero, e assim obtemos que o número representado pela equação 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  que $q_1=q_2$. Portanto $q_1=q_2$ e  $r_1=r_2$; ou seja, a decomposição de $a$ na forma $qb+r$ ´é única.

O quociente e o resto podem ser calculados com o seguinte algoritmo que deve ser familiar já do ensino fundamental.


function div_resto( a, b )
        
    d = length( digits( a )) - length( digits( b ))
    q = []
    r = a
    for i in d:-1:0
        push!( q, floor( r÷(10^i*b)))
        r -= 10^i*q[end]*b
        i -= 1
    end
    return q, r
end

O algoritmo usado na função anterior é prático, pois o laço é executado length(a)-length(b)=length(q) vezes. Além disso, dentro do laço a operação dominante é computar 10^i*q[end]*b que precisa de constante vezes length(b) operações. Portanto, o número de operações necessário para este algoritmo é constante vezes length(b)*length(q) (onde q é o quociente) e assim o algoritmo pode ser considerado prático.