<jupyter_start><jupyter_text>1. Indução e Projeto de Algoritmos 1.1. Prova por InduçãoTécnicas de demonstração por indução possuem grande importância na área de Ciência da Computação, pois permitem o desenvolvimento de um raciocínio construtivo que evidencia os passos necessários para a construção da solução de determinados problemas. Desta forma, além de serem úteis para provarmos teoremas, podem ser utilizadas para formularmos procedimentos **recursivos** e **indutivos**.Existem, basicamente, dois tipos de indução: **fraca** e **forte**. Ambos tipos seguem os seguintes passos durante o desenvolvimento de uma prova:1. Base2. Hipótese de indução3. Passo de indução- Príncipio da indução fraca: sejam $P_n$ afirmações que podem ser verdadeiras ou falsas associadas à cada inteiro positivo $n\geq k$. Se $P_k$ é verdadeira e, para cada inteiro positivo $j\geq k$, se $P_j$ é verdadeira, então $P_{j+1}$ também o é. Assim sendo, $P_n$ é verdadeira para todo inteiro positivo $n\geq k$.- Princípio da indução forte: para alguns problemas, para provarmos que $P_{j+1}$ é verdadeira, temos que assumir a veracidade de toda $P_i$, $k\leq i\leq j$. Assim, novamente, vamos assumir que tenhamos $P_n$ afirmações que podem ser verdadeiras ou falsas associadas a cada inteiro positivo $n\geq k$. Se $P_k$ é verdadeira e, para cada inteiro positivo $j\geq k$, se $P_k,P_{k+1}\ldots,P_j$ são verdadeiras, então $P_{j+1}$ também o é. Assim sendo, $P_n$ é verdadeira para todo inteiro positivo $n\geq k$.Vejamos, agora, um exemplo de prova por **indução fraca**. Prove que a seguinte inequalidade é verdadeira:\begin{equation}\tag{1}\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{2^n}<1\ \ \ \ \ \text{    para }n\geq1.\end{equation}1. Primeiro, vamos provar a **base**, ou seja, vamos provar que a inequalidade é verdadeira para $n=1$. Neste caso, temos que $\frac{1}{2}<1$, ou seja, a afirmação é verdadeira.2. O segundo passo consiste em assumir que a **hipótese** é verdadeira, ou seja, a inequalidade dada pela Equação 1 é verdadeira.3. Em seguida, utilizando a hipótese de indução, provamos que a inequalidade acima é valida para $n+1$, ou seja, temos que provar que $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{2^{n+1}}<1$. Temos, então, que:\begin{equation}\tag{2}\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{2^{n+1}} < 1,\end{equation}que pode ser também escrita da seguinte forma:\begin{equation}\tag{3}\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots+\frac{1}{2^n}+\frac{1}{2^{n+1}} < 1.\end{equation}Reescrevendo a Equação 3, temos que:\begin{align}\tag{4}\frac{1}{2}+\frac{1}{2}\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^n}\right) &< 1 \\\frac{1}{2}\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^n}\right) &< 1-\frac{1}{2} \\\frac{1}{2}\left(\frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^n}\right) &< \frac{1}{2} \\\end{align}Agora, suponha $x = \frac{1}{2}+\frac{1}{4}+\ldots+\frac{1}{2^n}$ de tal forma que a Equação 4 possa ser escrita da seguinte forma:\begin{equation}\tag{5}\frac{1}{2}x < \frac{1}{2}.\end{equation}Por hipótese de indução, temos que $x<1$. Desta forma, a Equação 5 é verdadeira, como queríamos demonstrar.Vejamos um outro exemplo de prova por **indução fraca**. Vamos provar que a seguinte equação é verdadeira:\begin{equation}\tag{6}1+2+3+\ldots+n = \frac{n(n+1)}{2}\ \ \ \ \ \text{    para }n\geq1.\end{equation}1. Base: para $n=1$, temos que $1 = \frac{1+1}{2} = \frac{2}{2}$. Portanto, a base é verdadeira.2. Hipótese de indução: vamos assumir que a Equação 6 é verdadeira para $n\geq 1$.3. Passo de indução: vamos provar que a Equação 6 é válida para $n+1$. Assim sendo, temos que:\begin{equation}\tag{7}1+2+3+\ldots+(n+1) = \frac{(n+1)((n+1)+1)}{2}\ \ \ \ \ \text{    para }n\geq1.\end{equation}A Equação 7 pode ser reescrita da seguinte maneira:\begin{align}\tag{8}1+2+3+\ldots+n+(n+1) &= \frac{n(n+1)}{2}+(n+1)\\&=\frac{n(n+1)+2(n+1)}{2}\\&=\frac{(n+1)(n+2)}{2}\\&=\frac{(n+1)((n+1)+1)}{2}.\end{align}Assim sendo, provamos o passo de indução.Vejamos, agora, um exemplo de prova por **indução forte**. Seja a sequência $a_1,a_2,a_3,\ldots,a_n$ tal que $a_1 = 0$, $a_2 = 0$ e $a_k = 3a_{\lfloor k/2\rfloor}+2$ para $k\geq 3$. Prove que $a_n$ é par para $n \geq 1$.1. Base: para $n=1$ e $n=2$ a base é verdadeira já que $a_1 = 0$ e $a_2 = 0$.2. Hipótese de indução: vamos supor que $a_k$ é par para $1\leq k<n$.3. Vamos provar que $a_n$ é par. Pela definição acima, temos que $a_n=3a_{\lfloor n/2\rfloor}+2$. Pela hipótese de indução, temos que o temos $a_{\lfloor n/2\rfloor}$ é par. Assim, o termo $3a_{\lfloor n/2\rfloor}$ também é par, ou seja, a multiplicação de um número ímpar por um número par resulta em um outro número par. Dado que o termo $3a_{\lfloor n/2\rfloor}$ é par, temos que $3a_{\lfloor n/2\rfloor}+2$ também é par. Assim sendo, provamos que $a_n$ é par para $n\geq 3$.  1.2. Projeto de Algoritmos por InduçãoPodemos fazer uso das técnicas de prova por indução para projetar algoritmos visando a resolução de diversos problemas, isto é, o desenvolvimento do algoritmo será dado de maneira análoga ao desenvolvimento de uma demonstração por indução. A complexidade final é dada por meio de uma análise de recorrência.O projeto de algoritmos por indução resulta em soluções recursivas, em que:- A base de indução corresponde ao critério de parada do algoritmo.- A aplicação da hipótese de indução corresponde às chamadas recursivas.- O passo de indução corresponde ao processo de obtenção da resposta final, ou seja, solução do algoritmo.Como benefício imediato, temos que o uso correto da técnica nos dá uma prova de corretude do algoritmo.Vejamos um exemplo de projeto de algoritmos por indução. Suponha o seguinte problema: dada uma sequência de números reais $a_n,a_{n-1},a_{n-2},\ldots,a_1,a_0$ e um número real $x$, calcular o valor do seguinte polinômio:\begin{equation}\tag{9}P_n(x) = a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.\end{equation}Como vimos anteriormente, podemos demonstrar que conseguimos resolver o problema acima da seguinte maneira:1. Base: Neste caso, temos que $n=0$ e a solução do problema seria $a_0$.2. Hipótese de indução: suponha que consigamos calcular $P_{n-1}(x)$.3. Passo de indução: para calcular $P_n(x)$ basta realizarmos a seguinte operação: $P_n(x) = P_{n-1}(x)+a_nx^n$.Pronto, o algoritmo está projetado conforme os passos que aprendemos em uma demonstração por indução. Basta, agora, implementarmos a solução acima conforme o seguinte algoritmo:<jupyter_code>import numpy
import math
def P_n(A, n, x):
    
    if n == 0: # Caso base
        return A[0]
    else:
        tmp = A[n]*math.pow(x, n)
        
        return tmp + P_n(A, n-1, x) # Hipótese de indução<jupyter_output><empty_output><jupyter_text>Exemplo de funcionamento:<jupyter_code>n = 4
x = 2
A = numpy.random.randint(0, 10, n+1)
print('Vetor de entrada: '+ str(A))
out = P_n(A, n, x)
print('Resultado: '+ str(out))<jupyter_output>Vetor de entrada: [9 4 7 0 6]
Resultado: 141.0<jupyter_text>Vamos agora, calcular a complexidade de nossa solução acima. Como temos um algoritmos recursivo, podemos fazer uso da análise de recorrência, como apresentado abaixo:\begin{equation}\tag{10}T(n) =    \begin{cases}      1 & \text{se $n=0$}\\      T(n-1) + f(n)& \text{caso contrário,}    \end{cases}  \end{equation}em que $f(n)$ corresponde ao número de multiplicações e adições. Em nosso caso, o residual $f(n)$ corresponde à linha do algoritmo acima ``tmp = A[n]*math.pow(x, n)``, em que temos $n+1$ multiplicações. Ademais, devemos considerar a adição realizada na hipótese de indução na linha ``return tmp + P_n(A, n-1, x)``. Em suma, temos $n+1$ multiplicações e uma operação de adição.Podemos, então, reescrever a Equação 10 da seguinte forma:\begin{equation}\tag{11}T(n) =    \begin{cases}      1 & \text{se $n=0$}\\      T(n-1) + [(n+1) \text{ multiplicações} + 1 \text{ adição}]& \text{caso contrário.}    \end{cases}  \end{equation}Mais especificamente, temos que:\begin{align}\tag{12}T(n) & = \sum_{i=1}^n [(n+1) \text{ multiplicações} + 1 \text{ adição}]\\    &= \sum_{i=1}^n [(n+1) \text{ multiplicações}] + \sum_{i=1}^n 1 \text{ adição}\\    &= \sum_{i=1}^n [(n+1) \text{ multiplicações}] + n\text{ adições}\\    &= \sum_{i=1}^n [n \text{ multiplicações}] + \sum_{i=1}^n [1 \text{ multiplicação}] + n\text{ adições}\\    &= \sum_{i=1}^n [n \text{ multiplicações}] + n \text{ multiplicações} + n\text{ adições}\\    &=\frac{n(n+1)}{2}+n \text{ multiplicações} + n\text{ adições}.\end{align}  No entanto, conseguimos melhorar essa complexidade assumindo uma hipótese de indução "mais forte". Suponha, agora, que saibamos calcular $P_{n-1}(x)$ e também o valor de $x^{n-1}$. Neste caso, o caso base $n=0$ possui como solução o par $(a_0,1)$. Desta forma, temos uma segunda versão de nosso algoritmo:<jupyter_code>def P_n2(A, n, x):
    
    if n == 0: # Caso base
        return (A[0], 1)
    else:
        
        (tmp_P, tmp_x) = P_n2(A, n-1, x)
        x_n = x*tmp_x
        
        return (tmp_P + A[n]*x_n, x_n) # Hipótese de indução<jupyter_output><empty_output><jupyter_text>Exemplo de funcionamento:<jupyter_code>print('Vetor de entrada: '+ str(A))
(out, tmp) = P_n2(A, n, x)
print('Resultado: '+ str(out))<jupyter_output>Vetor de entrada: [9 4 7 0 6]
Resultado: 141<jupyter_text>O próximo passo consiste na análise da complexidade de nossa segunda solução. Temos, agora, a seguinte relação de recorrência:\begin{equation}\tag{13}T(n) =    \begin{cases}      1 & \text{se $n=0$}\\      T(n-1) + [2\text{ multiplicações} + 1\text{ adição}]& \text{caso contrário.}    \end{cases}  \end{equation}A solução da recorrência é dada por:\begin{align}\tag{14}T(n) &= \sum_{i=1}^n [2\text{ multiplicações} + 1\text{ adição}]\\    &= 2\sum_{i=1}^n [1\text{ multiplicação}] + \sum_{i=1}^n [1\text{ adição}]\\    &= 2n \text{ multiplicações} + n \text{ adições}.\end{align}Temos, ainda, uma terceira solução, que envolve uma hipótese de indução **ainda mais forte**. Suponha, agora, que consigamos calcular $P^\prime_{n-1}(x)=a_nx^{n-1}+a_{n-1}x^{n-2}+\ldots+a_1$. Note que $P_n(x) = xP^\prime_{n-1}(x)+a_0$.Temos que o caso base $n=0$ para a abordagem acima é trivial, ou seja, $a_0 = 0$. O algoritmo para essa terceira versão é dado como segue:<jupyter_code>def P_n3(A, n, x):
    
    if n == 0: # Caso base
        return A[0]
    else:
        tmp_P = P_n3(A, n-1, x)      
        
        return x*tmp_P + A[0] # Hipótese de indução<jupyter_output><empty_output><jupyter_text>Exemplo de funcionamento:<jupyter_code>print('Vetor de entrada: '+ str(A))
out = P_n3(A, n, x)
print('Resultado: '+ str(out))<jupyter_output>Vetor de entrada: [9 4 7 0 6]
Resultado: 279
{'fraction_non_alphanumeric': 0.15679639029892836, 'fraction_numerical': 0.03102086858432036, 'mean_word_length': 4.444728761514841, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '512396', 'license': 'Apache-2.0', 'n_tokens_mistral': 4342, 'n_tokens_neox': 4215, 'n_words': 1253, 'path': 'complexidade_algoritmos/aula_inducao_projeto_algoritmos/induction_design_algorithm.ipynb', 'repo_name': 'jppbsi/lectures', 'size': '10638'}