Apostila Prog Estatistica (Apostila R)

  • Published on
    03-Mar-2016

  • View
    24

  • Download
    0

DESCRIPTION

programao estatistica no R

Transcript

  • Apostila de Programacao Estatstica

    Jessica Kubrusly

    Departamento de EstatsticaInstituto de Matematica e Estatstica

    Universidade Federal Fluminenes

    marco de 2013

  • Prefacio

    Esta apostila foi desenvolvia com o objetivo de se tornar um roteiro de aula para a disci-plina Programacao Estatstica, oferecida aos alunos do curso de Graduacao em Estatsticapelo Departamento de Estatstica da Universidade Federal Fluminense - UFF.

    A disciplina de Programacao Estatstica e constituda por uma aula teorica e duaspraticas por semana. Cada captulo desta apostila aborda o conteudo trabalhado em cadasemana. Alem disso a apostila e separada em 3 partes. Ao final de cada parte os alunossao submetidos a uma prova teorica e uma prova pratica. O foco da disciplina e praticartecnicas de programacao usando a linguagem de programacao R e tendo como plano defundo conceitos de estatstica descritiva, algebra linear basica e calculo.

    O aluno matriculado nessa disciplina ja foi aprovado em uma disciplina introdutoriasobre programacao de computadores e por isso este nao e o seu primeiro contato como assunto. Ao final desta disciplina espera-se que o aluno tenha nao so aprimorado suahabilidade computacional como tambem reforcado conceitos de estatstica e calculo javistos em outras disciplinas.

    Para maiores informacoes sobre a linguagem de programacao R entre no site oficialdo projeto: http://www.r-project.org/. La e possvel obter informacoes sobre comobaixar e instalar o R em seu computador. Alem disso, manuais introdutorios sao dispo-nibilizados gratuitamente.

    i

  • Sumario

    Prefacio i

    I Conceitos Basicos de Programacao 1

    1 Objetos e Classes 21.1 Numeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Textos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Logicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.5 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.6 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    2 Controle de Fluxo 102.1 if/else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 repeat/break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

    3 Funcoes e o Conceito de Variavel Local 183.1 Funcoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Variaveis Locais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

    4 Algoritmos para CalculosEstatsticos 264.1 Maximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2 Mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3 Media . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.4 Mediana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.5 Quartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.6 Frequencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.7 Moda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.8 Amplitude Total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.9 Distancia Interquartlica . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.10 Variancia Amostral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.11 Desvio Medio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    ii

  • Sumario

    4.12 Covariancia Amostral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    5 Algoritmos para CalculosMatriciais 375.1 Multiplicacao de vetor por escalar . . . . . . . . . . . . . . . . . . . . . . 375.2 Soma entre vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.3 Subtracao entre vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4 Produto interno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.5 Multiplicacao de matriz por escalar . . . . . . . . . . . . . . . . . . . . . 395.6 Soma entre matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.7 Subtracao entre Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.8 Transposicao de Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.9 Multiplicacao entre matriz e vetor . . . . . . . . . . . . . . . . . . . . . . 415.10 Multiplicacao entre matrizes . . . . . . . . . . . . . . . . . . . . . . . . . 42Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    II Recursao 45

    6 Algoritmos Recursivos 466.1 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.2 Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.3 Sequencias Definidas a partir de

    Equacoes de Diferencas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.3.1 Padroes geometricos . . . . . . . . . . . . . . . . . . . . . . . . . 486.3.2 Matematica Financeira . . . . . . . . . . . . . . . . . . . . . . . . 496.3.3 Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    7 Algoritmos Recursivos(continuacao) 567.1 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567.2 Maior Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577.3 Torre de Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

    8 Algoritmos de Ordenacao 638.1 Ordenacao Bolha (Bubble Sort) . . . . . . . . . . . . . . . . . . . . . . . 638.2 Ordenacao Rapida (Quick Sort) . . . . . . . . . . . . . . . . . . . . . . . 67Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

    9 Complexidade deAlgoritmos 729.1 Nocao Introdutoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729.2 A Notacao O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739.3 Exemplos Basicos de Complexidade . . . . . . . . . . . . . . . . . . . . . 74

    9.3.1 Complexidade Constante - O(1) . . . . . . . . . . . . . . . . . . . 749.3.2 Complexidade Logartmica- O(log(n)) . . . . . . . . . . . . . . . 74

    Departamento de Estatstica - UFF iii

  • Sumario

    9.3.3 Complexidade Linear - O(n) . . . . . . . . . . . . . . . . . . . . . 749.3.4 Complexidade n log(n) - O(n log(n)) . . . . . . . . . . . . . . . . 749.3.5 Complexidade quadratica - O(n2) . . . . . . . . . . . . . . . . . . 759.3.6 Complexidade cubica - O(n3) . . . . . . . . . . . . . . . . . . . . 759.3.7 Complexidade exponencial - O(cn) . . . . . . . . . . . . . . . . . 75

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

    III Uma Introducao ao Calculo Numerico 79

    10 Aproximacao de Funcoes porSeries de Taylor 8010.1 Serie de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010.2 Aproximacao para a funcao exponencial . . . . . . . . . . . . . . . . . . 8110.3 Aproximacao para a funcao logaritmo . . . . . . . . . . . . . . . . . . . . 83Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

    11 Aproximacao de Razes deFuncoes Reais 8711.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8711.2 Metodo da Bissecao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8811.3 Metodo de Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . . . 9111.4 Comentarios Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

    12 Derivacao Numerica 9612.1 Metodos Numericos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

    12.1.1 Primeiro Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . 9612.1.2 Segundo Metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

    12.2 Analise dos erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9712.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

    13 Integracao Numerica 10413.1 Aproximacao por retangulos . . . . . . . . . . . . . . . . . . . . . . . . . 10513.2 Aproximacao por trapezios . . . . . . . . . . . . . . . . . . . . . . . . . . 10713.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

    Departamento de Estatstica - UFF iv

  • Parte I

    Conceitos Basicos de Programacao

    1

  • Semana 1: Objetos e Classes

    Toda variavel dentro da linguagem R e interpretada como um objeto que pertence a umadeterminada classe. Para saber qual a classe de um certo objeto podemos usar o comandoclass(obj), onde obj e o nome do objeto para o qual queremos saber a classe.

    Existem diversos tipos de classes. Algumas serao vistas ao longo deste curso e outrasapenas em disciplinas futuras. Por exemplo, podemos citar alguns tipos basicos que seraovistos na aula de hoje: "numeric", "logical", "character", "matrix" e "list".

    1.1 Numeros

    Os objetos numericos fazem parte da classe "numeric" e tratam-se dos numeros rais.Para criar um objeto desse tipo podemos usar, por exemplo, o comando x

  • Objetos e Classes

    Para saber mais sobre a classe "character" consulte o help do R atraves do comandohelp(character).

    1.3 Logicos

    Os objetos do tipo logico fazem parte da classe "logical" e podem ser de dois tipos:TRUE ou FALSE. Eles tambem podem ser simplesmente representados pelas letras T ouF. Para criar um objeto desse tipo podemos usar, por exemplo, o comando v

  • Objetos e Classes

    Um comando muito importante que pode ser usado em arrays e o length(), queretorna o tamanho do array. Por exemplo, se digitarmos length(a) a resposta sera onumero 3. Ou seja, se digitarmos n

  • Objetos e Classes

    Ao lado do sinal de = devemos colocar as informacoes da matriz que esta sendo criada:

    data= array com os objetos que serao alocado dentro da matriz;ncol= numero de colunas da matriz;nrow= numero de linhas da matriz;byrow= TRUE ou FALSE que indica se os objetos serao alocados

    por linha ou por coluna;dimnames = lista1 com os nomes para as linhas e colunas da matriz.

    Se alguma das informacoes nao for preenchida sera considerado o valor padrao paracada entrada, que nesse caso e: data=NA, ncol=1, nrow=1 e dimnames = NULL.

    Vejamos alguns exemplos de como usar este comando e criar matrizes. Considere osseguintes comandos digitados no prompt do R:

    > mdat1 mdat1[,1] [,2] [,3]

    [1,] 1 2 3

    [2,] 11 12 13

    Veja que mdat1 e um objeto da classe "matrix". Para verificar basta digitar:

    > class(mdat1)

    [1] "matrix"

    Veja que se mudarmos o numero de linhas ou colunas a matriz criada e totalmentediferente.

    > mdat2 mdat2[,1] [,2]

    [1,] 1 2

    [2,] 3 11

    [3,] 12 13

    Veja agora como ficaria a matriz se ela fosse alocada por colunas (byrow=FALSE).

    > mdat3 mdat3[,1] [,2]

    [1,] 1 11

    [2,] 2 12

    [3,] 3 13Quando criamos um objeto da classe "matrix", o numero de linhas e de colunas tem

    que ser determinado logo de incio e nao pode ser alterado depois.As posicoes de uma matriz sao acessadas usando o comando [ , ]. Por exemplo, se

    digitarmos mdat3[2,1] a resposta sera 2, que e o elemento guardado na segunda linha eprimeira coluna. Com esse mesmo comando podemos pegar linhas ou colunas inteirasde uma matriz: se digitarmos mdat3[1,] a resposta sera um array com os elementos dalinha 1; se digitarmos mdat3[,2] a resposta sera um array com os elementos da coluna2.

    Se quisermos o numero de linhas de uma matriz podemos usar o comando nrow(),se digitarmos nrow(mdat3) a resposta sera 3. Para saber o numero de colunas de umamatriz use, de forma analoga, o comando ncol().

    1A classe lista sera vista na proxima secao.

    Departamento de Estatstica - UFF 5

  • Objetos e Classes

    Para saber mais sobre a classe "matrix" consulte o help do R atraves do comandohelp(matrix).

    1.6 Listas

    Na linguagem R a classe que guarda os objetos em forma de lista e denominada "list".Esse objeto guarda uma sequencia de objetos e a sua principal diferenca para os arrays eque a lista pode guardar objetos de tipos diferentes.

    Para criarmos uma lista vamos usar o comando list(). Se simplesmente digitar-mos l1

  • Objetos e Classes

    Exerccios - 1 Semana

    1.1 Defina x, y e z como sendo objetos do tipo "numeric" que guardam os valores 0, -1 e32, respectivamente. Faca no prompt do R as contas a seguir e verifique se o resultado

    esta como o esperado.

    (a) a = x+ y + z, b = yz e c = zy;

    (b) z2, z3, zx e zy;

    (c)a,x ey;

    (d) 3b, 41c

    e3z2;

    (e) |x|, |y| e |z|;(f) exp(x), exp(y) e exp(c);

    (g) ln(x), ln(a) e ln(b);

    (h)pi e ex.

    1.2 Defina ch1, ch2 e ch3 como sendo objetos do tipo "character" que guardam ostextos a, b e c, respectivamente.

    (a) Usando a funcao paste a partir de ch1, ch2 e ch3 crie um quarto objeto da classe"character", ch4, definido por a.b.c.

    (b) Usando a funcao paste a partir de ch1, ch2 e ch3 crie um quinto objeto da classe"character", ch5, definido por abc.

    (c) Usando o comando == verifique se ch4 e ch5 sao iguais ou diferentes.

    (d) Usando o comando != verifique se ch4 e ch5 sao iguais ou diferentes.

    1.3 O operador %% fornece o resto da divisao entre dois numeros, por exemplo, 15%%4fornece o resto da divisao de 15 por 4, que e 3. Esse comando sera bastante usadodurante o curso. Faca os itens a seguir primeiros no papel e depois verifique a respostausando o R.

    (a) Qual a resposta para 18%%5, -5%%2, 15%%5 e 8.3%%3?

    (b) Como podemos usar o operador %% para testar se um numero e par? Faca o testeno prompt do R e use tambem os operadores == ou != de forma que a respostaseja TRUE se o numero for par e FALSE caso contrarios.

    (c) Como podemos usar o operador %% para testar se um numero e inteiro? Facao teste no prompt do R e use tambem os operadores == ou != de forma que aresposta seja TRUE se o numero for inteiro e FALSE caso contrarios.

    (d) Como podemos usar o operador %% para testar se um numero e natural, isto e,inteiro e positivo? Faca o teste no prompt do R e use tambem os operadores ==,!=, && ou || de forma que a resposta seja TRUE se o numero for natural e FALSEcaso contrarios.

    1.4 Digite no prompt do R:

    > a

  • Objetos e Classes

    (c) Crie um array z onde cada posicao de z e um objeto da classe "logic". A posicaoi de z vai guardar TRUE se a[i] for igual a b[i] e FALSE caso contrario.

    (d) Crie um array w onde cada posicao de w e um objeto da classe "logic". A posicaoi de w vai guardar TRUE se c[i] for maior que b[i] e FALSE caso contrario.

    1.5 No R ja exitem alguns objetos pre-definidos que sao chamados de constantes. Comoexemplo temos a constante pi, ja usada no exerccio (1), e os arrays letters eLETTERS: sequencias com as letras minusculas e maiusculas do alfabeto.

    (a) Primeiro digite letters e LETTERS para como sao exatamente esses objetos.

    (b) Qual a classe dos objetos letters e LETTERS? Primeiro tente responder sem usaro comando class e depois verifique a sua resposta usando tal comando.

    (c) Sem contar, como podemos encontrar o tamanho dos arrays letters e LETTERS?Qual o tamanho deles?

    (d) Se digitarmos a

  • Objetos e Classes

    perguntas: (i) Voce ja estagiou? ; (ii) Voce ja participou de algum projetocomo voluntario? ; (iii) Voce tem interesse em assuntos relacionados ao meioambiente?.

    (b) A partir do objeto minha_lista criado acesse o seu nome.

    (c) A partir do objeto minha_lista criado acesse a sua idade.

    (d) A partir do objeto minha_lista criado acesse a sua altura.

    (e) A partir do objeto minha_lista criado acesse o seu peso.

    (f) A partir do objeto minha_lista criado acesse a resposta para a pergunta Vocetem interesse em assuntos relacionados ao meio ambiente?.

    1.9 (a) Refaca o item (a) do exerccios anterior agora com os dados de um amigo oudados fictcios. Chame essa nova lista de lista_2.

    (b) Crie agora outra lista com 2 objetos, vamos chama-la de dados_alunos. Oprimeiro objeto dessa lista e a lista criada no exerccio anterior, minha_lista, eo segundo objeto e a lista criada no primeiro item desse exerccio, lista_2.

    (c) A partir do objeto dados_alunos criado acesse o seu nome.

    (d) A partir do objeto dados_alunos criado acesse o nome do seu amigo.

    (e) A partir do objeto dados_alunos criado acesse a sua altura.

    (f) A partir do objeto dados_alunos criado acesse a resposta do seu amigo para apergunta Voce ja estagiou?.

    1.10 Qual a diferenca entre os objeto obj1, obj2 e obj3 definidos a seguir?

    > obj1 obj2 obj3

  • Semana 2: Controle de Fluxo

    Os controles de fluxo sao operacoes definidas em todas as linguagens de programacao,como por exemplo C, C++, Java, Fortran, Pascal, etc. Como nao podia deixar de ser,tais operacoes tambem estao definidas dentro da linguagem R.

    Cada linguagem de programacao tem a sua propria sintaxe, isto e, sua propria regrade como essas operacoes devem ser usadas. Veremos nessa aula a sintaxe e mais detalhessobre os controles de fluxo para a linguagem R.

    2.1 if/else

    Sintaxe:

    if( afirmac~ao ) {

    tarefas 1

    } else {

    tarefas 2

    }

    Descricao:

    Realiza as tarefas 1 se a afirmacao for verda-deira e realiza as tarefas 2 se a afirmacao for falsa. Ocomando else e opicional. A afirmacao tem que serum objeto da classe "logical".

    Vejamos alguns exemplos de como usar o controle de fluxo if/else. Primeiro vamosescrever um codigo que imprimi um texto que varia de acordo com o valor guardado emuma variavel x. Se x recebe o valor 2, veja qual texto sera impresso.

    > x if( x < 5 ){

    + print(paste(x,"e menor que",5))

    + } else {

    + print(paste(x,"e maior ou igual a",5))

    + }

    [1] "2 e menor que 5"

    O comando print e responsavel por imprimir na tela e o comando paste por conca-tenar textos e criar um unico objeto do tipo character. Para mais detalhes digite noprompt do R help(print) e help(paste).

    Se a variavel x receber um valor maior que 5 o texto impresso e outro.

    > x if( x < 5 ){

    + print(paste(x,"e menor que",5))

    + } else {

    + print(paste(x,"e maior ou igual a",5))

    + }

    [1] "7 e maior ou igual a 5"

    10

  • Controle de Fluxo

    Considere agora a seguinte sequencia de comandos:

    > x if (x > 2){

    + y y for(i in 1:10){

    + y x for(var in 2:5){

    + x

  • Controle de Fluxo

    var assume o valor 4 e x e atualizado para 8+4=12. Na ultima iteracao var assume ovalor 5 e entao o valor de x recebe a sua ultima atualizacao: x = 12+5=17. Sendo assimseu valor final igual a 17.

    Para terminar de falar do for vale a pena apresentar um exemplo onde dois loopssao combinados, um dentro do outro. Suponha que temos uma matriz 5 5 cheia dezeros e queremos preencher cada posicao dessa matriz com o numero 1. O codigo a seguirexecuta essa tarefa.

    > M for(i in 1:5){

    + for(j in 1:5){

    + M[i,j] M for(i in 1:5){

    + for(j in 1:5){

    + M[i,j]

  • Controle de Fluxo

    > vet while(length(vet) < 100){

    + i

  • Controle de Fluxo

    > x for(i in 1:10){

    + x 1000) break

    + }

    Quais os valores das variaveis x e i ao final desse codigo? Vamos tentar acompanharo passo-a-passo feito pelo computador para responder essa pergunta.

    Quando o for comeca a variavel x guarda o valor 100 e a variavel i o valor 1. Naprimeira linha de comando dentro do for x passa a assumir o valor 100 + 100 1 = 200.Em seguida a condicao x>1000 e testada e como ela e falsa o processo nao e interrompido.Na segunda iteracao do for a variavel x comeca com o valor 200 e i com o valor 2. Logona primeira linha o valor de x e atualizado para 200 + 200 2 = 600. Novamente, comoa condicao testada no if nao e falsa o processo nao e interrompido. No incio da terceiraiteracao temos x=600 e i=3. Quando o valor de x e atualizado essa variavel passa aguardar o valor 600 + 600 3 = 2400. E nesse momento que a condicao testada passa aser verdadeira, x>1000, e entao o processo e interrompido.

    Logo, ao final desse for a variavel x guarda o valor 2400 e a variavel i guarda o valor3.

    Departamento de Estatstica - UFF 14

  • Controle de Fluxo

    Exerccios - 2 Semana

    2.1 Primeiro guarde nas variaveis a, b e c o tamanho dos lados de um triangulo qualquer.Em seguida implemente um codigo no R que imprime na tela uma mensagem infor-mando se o triangulo em questao e equilatero, isosceles ou escaleno. Teste o codigoimplementado para diferentes valores de a, b e c.

    2.2 Para cada item a seguir implemente um codigo no R para encontrar o que se pede.Nao use os comandos seq ou algo parecido. Dica: Comece com um vetor nulo e useo(s) controle(s) de fluxo que achar adequado para preenche-lo.

    (a) A sequencia com os 100 primeiros multiplos de 3.

    (b) A sequencia com todos os multiplos de 3 menores que 100.

    (c) A sequencia com os 100 primeiros numeros mpares.

    2.3 Usando os controles de fluxo vistos em sala de aula, faca o que se pede. Dica: a partirdo segundo item vai ser preciso usar dois loops, um dentro do outro.

    (a) Primeiro crie uma matriz 10 10 nula. Em seguida, usando um loop, preenchatoda a sua primeira linha com o numero 1.

    (b) Comece novamente com uma matriz 10 10 nula. Preencha cada uma de suaslinhas com o numero que indica a linha em questao. Por exemplo, a primeiralinha deve ser preenchido com 1, a segunda com 2 e assim por diante, ate a decimalinha que deve ser preenchida com 10.

    (c) Agora comece com uma matriz 100100 nula e implemente um loop que preenchecada coluna com o numero correspondente da coluna, isto e, a primeira colunacom o numero 1 e assim por diante.

    (d) Crie uma matriz 100100 tal que as posicoes em linhas pares recebem o numero2 e as posicoes em linhas mpares o numero 1.

    2.4 Comece cada item a seguir com uma matriz 100 100 nula e nao use o comando seqou um vetor pronto.

    (a) Crie uma matriz diagonal 100 100 cujos elementos da diagonal principal sao osnumeros de 1 ate 100 em ordem crescente.

    (b) Crie uma matriz diagonal 100 100 cujos elementos da diagonal principal sao osnumeros de 1 ate 100 em ordem decrescente.

    2.5 Usando os loops vistos em sala de aula crie as listas definidas em cada item a seguir.

    (a) L1 e uma lista com 10 posicoes tal que cada posicao i dessa lista guarda o numeroi.

    (b) L2 e uma lista com 10 posicoes tal que cada posicao i dessa lista guarda um vetorde tamanho i com todas as posicoes iguais a 1.

    (c) L3 e uma lista com 10 posicoes tal que cada posicao i dessa lista guarda um vetorcom os 10 primeiros multiplos de i.

    (d) L4 e uma lista com 10 posicoes tal que cada posicao i dessa lista guarda um vetorcom os i primeiros multiplos de 2.

    Departamento de Estatstica - UFF 15

  • Controle de Fluxo

    (e) L5 e uma lista com 10 posicoes tal que cada posicao i dessa lista guarda a matrizidentidade de tamanho ii.

    2.6 Usando as listas L1 e L3 do exerccio 2.5, faca o que se pede.

    (a) Encontre o valor da soma de todos os numeros guardados em L1.

    (b) Encontre o vetor definido pela soma de todos os vetores guardados em L3.

    2.7 Usando a lista L4 do exerccio 2.5, faca o que se pede.

    (a) Crie um vetor soma tal que a sua posicao i guarda a soma dos elementos do vetoralocado na posicao i da lista L4.

    (b) Crie um vetor v de character tal que a sua posicao i guarda o objeto soma[i]concatenado com "e um multiplo de 5" se a o valor da posicao i do vetor somafor um multiplo de 5. Caso contrario guarde na posicao i de v o objeto soma[i]concatenado com "n~ao e um multiplo de 5". Para concatenar textos use ocomando paste.

    (c) A partir do vetor soma ou do vetor v criados nos itens anteriores conte o numerode vetores da lista L4 tais que a sua soma e um numero multiplos de 5. Nao epara voce visualizar soma ou v e contar, e sim para usar um loop e um contadorpara realizar essa conta.

    2.8 Uma progressao aritmetica (p.a.) e uma sequencia numerica em que cada termo, apartir do segundo, e igual a` soma do termo anterior com uma constante r. O numeror e chamado de razao. O primeiro termo da sequencia sera chamado de x0.

    (a) Faca um codigo em R que determine os 100 primeiros termos da progressaoaritmetica cuja termo inicial e x0 = 2 e a razao e r = 3. Vamos chamar o vetorcom os elementos dessa sequencia de y.

    Depois que y estiver construdo,

    (b) Faca um codigo que determine a soma dos 35 primeiros termos dessa sequencia.Compare o valor encontrado com o valor fornecido pela formula da soma de umap.a.. Voce lembra dessa formula?

    (c) Faca um codigo que conte um numero de elementos em y multiplos de 4 (lembredo comando %% visto na semana passada, que fornece o resto da divisao).

    (d) Faca um codigo que conte um numero de elementos em y multiplos de 4 e mul-tiplos de 5 simultaneamente.

    (e) Faca um codigo que conte um numero de elementos em y multiplos de 4 oumultiplos de 5.

    (f) Vamos agora criar uma nova sequencia x a partir da sequencia y da seguintemaneira: cada termo par da sequencia y sera mantido e os termos mpares seraosubstitudos por 0. Faca um codigo que gere a sequencia x assim definida.

    Departamento de Estatstica - UFF 16

  • Controle de Fluxo

    2.9 A famosa sequencia de Fibonacci e definida da seguinte maneira: os dois primeiroselementos sao iguais a [1, 1] e a partir do terceiro elemento cada termo da sequenciae definido como a soma dos dois termos anteriores. Por exemplo, o terceiro termo e2 (= 1 + 1), o quarto termo e 3 (= 1 + 2), o quinto termo e 5 (= 2 + 3) e assim pordiante.

    (a) Faca um codigo em R para encontrar os 12 primeiros numeros da sequencia deFibonacci.

    (b) Faca um codigo em R para encontrar todos os numeros da sequencia de Fibonaccimenores que 300.

    (c) Faca um codigo em R que determine o numero de termos da sequencia de Fibo-nacci menores que 1.000.000. Veja que nesse caso voce nao precisa (e nem deve!)guardar os termos da sequencia, apenas precisa contar o numero de elementos.

    Departamento de Estatstica - UFF 17

  • Semana 3: Funcoes e o Conceito de VariavelLocal

    Nesse semana vamos ver como podemos criar funcoes dentro do R para tornar nossocodigo mais dinamico e pratico. Alem disso sera apresentado o conceito de variavel local,que e de grande importancia em qualquer linguagem de programacao.

    3.1 Funcoes

    Uma funcao dentro dentro de uma linguagem de programacao e definida pelos seguintesitens:

    nome da funcao;

    argumentos (entrada);

    sequencia de comandos (corpo);

    retorno (sada).

    Tanto os argumentos quanto a sada podem ser nulos, ou vazios, mas em geral elessao definidos.

    Depois que uma funcao e definida para executar a sua sequencia de comandos bastachama-la pelo nome, passando os argumentos de entrada caso estes nao sejam nulos.Veremos alguns exemplos ao longo da aula.

    Para definir uma funcao no R deve ser usada a seguinte sintaxe.

    Sintaxe:

    nome_da_funcao

  • Funcoes e o Conceito de Variavel Local

    Vejamos alguns exemplos. Primeiro vamos construir uma funcao que retorna o maiorentre dois valores passados como argumentos. Essa funcao ja existe pronta no R e sechama max, o que vamos fazer e entender como ela funciona criando a nossa propriafuncao.

    > maior b)

    + return(a)

    + else

    + return(b)

    + }

    Depois da funcao definida e compilada podemos chama-la sem ter que digitar todo ocodigo novamente. Veja o que acontece quando a funcao e chamada no prompt do R.

    > maior(3,2)

    [1] 3

    > maior(-1,4)

    [1] 4

    > maior(10,10)

    [1] 10

    Tambem podemos optar por guardar a sada da funcao em uma variavel, o que podeser bastante util.

    > x maior(1,maior(2,5))

    [1] 5

    > maior(10,maior(6,-1))

    [1] 10

    > maior(-3,maior(0,1))

    [1] 1

    Outra alternativa e criar uma funcao com tres argumentos propria para isso.

    > maior_de_3 b && a>c){

    + return(a)

    + } else {

    + if(b>c)

    + return(b)

    + else

    + return(c)

    + }

    + }

    > y y

    [1] 15

    Departamento de Estatstica - UFF 19

  • Funcoes e o Conceito de Variavel Local

    Vamos agora fazer uma funcao que recebe como argumento um numero natural n eretorna um vetor com os n primeiros multiplos de 3. Na semana passada, na aula pratica,fizemos isso para n = 100, agora estamos fazendo para qualquer n, quem vai escolher oseu valor e o usuario quando ele chamar a funcao.

    Temos muitas maneiras de fazer isso, veja duas alternativas usando o for.

    > multiplos_3

  • Funcoes e o Conceito de Variavel Local

    + vet multiplos_3(1.5)

    Error in multiplos_3(1.5) : n tem que ser um natural

    3.2 Variaveis Locais

    As variaveis locais sao aquelas usadas somente no corpo da funcao. Para garantirmos queessa variavel realmente nao esta assumindo um valor pre definido e preciso que ela sejainiciada dentro do corpo da funcao.

    Ainda trabalhando com a funcao que retorna os multiplos de 3, veja como as variaveislocais devem ser iniciadas dentro da propria funcao.

    Forma Correta:

    > multiplos_3

  • Funcoes e o Conceito de Variavel Local

    A variavel y retornada pela funcao sera um vetor com 20 posicoes onde as 10 primeiraspossuem multiplos de 3 e as 10 ultimas o valor do ndice da posicao.

    Tanto para a implementacao correta quanto para a implementacao errada a variavelvet permanece a mesma apos as duas linhas de comando. Faca o teste no R e verifique!

    !

    ! Dentro de uma funcao podemos ter dois tipos de variaveis: aquelas passadascomo argumento e as variaveis locais. As variaveis passadas como argumento naopodem ser iniciadas dentro do corpo da funcao, nesse caso perderamos o valorinformado pelo usuario. Ja as variaveis locais, aquelas que nao foram passadascomo argumento, devem ser iniciadas dentro da funcao.

    Veja mais um exemplo de funcao antes da secao de exerccios.Suponha agora que queremos criar uma funcao que em vez de retornar os n primeiros

    multiplos de 3 passe a retornar os n primeiros multiplos de m. Veja como esta funcaopode ser implementada.

    > multiplos

  • Funcoes e o Conceito de Variavel Local

    Exerccios - 3 Semana

    3.1 (a) Implemente uma funcao que recebe como argumento dois numeros reais e retornao menor entre eles.

    (b) Implemente uma funcao que recebe como argumento tres numeros reais e retornao menor entre eles.

    OBS: Nao use a funcao min pronta no R.

    3.2 Implemente uma funcao que recebe como argumento o tamanho de cada lado deum triangulo e retorna um texto informando se o triangulo e equilatero, isosceles ouescaleno. Antes de fazer o exerccio pense:

    Quantos argumentos a sua funcao vai receber?

    Quais sao os valores aceitaveis para esses argumentos?

    Qual o tipo de objeto que a sua funcao deve retornar?

    3.3 Implemente uma funcao que recebe como argumento um vetor de numeros reais eretorna a quantidade de elementos positivos desse vetor. Nao se esqueca de inciartodas as variaveis locais usadas em sua funcao. OBS: Depois que a sua funcao estiverpronta invente vetores para serem passados como argumento de forma a verificar se a funcao esta

    funcionando como o esperado. Por exemplo, use a funcao para contar o numero de elementos

    positivos em v = (1.0, 3.2,2.1, 10.6, 0.0,1.7,0.5).item Implemente uma funcao que recebe como argumento um vetor de numeros reaisv| e um numero real e retorna o numero de elementos do vetor v menores que .

    3.4 Para cada item a seguir faca o que se pede. Nao se esqueca de fazer as verificacoesnecessarias para garantir que o usuario passe os argumentos de forma correta.

    (a) Implemente uma funcao que recebe como argumento as variaveis n e m e retornaum vetor que guarda os n primeiros multiplos de m.

    (b) Implemente uma funcao que recebe como argumento as variaveis m e K e retornaum vetor com os multiplos de m menores que K.

    (c) Implemente uma funcao que recebe como argumento as variaveis m e K e retornaa quantidade de multiplos de m menores que K.

    (d) Classifique cada variavel que aparece dentro das funcoes implementadas nesseexerccio como variavel local ou argumento da funcao. Todas as variaveislocais foram iniciadas dentro do corpo da funcao?

    3.5 Para cada item a seguir faca o que se pede. Nao se esqueca de fazer as verificacoesnecessarias para garantir que o usuario passe os argumentos de forma correta.

    (a) Implemente uma funcao que recebe como entrada um numero natural n e retornauma matriz n n tal que as posicoes em linhas pares recebem o numero 2 e asposicoes em linhas mpares o numero 1.

    (b) Implemente uma funcao que recebe como entrada um numero natural n e retornauma matriz n n tal que a coluna i dessa matriz guarda o elemento i. Porexemplo, a primeira coluna deve ser preenchida com 1, a segunda com 2 e assimpor diante, ate a n-esima coluna que deve ser preenchida com o numero n.

    Departamento de Estatstica - UFF 23

  • Funcoes e o Conceito de Variavel Local

    (c) Implemente uma funcao que recebe como entrada um numero natural n e retornauma matriz diagonal n n tal que na diagonal principal aparecem os valores de1 ate n. Por exemplo, a posicao (1, 1) deve ser preenchido com 1, a posicao (2, 2)com 2 e assim por diante. As demais posicoes devem ser nulas, uma vez que amatriz de sada e diagonal.

    3.6 Para cada item a seguir faca o que se pede. Nao se esqueca de fazer as verificacoesnecessarias para garantir que o usuario passe os argumentos de forma correta.

    (a) Implemente uma funcao que recebe como entrada um vetor de numero reais ve retorna uma matriz diagonal com os elementos de v guardados na diagonalprincipal.

    (b) Implemente uma funcao que recebe como entrada um vetor de numero reais v eretorna uma matriz quadrada cujas colunas sao iguais ao vetor v.

    (c) Implemente uma funcao que recebe como entrada um vetor de numero reais v eretorna uma matriz quadrada cujas linhas sao iguais ao vetor v.

    3.7 Para cada item a seguir faca o que se pede. Nao se esqueca de fazer as verificacoesnecessarias para garantir que o usuario passe os argumentos de forma correta.

    (a) Implemente uma funcao que recebe como argumento o valor inicial x0 e retornaos 10 primeiros termos de uma p.a. cuja razao e 3.

    (b) Implemente uma funcao que recebe como argumento o valor inicial x0, a razao re retorna um vetor com os 10 primeiros termos dessa p.a.

    (c) Implemente uma funcao que recebe como argumentos o valor inicial x0, a razaor, um inteiro n e retorna um vetor com os n primeiros termos de uma p.a. Vamoschamar essa funcao de pa.

    (d) Usando a funcao pa implementada no item anterior, implemente outra funcaoque recebe como argumento o valor inicial x0, a razao r, um inteiro n e retornaa soma dos n primeiros termos de uma p.a. Para isso, chame a funcao pa dentroda nova funcao que esta sendo implementada neste item.

    (e) Classifique cada variavel que aparece dentro das funcoes implementadas nos itens3.7c e 3.7d como variavel local ou argumento da funcao. Todas as variaveislocais foram iniciadas dentro do corpo da funcao?

    3.8 Implemente uma funcao que:

    (a) recebe como argumento a variavel n e retorna um vetor com os n primeiros termosda sequencia de Fibonacci.

    (b) recebe como argumento a variavel K e retorna um vetor com os todos os termosda sequencia de Fibonacci menores que K.

    (c) recebe como argumento a variavel K e retorna o numero de termos da sequenciade Fibonacci menores que K.

    3.9 Suponha que a seguinte funcao foi implementada no R com o intuito de gerar umvetor com os naturais de 1 ate n, este passado como argumento pelo usuario.

    Departamento de Estatstica - UFF 24

  • Funcoes e o Conceito de Variavel Local

    > f

  • Semana 4: Algoritmos para CalculosEstatsticos

    A partir dessa semana vamos nos concentrar na analise e implementacao de algoritmose por isso sera evitado a apresentacao de codigos prontos na linguagem R. Em vez dissoserao apresentados e discutidos alguns pseudo-codigos (passo-a-passo), como costumaaparecer na maioria dos livros. As aulas praticas serao dedicadas a` implementacao dosalgoritmos a partir dos pseudo-codigos apresentados em sala de aula.

    Nesse captulo vamos discutir como podemos encontrar os valores para algumas esta-tsticas a partir de um conjunto de dados guardados em um array. Por falta de temponem todas as secoes serao vistas em detalhes na aula teorica, algumas ficaram para leituraem casa. A ideia principal e rever alguns conceitos e pensar como podemos ensinar ocomputador a encontra-los.

    A maioria das funcoes que serao implementadas nessa secao ja estao prontas no R.Mais uma vez nao vamos usar tais funcoes prontas e sim parar para pensar como elasforam implementadas e escrever nosso proprio codigo.

    4.1 Maximo

    Definicao 4.1.1 Seja A um conjunto de dados. Dizemos que a A e o maximo desseconjunto se a r r A.

    Queremos escrever um pseudo-codigo que recebe como entrada um array de dados eretorna o seu maximo de acordo com a definicao acima. Na semana anterior foi imple-mentando uma funcao que recebe dois ou tres numeros e retorna o maior entre eles. Oque esta sendo pedido agora e o caso geral: encontrar o maximo entre todos os elementosguardados em um vetor.

    A ideia principal do algoritmo apresentado a seguir e percorrer um vetor guardandoo maior elemento encontrado ate o momento. O algoritmo termina quando o vetor ja foipercorrido por completo. Veja como isso pode ser feito no passo-a-passo a seguir.

    Entrada: v = array com os dados.Sada: valor maximo em v.

    Defina n = tamanho do vetor v;1Faca max = v1;2Inicie i = 2;3Se vi > max,max = vi;4Incremente i: i = i+ 1;5Se i n, volta para a linha 4;6Retorne max.7

    26

  • Algoritmos para Calculos Estatsticos

    Na linha 2 a variavel max guarda o primeiro elemento do vetor, pois no incio doalgoritmo esse e o unico valor observado, logo o maximo ate o momento. Na linha 4acontece a troca do valor guardado em max, caso o novo valor observado seja maior queo maximo ate o momento.

    Veja que o passo-a-passo descreve um loop: as linhas 4 - 6 se repetem varias vezes.Como podemos reproduzir isso em uma linguagem de programacao? A resposta e: usandoum dos controles de fluxo para loop vistos no Captulo 2.

    A escolha do controle de fluxo depende do algoritmo. No caso deste temos a variavel ique comeca assumindo o valor 2 e e incrementada ate atingir o valor n, ou seja, conhecemoso valor inicial e final da variavel i. Dessa forma parece que o for e uma opcao bastanterazoavel, onde i sera a variavel definida dentro dele.

    4.2 Mnimo

    Definicao 4.2.1 Seja A um conjunto de dados. Dizemos que a A e o mnimo desseconjunto se a r r A.

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna o seu mnimo, de acordo com a definicao acima.

    A ideia principal do algoritmo proposto e percorrer um vetor guardando o menorelemento encontrado ate o momento. O algoritmo termina quando o vetor ja foi percorridopor completo. Repare que esse algoritmo e analogo ao apresentado para o maximo, porisso a elaboracao do pseudo-codigo (passo-a-passo) sera deixada como exerccio.

    4.3 Media

    Definicao 4.3.1 Seja A = {a1, a2, . . . , an} um conjunto finito de dados e n o seu numerode elementos. A media amostral desse conjunto e definido por:

    media =a1 + a2 + . . .+ an

    n=

    ni=1 ain

    .

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna a sua media de acordo com a definicao acima. A ideia principal sera per-correr o vetor v somando seus elementos uma a um. Quando v ja tiver sido percorrido porcompleto, basta dividir a soma final pelo numero total de elementos que encontraremosa media.

    Entrada: v = array com os dados.Sada: a media amostral dos valores de v.

    Defina n = tamanho do vetor v;1Inicie soma = 0;2Inicie i = 1;3

    Departamento de Estatstica - UFF 27

  • Algoritmos para Calculos Estatsticos

    Incremente a variavel soma: soma = soma+ vi;4Incremente a posicao a ser somada: i = i+ 1;5Se i n, volta para a linha 4;6Faca media = soma/n;7Retorne media.8

    Repare que temos novamente a ocorrencia de um loop dentro do algoritmo, bastanotar a repeticao das linhas 4 - 6. Entao quando esse passo-a-passo for implementado emuma linguagem de programacao sera preciso escolher um controle de fluxo para realizaresse loop.

    4.4 Mediana

    Definicao 4.4.1 Seja A = {a1, a2, . . . , an} um conjunto finito de dados e n o seu numerode elementos. Considere a notacao de estatstica de ordem tal que A = {a(1), a(2), . . . , a(n)}e a(1) a(2) . . . a(n). A mediana desse conjunto e definida informalmente como oponto que separa o conjunto ordenado em duas partes de mesmo tamanho. Sua definicaoformal encontra-se a seguir.

    mediana =

    {a(n+1

    2) , se n e mpar;

    (a(n2) + a(n

    2+1))/2 , se n e par;

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna a sua mediana de acordo com a definicao acima.

    Entrada: v = array com os dados.Sada: a mediana dos valores de v.

    Defina n = tamanho do vetor v;1Defina v como o vetor v ordenado;2Se n e mpar, faca mediana = vn+1

    2;3

    Se n e par, faca mediana = (vn2

    + vn2+1)/2;4

    Retorne mediana.5

    Veja que nesse algoritmo nao temos a ocorrencia de loops.Na linha 2 do passo-a-passo acima o vetor v e ordenado. Ainda nao aprendemos como

    ordenar vetores, isso sera visto somente no Captulo 8. Por isso, pro enquanto, usaremoso comando sort do R para ordenar vetores.

    4.5 Quartis

    Definicao 4.5.1 Seja A = {a1, a2, . . . , an} um conjunto finito de dados e n o seu numerode elementos. Considere a notacao de estatstica de ordem tal que A = {a(1), a(2), . . . , a(n)}

    Departamento de Estatstica - UFF 28

  • Algoritmos para Calculos Estatsticos

    e a(1) a(2) . . . a(n). Os quartis desse conjunto e definido informalmente como ostres pontos que separam o conjunto ordenado em quatro partes de mesmo tamanho.

    Existem alguns metodos para encontrar os quartis de um conjunto de dados. Vejamosa seguir dois desses metodos.

    Metodo 1

    1. Encontre a mediana do conjunto de dados e divida o conjunto ordenado em doissubconjuntos. Nao inclua a mediana em nenhum deles.

    2. O primeiro quartil e a mediana do subconjunto com os menores valores.

    3. O segundo quartil e a mediana do conjunto original.

    4. O terceiro quartil e a mediana do subconjunto com os maiores valores.

    Metodo 2

    1. Encontre a mediana do conjunto de dados e divida o conjunto ordenado em doissubconjuntos. Caso a mediana seja um elemento do conjunto original ela deve serincluda em ambos os subconjuntos.

    2. O primeiro quartil e a mediana do subconjunto com os menores valores.

    3. O segundo quartil e a mediana do conjunto original.

    4. O terceiro quartil e a mediana do subconjunto com os maiores valores.

    Queremos escrever um pseudo-codigo que recebe como entrada um array de dadose retorna cada um dos seus quartis. A ideia sera simplesmente seguir um dos metodosacima e recorrer ao calculo da mediana, que ja e conhecido. A seguir isso sera feitoconsiderando Metodo 1. Faca como exerccio o pseudo-codigo considerando o Metodo 2.

    Entrada: v = array com os dados.Sada: quartis do conjunto de dados v.

    Defina n = tamanho do vetor v;1Defina v como o vetor v ordenado;2Se n for par, seja k = n/2 e j = k + 1;3Se n for mpar, seja k = (n 1)/2 e j = k + 2;4Defina v1 como sendo o vetor v das posicoes de 1 ate k;5Defina v2 como sendo o vetor v das posicoes de j ate n;6Defina q1 = mediana de v1;7Defina q2 = mediana de v;8Defina q3 = mediana de v2;9Retorne o vetor (q1, q2, q3).10

    Veja que nas linhas 3 e 4 sao definidas as posicoes de v onde termina v1 e comeca v2,considerando o Metodo 1. Essas linhas devem mudar para o Metodo 2.

    Departamento de Estatstica - UFF 29

  • Algoritmos para Calculos Estatsticos

    4.6 Frequencias

    Quando temos um vetor de dados pode ser interessante conhecer a frequencia com quecada valor aparece dentro desse vetor. Para isso podemos pensar em dois tipos de frequen-cia: absoluta e acumulada.

    Definicao 4.6.1 Seja A = {a1, . . . , an} um finito conjunto de dados. A frequencia ab-soluta de um valor x e definida pelo numero de vezes que esse valor aparece no conjuntoA.

    Definicao 4.6.2 Seja A = {a1, . . . , an} um conjunto de dados com n elementos. Afrequencia absoluta de um valor x e definida pela razao entre o numero de vezes que essevalor aparece no conjunto A e n.

    Queremos escrever um pseudo-codigo que recebe como entrada um array de dados eretorne uma matriz de duas linhas. Na primeira linha deve aparecer os diferentes valoresque aparecem no array de entrada. Na segunda linha deve aparecer a frequencia absolutade cada valor.

    A ideia principal desse pseudo-codigo e varrer o array de entrada lendo todos osvalores guardados nele. Toda vez que um valor novo e encontrado ele deve ser guardadoem um array e a sua frequencia absoluta iniciada com o valor 1. Se um valor e encontradomais de uma vez, apenas e preciso incrementar a sua frequencia absoluta. Veja o passo-a-passo a seguir.

    Entrada: v = array com os dados.Sada: matriz M com as frequencias absolutas.

    Defina n = tamanho do vetor v;1Inicie dois arrays: val e freq;2Faca val1 = v1 e freq1 = 1;3Inicie i = 2;4Se existe o valor vi dentro do array val, va para a linha 7;5Caso contrario, va para a linha 8;6Seja k a posicao do valor vi em val, incremente freqk e va pra linha 9;7Seja j o tamanho do array val, faca valj+1 receber vi e freqj+1 receber 1;8Incremente i: i = i+ 1;9Se i n, volte para a linha 5;10Crie uma matriz M cuja primeira linha contem os elementos de val e a segunda linha os11elementos de freq;12Retorne M .13

    Veja que na linha 5 e feito a busca pelo elemento vi dentro do array val. Ficara maissimples o codigo se voce criar uma funcao propria para isso. Ou seja, defina uma funcaoa parte que recebe como entrada um array e um valor e retorna TRUE se existe o valordentro do array ou FALSE caso nao exista.

    Se o interesse for na frequencia relativa basta dividir os elementos do vetor freq porn antes de criar a matriz de sada.

    Departamento de Estatstica - UFF 30

  • Algoritmos para Calculos Estatsticos

    4.7 Moda

    Definicao 4.7.1 Seja A = {a1, a2, . . . , an} um conjunto finito de dados. A moda desseconjunto e definida pelo valor mais frequente dentro do conjunto de dados.

    Queremos escrever um pseudo-codigo que recebe como entrada um array de dados eretorna a sua moda.

    A ideia principal e procurar o valor com maior frequencia. Como ja sabemos encontraras frequencias de cada valor (Secao 4.6) o algoritmo fica bem simples: basta procurar ondeesta o maior valor na segunda linha da matriz de frequencias.

    Entrada: v = array com os dados.Sada: a moda de v.

    Seja M a matriz de frequencias criada a partir de v;1Seja j a coluna referente ao maior elemento da linha 2 de M ;2Retorne M1,j;3

    A parte difcil e encontrar a posicao do maior elemento da linha 2 de M . Mas issopode ser feito em uma funcao a parte para simplificar o codigo.

    4.8 Amplitude Total

    Definicao 4.8.1 Seja A um conjunto de dados, max o seu maximo e min o seu mnimo,como definidos anteriormente. A amplitude total de A e definida pela diferenca max min.

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna a sua amplitude total. Veja que podemos considerar que ja sabemosencontrar o maximo e o mnimo. Faca voce mesmo esse pseudo-codigo como exerccio.

    4.9 Distancia Interquartlica

    Definicao 4.9.1 Seja A um conjunto de dados, q1 o primeiro quartil e q3 o terceiroquartil. A distancia interquartlica de A e definida por q3 q1.

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna a sua distancia interquartlica. Faca voce mesmo esse pseudo-codigoconsiderando que voce ja sabe encontrar o primeiro e terceiro quartil.

    4.10 Variancia Amostral

    Definicao 4.10.1 Seja A = {a1, a2, . . . , an} um conjunto finito de dados e n o seu nu-mero de elementos. Seja m a media amostral de A. A variancia amostral desse conjunto

    Departamento de Estatstica - UFF 31

  • Algoritmos para Calculos Estatsticos

    e definido por:

    S2 =

    ni=1(ai m)2n 1 .

    Queremos escrever um pseudo-codigo que recebe como entrada um array de dados eretorna a sua variancia amostral. A ideia principal e primeiro encontrar a media amostrale em seguida percorrer o array de entrada calculando a variancia amostral.

    Entrada: v = array com os dados.Sada: variancia amostral dos valores de v.

    Defina n = tamanho do vetor v;1Defina m = media amostral de v;2Inicie soma = 0;3Inicie i = 1;4Incremente a variavel soma: soma = soma+ (vi m)2;5Incremente i: i = i+ 1;6Se i n, volta para a linha 5;7Faca s2 = soma/(n 1);8Retorne s2.9

    4.11 Desvio Medio

    Definicao 4.11.1 Seja A = {a1, . . . , an} um conjunto de dados e n o seu numero deelementos. Seja m a media amostral de A. O desvio medio e definido por:

    dm =

    ni=1 |ai m|

    n.

    Queremos agora escrever um pseudo-codigo que recebe como entrada um array dedados e retorna o seu desvio medio. Esse pseudo-codigo e bem parecido com o da varianciaamostral. Faca voce mesmo como exerccio.

    4.12 Covariancia Amostral

    Definicao 4.12.1 Seja A = {a1, a2, . . . , an} e B = {b1, b2, . . . , bn} dois conjuntos dedados pareados e n o seu numero de elementos. Seja mA a media amostral de A e mB amedia amostral de B. A covariancia amostral entre os conjuntos A e B e definida por:

    covA,B =

    ni=1(ai mA)(bi mB)

    n 1 .

    Queremos agora escrever um pseudo-codigo que recebe como entrada dois arrays dedados e retorna a covariancia amostral entre eles.

    Departamento de Estatstica - UFF 32

  • Algoritmos para Calculos Estatsticos

    Entradas: v = array com os dados; w = array com os dados.Sada: covariancia amostral entre os valores em v e w.

    Defina n = tamanho do vetor v;1Defina k = tamanho do vetor w;2Se n 6= k retorna erro;3Defina mv = media amostral de v;4Defina mw = media amostral de w;5Inicie soma = 0;6Inicie i = 1;7Incremente a variavel soma: soma = soma+ (vi mv)(wi mw);8Incremente i: i = i+ 1;9Se i n, volta para a linha 8;10Faca cov = soma/(n 1);11Retorne cov.12

    Departamento de Estatstica - UFF 33

  • Algoritmos para Calculos Estatsticos

    Exerccios - 4 Semana

    Para todos os exerccios a seguir nao se esqueca de:

    Verificar sempre se as entradas passadas pelo usuario sao viaveis para os calculosdas funcoes.

    Inventar varias entradas para as funcoes implementadas a fim de verificar se elasestao funcionando corretamente.

    Sempre que possvel chamar as funcoes ja implementadas dentro de uma nova fun-cao. Assim voce simplifica bastante seu codigo.

    4.1 Faca o que se pede sem usar as funcoes max e which.max do R.

    (a) No computador implemente o algoritmo visto em sala de aula que recebe comoentrada um vetor v e retorna o seu valor maximo.

    (b) Em seu caderno escreva um pseudo-codigo para o algoritmo que recebe comoentrada um vetor v e retorna a posicao onde se encontra o maximo. Nesse itemnao e para usar o computador.

    (c) Agora, novamente no computador, implemente uma nova funcao que executa opseudo-codigo elaborado no item 1b. Nao use o mesmo nome da funcao imple-mentada no item 1a.

    4.2 Faca o que se pede sem usar as funcoes min e which.min do R.

    (a) Primeiro escreva em seu caderno um pseudo-codigo para o algoritmo que recebecomo entrada um vetor v e retorna o valor mnimo guardado em v. Nesse itemnao e para usar o computador.

    (b) Agora no computador implemente uma funcao que executa o pseudo-codigo ela-borado do item 2a.

    (c) De volta ao caderno escreva um pseudo-codigo para o algoritmo que recebe comoentrada um vetor v e retorna a posicao onde se encontra o mnimo. Nesse itemnao e para usar o computador.

    (d) Novamente no computador implemente no uma nova funcao que executa o pseudo-codigo elaborado no item 2c. Nao use o mesmo nome da funcao implementadano item 2b.

    4.3 Faca o que se pede sem usar as funcoes mean e sum do R. No computador implementeo algoritmo visto em sala de aula que recebe como entrada um vetor v e retorna amedia amostral dos valores em v.

    OBS: Se quiser use a funcao mean para comparacao.

    4.4 Faca o que se pede sem usar a funcao median do R. Para ordenar o vetor de entradause a funcao sort do R. No computador implemente o algoritmo visto em sala deaula que recebe como entrada um vetor v e retorna a mediana de v.

    OBS: Se quiser use a funcao median para comparacao.

    Departamento de Estatstica - UFF 34

  • Algoritmos para Calculos Estatsticos

    4.5 Faca o que se pede sem usar a funcao quantile do R. Para ordenar o vetor de entradause a funcao sort do R.

    (a) No computador implemente o pseudo-codigo visto em sala de aula, baseado noMetodo 1, que recebe como entrada um vetor v e retorna os tres quartis.

    (b) No caderno escreva um pseudo-codigo que calcula os tres quartis a partir doMetodo 2.

    (c) No computador implemente o pseudo-codigo escrito no item acima.

    4.6 Faca o que se pede sem usar a funcao table ou algo parecido.

    (a) No computador implemente o algoritmo visto em sala de aula que recebe comoentrada um vetor v e retorna uma matriz cuja primeira linha guarda os diferentesvalores de v e a segunda as frequencias absolutas com que esses valores aparecemno vetor de dados.

    (b) Repita o item 6a gerando agora as frequencias relativas. Nao use o mesmo nomeda funcao implementada no item 6a.

    (c) Faca agora uma outra funcao que recebe como argumento alem do vetor v umobjeto to tipo "logic", vamos chama-lo de rel. Se rel = TRUE a matriz desada deve guardar as frequencias relativas, caso contrario ela guarda a frequenciaabsoluta.

    4.7 Usando as funcoes implementadas em 6, implemente o algoritmo visto em sala deaula que recebe como entrada um vetor de dados e retorna a moda desse vetor.

    4.8 (a) Primeiro escreva no caderno um pseudo-codigo para o algoritmo que recebe comoentrada um vetor v e retorna a sua Amplitude Total. Nao e para usar o compu-tador ainda. Considere que voce ja sabe calcular os valores mnimo e maximo doseu vetor de entrada.

    (b) Agora no computador implemente o pseudo-codigo feito do item 8a usando asfuncoes implementadas nos exerccios 1 e 2.

    4.9 (a) Primeiro escreva no caderno um pseudo-codigo para o algoritmo que recebe comoentrada um vetor v e retorna a sua Distancia Interquartlica. Nao e para usar ocomputador ainda. Considere que voce ja sabe calcular os quartis de v.

    (b) Agora no computador implemente o passo-a-passo feito do item 9a usando asfuncoes implementadas no exerccio 5.

    4.10 Faca o que se pede sem usar as funcoes sd, mean e sum do R. No computador im-plemente o algoritmo visto em sala de aula que recebe como entrada um vetor v eretorna a sua variancia amostral. Para simplificar use a funcao implementada noexerccio 3.

    OBS: Se quiser use a funcao sd para comparacao.

    4.11 (a) Primeiro escreva no caderno um pseudo-codigo para o algoritmo que recebe comoentrada um vetor v e retorna o seu Desvio Medio. Nao e para usar o computadorainda. Considere que voce ja sabe calcular a media de v.

    (b) Agora no computador implemente o pseudo-codigo feito do item 11a.

    Departamento de Estatstica - UFF 35

  • Algoritmos para Calculos Estatsticos

    4.12 Faca o que se pede sem usar as funcoes mean e sum do R.

    (a) Implemente o algoritmo visto em sala de aula que recebe como entrada doisvetores v e w e retorna a covariancia amostral entre eles. Para simplificar use afuncao implementada no exerccio 3.

    (b) Desafio: vamos generalizar o item 12a. Implemente uma funcao que recebe comoentrada uma matriz de dados. Considere que cada coluna dessa matriz representaum vetor de dados. A funcao implementada deve retornar a matriz de covarianciaamostral entre os vetores coluna dessa matriz.

    Lembre-se que a matriz de covariancia e definida pela matriz cuja posicao (i, j) guarda a

    covariancia da variavel i com a j.

    Departamento de Estatstica - UFF 36

  • Semana 5: Algoritmos para CalculosMatriciais

    A motivacao dese captulo e implementar funcoes que realizam calculos matriciais. Assimcomo no captulo anterior, na aula teorica sera visto os pseudo-codigos e estes seraoimplementados durantes as aulas praticas, atraves dos exerccios propostos ao final docaptulo.

    Primeiro serao apresentadas algumas operacoes entre vetores. Em seguida sera vistooperacoes tambem envolvendo matrizes.

    5.1 Multiplicacao de vetor por escalar

    Definicao 5.1.1 Sejam v = (v1, v2, . . . , vn) Rn e R. A multiplicacao do vetor vpelo escalar e o vetor w = v definido por w = (v1, v2, . . . , vn) Rn.

    Queremos escrever um pseudo-codigo que recebe como entrada um vetor v e um escalar e retorna o vetor definido por w = v. Para isso basta percorrer o vetor v multiplicandocada posicao pelo escalar . Veja como isso pode ser feito no pseudo-codigo a seguir.

    Entradas: v = vetor de numeros reais; = numero realSada: o vetor w = v

    n = tamanho do vetor v;1Inicie o vetor w como nulo;2Inicie i = 1;3Faca wi = vi;4Incremente i = i+ 1;5Se i n, volte para a linha 4;6Retorne w;7

    5.2 Soma entre vetores

    Definicao 5.2.1 Sejam v = (v1, v2, . . . , vn) Rn e u = (u1, u2, . . . , un) Rn. A somaentre os vetores v e u e o vetor w = v+u definido por w = (v1+u1, v2+u2, . . . , vn+un) Rn.

    Queremos escrever um pseudo-codigo que recebe como entrada dois vetores v e u eretorna o vetor definido pela soma entre eles. Veja que para essa operacao ser realizada e

    37

  • Algoritmos para Calculos Matriciais

    preciso que ambos os vetores tenham mesma dimensao. Para encontrar a soma entre osdois vetores de mesma dimensao basta somar cada posicao uma a uma. Veja o pseudo-codigo a seguir.

    Entradas: v e u, vetores que serao somados.Sada: o vetor w = v + u.

    n = tamanho do vetor v;1m = tamanho do vetor u;2Se n 6= m, retorne uma mensagem de erro e FIM;3Inicie o vetor w como nulo;4Inicie i = 1;5Faca wi = vi + ui;6Incremente i = i+ 1;7Se i n, volte para a linha 6;8Retorna w.9

    5.3 Subtracao entre vetores

    Definicao 5.3.1 Sejam v = (v1, v2, . . . , vn) Rn e u = (u1, u2, . . . , un) Rn. A substra-cao do vetor v por u e o vetor w = vu definido por w = (v1u1, v2u2, . . . , vnun) Rn.

    O pseudo-codigo que recebe como entrada dois vetores e retorna o vetor definido pelasubtracao entre eles pode ser feito de duas maneiras. A primeira alternativa e fazer umpseudo-codigo analogo ao definido para a soma entre dois vetores. A segunda alternativae combinar a multiplicacao de um vetor por um escalar com a soma entre dois vetores:primeiro multiplica-se o vetor u pelo escalar 1 e em seguida soma o resultado com ovetor v.

    Faca voce mesmo esse pseudo-codigo para a subtracao entre dois vetores da maneiraque achar melhor.

    5.4 Produto interno

    Definicao 5.4.1 Sejam v = (v1, v2, . . . , vn) Rn e u = (u1, u2, . . . , un) Rn. O produtointerno entre v e u e o numero real definido por:< v, u >= v1u1 + v2u2 + . . .+ vnun =

    ni=1 viui.

    Queremos escrever o pseudo-codigo que recebe como entrada dois vetores v e u eretorna o produto interno entre eles. Veja que essa operacao so e possvel se ambos osvetores tiverem mesma dimensao. A ideia e percorrer as posicoes dos vetores, multipli-cando posicao a posicao e guardando a soma em uma variavel local. Veja o pseudo-codigoa seguir.

    Departamento de Estatstica - UFF 38

  • Algoritmos para Calculos Matriciais

    Entrada: v e u, vetores para os quais queremos o produto internoSada: o produto interno entre v e u: < v, u >.

    Defina n = tamanho do vetor v;1Defina m = tamanho do vetor w;2Se n 6= m, retorne uma mensagem de erro e FIM;3Inicie p = 0;4Inicie i = 1;5Incremente p = p+ viwi;6Incremente i = i+ 1;7Se i n, volte para a linha 6;8Retorna p.9

    5.5 Multiplicacao de matriz por escalar

    Definicao 5.5.1 Sejam A uma matriz de dimensao n m e Rn um escalar. Amultiplicacao de A pelo escalar e a matriz M = A de dimensao n m onde cadaposicao (i, j) e definida por Mi,j = Ai,j.

    Queremos escrever um pseudo-codigo que recebe como entrada uma matriz A e umescalar e retorna a matriz definida por M = A. Para isso basta percorrer a matriz Amultiplicando cada posicao pelo escalar . Mas lembre-se que para percorrer uma matrize preciso usar um loop dentro do outro. Veja como isso pode ser feito no pseudo-codigoa seguir.

    Entradas: A = matriz de numeros reais; = numero realSada: a matriz M = A

    n = numero de linhas da matriz A;1m = numero de colunas da matriz A;2Inicie uma matriz M de dimensao nm;3Inicie i = 1;4Inicie j = 1;5Faca Mi,j = Ai,j;6Incremente j = j + 1;7Se j m, volte para a linha 6;8Incremente i = i+ 1;9Se i n, volte para a linha 5;10Retorne M ;11

    Reparou que temos dois loops? O primeiro esta entre as linhas 6 e 8 e o outro entreas linhas 5 e 10. Como isso pode ser implementado em uma linguagem de programacao,em particular na linguagem R?

    Departamento de Estatstica - UFF 39

  • Algoritmos para Calculos Matriciais

    5.6 Soma entre matrizes

    Definicao 5.6.1 Sejam A e B duas matrizes de dimensao nm. A soma das matrizesA e B e a matriz M = A+B de dimensao nm onde cada posicao (i, j) e definida porMi,j = Ai,j +Bi,j.

    Queremos escrever o pseudo-codigo que recebe como entrada duas matrizes A e B eretorna a matriz definida pela soma delas. Novamente como teremos que percorrer aslinhas e colunas das matrizes sera preciso usar dois loops, um dentro de outro. Veja nopseudo-codigo a seguir como isso pode ser feito.

    Entrada: A e B, matrizes que serao somadasSada: matriz M = A+B.

    Defina n = numero de linhas de A;1Defina m = numero de colunas de A;2Defina l = numero de linhas de B;3Defina c = numero de colunas de B;4Se n 6= l, retorne uma mensagem de erro e FIM.5Se m 6= c, retorne uma mensagem de erro e FIM.6Crie uma matriz M de dimensao nm;7Inicie i = 1;8Inicie j = 1;9Preencha a posicao (i, j) de M : Mi,j = Ai,j +Bi,j;10Incremente j = j + 1;11Se j m, volta para a linha 10;12Incremente i = i+ 1;13Se i n, volta para a linha 9;14Retorna M .15

    5.7 Subtracao entre Matrizes

    Definicao 5.7.1 Sejam A e B duas matrizes de dimensao nm. A subtracao da matrizA pela matriz B e a matriz M = A B de dimensao n m onde cada posicao (i, j) edefinida por Mi,j = Ai,j Bi,j.

    Assim como a subtracao de vetores, o pseudo-codigo que recebe como entrada duasmatrizes e retorna a matriz definida pela subtracao entre elas pode ser feito de duasmaneiras. A primeira alternativa e fazer um pseudo-codigo analogo ao definido para asoma entre matrizes. A segunda alternativa e combinar a multiplicacao de uma matrizpor um escalar com a soma entre duas matrizes: primeiro multiplica-se a matriz B peloescalar 1 e em seguida soma o resultado com a matriz A.

    Faca voce mesmo o pseudo-codigo para a subtracao entre duas matrizes da maneiraque achar melhor.

    Departamento de Estatstica - UFF 40

  • Algoritmos para Calculos Matriciais

    5.8 Transposicao de Matrizes

    Definicao 5.8.1 Seja A uma matriz nm. A transposta da matriz A e a matriz AT dedimensao m n onde cada posicao (i, j) e definida por ATi,j = Aj,i.

    Queremos escrever um pseudo-codigo que recebe como entrada uma matriz A e retornaa sua transposta. Veja que so precisamos percorrer as linhas e colunas da matriz e guardarna posicao (i, j) o elemento guardando na posicao (j, i) da matriz de entrada. O pseudo-codigo a seguir realiza essa tarefa.

    Entrada: A, matriz a ser transpostaSada: matriz AT

    Defina n = numero de linhas da matriz A;1Defina m = numero de colunas da matriz A;2Crie uma matriz M com dimensao m n;3Inicie i = 1;4Inicie j = 1;5Preencha a posicao (i, j) da matriz M : Mi,j = Aj,i;6Incremente j = j + 1;7Se j n, volta para a linha 6;8Incremente i = i+ 1;9Se i m, volta para a linha 5;10Retorna M .11

    5.9 Multiplicacao entre matriz e vetor

    Definicao 5.9.1 Seja A uma matriz n m e v Rm um vetor. Considere ai Rm ovetor formado pela i-esima linha da matriz A. O produto entre a matriz A e o vetor v eo vetor w = Av Rn tal que cada posicao e definida por wi =< ai, v >.

    A partir da definicao acima vamos escrever um pseudo-codigo para uma funcao querecebe como entrada uma matriz A e um vetor v e retorna o vetor definido pelo produtoentre eles. Vamos considerar que ja sabemos calcular o produto interno entre dois vetores.Entao basta percorrer as colunas da matriz e calcular o produto interno entre os vetorescolunas e o vetor v. Veja que as dimensoes de A e v devem ser testadas para verificarse a multiplicacao realmente pode ser realizada: a conta so e possvel quando o numerode colunas da matriz e igual ao numero de elementos no vetor. O pseudo-codigo a seguirmostra como isso pode ser feito.

    Entrada: uma matrizes A e um vetor v.Sada: vetor w = Av.

    Defina n = numero de linhas de A;1Defina m = numero de colunas de A;2Defina k = a dimensao do vetor v;3

    Departamento de Estatstica - UFF 41

  • Algoritmos para Calculos Matriciais

    Se k 6= m, retorne uma mensagem de erro e FIM.4Inicie um vetor w como nulo;5Inicie i = 1;6Crie ai como o vetor definido pela linha i da matriz A;7Faca wi =< ai, v >;8Incremente i = i+ 1;9Se i n, volta para a linha 7;10Retorne w.11

    Dica: Na linguagem R se o objeto A e uma matriz entao o objeto ai = A[,i] e umarray de "numeric" definido pela i-esima coluna de A.

    5.10 Multiplicacao entre matrizes

    Definicao 5.10.1 Seja A uma matriz nm e B uma matriz m k. Considere ai Rmo vetor formado pela i-esima linha da matriz A e bj Rm o vetor formado pela j-esimacoluna da matriz B. O produto entre a matriz A e a matriz B e a matriz M = AB dedimensao n k onde cada posicao e definida por Mi,j =< ai, bj >.

    A partir da definicao acima vamos escrever um pseudo-codigo para uma funcao querecebe como entrada duas matrizes A e B e retorna outra matriz definida pelo produtoentre elas. Vamos considerar que ja sabemos calcular o produto interno entre dois vetores.Veja que as dimensoes de A e B devem ser testadas para verificar se a multiplicacaorealmente pode ser realizada: so podemos multiplicar A por B se o numero de colunasde A for igual ao numero de colunas de B.

    Entrada: A e B, matrizes que serao multiplicadasSada: matriz M = AB.

    Defina n = numero de linhas de A;1Defina m = numero de colunas de A;2Defina l = numero de linhas de B;3Defina k = numero de colunas de B;4Se m 6= l, retorne uma mensagem de erro e FIM.5Crie uma matriz M de dimensao n k;6Inicie i = 1;7Inicie j = 1;8Crie ai como o vetor definido pela linha i da matriz A;9Crie bj como o vetor definido pela coluna j da matriz B;10Faca Mi,j =< ai, bj >;11Incremente j = j + 1;12Se j k, volta para a linha 10;13Incremente i = i+ 1;14Se i n, volta para a linha 8;15Retorne M .16

    Departamento de Estatstica - UFF 42

  • Algoritmos para Calculos Matriciais

    Exerccios - 5 Semana

    5.1 Implemente uma funcao que recebe como entrada um vetor v e um escalar e retornao vetor v.

    5.2 Implemente uma funcao que recebe como entrada dois vetores v e u e retorna outrovetor definido pela soma entre eles.

    5.3 (a) No caderno escreva um pseudo-codigo para o algoritmo que recebe como entradadois vetores v e u e retorna outro vetor definido pela subtracao do primeiro pelosegundo.

    (b) Agora no computador implemente o pseudo-codigo elaborado no item acima.

    5.4 Implemente uma funcao que recebe como entrada dois vetores v e u e retorna oproduto interno entre eles.

    5.5 Implemente uma funcao que recebe como entrada dois vetores e retorna TRUE casoeles forem ortogonais e FALSE caso contrario.

    Dica: da para saber se dois vetores sao ortogonais a partir do produto interno entreeles.

    5.6 Implemente uma funcao que recebe como entrada uma matriz A e um escalar eretorna a matriz A.

    5.7 Implemente uma funcao que recebe como entrada duas matrizes A e B e retornaoutra matriz definida pela soma entre elas.

    5.8 (a) No caderno escreva um pseudo-codigo para o algoritmo que recebe como entradaduas matrizes A e B e retorna outra matriz definida pela subtracao da primeirapela segunda.

    (b) Agora no computador implemente o pseudo-codigo elaborado no item acima.

    5.9 Implemente uma funcao que recebe como entrada uma matriz A e retorna a suatransposta.

    5.10 (a) No caderno escreva um pseudo-codigo para o algoritmo que recebe como entradauma matriz A e retorna TRUE se essa matriz for simetrica e FALSE casocontrario. Lembre-se: uma matriz simetrica e uma matriz quadrada tal queAi,j = Aj,i.

    (b) Agora no computador implemente o pseudo-codigo elaborado no item acima.

    5.11 Implemente uma funcao que recebe como entrada uma matriz A e um vetor v eretorna o vetor definido por Av.

    5.12 Implemente uma funcao que recebe como entrada duas matrizes A e B e retorna amatriz definida pelo produto entre A e B.

    Departamento de Estatstica - UFF 43

  • Algoritmos para Calculos Matriciais

    5.13 Considere = 4, = 3, v1 = (2,3,1, 5, 0,2), v2 = (3, 4,1, 0, 1, 1), v3 =

    (1, 2, 3, 4, 5), v4 = (0, 1, 1), M1 =

    (1 3 21 0 1

    ), M2 =

    0 5 31 1 11 4 0

    , M3 = 3 12 10

    3 1

    , M4 = ( 1 10 1)

    e M5 =

    3 1 0 11 1 3 20 3 5 01 2 0 0

    .Usando as funcoes que voce implementou nos exerccios anteriores faca as contas quese pede. Tente cada item usando apenas uma linha de comando no R.

    (a) v3

    (b) v1 + v2

    (c) v3 v1(d) < v1, v2 >

    (e) < v1, v2 v1 >(f) < v1 + v2, v1 v2 >(g) Os vetores v1 e v2 acima sao perpendiculares (ortogonais)?

    (h) M1

    (i) MT1

    (j) Verifique se as matrizes M1, M4 e M5 sao simetricas.

    (k) M1v4

    (l) M2v4 + v4

    (m) M1M2

    (n) M2M1

    (o) MT3 M2

    (p) (M1M3) +M4

    (q) M1M2M3

    (r) M1M2M3 M4

    Departamento de Estatstica - UFF 44

  • Parte II

    Recursao

    45

  • Semana 6: Algoritmos Recursivos

    Na ciencia da computacao um algoritmo e dito recursivo quando ele chama a si propriocom entradas mais simples. De forma semelhante, dizemos que uma funcao e implemen-tada de forma recursiva quando ela chama a si propria com argumentos mais simples.Vejamos alguns exemplos de algoritmos e funcoes implementadas de forma recursiva noR nas secoes a seguir.

    Como sera mostrado nesse captulo, para todo algoritmo recursivo existe outro queexecuta a mesma tarefa de forma nao recursiva. A vantagem em usar os algoritmosrecursivos e a maior simplicidade e clareza no codigo (confira!). A desvantagem e que emgeral tais algoritmos consomem muita memoria, devido ao uso intensivo de pilha.

    6.1 Fatorial

    O exemplo mais classico em recursao e o calculo do fatorial de n. Podemos fazer isso deforma recursiva ou nao. Vejamos primeiro o algoritmo sem recursao.

    Entrada: nSada: n!

    Se n nao for inteiro positivo, retorne erro.1Inicie saida = 1;2Se n = 0, retorne saida;3Inicie i = 1;4Faca saida = saida i;5Incremente i = i+ 1;6Se i n, volte para a linha 5;7Retorne saida.8

    No caso do algoritmo recursivo e importante definir o seu nome para que fique claraa chamada recursiva. Veja agora o algoritmo recursivo.

    Entrada: nSada: n!Nome: Fatorial

    Se n nao for inteiro positivo, retorne erro.1Se n = 0, retorne 1;2Retorne n Fatorial(n 1).3

    46

  • Algoritmos Recursivos

    Veja que a chamada recursiva aparece na linha 3. A funcao Fatorial, que esta sendodefinida para uma entrada n, e chamada para a entrada n 1. Ou seja, o algoritmochama a si proprio com entrada simplificada. Dessa forma garantimos que em algummomento a funcao Fatorial sera chamada para n = 0, argumento para o qual temosresposta imediata.

    Vamos comparar agora as respectivas implementacoes no R.

    Sem recursao:

    > fatorial_1

  • Algoritmos Recursivos

    Defina n = tamanho do vetor v;1Se n = 1, retorne v1;2Defina w = (v2, v3, ..., vn);3Defina maxw =Max(w);4Se v1 > maxw, retorne v1;5Retorne maxw.6

    Veja que a chamada recursiva aparece na linha 4. Nesse exemplo o argumento foisimplificado uma vez que vetor passado como argumento tem uma dimensao a menos.Assim garantimos que em algum momento a funcao sera chamada para um vetor detamanho 1, entrada para a qual temos uma resposta imediata.

    6.3 Sequencias Definidas a partir de

    Equacoes de Diferencas

    Uma sequencia de numeros reais {xn}n=1 e definida a partir de uma equacao de diferencasquando o seu n-esimo termo e escrito em funcao de termos anteriores. Ou seja, quandoexiste f tal que xn = f(n, xn1, xn2, . . .).

    Um exemplo de equacao de diferencas e a sequencia de Fibonacci, que ja foi vistaem captulos anteriores. Esse exemplo sera revisto na secao 6.3.3. Antes disso veremosalguns outros exemplos.

    Encontrar a solucao de uma equacao de diferencas consiste em determinar o n-esimotermo da sequencia de forma direta, sem depender dos termos anteriores, dependendoapenas de n. Para isso existem muitas tecnicas, mas aprender essas tecnicas nao e o focodo nosso curso.

    Por exemplo, seja {xn}n=1 uma sequencia definida por:x0 = 1 e xn = 2xn1 + 1.

    Com essas informacoes podemos calcular todos os termos de forma iterativa:

    x0 = 1,x1 = 2 1 + 1 = 3,x2 = 2 3 + 1 = 7,x3 = 2 7 + 1 = 15, . . .

    A solucao dessa equacao de diferencas e xn = 2n 1 (verifique!). Mas nesse curso

    nao vamos aprender como chegar nessa solucao, nosso trabalho sera montar a equacaoe resolver o problema de forma iterativa a partir de uma funcao implementada no R.Faremos isso usando e nao usando recursao.

    Vejamos a seguir alguns problemas que utilizam equacoes de diferencas em sua mo-delagem.

    6.3.1 Padroes geometricos

    Veja o padrao geometrico a seguir e pense em uma equacao de diferencas que expresseo numero de bolinhas em cada grupo. Ou seja, considere xn o numero de bolinhas nogrupo e pense em como podemos escrever xn em funcao de xn1 e n.

    Departamento de Estatstica - UFF 48

  • Algoritmos Recursivos

    (1) (2) (3) (4)

    Figura 6.1: Padrao Geometrico Triangular

    Pela figura temos x1 = 1, x2 = 3, x3 = 6 e x4 = 10. Voce identificou algum padraonessa formacao? Veja que xn = xn1 + n.

    Agora vamos escrever um pseudo-codigo que recebe como argumento um numero ne retorna o numero de bolinhas no n-esimo grupo, ou seja, xn. Primeiro de forma naorecursiva.

    Entrada: nSada: xn

    Se n nao for inteiro positivo, retorne erro.1Se n = 1 retorne 1;2Defina x = 1;3Faca i = 2;4Faca x = x+ i ;5Incremente i = i+ 1;6Se i n, volte para a linha 5;7Retorne x.8

    Agora o pseudo-codigo usando recursao.

    Entrada: nSada: xnNome: NumBolinhas

    Se n nao for inteiro positivo, retorne erro.1Se n = 1 retorne 1;2Retorne NumBolinhas(n 1) + n3

    Veja que novamente a chamada recursiva usou um argumento simplificado: trocou npor n 1.

    6.3.2 Matematica Financeira

    Em Matematica Financeira muitos problemas que envolvem juros, como investimentos oudvidas, podem ser expressos em termos de sequencias de diferencas. Veja dois exemplosa seguir.

    Suponha que voce investiu R$ 1.000,00 em um fundo de investimento que paga 0, 7%de rendimento ao mes. Considere xn como sendo o total acumulado apos n meses de

    Departamento de Estatstica - UFF 49

  • Algoritmos Recursivos

    investimento. Primeiro veja que o total acumulado apos n meses depende diretamente dototal acumulado apos n 1 meses:

    x0 = 1.000, 00xn = xn1 + 0, 007 xn1 = 1, 007 xn1

    Essa e uma equacao de diferencas homogenea de primeira ordem com coeficiente cons-tante, ou seja, ela e do tipo: xn = cxn1 com c R. Toda equacao desse tipo tem umasolucao facil: xn = c

    nx0 (verifique!). Mas nao e isso que estamos buscando. Nesse ca-ptulo queremos treinar a implementacao de algoritmos usando recursao. Vamos entaoescrever um codigo que recebe como entrada n e retorna xn, onde cada xi e calculado deforma iterativa, como se nao soubessemos a solucao da equacao de diferencas.

    Veja primeiro o pseudo-codigo sem usar recursao.

    Entrada: nSada: xn

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0 retorne 1.000;2Defina x = 1.000;3Faca i = 1;4Faca x = 1, 007 x ;5Incremente i = i+ 1;6Se i n, volte para a linha 5;7Retorne x.8

    Agora o usando recursao.

    Entrada: nSada: xnNome: Investimento

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0 retorne 1.000;2Retorne 1, 007Investimento(n 1)3

    Vejamos agora outro exemplo envolvendo juros: um financiamento.Suponha que voce vai pegar emprestado R$1.000,00 no banco e devera pagar esse

    valor corrigido por um juros composto de 1,5% ao mes. Ou seja, a cada mes sua dvidacresce 1,5%. Suponha que voce esta disposto a pagar parcelas mensais de R$ 200,00.

    Considere yn como sendo sua dvida apos n meses do incio do financiamento. Primeiroveja que a dvida apos n meses depende diretamente da dvida apos n 1 meses:

    y0 = 1.000, 00yn = yn1 + 0, 015 yn1 200 = 1, 015 yn1 200

    Com essas informacoes podemos escrever um pseudo-codigo que fornece a dvida aposn meses. So temos que tomar cuidado que essa sequencia apos um numero finito de passos

    Departamento de Estatstica - UFF 50

  • Algoritmos Recursivos

    passa a ser negativa, caso contrario a dvida nao seria paga nunca. Nesse caso, apesarde yn < 0 a real dvida nao existe mais, entao a funcao deve retornar 0. Veja primeiro opseudo-codigo sem usar recursao.

    Entrada: nSada: yn

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0 retorne 1.000;2Defina y = 1.000;3Faca i = 1;4Faca y = 1, 015 y 200 ;5Incremente i = i+ 1;6Se i n, volte para a linha 5;7Se y < 0, retorne 0. Senao, retorne y.8

    Agora o usando recursao.

    Entrada: nSada: ynNome: Dvida

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0 retorne 1.000;2Faca d = 1, 015Dvida(n 1) 200;3Se d < 0, retorne 0. Senao, retorne d.4

    Outra informacao que pode ser de interessante e o tempo que a dvida vai demorarpara ser paga. Como podemos achar isso? Pense em um pseudo-codigo que recebe comoentrada o valor das parcelas fixas que serao pagas por mes e retorna o numero de mesesque a pessoa demora para pagar a dvida de R$1.000,00 considerando um juros compostode 1,5% ao mes.

    6.3.3 Fibonacci

    A sequencia de Fibonacci e um caso particular de equacoes de diferencas de segundaordem, isto e, uma equacao em que xn depende nao so de xn1 como tambem de xn2.Lembrando, uma sequencia de Fibonacci e definida por:

    F1 = 1,F2 = 1Fn = Fn1 + Fn2.

    Vamos escrever um pseudo-codigo que recebe como entrada n e retorna o n-esimotermo da sequencia de Fibonacci (Fn). Primeiro sem recursao.

    Departamento de Estatstica - UFF 51

  • Algoritmos Recursivos

    Entrada: nSada: Fn

    Se n = 1 ou n = 2, retorne 11Defina F1 = 1 e F2 = 12Inicie i = 33Faca F = F1 + F24Faca F1 = F , F2 = F15Incremente i = i+ 16Se i n, volte para a linha 47Retorne F8

    Agora com recursao.

    Entrada: nSada: FnNome: Fibonacci

    Se n = 1 ou n = 2, retorne 11Retorne Fibonacci(n 1) + Fibonacci(n 2)2

    Veja que nesse exemplo, por se tratar de uma equacao de diferencas de segunda ordem,a chamada recursiva e feita duas vezes: Fibonacci(n 1) e Fibonacci(n 2). Em ambaso argumento foi simplificado. Como temos dois casos basicos, n = 1 e n = 2, garantimosque para qualquer natural n sempre teremos solucao.

    Departamento de Estatstica - UFF 52

  • Algoritmos Recursivos

    Exerccios - 6 Semana

    6.1 Implemente de forma recursiva uma funcao que recebe como entrada um numeronatural n e retorna n!. Nao esqueca de verificar se o argumento passado como entradae realmente um numero natural.

    6.2 Implemente de forma recursiva uma funcao que recebe como entrada um vetor v eretorna o valor maximo desse vetor.

    6.3 (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um vetor v e retorna a soma dos elementos desse vetor.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    6.4 (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um vetor v e retorna a posicao onde se encontra o valor maximo dessevetor. Dica: em vez de definir w = (v2, v3, . . . , vn) defina w = (v1, v2, . . . , vn1).Mas cuidado que isso muda um pouco a forma de pensar.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    6.5 Considere o seguinte padrao geometrico.

    (1) (2) (3) (4)

    Figura 6.2: Padrao Geometrico Quadrado

    Defina xn como o numero de bolinhas no grupo n.

    (a) Encontre uma formula recursiva para xn, ou seja, escreva xn como funcao dexn1.

    (b) Usando a formula encontrada, no caderno escreva um pseudo-codigo recursivopara o algoritmo que recebe como entrada um numero natural n e retorna onumero de bolinhas no grupo n.

    (c) Agora no computador implemente o pseudo-codigo elaborado acima.

    6.6 Suponha que voce va investir R$ 500, 00 na poupanca e que esta rende 7, 5% ao ano.

    (a) Calcule na mao o quanto de dinheiro voce teria no banco depois de 1, 2 e 3 anosde investimento.

    (b) Tente achar uma equacao que relacione o total de dinheiro acumulado em n anosde investimento com o total de dinheiro acumulado em n 1 anos.

    (c) Usando a equacao encontrada, no caderno escreva um pseudo-codigo recursivopara o algoritmo que recebe como entrada um numero natural n e retorna odinheiro acumulado em n anos nesse investimento.

    (d) Agora no computador implemente o pseudo-codigo elaborado acima.

    Departamento de Estatstica - UFF 53

  • Algoritmos Recursivos

    6.7 Vamos generalizar o exerccio anterior.

    (a) Seja I o valor investido em uma aplicacao de rentabilidade j% ao ano. Implementeuma funcao que recebe como entrada I, j e n e retorna o total acumulado nessaaplicacao apos n anos.

    (b) Use a funcao implementada para descobrir quanto de dinheiro teramos a maisse investssemos R$ 1.000,00 durante 2 anos em um fundo que rendesse 10% aoano em vez de 7, 5%.

    6.8 Suponha que voce vai fazer um financiamento de R$ 1.200,00 e vai pagar juros com-postos de 2% ao mes. Considere que voce pode pagar R$150,00 por mes.

    (a) Calcule na mao o valor da sua dvida depois de 1, 2 e 3 meses.

    (b) Tente achar uma equacao que relacione a sua dvida no mes n com a sua dvidano mes n 1.

    (c) Usando a equacao encontrada escreva no caderno um pseudo-codigo recursivopara o algoritmo que recebe como entrada um numero natural n e retorna a suadvida apos n meses do incio do financiamento. Nao se esqueca de considerar ocaso em que a dvida foi paga, nesse caso voce deve retornar 0.

    (d) Agora no computador implemente o pseudo-codigo elaborado acima.

    6.9 Vamos generalizar o exerccio anterior.

    (a) Seja F o valor financiado a juros compostos de j% ao mes. Considere K o valordas parcelas fixas que serao pagas todo mes. Implemente uma funcao recursivaque recebe como entrada F , j, K e n e retorna a dvida existente apos n mesesdesde o incio do financiamento.

    (b) Use a funcao implementada acima para comparar o valor da sua dvida de R$1.200,00 apos 10 meses nos seguintes casos: parcela mensal de R$ 150,00 e parcelamensal de R$ 120,00. Considere os mesmos 2% de juros compostos ao mes.

    6.10 Vamos fazer outro exerccio que considera um financiamento, mas agora estamosinteressados na quantidade de meses para se pagar a dvida. Suponha que vocevai fazer um financiamento de F rais e vai pagar juros compostos de j% ao mes.Considere que voce pode pagar K reais por mes.

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada F , j e K e retorna o numero de meses que voce vai demorar para pagara sua dvida.Dica: A simplificacao na chamada recursiva ocorre na entrada F .

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    (c) Use a funcao implementada acima para comparar o numero de meses ate a qui-tacao da dvida de R$ 1.200,00 nos seguintes casos: parcela mensal de R$ 150,00;parcela mensal de R$ 120,00 e parcela mensal de R$ 200,00. Considere os mesmos2% de juros compostos ao mes.

    6.11 Implemente uma funcao recursiva que recebe como entrada um numero natural n eretorna o n-esimo termo da sequencia de Fibonacci.

    Departamento de Estatstica - UFF 54

  • Algoritmos Recursivos

    6.12 Considere a seguinte sequencia definida a partir de uma equacao de diferencas desegunda ordem.

    yn = 2yn1 + yn2 + n com y1 = 0 e y2 = 0

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e retorna o valor de yn.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    Departamento de Estatstica - UFF 55

  • Semana 7: Algoritmos Recursivos(continuacao)

    Nessa semana veremos mais alguns exemplos de algoritmos recursivos. Diferente docaptulo anterior, nesse sera apenas apresentado o algoritmos recursivo. Mas vale lembrarque sempre existe um outro algoritmo nao recursivo que realiza a mesma tarefa.

    7.1 Series

    Seja {xi}i=0 uma sequencia de numero reais. Defina outra sequencia {Sn}n=0 como asoma dos n primeiros termos dessa sequencia: Sn =

    ni=0 xi. A sequencia {Sn}n=0 e

    chamada de serie.Nessa secao vamos usar a recursao para encontrar os termos de uma seria Sn =

    ni=0 xi

    dada a sequencia {xi}. Ou seja, para uma dada sequencia {xi} e um natural n estamosinteressados em encontrar a soma dos n primeiros termos dessa sequencia.

    Como primeiro exemplo considere xi = i e Sn =n

    i=1 xi =n

    i=1 i. Veja que para esseexemplo Sn = 1 + 2 + . . .+ n. Vamos escrever um algoritmo que recebe como entrada ne retorna o n-esimo termo dessa serie, isto e, Sn.

    Entrada: nSada: Sn =

    ni=0 i

    Nome: Serie1

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0, retorne 0;2Retorne n+ Serie1(n 1).3

    Veja que a chamada recursiva usa como argumento n 1. Dessa forma garantimos asimplificacao do argumento e que em algum momento chegaremos ao caso mais simplese o algoritmo termina.

    Vejamos agora outro exemplo. Considere xi =1i!

    e defina Sn =n

    i=0 xi =n

    i=01i!.

    Podemos criar um algoritmo recursivo e usar o computador para encontrar qualquer termon dessa serie, como mostra o pseudo-codigo a seguir.

    Entrada: nSada: Sn =

    ni=1

    1i;

    Nome: Serie2

    56

  • Algoritmos Recursivos (continuacao)

    Se n nao for inteiro nao negativo, retorne erro.1Se n = 0, retorne 1;2Retorne Serie2(n 1) + 1

    n!.3

    Veja que no codigo acima consideram que ja sabemos calcular n!. Mas e verdade, jafizemos isso na secao 6.1 acima. Entao quando formos implementa esse ultimo codigo nocomputador vamos chamar a funcao feita anteriormente que calcula n! tambem de formarecursiva.

    Ja vimos em algumas disciplinas que a sequencia Sn definida acima converge para onumero irracional e = 2.718282 . . ., ou seja, Sn

    ne. Se ainda nao vimos veremos

    em breve. Entao para n razoavelmente grande esperamos que Sn esteja proximo dee = 2.718282 . . ., como indica o limite. Com essa ideia podemos usar o algoritmo acimapara encontrar uma aproximacao para o numero irracional e, basta chamar a funcao comvalores grandes de n.

    7.2 Maior Divisor Comum

    Um algoritmo recursivo bem famoso e o Algoritmo de Euclides, conhecido desde a obraElements de Euclides, por volta de 300 a.c.. Este algoritmo calcula o maior divisor comumentre dois numeros sem precisar fatora-los. Lembrando, o maior divisor comum (MDC)entre dois numeros inteiros e o maior numero inteiro que divide ambos sem deixar resto.

    O algoritmo de Euclides e baseado no princpio de que o MDC nao muda se o maiornumero for subtrado do menor. Por exemplo, o MDC entre 252 e 105 e 21. Veja que252 = 21 12 e 105 = 21 5. Tambem e verdade que o MDC entre 252 - 105 = 147 e105 e 21. Veja que 147 = 252 105 = 21 12 21 5 = 21 7.

    A partir dessa ideia podemos afirmar que:

    MDC(n,m) = MDC(m,n);

    se n = 0, MDC(n,m) = m;

    se 0 < n m, MDC(n,m) = MDC(n,m n) = MDC(m,m n).Podemos entao criar uma funcao recursiva que encontra o MDC entre dois numeros

    inteiros quaisquer.

    MDC(n,m) =

    m, se n = 0;n, se m = 0;MDC(n,m n) se n m;MDC(m,nm) se m < n;

    A partir da funcao acima podemos criar um pseudo-codigo recursivo que recebe comoentrada dois numeros inteiros nao negativos n e m e retorna o maior divisor comum entreeles.

    Departamento de Estatstica - UFF 57

  • Algoritmos Recursivos (continuacao)

    Entradas: n e m, inteiros nao negativosSada: maior divisor comum entre n e mNome: MDC

    Se n ou m nao forem inteiros nao negativo, retorne erro.1Seja maior = maior entre n e m;2Seja menor = menor entre n e m;3Se menor = 0, retorne maior;4Retorne MDC(menor,maior menor) .5

    Veja que a chamada recursiva ocorre na linha 5 e que ambos os argumentos estaosendo simplificados. Ate poderamos fazer a chamada recursiva simplificando somente umargumento, por exemplo, substituindo a linha 5 por: Retorne MDC(m,maior menor)ou Retorne MDC(n,maior menor). Mas do jeito que esta implementando no passo-a-passo a recursao vai precisar de menos passos para chegar no caso base onde uma dasentradas e zero.

    Podemos melhorar ainda mais o desempenho do nosso algoritmo. Veja que se m emuito maior que n nossa chamada recursiva sera MDC(n,m n) varias vezes. Isso vaiterminar quando ja tivermos tirado todos os n que cabem dentro do m. Ou seja, aultima chamada recursiva desse tipo sera MDC(n,m%%n)! Entao se substituirmos nalinha 5 maior menor por maior%%menor (resto da divisao de maior por menor)vamos economizar muitos passos da recursao. Nesse caso o pseudo-codigo mais enxutosera:

    Entradas: n e m, inteiros nao negativosSada: maior divisor comum entre n e mNome: MDC

    Se n ou m nao forem inteiros nao negativo, retorne erro.1Seja maior = maior entre n e m;2Seja menor = menor entre n e m;3Se menor = 0, retorne maior;4Retorne MDC(menor,maior%%menor).5

    7.3 Torre de Hanoi

    O problema ou quebra-cabeca conhecido como Torre de Hanoi foi publicado em 1883pelo matematico frances Edouard Lucas, tambem conhecido por seus estudos com a serieFibonacci.

    O problema Consiste em transferir a torre composta por N discos, como na Figura 7.1,do pino A (origem) para o pino C (destino), utilizando o pino B como auxiliar. Somenteum disco pode ser movimentado de cada vez e um disco nao pode ser colocado sobreoutro disco de menor diametro.

    Veja que se existe um unico dico, N = 1, a solucao e imediata: mova este disco deA para C. E se existirem N discos, quais os movimentos que devemos fazer? E isso quevamos tentar resolver.

    Departamento de Estatstica - UFF 58

  • Algoritmos Recursivos (continuacao)

    A B C

    Figura 7.1: Torre de Hanoi

    Suponha que sabemos a sequencia de movimentos para mover N 1 discos de umpino origem para um pino destino. Entao para mover os N discos do pino A para o pinoC devemos primeiro mover os primeiros N 1 discos de A para B, veja figura 7.2(b).Em seguida mova o disco que sobrou no pino A para o pino C, veja figura 7.2(c). Paraterminar basta mover novamente os N 1 discos, agora do pino B para o pino C, vejafigura 7.2(d).

    A B C

    (a) Incio

    A B C

    (b) Primeiro passo

    A B C

    (c) Segundo passo

    A B C

    (d) Terceiro passo

    Figura 7.2: Torre de Hanoi - Esquema Recursivo

    Dessa forma foi definida uma solucao recursiva para o problema:

    Se N = 1: mova um disco do pino A para o pino C.Se N > 1:

    - primeiro transfira N 1 discos de A para B (Figura 7.2(b));- em seguida mova um disco do pino A para o pino C (Figura 7.2(c));- por ultimo transfira N 1 discos de B para C (Figura 7.2(d)).

    Baseado nessa ideia vamos escrever o pseudo-codigo que fornece a sequencia de movi-mentos para transferir N discos do pino A (origem) para o pino C (destino).

    Departamento de Estatstica - UFF 59

  • Algoritmos Recursivos (continuacao)

    Entradas: N ,A,C,B (numero de discos, nome do pino origem, nome do pino destino enome do pino auxiliar).Sada: -Nome: Hanoi

    Se N nao for inteiro positivo, retorne erro.1Se N = 1, imprima mova um disco do pino A para o pino C e fim.2Hanoi(N-1,A,B,C);3Imprima mova um disco do pino A para o pino C4Hanoi(N-1,B,C,A);5Fim.6

    Veja que o pseudo-codigo nada retorna, ele apenas imprime a sequencia de movimentosque deve ser realizado. Veja que como o nome do pino que aparece na mensagem impressae o argumento da funcao ha a necessidade de concatenar os textos. No R podemos concate-nar e imprimir textos usando o comando cat. Por exemplo, na linha 2 a impressao da men-sagem no R pode ser feita assim: cat("mova um disco do pino ",A," para o pino ",C).

    Uma outra possibilidade e fazer com que a sada seja um array de objetos do tipo"character" tal que cada posicao desse array guarda uma mensagem com um movimento.Veja como fica o pseudo-codigo com essa mudanca.

    Entradas: N ,A,C,B (numero de discos, nome do pino origem, nome do pino destino enome do pino auxiliar).Sada: Sequencia de movimentos guardados em um array de textos.Nome: Hanoi

    Se N nao for inteiro positivo, retorne erro.1Se N = 1, retorne mova um disco do pino A para o pino C e fim.2mov1 = Hanoi(N-1,A,B,C);3mov2 = mova um disco do pino A para o pino C4mov3 = Hanoi(N-1,B,C,A);5Retorne (mov1,mov2,mov3).6

    Nesse caso vamos usar o comando paste para concatenar os textos, pois nesse casonao queremos imprim-lo.

    Repara que a primeira posicao do array de sada guarda o texto com o primeiromovimento e a i-esima posicao do array de sada guarda o i-esimo movimento. O tamanhodo array de sada indica o numero de movimentos necessarios para mover os N discos.

    Departamento de Estatstica - UFF 60

  • Algoritmos Recursivos (continuacao)

    Exerccios - 7 Semana

    7.1 Implemente de forma recursiva uma funcao que recebe como entrada um numeronatural n e retorna a soma de todos os naturais ate n, isto e, retorna Sn =

    ni=0 i =

    0 + 1 + 2 + . . .+ n.

    7.2 (a) Implemente uma funcao que recebe como entrada um numero natural n e retornao n-esimo termo da serie Sn =

    ni=0

    1i!.

    (b) Teste a funcao implementada para diferentes valores de n e veja se quando ncresce Sn se aproxima de e = 2.718282...

    7.3 Considere a seguinte serie: Sn =n

    i=0 4(1)i2i+1

    . Essa seria foi desenvolvida por Leibnizem 1682 e e conhecida para calcular aproximacoes para o numero irracional pi, umavez que Sn

    npi.

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e retorna Sn de acordo com a formula acima.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    (c) Teste a funcao implementada para diferentes valores de n e veja se quando ncresce Sn se aproxima de pi = 3.141593...

    7.4 (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e retorna a soma dos n primeiros termos da sequen-cia de Fibonacci. Considere que voce sabe encontrar a o termo n da sequenciade Fibonacci.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima. Use a funcaoque retorna o n-esimo termos da sequencia de Fibonacci implementada na semanapassada.

    7.5 Seja {xi} a sequencia definida por xi = 13i . Defina Sn =n

    i=0 xi.

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e retorna Sn.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    (c) Para a b e a, b N defina Soma(a, b) = xa + xa+1 + . . . + xb. Implemente nocomputador uma funcao que recebe como entrada a e b e retorna Soma(a, b) deforma recursiva, sem chamar a funcao implementada no item 5b.Dica: O caso base acontece quando a = b, nesse caso qual deve ser a sada deSoma(a, b)? E se a < b, como sera a chamada recursiva?

    7.6 Considere a funcao f(n) = 2n, onde n um numero natural. Veja que ela pode sercalculada de forma recursiva:

    20 = 1 ; 21 = 220 ; 22 = 221 ; 23 = 222 ; 24 = 223 . . .

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e retorna f(n) = 2n.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    Departamento de Estatstica - UFF 61

  • Algoritmos Recursivos (continuacao)

    7.7 Agora vamos generalizar a questao anterior. Considere a funcao f(x, n) = 2n, onden um numero natural e x um numero real. Veja que ela pode ser calculada de formarecursiva:

    x0 = 1 ; x1 = xx0 ; x2 = xx1 ; x3 = xx2 ; x4 = xx3 . . .

    (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um numero natural n e um numero real x e retorna f(x, n) = xn.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    7.8 (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um array de numeros e retorna o numero de elementos nulos nesse array.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    7.9 (a) No caderno escreva um pseudo-codigo recursivo para o algoritmo que recebe comoentrada um array qualquer e retorna outro array definido pela ordem inversa doarray de entrada.

    (b) Agora no computador implemente o pseudo-codigo elaborado acima.

    7.10 (a) Implemente de forma recursiva uma funcao que recebe como entrada dois numerosinteiros e retorna o maior divisor comum entre eles.

    (b) Usando a funcao acima encontre o maior divisor comum entre os seguintes paresde numeros: 125 e 325, 2829 e 861, 299 e 217.

    7.11 Implemente de forma recursiva uma funcao que recebe como entrada o numero dediscos em uma torre de Hanoi, o nome do pino definido como origem, o nome do pinodefinido como destino e o nome do pino que sera usado como auxiliar.

    (a) Primeiro faca uma funcao que retorne nada, mas imprimi na tela os movimentosque devem ser feitos a fim de levar os discos do pino origem para o pino destino.

    (b) Faca agora uma funcao que nao imprime nada na tela, mas retorna um array de"character" que guarda em cada posicao i o i-esimo movimento que deve serfeito a fim de levar os discos do pino origem para o pino destino.

    (c) Para terminar faca agora uma terceira funcao para resolver o problema da torrede Hanoi. Nessa o retorno deve ser uma lista com dois array de "character":s e c. Tais arrays indicam os movimentos da seguinte forma: cada posicao i des guarda o nome do pino que sai o disco no i-esimo movimento enquanto cadaposicao i de c guarda o nome do pino que chega o disco no i-esimo movimento.Dessa forma cada movimento i e definido pelo transporte de um disco do pino sipara o pino ci.

    (d) Teste as funcoes implementadas nesta questao em algum site de jogos online quetenha a Torre de Hanoi.

    7.12 Implemente uma funcao recursiva que recebe como entrada um array de dados e re-torna todos as permutacoes possveis com ele. A sada pode ser uma matriz, cujaslinhas guardam as permutacoes, ou uma lista. Quando for testar sua funcao entrecom arrays pequenos, de tamanho nao muito maior que 10, caso contrario vai demo-rar muito para rodar. Lembre-se que para um conjunto com n elementos temos n!permutacoes.

    Departamento de Estatstica - UFF 62

  • Semana 8: Algoritmos de Ordenacao

    Nessa semana serao apresentados dois algoritmos de ordenacao, isto e, algoritmos queordem os elementos em um vetor qualquer. Veja que isso nada mais e do que a imple-mentacao da funcao sort ja pronta no R.

    Existem varios algoritmos de ordenacao, uns mais eficientes que os outros como vere-mos na semana que vem. Nessa semana vamos aprender dois desses metodos: O metodode Ordenacao Bolha (Bubble Sort) e o metodo de Ordenacao Rapida (Quick Sort).

    8.1 Ordenacao Bolha (Bubble Sort)

    A ideia desse metodo e ordenar o vetor seguindo os seguintes passos:

    Primeiro leve o maior elemento para a ultima posicao, comparando os elementosdois a dois ate a ultima posicao;

    Depois repita o processo e levar o segundo maior elemento para a segunda maiorposicao, comparando os elementos dois a dois ate a penultima posicao;

    Esse processo se repete varias vezes ate que o vetor esteja todo ordenado.

    Exemplo 8.1.1 Suponha v = (37, 33, 48, 12, 92, 25, 86, 57) o vetor de entrada, ou seja, ovetor que queremos ordenar. O primeiro passo e levar o maior elementos para a maiorposicao fazendo comparacoes de elementos dois a dois. Vamos indicar por negrito oselementos que estao sendo comparados em cada passo.

    37 33 48 12 92 25 86 57 como 37>33, troca33 37 48 12 92 25 86 57 como 3712, troca33 37 12 48 92 25 86 57 como 4825, troca33 37 12 48 25 92 86 57 como 92>86, troca33 37 12 48 25 86 92 57 como 92>57, troca33 37 12 48 25 86 57 92 fim dessa etapa

    Os elementos que ja estiverem em suas devidas posicoes serao sublinhado.Veja que para realizar essa etapa foram necessarias 7 comparacoes.Agora que o maior elemento ja esta na ultima posicao o proximo passo e levar o

    segundo maior elemento ate a segunda maior posicao. Repare que nesse caso as compa-racoes serao ate a penultima posicao, uma vez que a ultima posicao ja esta com o seudevido elemento.

    63

  • Algoritmos de Ordenacao

    33 37 12 48 25 86 57 92 nao troca33 37 12 48 25 86 57 92 troca33 12 37 48 25 86 57 92 nao troca33 12 37 48 25 86 57 92 troca33 12 37 25 48 86 57 92 nao troca33 12 37 25 48 86 57 92 troca33 12 37 25 48 57 86 92 fim dessa etapa

    Veja que para realizar essa etapa foram necessarias 6 comparacoes. Agora o terceiromaior elementos sera levado para a terceira maior posicao.

    33 12 37 25 48 57 86 92 troca12 33 37 25 48 57 86 92 nao troca12 33 37 25 48 57 86 92 troca12 33 25 37 48 57 86 92 nao troca12 33 25 37 48 57 86 92 nao troca12 33 25 37 48 57 86 92 fim dessa etapa

    Veja que para realizar essa etapa foram necessarias 5 comparacoes. Agora o quartomaior elementos sera levado para a quarta maior posicao.

    12 33 25 37 48 57 86 92 nao troca12 33 25 37 48 57 86 92 troca12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 fim dessa etapa

    Veja que para realizar essa etapa foram necessarias 4 comparacoes.Nesse momento o vetor ja esta ordenado, porem o computador nao tem como saber

    disso. Por isso as etapas seguintes serao realizadas, apesar de nenhuma troca ser feita.

    12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 fim de mais uma etapa

    12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 fim de mais uma etapa

    12 25 33 37 48 57 86 92 nao troca12 25 33 37 48 57 86 92 fim de mais uma etapa

    12 25 33 37 48 57 86 92 fim de mais uma etapa

    E assim o vetor foi ordenado!

    A seguir algumas observacoes sobre o metodo e o sobre exemplo acima.

    Em um vetor de tamanho n e preciso de n1 comparacoes para realizar a primeiraetapa, isto e, levar o maior elemento para a maior posicao.

    Departamento de Estatstica - UFF 64

  • Algoritmos de Ordenacao

    Ja para levar o segundo maior elemento para a segunda maior posicao sao realizadasn 2 comparacoes. De forma geral, para levar o j-esimo maior elemento para a j-esima maior posicao,

    isto e realizar a etapa j, sao realizadas n j comparacoes. Em cada etapa j serao comparados os elementos das posicoes i e i + 1 para i =

    1, . . . , n j. Veja que no exemplo acima foram realizadas 7 etapas para ordenar um vetor de

    tamanho 8. De forma geral, para ordenar um vetor de tamanho n sao realizadasn 1 etapas.

    Veja que serao necessarios dois loops, um dentro do outro. Um para controlar asetapas e outro para controlar as comparacoes dentro de cada etapa. Veja a seguir umprimeiro pseudo-codigo nao recursivo para o algoritmo apresentado.

    Entrada: vSada: vetor v arrumado em ordem crescente.Nome: OrdenaBolha

    Defina n = tamanho do vetor v;1Inicie j = 1;2Inicie i = 1;3Se vi < vi+1, troque a posicao i com posicao i+ 1 no vetor v;4Incremente i = i+ 15Se i n j, volte para a linha 4;6Incremente j = j + 17Se j n 1 , volte para a linha 3;8Retorne v.9

    Veja que a variavel j controla as etapas, por isso ela varia de 1 ate n1. Ja a variaveli controla as comparacoes dentro de cada etapa j, por isso ela varia de 1 ate n j.

    !

    ! Na linha 4 o elemento da posicao i sera trocado com o elemento da posicao i+ 1.Para isso e necessario utilizar uma variavel temporaria, se nao um dos elementosdo vetor sera perdido.

    No R a troca dos elementos entre as posicoes i e i + 1 pode ser feita da seguintemaneira: temp

  • Algoritmos de Ordenacao

    Se vi < vi+1, troque a posicao i com posicao i+ 1 no vetor v;4Incremente i = i+ 15Se i n 1, volte para a linha 4;6Defina w = (v1, v2, ..., vn1);7Defina wo =OrdenaBolhaRec(w);8Retorne vo = (wo, vn).9

    Veja que entre as linhas 3 e 6 o que esta sendo feito e levar o maior elemento para amaior posicao. Dessa forma o vetor w sera formado pelos elementos do vetor v a menos domaior deles, que agora esta na posicao de ndice n. Dessa forma wo guarda os elementosde v, a menos do maior deles, ja em ordem crescente. Entao v em ordem crescente seradefinido pela concatenacao entre os elementos em wo e o maior elementos de v, que estaguardado em vn.

    Repare que nos dois algoritmos acima se o vetor ficar ordenado no meio do processo oalgoritmo continua mesmo assim, ou seja, ele ira fazer todas as iteracoes e comparacoesmesmo que nenhuma troca seja realizada. Para evitar algumas comparacoes desnecessa-rias podemos introduzir uma variavel que indica se o vetor ja esta ou nao ordenado. Oprocesso sera interrompido caso ele esteja.

    Mas como saber se um vetor ja esta ordenado? Se em uma etapa j qualquer naoocorre nenhuma troca isso significa que o vetor ja esta ordenado.

    O pseudo-codigo a seguir e uma alternativa ao pseudo codigo nao recursivo ja apre-sentado acima. A diferenca e que neste foi introduzida uma variavel troca para evitaralgumas trocas desnecessarias.

    Entrada: vSada: vetor v arrumado em ordem crescente.Nome: OrdenaBolha2

    Defina n = tamanho do vetor v;1Inicie j = 1;2Inicie troca = F ;3Inicie i = 1;4Se vi < vi+1, troque a posicao i com posicao i+ 1 no vetor v e faca troca = T ;5Incremente i = i+ 16Se i n j, volte para a linha 5;7Incremente j = j + 18Se j n 1 e troca = T , volte para a linha 3;9Retorne v.10

    Veja que a variavel troca e um objeto do tipo "logical" que guarda TRUE ou FALSE.Sempre que iniciamos uma etapa essa variavel comeca com FALSE, veja linha 3. Ela seratrocada para TRUE quando acontecer uma primeira troca. Entao se chegarmos na linha 9com troca=FALSE significa que nao houve troca alguma e por isso sabemos que o vetor jaesta ordenado. Nesse caso nao devemos continuar as iteracoes, o processo e interrompido.

    A mesma modificacao pode ser feita tambem no algoritmo recursivo.

    Departamento de Estatstica - UFF 66

  • Algoritmos de Ordenacao

    Entrada: vSada: vetor v arrumado em ordem crescente.Nome: OrdenaBolhaRec2

    Defina n = tamanho do vetor v;1Se n = 1, retorne v;2Inicie troca = F ;3Inicie i = 1;4Se vi < vi+1, troque a posicao i com posicao i+ 1 no vetor v e faca troca = T ;5Incremente i = i+ 16Se i n 1, volte para a linha 5;7Se troca = F , retorne v;8Defina w = (v1, v2, ..., vn1);9Defina wo =OrdenaBolhaRec2(w);10Defina vo = (wo, vn);11Retorne vo.12

    8.2 Ordenacao Rapida (Quick Sort)

    A ideia desse metodo e ordenar o vetor da seguinte maneira:

    Primeiro o valor guardado na primeira posicao, chamado de pivo, sera levado paraa sua posicao correta de forma que os elementos a` esquerda sao menores que o pivoe os elementos a` direita sao maiores que o pivo.

    O passo seguinte e repetir o mesmo processo no sub-vetor a` esquerda e no sub-vetora` diretia do pivo.

    A questao e: como se leva o pivo para a sua posicao correta? Essa tarefa sera feitada seguinte maneira:

    Primeiro percorra o vetor a partir da posicao seguinte a do pivo ate encontrar umelemento maior que o pivo. Seja i a posicao desse elemento.

    Se nao existe elemento maior que o pivo, a posicao correta do pivo e a ultima.

    Caso contrario, percorra o vetor do final para o incio ate encontrar um elementomenor ou igual ao pivo. Seja j a posicao desse elemento.

    Se i < j, troque os elementos das posicoes i e j e recomece a busca por novos i e ja partir das posicoes trocadas.

    Se i > j, a posicao correta para o pivo e a posicao j.

    Vejamos como o mesmo vetor v do Exemplo 8.1.1 sera ordenado pelo metodo deOrdenacao Rapida.

    Exemplo 8.2.1 Suponha v = (37, 33, 48, 12, 92, 25, 86, 57) o vetor de entrada, ou seja, ovetor que queremos ordenar. O primeiro passo e encontrar a posicao correta do pivo, queno caso e o 25.

    Departamento de Estatstica - UFF 67

  • Algoritmos de Ordenacao

    37 33 48 12 92 25 86 57 definicao do pivo37 33 48 12 92 25 86 57 incio da busca por i37 33 48 12 92 25 86 57 definicao de i = 337 33 48 12 92 25 86 57 incio da busca por j37 33 48 12 92 25 86 5737 33 48 12 92 25 86 57 definicao de j = 637 33 25 12 92 48 86 57 como i < j, troca vi com vj37 33 25 12 92 48 86 57 incio da busca por i37 33 25 12 92 48 86 57 definicao de i = 537 33 25 12 92 48 86 57 incio da busca por j37 33 25 12 92 48 86 5737 33 25 12 92 48 86 5737 33 25 12 92 48 86 5737 33 25 12 92 48 86 57 definicao de j = 412 33 25 37 92 48 86 57 como i > j, troca o pivo com vj

    Veja que depois desses passos o pivo esta em sua posicao correta uma vez que antesdele estao os elementos menores que ele e depois os maiores. Agora o algoritmo e repetidopara o sub-vetor a` esquerda.

    12 33 25 37 92 48 86 57 definicao do vetor12 33 25 37 92 48 86 57 definicao de i = 212 33 25 37 92 48 86 57 incio da busca por j12 33 25 37 92 48 86 5712 33 25 37 92 48 86 57 definicao de j = 112 33 25 37 92 48 86 57 como i > j, troca o pivo com vj

    Nesse momento os elementos 12 e 37 ja estao em suas posicoes corretas. Agora vamosrefazer o processo para o sub-vetor a` direita do pivo 12, ou seja, agora vamos trabalharapenas com as posicoes de 2 e 3.

    12 33 25 37 92 48 86 57 definicao do pivo12 33 25 37 92 48 86 57 como nao existe elemento maior que o pivo,

    troque o pivo com vn12 25 33 37 92 48 86 57 definicao de j = 3

    Veja que depois desses passos o pivo 33 tambem esta em sua posicao correta. Agorao algoritmo e repetido para o seu sub-vetor a` direita, que tem apenas uma posicao, logoja esta ordenado. Como nao existe sub-vetor a esquerda do pivo 33 temos a seguintesituacao nesse momento:

    12 25 33 37 92 48 86 57

    Agora o processo sera repetido no sub-vetor a` direita do pivo 37. Ou seja, vamostrabalhar entre as posicoes 5-8.

    12 25 33 37 92 48 86 57 definicao do pivo12 25 33 37 92 48 86 57 incio da busca por i12 25 33 37 92 48 86 5712 25 33 37 92 48 86 5712 25 33 37 92 48 86 5712 25 33 37 57 48 86 92 como nao existe elemento maior que o pivo,

    troque o pivo com vn

    Departamento de Estatstica - UFF 68

  • Algoritmos de Ordenacao

    Agora o processo se repete no sub-vetor a` esquerda do pivo 92.

    12 25 33 37 57 48 86 92 definicao do pivo12 25 33 37 57 48 86 92 incio da busca por i12 25 33 37 57 48 86 92 definicao de i = 712 25 33 37 57 48 86 92 incio da busca por j12 25 33 37 57 48 86 92 definicao de j = 612 25 33 37 48 57 86 92 como i > j, troca o pivo com vj

    Como tanto o sub-vetor a esquerda quanto o sub-vetor a` direta do pivo 57 sao detamanho 1, eles ja estao ordenados e o processo termina.

    12 25 33 37 48 57 86 92

    E assim o vetor foi ordenado!

    Reparou que a ideia do algoritmo e recursiva? Caso base: se n = 1 retorna o propriovetor de entrada. Se nao, primeiro coloque o pivo na posicao correta, como explicadoacima. Em seguida defina we e wd como os sub-vetores a` esquerda e a` direita e apliquea funcao neles. O vetor ordenado sera a concatenacao entre we ordenado, o pivo e wdordenado.

    A implementacao de forma nao recursiva e bem mais complicada, por isso sera apenasapresentada a versao recursiva para o pseudo-codigo desse algoritmo.

    Entrada: vSada: vetor v arrumado em ordem crescente.Nome: OrdenaRapidoRec

    Defina n = tamanho do vetor v;1Se n = 1, retorne v;2Inicie i = 2 e j = n;3Se v1 < vi, va para a linha 8;4Incremente i = i+ 15Se i n, volte para a linha 4;6Troque a posicao de v1 com vn e retorne v.7Se v1 vj, va para a linha 11;8Decremente j = i 19Se j 1, volte para a linha 8;10Se i < j, troque as posicoes vi com vj e volte para a linha 5;11Troque as posicoes v1 com vj ;12Defina we = (v1, v2, ..., vj1);13Defina wd = (vj+1, v2, ..., vn);14Defina weo =OrdenaRapidoRec(we);15Defina wdo =OrdenaRapidoRec(wd);16Retorne vo = (weo, vj, wdo).17

    Departamento de Estatstica - UFF 69

  • Algoritmos de Ordenacao

    Exerccios - 8 Semana

    8.1 Implemente uma funcao que recebe como entrada um vetor v e retorna um vetorcom os mesmos elementos de v mas em ordem crescente a partir do algoritmo deOrdenacao Bolha visto na ultima aula teorica.

    (a) Faca seguindo a primeira implementacao sugerida: nao-recursiva e sem a variaveltroca.

    (b) Faca seguindo a segunda implementacao sugerida: recursiva e sem a variaveltroca.

    (c) Faca seguindo a terceira implementacao sugerida: nao-recursiva e com a variaveltroca.

    (d) Faca seguindo a quarta implementacao sugerida: recursiva e com a variaveltroca.

    8.2 Modifique as quarto funcoes implementadas no exerccio 8.1 acima de forma que elasretornem, alem do vetor ordenado, o numero de comparacoes realizadas para ordenaro vetor.

    8.3 Modifique as quarto funcoes implementadas no exerccio 8.1 acima de forma que elasretornem, alem do vetor ordenado, o numero de trocas realizadas para ordenar ovetor.

    8.4 Usando as funcoes ja implementadas, verifique quantas comparacoes cada uma delasprecisa para ordenar os seguintes vetores:

    (a) v

  • Algoritmos de Ordenacao

    8.7 Implemente uma funcao que recebe como entrada um vetor v e retorna um vetorcom os mesmos elementos de v mas em ordem crescente a partir do algoritmo deOrdenacao Rapida visto na ultima aula teorica.

    8.8 Modifique a funcao implementada no exerccio 8.7 acima de forma que ela retorne,alem do vetor ordenado, o numero de comparacoes realizadas para ordenar o vetor.

    8.9 Modifique a funcao implementada no exerccio 8.7 acima de forma que ela retorne,alem do vetor ordenado, o numero de trocas realizadas para ordenar o vetor.

    8.10 Verifique quantas comparacoes e quantas trocas sao necessarias para ordenar osmesmo vetores do exerccio 8.4 a partir da ordenacao rapida.

    8.11 Refaca a questao 8.7 de forma que o vetor retornado esteja em ordem decrescente emvez de em ordem crescente.

    Departamento de Estatstica - UFF 71

  • Semana 9: Complexidade deAlgoritmos

    Nessa ultima semana da segunda parte do curso sera apresentado uma nocao introdutoriasobre complexidade de algoritmos. A ideia e apresentar o conceito, alguns exemplos e asnotacoes usadas. Um estudo mais detalhado sobre esse tema precisaria de muito maisaulas.

    9.1 Nocao Introdutoria

    Analisar a complexidade de um algoritmo consiste em tentar calcular o custo para ocomputador em executar esse algoritmo. Esse calculo na maioria das vezes nao sera pre-ciso, mas a partir dele sera possvel comparar a complexidade entre diferentes algoritmos.Assim espera-se conseguir decidir entre dois algoritmos que realizam a mesma tarefa quale o mais eficiente, ou seja, qual tem a menor complexidade.

    Mas como podemos medir a complexidade de algoritmos? Uma alternativa e medir otempo de execucao, mas esse tempo varia de acordo com as especificacoes do computadore por isso nao seria uma boa medida de comparacao. Ao inves disso vamos contar onumero de iteracoes realizadas pelo algoritmo em questao.

    Exemplo 9.1.1 Suponha um algoritmo que recebe como entrada um vetor v e retorna omaior elemento desse vetor, como no pseudo-codigo abaixo.

    Entrada: vSada: maior elemento de v.

    Defina n = tamanho do vetor v;1Inicie max = v1;2Inicie i = 2;3Se max < vi, faca max = vi;4Incremente i = i+ 15Se i n, volte para a linha 4;6Retorne max.7

    E possvel calcular o numero de iteracoes realizadas quando a entrada e um vetor detamanho n? Veja que nesse caso serao feitas n 1 iteracoes.

    Como no exemplo acima na maioria das vezes o numero de iteracoes depende dotamanho dos argumentos de entrada, por isso o que vamos tentar encontrar e umaexpressao que nos diga o numero de operacoes em funcao de n.

    72

  • Complexidade de Algoritmos

    Em alguns casos fica ainda mais complicado de encontrar esse numero de operacoes.Veja no exemplo 9.1.2 a seguir.

    Exemplo 9.1.2 Suponha um algoritmo que recebe como entrada um vetor v e um numerok e busca a posicao de k dentro do vetor v como no pseudo-codigo abaixo.

    Entrada: v, kSada: posicao de k em v.

    Defina n = tamanho do vetor v;1Inicie i = 1;2Se vi = k, retorne i;3Incremente i = i+ 14Se i n, volte para a linha 3;5Imprima: O elemento nao pertence ao vetor;6Retorne NULL.7

    E nesse caso, e possvel calcular o numero de iteracoes realizadas quando a entradae um vetor de tamanho n? Para esse algoritmo o numero de iteracoes depende nao sode n como tambem de onde esta k. Por exemplo, se k for o primeiro elemento do vetorsera feita apenas 1 iteracao. Se k for o ultimo ou se nao houver elemento em v igual ak serao feitas n iteracoes. Na media, supondo que k tem chance igual de estar em cadauma das n posicoes, serao necessarias 1+2+...+n

    n= n+1

    2iteracoes.

    Dessa forma dizemos que no pior caso serao realizadas n iteracoes, no melhor caso 1iteracao e no caso medio n+1

    2operacoes.

    Devido a situacao exposta no Exemplo 9.1.2 em geral vamos analisar a complexidadede um algoritmo pensando separadamente no melhor caso, no pior caso e no caso medio.As vezes um algoritmo ganha no pior caso mas perde no caso medio, por isso a importanciaem separar os casos.

    9.2 A Notacao O

    Como ja foi comentado, na maioria das vezes a conta nao sera feita de forma exata devidoa dificuldade em fazer isso. Como estamos interessados em comparar a complexidade paraentradas grandes vamos apenas pensar qual algoritmo sera mais eficiente quando n,onde n e o tamanho da entrada.

    Suponha que o numero de iteracoes para realizar um certo algoritmo e definido porg(n). Vamos tentar classificar esse numero de operacao em algum tipo de ordem. Vejamosalgumas complexidades padroes:

    Se g(n) = c0 dizemos que o algoritmo e da ordem O(1);

    Se g(n) = cknk dizemos que o algoritmo e da ordem O(nk);

    Se g(n) = cn dizemos que o algoritmo e da ordem O(cn);

    Se g(n) = c log(n) dizemos que o algoritmo e da ordem O(log(n));

    Departamento de Estatstica - UFF 73

  • Complexidade de Algoritmos

    Se g(n) = n log(n) dizemos que o algoritmo e da ordem O(n log(n)).

    Vale a seguinte hierarquia:

    O(1) < O(log(n)) < O(n) < O(n log(n)) < O(n2) < O(n3) < . . . < O(cn)

    Alem disso, se g(n) = g1(n)+g2(n) a ordem do algoritmo sera a maior entre as ordemde g1 e g2.

    9.3 Exemplos Basicos de Complexidade

    9.3.1 Complexidade Constante - O(1)

    Sempre que o numero de operacoes nao depender dos argumentos de entrada o algoritmossera de ordem constante, isto e, sera O(1). Como exemplo temos o seguinte algoritmo.

    Entrada: nSada: indica se n e ou nao maior que 5.

    Se n > 5, retorne TRUE;1Retorne FALSE.2

    Veja que nesse caso g(n) = 1 e por isso dizemos que o algoritmo e de complexidadeconstante.

    9.3.2 Complexidade Logartmica- O(log(n))

    Acontece quando um problema de tamanho n e transformado em um problema de tama-nho n

    2em cada iteracao. Por exemplo, quando buscamos a posicao de um elemento em

    um vetor ordenado. Se o elemento procurado nao estiver na posicao central desse vetorpodemos busca-lo no sub-vetor a` esquerda ou a` direita, nao e preciso buscar no vetortodo.

    9.3.3 Complexidade Linear - O(n)

    Sempre que o numero de operacoes for proporcional a n o algoritmos sera de ordem linear,isto e, sera O(n). Como exemplo podemos citar o algoritmo que recebe um vetor e retornao seu maior elemento (Exemplo 9.1.1). Veja que nesse caso temos g(n) = n1. De formageral, sempre que tivermos um loop simples, isto e um for ou um while, o algoritmo serade ordem O(n). Alem disso, se tivermos dois loops seguidos (e nao um dentro do outro)o algoritmo tambem sera de ordem linear.

    9.3.4 Complexidade n log(n) - O(n log(n))

    Ocorre tipicamente quando um algoritmo divide o problema em dois problemas menorese resolve cada um deles separadamente. Geralmente isso ocorre a partir de um algoritmorecursivo. Como exemplo temos o algoritmo de Ordenacao Rapida visto na semana

    Departamento de Estatstica - UFF 74

  • Complexidade de Algoritmos

    passada. Veja que no caso da ordenacao rapida podemos dizer que g(n) = 1 + g(k) +g(n k 1) e g(1) = 1, com k < n e n indicando o tamanho do vetor de entrada.Sempre que o numero de iteracoes em um algoritmo tiver esse perfil ele sera da ordemO(n log(n)).

    9.3.5 Complexidade quadratica - O(n2)

    Ocorre tipicamente quando temos dois loops um dentro do outro. Como exemplo temosa soma de duas matrizes: se as matrizes de entrada forem n n o numero de iteracoessera dados por g(n) = n2, pois sera preciso percorrer cada posicao das matrizes.

    Tambem e O(n2) o pior caso e o caso medio do algoritmo de Ordenacao Bolha. Vejaque o melhor caso desse algoritmo e O(n), seria quando o vetor passado como entrada jaestivesse ordenado.

    9.3.6 Complexidade cubica - O(n3)

    Ocorre tipicamente quando temos tres loops um dentro do outro. Como exemplo temosa multiplicacao de matrizes: se as matrizes de entrada forem n n para cada posicaodas matrizes sera feito o produto interno entre os vetores linhas e colunas, para realizarcada produto interno sao necessarias n iteracoes, como isso sera feito para cada um dasn2 posicoes no final serao feitas n3 iteracoes.

    9.3.7 Complexidade exponencial - O(cn)

    Um tpico exemplo da complexidade exponencial e o calculo do n elemento da serie deFibonacci a partir do algoritmo recursivo. Tambem temos a torre de hanoi. Em geral umalgoritmo recursivo que depende de n que faz duas chamas recursiva simplificando paran 1 ou n 2 e de complexidade exponencial. Repare que a ordenacao rapida nao e,apesar de ter duas chamas recursivas cada uma delas foi diminuda de forma que a somadas duas ainda e menor que n.

    Departamento de Estatstica - UFF 75

  • Complexidade de Algoritmos

    Exerccios - 9 Semana

    9.1 Considere os algoritmos a seguir. Para cada um deles encontre a sua ordem decomplexidade. Justifique a sua resposta. Se quiser, implemente os algoritmos parafacilitar a sua analise.

    a) Algoritmo nao recursivo que retorna a soma dos elementos de um vetor de tamanhon passado como entrada.

    b) Algoritmo recursivo que retorna a soma dos elementos de um vetor de tamanho npassado como entrada.

    c) Algoritmo nao recursivo que retorna a soma dos elementos de uma matriz detamanho n n passada como entrada.

    d) Algoritmo nao recursivo que busca a posicao de um elementos passado como en-trada em uma matriz de tamanho n n tambem passada como entrada.

    e) Algoritmo nao recursivo que fornece o produto interno entre dois vetores de ta-manho n passados como entrada.

    f) Algoritmo nao recursivo que fornece o produto entre uma matriz de tamanho nne um vetor de tamanho n passados como entrada.

    g) Algoritmo nao recursivo que verifica se uma matriz de tamanho n n passadacomo entrada e simetrica ou nao.

    h) Algoritmo recursivo que retorna todas as permutacoes de um array de tamanhon passado como entrada (ex. 7.12)

    9.2 Considere os dois pseudo-codigos a seguir. Ambos recebem como entrada um numeronatural n e retorna o n-esimo termo da sequencia xn = 2xn1 + n, com x0 = 1.

    Entrada: nSada: xnNome: Seq1Se n = 0, retorne 1;Retorne 2Seq1(n 1) + n

    Entrada: nSada: xnNome: Seq2Se n = 0, retorne 1;Retorne Seq2(n 1)+Seq2(n 1) + n

    (a) Implemente cada um dos pseudo-codigos acima no R.

    (b) Teste as duas implementacoes para n = 15. Percebeu alguma diferenca no tempode execucao?

    (c) Vamos agora fazer um grafico dos tempos de execucao em funcao do valor deentrada em cada funcao. Para isso use os comandos plot e Sys.time(), esteultimo retorna o instante de tempo em que o comando foi chamada. Analise osgraficos gerados e deduza a ordem de complexidade de cada uma das implemen-tacoes.OBS: Veja uma sugestao de codigo para o grafico no final desta lista.

    (d) O que tem de diferente nas duas implementacoes para uma ser tao mais demoradaque a outra?

    9.3 Fibonacci com Recursao:

    Departamento de Estatstica - UFF 76

  • Complexidade de Algoritmos

    (a) Refaca a funcao que retorna o n-esimo elemento da sequencia de Fibonacci usandorecursao.

    (b) Verifique o tempo de execucao para n = 1, 2, . . . , 30, ou seja, o tempo que a funcaodemora para rodar. Para isso crie um vetor de tamanho 30 que guarda o tempode execucao para cada n = 1, 2, . . . , 30. Para isso use o comando Sys.time()sugerido anteriormente.

    (c) Faca um grafico de n versus o tempo de execucao.

    (d) Analisando o grafico, o que voce diria da ordem desse algoritmo?

    (e) Esse algoritmo e de ordem O(2n). Essa informacao esta de acordo com o grafico?

    (f) Veja que para n um pouco maior que 30 ja demora muito para rodar.

    OBS: Se fizermos as contas podemos ver que para n = 100 o algoritmo ja fica im-possvel de rodar. Considerando que uma operacao leva um picosegundo (1 1012segundos), 2100 operacoes levam 2100 1012 s = 30.000.000.000.000 anos!!!

    9.4 Fibonacci sem Recursao:

    (a) Implemente o passo-a-passo a seguir e verifique que ele fornece o n-esimo termoda sequencia de Fibonacci sem usar recursao.

    Se n = 1 ou n = 2 retorne 1.1Defina penultimo = 1;2Defina ultimo = 1;3Inicie i = 3;4Defina atual = ultimo+ penultimo;5Atualize penultimo = ultimo;6Atualize ultimo = atual;7Incremente i = i+ 1;8Se i n, volte para a linha 5;9Retorne atual.10

    (b) Analisando o codigo implementado, qual a ordem desse algoritmo?

    (c) Como na questao anterior, gere um vetor com os tempos de execucao.

    (d) Faca um grafico de n versus o tempo de execucao.

    (e) Analisando o grafico, o que voce diria da ordem desse algoritmo?

    (f) Para o grafico ficar mais explicativo, gere um vetor que guarda os tempos de exe-cucao para n = 1, 2001, 4001, 6001, ..., 40001 e em seguida faca um novo grafico.

    9.5 Vamos agora comparar o tempo de execucao para o pior caso entre os dois algoritmosde ordenacao vistos na semana passada.

    (a) Escolha um dos algoritmos ja implementados que ordenam um vetor passadocomo entrada pelo metodo de Ordenacao Bolha. Veja que para esse metodoo pior caso e quando o vetor esta na ordem inversa, por exemplo (1, 2, 3, 4, 5).Entao, com base no codigo ao final dessa lista de exerccios, dentro do for paracada i defina um vetor v = (i, i 1, . . . , 2, 1) e rode o metodo bolha nesse vetor.

    Departamento de Estatstica - UFF 77

  • Complexidade de Algoritmos

    Faca ao final o grafico do tempo de execucao em funcao do tamanho do vetor deentrada. Em vez de subir o tamanho do vetor de entrada de um em um use umwhile e suba de 10 em 10.

    (b) Faca o mesmo para a Ordenacao Rapida, mas veja que nesse caso o pior caso jae o vetor ordenado. Entao o vetor v definido dentro do for sera v = (1, 2, . . . , i).Faca ao final o grafico do tempo de execucao em funcao do tamanho do vetor deentrada.

    Sugestao de codigo para fazer o grafico do tempo de execucao de uma funcao f em funcaodo argumento de entrada, supondo este inteiro.

    > Temp for(i in 1:20){

    + ta

  • Parte III

    Uma Introducao ao CalculoNumerico

    79

  • Semana 10: Aproximacao de Funcoes porSeries de Taylor

    Na terceira parte do curso serao vistos alguns metodos numericos. Nessa primeira semanavamos aprender de que forma o computador calcula funcoes como exp(x), log(x), sin(x),entre outras. Para isso vamos estudar a aproximacao de funcao pela Serie de Taylor.

    10.1 Serie de Taylor

    Definicao 10.1.1 Se uma funcao f e definida em 0 e n vezes diferenciavel em 0, istoe existe f(0) e f (i)(0) para i = 1, 2, . . . , n, definimos o n-esimo Polinomio de Maclaurinpara f como sendo:

    pMn (x) = f(0) + f(0)x+

    f (0)x2

    2!+f (0)x3

    3!+ . . .+

    f (n)(0)xn

    n!=

    ni=0

    f (i)(0)xi

    i!

    Veja que o n-esimo Polinomio de Maclaurin para f e um polinomio de grau n quesatisfaz as seguintes propriedades:

    pMn (0) = f(0).

    pM(i)n (x)|x=0 = f (i)(x)|x=0. pM1 (x) e a aproximacao linear local de f em torno de x = 0; p

    M2 (x) e a aproximacao

    quadratica local de f em torno de x = 0; e assim por diante.

    Entao para pontos x perto de 0 pMn (x) e uma aproximacao para f(x).

    Quanto mais proximo x esta de 0, melhor e a aproximacao.

    Quanto maior o valor de n, melhor sera a aproximacao.

    O Polinomio de Maclaurin e um caso particular do Polinomio de Taylor quando x0 = 0.Veja a definicao formal do Polinomio de Taylor.

    Definicao 10.1.2 Se uma funcao f e definida em x0 e n vezes diferenciavel em x0, istoe existe f (i)(x0) para i = 1, 2, . . . , n, definimos o n-esimo Polinomio de Taylor para f emtorno de x0 como sendo:

    pTn (x) = f(x0) + f(x0)(x x0) + . . .+ f

    (n)(x0)(x x0)nn!

    =ni=0

    f (i)(x0)(x x0)ii!

    80

  • Aproximacao de Funcoes por Series de Taylor

    Assim como o Polinomio de Maclaurin, o n-esimo Polinomio de Taylor para f emtorno de x0 e um polinomio de grau n que satisfaz as seguintes propriedades:

    pTn (x0) = f(x0).

    pT (i)n (x)|x=x0 = f (i)(x)|x=x0 . p1(x) e a aproximacao linear local de f em torno de x = x0; p2(x) e a aproximacao

    quadratica local de f em torno de x = x0; e assim por diante.

    Entao para pontos x perto de x0 pTn (x) e uma aproximacao para f(x).

    Quanto mais proximo x esta de x0, melhor e a aproximacao.

    Quanto maior o valor de n, melhor sera a aproximacao.

    O que vamos fazer nessa semana e usar os polinomios acima para aproximar as funcoesque nao sabemos fazer as contas na mao. Veja algumas aplicacoes nas secoes a seguir.

    10.2 Aproximacao para a funcao exponencial

    Queremos encontrar uma aproximacao de f(x) = ex para um x qualquer usando o Po-linomio de Taylor. O primeiro passo e escolher qual x0 usar. Veja que e preciso conhecerf(x0), f

    (x0), f (x0), . . . Qual seria uma sugestao natural? So sabemos essa informacaopara x0 = 0, nesse caso vamos trabalhar com o Polinomio de Maclaurin.

    Veja que para f(x) = ex temos todas as derivadas iguais a ex. Logo f (i)(0) = e0 = 1para qualquer valor de i. Entao, o n-esimo Polinomio de Taylor em torno de x0 = 0 (oun-esimo Polinomio de Maclaurin) para f(x) = ex e definido por:

    pMn (x) = 1 + x+x2

    2!+x3

    3!+ . . .+

    xn

    n!=

    ni=0

    xi

    i!

    E como vamos usar esse polinomio para aproximar f(x) = ex em um x qualquer?Vamos simplesmente calcular o n-esimo termo dessa serie para um n que seja grande osuficiente para garantir que a aproximacao seja razoavelmente boa. Veja no exemplo aseguir.

    Exemplo 10.2.1 Suponha que voce esteja em uma ilha deserta, isto e sem calculadoraou computador, e precisa muito calcular o valor de e1.5 = e

    32 . Como voce consegue

    encontrar essa resposta? Ou pelo menos uma aproximacao boa para ela? Basta usar oPolinomio de Maclaurin (que nada mais e do que o Polinomio de Taylor em torno dex0 = 0).

    Veja qual seria a aproximacao se usarmos o polinomio de grau 2:

    e1.5 = e32 1 +

    (3

    2

    )+

    (32

    )22!

    = 1 32

    +9

    8=

    8 12 + 98

    =5

    8= 0.625

    Departamento de Estatstica - UFF 81

  • Aproximacao de Funcoes por Series de Taylor

    E se quisermos uma aproximacao mais precisa podemos usar o polinomio com graumaior. Vamos ter que fazer um pouco mais de contas, mas teremos uma aproximacaomelhor. Por exemplo veja a aproximacao se usarmos o polinomio de grau 3.

    e1.5 = e32 1 +

    (3

    2

    )+

    (32

    )22!

    +

    (32

    )33!

    =5

    8 9

    16=

    10 916

    =1

    16= 0.062

    Usando o polinomio de grau 4.

    e1.5 = e32 1 +

    (3

    2

    )+

    (32

    )22!

    +

    (32

    )33!

    +

    (32

    )44!

    =1

    16+

    27

    128=

    35

    128 0.2734

    Usando o polinomio de grau 5.

    e1.5 = e32 1+

    (3

    2

    )+

    (32

    )22!

    +

    (32

    )33!

    +

    (32

    )44!

    +

    (32

    )55!

    =35

    128 81

    1280=

    269

    1280 0.2101

    Se usarmos a calculadora vamos encontrar a seguinte aproximacao para e1.5 =0.223130. Veja que realmente as aproximacoes a partir do Polinomio de Maclaurin me-lhoraram quando o grau do polinomio cresceu.

    Se tivermos um computador podemos criar um programa que faca as contas paraa gente. Mas como escolher que grau usar? Podemos verificar o incremento entre duasaproximacoes consecutivas e parar quando este for relativamente pequeno, ou seja, quandoa aproximacao para o grau usado e para o grau seguinte for praticamente a mesma. Vejacomo isso sera feito no pseudo-codigo a seguir.

    Entrada: x e erro.Sada: uma aproximacao para ex.Nome: AproxExp.

    Inicie i = 1;1Defina y = x2Inicie soma = 1 + y;3Se |y| < erro, retorne soma;4Incremente i = i+ 1;5Defina y = x

    i

    i!;6

    Incremente soma = soma+ y;7Volte para a linha 4.8

    Veja que a linha 6 poderia ser alterada para y = y xi. Isso tornaria o codigo mais

    eficiente.O pseudo-codigo acima simplesmente calcula a serie ate que o incremento da serie,

    definido por y, seja menor que o erro escolhido pelo usuario e passado como argumento.Garantimos que isso em algum momento acontece uma vez que x

    n

    n!n

    0 para todo

    x R.A escolha do erro e feita pelo usuario. Geralmente se escolhe valores muito pequenos,

    como por exemplo, erro = 103 = 0.001 ou ate menores. Quando procura-se uma aproxi-macao k casas decimais exatas usamos em geral um erro de 10k, pois assim garantimosque aproximacoes consecutivas coincidirao nas primeiras k casas decimais.

    Departamento de Estatstica - UFF 82

  • Aproximacao de Funcoes por Series de Taylor

    10.3 Aproximacao para a funcao logaritmo

    Agora queremos encontrar uma aproximacao de f(x) = ln(x) para qualquer x > 0 usandoo Polinomio de Taylor. Novamente o primeiro passo e escolher qual x0 usar. Nesse casox0 = 0 nao e uma alternativa uma vez este ponto nem faz parte do domnio da funcaof . Lembre-se que e preciso escolher x0 tal que se conheca f(x0), f

    (x0), f (x0), . . . Qualseria uma sugestao natural? Sabemos o valor de f(x0) = ln(x0) somente para x0 = 1,entao sera essa a nossa escolha.

    Veja que para f(x) = ln(x) temos:

    f (x) =1

    x= x1, f (x) = 1

    x2= x2, f (3)(x) = 2

    x3= 2x3

    f (4)(x) = 6x4

    = 6x4, f (5)(x) = 24x5

    = 24x5, . . .

    De forma geral:

    f (i)(x) = (1)i+1 (i 1)!xi

    .

    Logo f (i)(x0) = f(i)(1) = (1)i+1(i 1)! para qualquer valor de i. Entao, o n-esimo

    Polinomio de Taylor em torno de x0 = 1 para f(x) = ln(x) e definido por:

    pTn (x) = 0 + (x 1)(x 1)2

    2+

    (x 1)33

    (x 1)4

    4+ . . .+

    (1)n+1(x 1)nn

    Da mesma forma que no exemplo da exponencial, vamos usar o polinomio de Taylorpara encontrar uma aproximacao para f(x) = ln(x). Veja no exemplos a seguir.

    Exemplo 10.3.1 Como encontrar uma aproximacao para ln(0.5) sem usar calculadoraou computador? Usando o Polinomio de Taylor em torno de x0 = 1. Veja como fica aaproximacao se usarmos o polinomio de grau 4.

    ln(0.5) = ln

    (1

    2

    )(

    1

    2 1)(12 1)22

    +

    (12 1)33

    (12 1)44

    = 12 1

    8 1

    24 1

    64=

    =96 24 8 3

    192= 130

    192 0.677

    Se usarmos uma calculadora vamos encontrar a seguinte aproximacao: ln(0.5) 0.6931. Veja que ja estamos bem perto.

    Vamos agora encontrar uma aproximacao para ln(0.2) usando novamente o polinomiode grau 4.

    ln(0.2) = ln

    (1

    5

    )(

    1

    5 1)(15 1)22

    +

    (15 1)33

    (15 1)44

    = 4516

    50 64

    375 256

    2500=

    = 45 16

    50 64

    375 6000 2400 1280 768

    7500= 10448

    7500= 2612

    1875 1.393

    Fazendo a conta na calculadora chegamos no valor aproximado ln(0.2) 1.609.Veja que usando o Polinomio de Taylor de mesmo grau, no caso 4, conseguimos umaaproximacao melhor para ln(0.5) do que para ln(0.2). Por que? Porque quanto maisproximo de x0 melhor sera a aproximacao.

    Departamento de Estatstica - UFF 83

  • Aproximacao de Funcoes por Series de Taylor

    !

    ! Mas para o caso de f(x) = ln(x) temos um problema: so e possvel garantir quepTn (x)

    nln(x) se x for tal que |x 1| < 1. Isso por que so para x tal que

    |x 1| < 1 o incremento (1)n+1(x1)nn

    n

    0. Entao o Polinomio de Taylor para

    f(x) = ln(x) so garante uma boa aproximacao quando n cresce para ln(x) com0 < x < 2.

    E se quisermos calcular ln(10), por exemplo? Nesse caso a solucao sera usar as pro-priedades do logaritmo. Veja como isso sera feito.

    Seja x > 0 tal que x 2. Entao a primeira observacao e que 1x 1

    2, logo podemos usar

    o polinomio para encontrar uma aproximacao para ln( 1x). Lembrando das propriedades

    do logaritmo sabemos que ln( 1x) = ln(1) ln(x) = 0 ln(x) = ln(x). Entao, ln(x) =

    ln( 1x). Dessa forma para encontrar uma aproximacao para ln(x) com x 2 vamos na

    verdade buscar uma aproximacao para ln( 1x) e retornar o oposto do resultado encontrado.

    Exemplo 10.3.2 Encontre uma aproximacao para ln(3) usando o Polinomio de Taylorde grau 4.

    ln(3) = ln(

    1

    3

    )

    ((1

    3 1)(13 1)22

    +

    (13 1)33

    (13 1)44

    )=

    = (2

    3 2

    9 8

    81 16

    324

    )=

    216 + 72 + 32 + 16

    324=

    336

    324 1.037

    Usando a calculadora chegamos em ln(3) 1.0986.Veja no pseudo-codigo a seguir como fica o algoritmo para encontrar uma aproxima-

    cao para ln(x). Assim como no caso para a aproximacao da exponencial, o algoritmoincrementa o grau do polinomio ate encontrar uma aproximacao boa.

    Entrada: x e erro.Sada: uma aproximacao para ln(x).Nome: AproxLn.

    Se x 0, pare e retorne mensagem de erro;1Se x 2, retorne AproxLn( 1

    x,erro);2

    Inicie i = 1;3Defina y = x 14Inicie soma = y;5Se |y| < erro, retorne soma;6Incremente i = i+ 1;7

    Defina y = (1)i+1(x1)ii

    8

    Incremente soma = soma+ y;9Volte para a linha 6.10

    Veja que a linha 8 poderia ser alterada para y = y (x1)(i1)i

    . Isso tornaria o codigomais eficiente.

    Departamento de Estatstica - UFF 84

  • Aproximacao de Funcoes por Series de Taylor

    Exerccios - 10 Semana

    10.1 A partir do Polinomio de Maclaurin de grau 4 para a funcao f(x) = ex visto emsala de aula encontre uma aproximacoes para f(1) = e1 e f(3) = e3. Faca as contasna mao.

    10.2 a) Implemente uma funcao que recebe como entrada x R e n N e retorna ovalor do n-esimo Polinomio de Maclaurin para f(x) = ex avaliado em x. Isto

    e, retorna pMn (x) =n

    i=0xi

    i!(veja pagina 81). Vamos chamar essa funcao de

    pol_exp(x,n).

    b) Digite o codigo a seguir para ver como o Polinomio de Maclaurin se aproxima dafuncao conforme o grau do polinomio cresce.

    > plot(exp,-4,4)

    > grid()

    > segments(x0=0,y0=0,x1=0,y1=150,lty=2)

    > curve(pol_exp(x,n=2),add=T,col="violet")

    > curve(pol_exp(x,n=3),add=T,col="red")

    > curve(pol_exp(x,n=4),add=T,col="blue")

    > curve(pol_exp(x,n=5),add=T,col="green")

    Veja que a aproximacao melhora quanto mais perto de x0 = 0 for o ponto avaliadoou quando maior for o valor de n.

    10.3 a) Implemente o pseudo-codigo visto em sala de aula que recebe como entrada x Re um erro e retorna uma aproximacao para ex.

    b) Use a funcao implementada acima e encontre aproximacoes para e, e1, e3,e

    e e7.3 com 3 e 5 casas decimais exatas. Compare os resultados com os valoresfornecidos pela funcao exp do R.

    c) Refaca a funcao implementada em 3a de forma que alem da aproximacao para ex

    ela tambem retorne o grau do Polinomio de Maclaurin usado para realizar essaaproximacao. Refaca tambem os testes sugeridos em 3b.

    d) Usando a funcao implementada no item 3a, isto e, a aproximacao para ex, im-plemente um outra funcao que recebe como entrada x e um erro e retorna umaaproximacao para ex

    2/2.

    10.4 a) Encontre o polinomio de Maclaurin para a funcao f(x) = e3x.

    b) Para exercitar, ainda no caderno e sem a ajuda do computador, encontre umaaproximacao para f(1) = e3 usando o Polinomio de Maclaurin de grau 4.

    c) Qual das duas aproximacoes para e3 voce acredita ser mais precisa, a encontradano item 1 ou no item 4b? Por que?

    d) Ainda no caderno escreva um pseudo-codigo que recebe como entrada um numeroreal x e um erro e retorna uma aproximacao para f(x) = e3x.

    e) Implemente o pseudo-codigo escrito no item anterior.

    f) Use a funcao implementada acima e encontre aproximacoes para e3, e1 e e1.5

    com 3 e 5 casas decimais exatas. Compare os resultados com os valores fornecidospela funcao exp do R.

    Departamento de Estatstica - UFF 85

  • Aproximacao de Funcoes por Series de Taylor

    10.5 a) A partir do polinomio de Taylor de grau 3 em torno de x0 = 1 para a funcaof(x) = ln(x) visto em sala de aula encontre encontre uma aproximacoes paraf( 1

    10) = ln( 1

    10), f(3

    5) = ln(3

    5) e f(4) = ln(4). Faca as contas na mao.

    b) Sem olhar os valores exatos quais das aproximacoes encontradas no item 5a voceacha que e mais precisa, a aproximacao para ln( 1

    10) ou para ln(3

    5)? Por que?

    10.6 a) Implemente uma funcao que recebe como entrada x R e n N e retorna ovalor do n-esimo Polinomio de Taylor para f(x) = ln(x) em torno de x0 = 1avaliado em x (veja pagina 83). Vamos chamar essa funcao de pol_ln(x,n).

    b) Digite o codigo a seguir para ver como o Polinomio de Taylor se aproxima dafuncao conforme o grau do polinomio cresce.

    > plot(log,0,4)

    > grid()

    > segments(x0=1,y0=-4,x1=1,y1=10,lty=2)

    > curve(pol_ln(x,n=2),add=T,col="violet")

    > curve(pol_ln(x,n=3),add=T,col="red")

    > curve(pol_ln(x,n=4),add=T,col="blue")

    > curve(pol_ln(x,n=5),add=T,col="green")

    Veja que a aproximacao melhora quanto mais perto de x0 = 1 for o ponto avaliadoou quando maior for o valor de n.

    10.7 a) Implemente o pseudo-codigo visto em sala de aula que recebe como entrada umnumero real positivo x e um erro retorna uma aproximacao para ln(x).

    b) Use a funcao implementada acima e encontre aproximacoes para ln(0.1), ln(2),ln(10) e ln(3.8) com 3 e 5 casas decimais exatas. Compare os resultados com osvalores fornecidos pela funcao ln do R.

    c) Implemente agora uma funcao que retorna o logaritmos de x em qualquer base, ouseja, essa nova funcao recebe como entrada x, b e erro e retorna uma aproximacaopara logb(x). Para isso lembre-se da seguinte propriedade:

    logb(x) =loga(x)

    loga(b) a, b, x R+.

    Dica: essa nova funcao deve chamar a funcao implementada em 7a e usar apropriedade acima considerando a = e.

    10.8 a) Encontre o polinomio de Maclaurin para a funcao f(x) = sen(x).

    b) No caderno escreva um pseudo-codigo que recebe como entrada um numero realx e um erro e retorna uma aproximacao para sen(x).

    c) Implemente o pseudo-codigo escrito no item anterior.

    d) Use a funcao implementada acima e encontre aproximacoes para sen(1), sen(25),sen(50o) e sen(pi

    3) com 3 e 5 casas decimais exatas. Compare os resultados com

    os valores fornecidos pela funcao sin do R.

    OBS: Para encontrar sen(50o) primeiro e preciso achar o angulo em radiano. Tantopara esse calculo quanto para o calculo de sen(pi

    3) sera necessario a utilizacao do

    numero irracional pi. Use o comando pi no R ou a aproximacao para pi encontradano exerccio 7.3.

    Departamento de Estatstica - UFF 86

  • Semana 11: Aproximacao de Razes deFuncoes Reais

    Encontrar razes de funcoes tem diversas aplicacoes praticas, como por exemplo, encon-trar aproximacoes para numeros irracionais ou achar maximo de funcoes. Nessa semanaveremos dois metodos numericos para encontrar aproximacoes de razes: o metodo da bis-secao e o metodo de Newton-Raphson. Existem ainda outros que nao serao apresentadosno curso, como por exemplo, Metodo do Ponto Fixo e Metodo da Secante.

    11.1 Preliminares

    Primeiro vamos lembrar o que e raiz de uma funcao real.

    Definicao 11.1.1 Seja f : R R uma funcao real. Dizemos que x R e raiz de fquando f(x) = 0.

    O problema de encontrar razes de uma funcao real muitas vezes e bem facil. Sabemos,por exemplo, achar facilmente as razes das funcoes f(x) = x + 3, f(x) = x2 x + 4,f(x) = 1 ex, f(x) = ln(x + 1). Mas dependendo da expressao da funcao f encontrarsuas razes pode ser uma tarefa muito difcil, como por exemplo para as funcoes f(x) =x3 + 2x2 x + 1, f(x) = x + ln(x), f(x) = ex + x2 2. Nesses casos o problemasera resolvido de forma aproximada a partir de metodos numericos, como veremos nessasemana.

    Antes de aplicar um metodo numerico para encontrar uma raiz pode ser de grandeajuda um estudo previo da funcao f a fim de conhecer melhor a localizacao dessa raiz.Isto e, analisar a funcao para a qual se busca as raizes e tentar identificar um intervalo[a, b] que contenha a raiz procurada. Esse estudo pode ser a partir do Teorema de Bolanoou por metodos graficos.

    Teorema 11.1.2 (Teorema de Bolzano) Seja f uma funcao contnua em um intervalo[a, b], tal que, f(a)f(b) < 0 (isto e, o sinal de f(a) e f(b) sao diferentes). Entao a funcaof possui pelo menos uma raiz no intervalo [a, b].

    Assim, se f e uma funcao contnua, para encontrar um intervalo [a, b] em que f possuipelo menos uma raiz basta encontrar a e b tais que f(a) e f(b) tenham sinais diferentes.Esse resultado sera de grande utilidade para o Metodo da Bissecao.

    Outra alternativa, que nem sempre e possvel, e usar graficos para encontrar esseintervalo. Nesse caso a vantagem e que muitas vezes podemos saber exatamente quantasrazes existem no intervalo. Veja a seguir dois exemplos em que o grafico de f e usadopara encontrar um intervalo [a, b] em que f possui pelo menos uma raiz.

    87

  • Aproximacao de Razes de Funcoes Reais

    Exemplo 11.1.3 Seja f(x) = ex+x22. Queremos nesse exemplo encontrar intervalosreais que contenham a raiz procurada. Veja que nesse caso e possvel afirmar que f(x) =g(x)h(x), com g(x) = ex e h(x) = 2x2. Logo, f(x) = 0 se e somente se g(x) = h(x).Nao sabemos ainda resolver a equacao, mas sabemos desenhar o grafico de g e h. Asrazes de f serao as abcissas dos pontos de intercessao da curva de g com h. Veja ografico apresentado na Figura 11.1.

    Figura 11.1: Graficos das curvas g(x) = ex e h(x) = 2 x2 (Exemplo 11.1.3).

    Logo, podemos afirmar que existe uma raiz de f no intervalo [2,1] e outra nointervalo [0, 1].

    Exemplo 11.1.4 O mesmo pode ser feito para encontrar um intervalo [a, b] onde a fun-cao f(x) = x + ln(x) 2 possui pelo menos uma raiz. Vamos desenhar o grafico deg(x) = ln(x) e h(x) = x+ 2 e procurar as intercessoes das duas curvas. Veja o graficoapresentado na Figura 11.2. Assim podemos afirmar que a unica raiz de f esta dentrodo intervalo [1, 2].

    11.2 Metodo da Bissecao

    Para que o metodo da Bissecao seja aplicado e preciso primeiro conhecer um intervalo[a, b] tal que f(a) e f(b) tenham sinais opostos, isto e, tal que f(a)f(b) < 0. Dessa forma,de acordo com o Teorema de Bolzano, podemos garantir que existe pelo menos uma raiznesse intervalo. O que o metodo vai fazer e retornar uma aproximacao para uma dessasrazes.

    A ideia do metodo e dividir o intervalo [a, b] ao meio e, usando o resultado do Teoremade Bolzano, decidir em qual dos dois lados a raiz esta. Ou seja, comecamos com [a, b]tal que f(a)f(b) < 0 e depois de um passo chegamos em dois outros intervalos: [a, a+b

    2] e

    [a+b2, b]. Calculando o valor de f(a+b

    2) e comparando o seu sinal com os sinais de f(a) e

    f(b) podemos determinar em qual dos dois subintervalos a raiz esta.Se f(a)f(a+b

    2) < 0 sabemos que a raiz esta no intervalo [a, a+b

    2], caso contrario teremos

    f(b)f(a+b2

    ) < 0 e com isso podemos concluir que a raiz esta no intervalo [a+b2, b]. Veja

    Departamento de Estatstica - UFF 88

  • Aproximacao de Razes de Funcoes Reais

    Figura 11.2: Graficos das curvas g(x) = ln(x) e h(x) = x+ 2 (Exemplo 11.1.4).

    que dessa forma chegamos em um intervalo menor tal que a funcao f avaliada nos pontosextremos desse intervalo tem sinais opostos. O processo e repetido e em cada iteracaochegamos em um intervalo cada vez menor, ou seja, estamos cada vez mais proximos deuma raiz de f .

    Exemplo 11.2.1 Seja f(x) = x3 x 4. Nesse exemplo vamos encontrar uma aproxi-macao para uma raiz real de f . Primeiro veja que a funcao f possui uma raiz no intervalo[0, 2], uma vez que f(0) = 4 e f(2) = 2. Entao vamos realizar 4 iteracoes do metodo dabissecao para encontrar na mao uma aproximacao para uma raiz de f nesse intervalo.

    Comecamos com a = 0 e b = 2: f(a) = f(0) = 4 < 0 e f(b) = f(2) = 2 > 0.Definimos entao m como sendo o ponto medio entre a e b: m = a+b

    2= 1. Veja que

    f(m) = f(1) = 4. Como f(m) e f(b) tem sinais opostos podemos afirmar que existeuma raiz dentro do intervalo [m, b] = [1, 2]. Veja que chegamos em um intervalo menorque o original.

    Vamos fazer agora tudo de nova a partir desse novo intervalo [1, 2]. Entao na segundaiteracao do metodo temos a = 1 e b = 2 tais que f(a) < 0 e f(b) > 0. Definimos entaom como sendo o ponto medio entre a e b: m = 1+2

    2= 3

    2. Veja que f(m) = 27

    8 3

    2 4 =

    2724328

    < 0. Entao f(m) e f(b) tem sinais opostos e por isso podemos afirmar que existeuma raiz dentro do intervalo [m, b] = [3

    2, 2]. E assim reduzimos ainda mais o tamanho do

    intervalo que contem a raiz que estamos procurando.Na terceira iteracao temos a = 3

    2e b = 2, assim definimos m =

    (32

    + 2)

    12

    = 74. Veja

    que f(m) = 34364 7

    4 4 = 343112256

    64< 0. Entao f(m) e f(b) tem sinais opostos e por

    isso podemos afirmar que existe uma raiz dentro do intervalo [m, b] = [74, 2]. E assim

    reduzimos ainda mais o tamanho do intervalo que contem a raiz que estamos procurando.A quarta e ultima iteracao realizada nesse exerccio comeca com a = 7

    4e b = 2.

    Defina m =(74

    + 2)

    12

    = 158

    . Veja que f(m) = 3375512 15

    8 4 = 33759602048

    512> 0. Entao

    f(a) e f(m) tem sinais opostos e por isso podemos afirmar que existe uma raiz dentrodo intervalo [a,m] = [7

    4, 15

    8]. E assim reduzimos ainda mais o tamanho do intervalo que

    contem a raiz que estamos procurando.

    Departamento de Estatstica - UFF 89

  • Aproximacao de Razes de Funcoes Reais

    Veja que ao final de 4 iteracoes podemos afirmar que existe uma raiz dentro do in-tervalo [7

    4, 15

    8] = [1.75, 1.875], entao com certeza o ponto medio desse intervalo dista da

    verdadeira raiz no maximo(158 7

    4

    )12

    = 116

    = 0.0625. Ou seja,(158

    + 74

    )12

    = 2916

    = 1.8125e uma aproximacao para a raiz de f com erro de no maximo 0.0625.

    Seguindo a ideia apresentada no exemplo podemos fazer com que o computador realizediversas iteracoes do metodo da bissecao ate alcancar a precisao desejada. Ou seja ousuario indica um erro e quando o algoritmo chegar em um intervalo [an, bn] de diametromenor que , isto e bnan < , podemos afirmar que qualquer ponto desse intervalo distamenos que de uma raiz de f .

    Veja a seguir o pseudo-codigo de uma funcao que recebe como entrada a, b, f e eretorna uma aproximacao com erro menor que para uma raiz de f dentro do intervalo[a, b] a partir do Metodo da Bissecao.

    Entrada: a, b, f e .Sada: uma aproximacao para uma raiz de f dentro do intervalo [a, b].Nome: RaizBissecao.

    Se f(a) e f(b) tem sinais opostos, pare e retorne erro.1Defina m = a+b

    2, o ponto medio do intervalo [a, b];2

    Se b a < , retorne m;3Se f(a)f(m) < 0, faca b = m e volte para a linha 2;4Caso contrario, faca a = m e volte para a linha 2.5

    Veja que na linha 4 quando fazemos b = x estamos escolhendo ficar com o intervalo[a, a+b

    2] pois e nesse subintervalo que a raiz esta. Ja na linha 5 a escolha e por ficar com o

    subintervalo [a+b2, b], uma vez que f(a)f(x) > 0 e isso indica que a e x tem mesmo sinal

    logo b e x tem sinais opostos.Dica: Talvez fique mais simples se o algoritmo for implementado usando o repeat.O algoritmo tambem pode ser implementado de forma recursiva. Veja como no pseudo-

    codigo a seguir.

    Entrada: a, b, f e .Sada: uma aproximacao para uma raiz de f dentro do intervalo [a, b].Nome: RaizBissecaoRec.

    Se f(a) e f(b) tem sinais opostos, pare e retorne erro.1Defina m = a+b

    2, o ponto medio do intervalo [a, b];2

    Se b a < , retorne m;3Se f(a)f(m) < 0, retorne RaizBissecaoRec(a,m, f, );4Caso contrario, retorne RaizBissecaoRec(a,m, f, );5

    Algumas vantagens desse metodo: se conseguimos um intervalo [a, b] tal que f(a) ef(b) tem sinais opostos, temos a garantia de que o metodo converge para uma raiz def ; ao final do metodo sabemos que chegamos em uma aproximacao com precisao , ouseja, o valor x fornecido pelo metodo e tal que |x | < , onde e a rais procurada edesconhecida.

    Departamento de Estatstica - UFF 90

  • Aproximacao de Razes de Funcoes Reais

    Algumas desvantagens desse metodo: e necessario conhecer um intervalo [a, b] tal quef(a)f(b) < 0, as vezes esse intervalo nem existe; o processo de convergencia nao e dosmais rapidos.

    11.3 Metodo de Newton-Raphson

    O metodo de Newton-Raphson nao precisa de um intervalo [a, b] tal que f(a)f(b) < 0,como no Metodo da Bissecao. E preciso apenas um chute inicial x0 no domnio de f ,que nao precisa ser bom. Mas se tivermos alguma ideia de onde a raiz esta e melhorescolher x0 numa vizinhanca dela. A partir desse chute inicial x0 sera definida umasequencia {xn} que converge (quase sempre) para uma raiz de f . Veremos agora comoessa sequencia e definida.

    Essa sequencia sera construda da seguinte maneira: x1 sera o ponto do eixo x em quea reta tangente a f no ponto x0 cruza o eixo das abcissas; x2 sera o ponto do eixo x emque a reta tangente a f no ponto x1 corta o eixo das abcissas; e assim por diante. Vejana Figura 11.3 que essa sequencia converge para a raiz de f .

    Figura 11.3: Metodo de Newton-Raphson.

    Vamos definir uma expressao recursiva para essa sequencia. Ou seja, vamos definiruma expressao para xn+1 a partir de xn. Para isso precisamos encontrar a equacao dareta tangente a f no ponto xn e depois encontrar a intersecao dessa reta com o eixo x.

    Qual a equacao da reta tangente a f no ponto xn? Qualquer rata pode ser definidapor: r(x) = ax + b. No caso da reta tangente a` f em xn quem sao a e b? Sabemosque a = f (xn) e b pode ser encontrado resolvendo r(xn) = f(xn). Logo, f (xn)xn + b =f(xn) b = f(xn) f (xn)xn.

    Qual o ponto de intersecao de r e o eixo x? Basta descobrir quem e x tal que r(x) = 0,ou seja, r(x) = ax+ b = 0 x = b

    a. Esse sera xn+1.

    Assim chegamos na seguinte expressao que define os termos da sequencia a partir deum x0 inicial qualquer:

    xn+1 = xn f(xn)f (xn)

    .

    Departamento de Estatstica - UFF 91

  • Aproximacao de Razes de Funcoes Reais

    Exemplo 11.3.1 Vamos nesse exemplo procurar novamente uma aproximacao para umaraiz de f(x) = x3 x 4, mas agora pelo Metodo de Newton-Raphson. Entao primeirovamos definir a derivada de f , f (x) = 3x2 1, e vamos comecar com x0 = 1. Veja quenesse caso

    x1 = x0 f(x0)f (x0)

    = 1 f(1)f (1)

    = 1 42

    = 3.

    Na segunda iteracao encontramos x2 a partir de x1:

    x2 = x1 f(x1)f (x1)

    = 3 f(3)f (3)

    = 3 2026

    =58

    26=

    29

    13 2.2307.

    Na terceira iteracao encontramos x3 a partir de x2:

    x3 = x2 f(x2)f (x2)

    =29

    13 f

    (2913

    )f (2913

    ) = 2913 10700

    133132

    2354= . . . =

    269

    13 1.8811.

    Se quisermos aproximacoes mais precisas e so realizar mais iteracoes do metodo.

    Podemos entao colocar o computador para fazer as contas para a gente. Mas quandoparar? Quando sabemos se ja estamos realmente proximo da raiz.

    Se soubermos que a curva de f nao tangencia o eixo x na raiz que estamos buscando,isto e, que f(x ) e f(x+ ) tem sinais opostos, podemos usar como criterio de paradauma condicao semelhante a usada para a Bissecao. A partir de um erro indicado pelousuario vamos realizar as iteracoes ate chegar em xn tal que f(xn )f(xn + ) < 0,quando isso acontecer podemos afirmar que xn e uma aproximacao para uma raiz de fcom erro menor que .

    Mas se nao pudemos afirmar que a curva de f nao tangencia o eixo x em sua raizvamos precisar de outro criterio de parada, pois pode acontecer f(xn )f(xn + ) > 0para todo . Uma alternativa e usar a distancia na imagem em vez de usar a distanciano domnio. Vamos considerar que a aproximacao e boa quando chegamos em xn tal que|f(xn)| < . Nesse caso |f(x)| e quase zero, pois e bem pequeno, e por isso acreditamosque xn e uma boa aproximacao para uma raiz.

    Outra alternativa e parar quando a distancia entre duas estimativas consecutivas erazoavelmente pequena, ou seja, quando |xn xn+1| < . Mas para esses dois ultimoscriterios de parada nao e possivel afirmar que xn dista menos de da raiz.

    Entrada: x0, f , f e .

    Sada: uma aproximacao para uma raiz de f .Nome: RaizNewtonRaphson.

    Defina x = x0;1Se f(x )f(x+ ) < 0, retorne x;2Faca x = x f(x)

    f (x) e volte para o passo 2.3

    Veja que para esse metodo temos que passar como argumento nao a funcao f comotambem a sua derivada f .

    Dica: Talvez fique mais simples se o algoritmo for implementado usando o repeat.O metodo tambem pode ser implementado de forma recursiva, veja no pseudo-codigo

    a seguir.

    Departamento de Estatstica - UFF 92

  • Aproximacao de Razes de Funcoes Reais

    Entrada: x0, f , f e .

    Sada: uma aproximacao para uma raiz de f .Nome: RaizNewtonRaphsonRec.

    Defina x = x0;1Se f(x )f(x+ ) < 0, retorne x;2Faca x = x f(x)

    f (x) ;3

    Retorne RaizNewtonRaphsonRec(x, f, f , ).4

    Algumas vantagens desse metodo: sua convergencia e bem mais rapida do que noMetodo da Bissecao, isto e, precisamos de menos iteracoes para encontrar uma boa apro-ximacao; esse metodo nao depende de um intervalo [a, b] inicial tal que f(a) e f(b) tenhamsinais opostos.

    Algumas desvantagens desse metodo: se em algum momento chegarmos em xn tal quef (xn) = 0, teremos um problema: divisao por zero! Nesse caso o metodo tambem naoconverge; a escolha de x0 nao garante que o metodo converge para a raiz escolhida.

    11.4 Comentarios Gerais

    Os metodos citados sao usados para encontrar razes de funcoes, mas eles tambem podemser muito uteis para outros problemas que acabam virando um problema de encontrarrazes.

    Por exemplo, se quisermos encontrar uma solucao para a expressao ex x2 = xpodemos transformar esse problema original para o de encontrar as razes da funcaof(x) = ex x2 x. Entao um metodo numerico pode ser aplicado nessa funcao f .

    Outro exemplo que podemos citar e quando queremos encontrar o ponto de maximo(ou de mnimo) de uma funcao f . Para encontrar o ponto de maximo vamos derivar fe procurar as razes de f . Se nao for possvel de encontrar as razes na mao podemosprocurar aproximacoes para ela a partir dos metodos vistos nesse captulo. Mas nessecaso atencao, a funcao para a qual estamos aplicando o metodo e f . Entao se formosusar o Metodo da Bissecao precisamos de um intervalo [a, b] tal que f (a)f (b) < 0 e seformos usar o Metodo de Newton-Raphson precisamos encontrar a derivada de f .

    Departamento de Estatstica - UFF 93

  • Aproximacao de Razes de Funcoes Reais

    Exerccios - 11 Semana

    11.1 Vamos usar o Metodo da Bissecao para encontrar a raiz de f(x) = ex 1x.

    a) Primeiro implemente uma funcao que recebe como entrada os valores a, b e eretorna uma aproximacao da raiz de f(x) = ex 1

    xpelo Metodo da Bissecao.

    b) Para testar a sua funcao e preciso primeiro escolher valores de a e b tais que f(a)e f(b) tenham sinais opostos. Encontre um intervalo com essa caracterstica.Tente usar o metodo grafico.

    c) Escolha a precisao e encontre uma aproximacao para a raiz de f com precisao.

    d) Refaca agora o item 1a usando recursao. Ou seja, implemente uma funcaorecursiva que recebe como entrada os valores a, b e e retorna uma aproximacaoda raiz de f(x) = ex 1

    xpelo Metodo da Bissecao.

    e) Vamos ver com mais detalhes como esse metodo funciona. Para isso modifiqueuma das funcoes implementadas (1a ou 1d)de forma que a funcao implementadaretorne um array com todos os pontos medios dos intervalos encontrados duranteo metodo.

    f) Use os comandos de desenho plot, curve, points para visualizar o passo-a-passo do algoritmo. Guarde a os pontos medios retornado pela ultima funcaoimplementadas em uma variavel de nome saida e siga a sugestao de codigo aseguir.

    > plot(0,xlab="x",ylab="f(x)",xlim=c(0,1),ylim=c(-1,1),type="n")

    > grid()

    > segments(x0=-1,y0=0,x1=2,y1=0)

    > segments(x0=0,y0=-2,x1=0,y1=2)

    > curve(exp(x)-1/x,col="blue",add=T)

    > for(i in 1:length(saida)){

    + points(saida[i],0,col="red",pch=18,cex.lab=1)

    + text(saida[i],-0.2,i,col="red")

    + }

    11.2 Vamos usar o Metodo da Bissecao para encontrar uma aproximacao para o numeroirracional

    3.

    a) Escolha uma funcao f que tenha uma raiz em

    3. Nao vale f(x) = x3, poisestamos supondo que nao sabemos calcular

    3. A funcao deve conter apenas

    numeros racionais.

    b) Implemente, para a funcao escolhida, o Metodo da Bissecao.

    c) Escolha valores iniciais de a, b e e encontre a aproximacao desejada.

    11.3 Vamos usar o Metodo da Bissecao para encontrar uma aproximacao para o mnimoglobal da funcao f(x) = ex x3 + x.a) Primeiro faca o grafico da funcao f para conhecer um pouco mais sobre ela. Para

    isso use o comando curve e escolha uma janela apropriada.

    Departamento de Estatstica - UFF 94

  • Aproximacao de Razes de Funcoes Reais

    b) Agora tente achar o valor do mnimo global na mao. O que podemos fazer paraencontra-lo? Como o Metodo da Bissecao pode ser util?

    c) Use o Metodo da Bissecao para encontrar o mnimo global da funcao f . Atencaona escolha dos valores iniciais de a e b. Se escolhermos os valores errados podemoschegar na resposta errada, por exemplo, chegar em um mnimo local (que nao eglobal) ou ate mesmo em um maximo local.

    11.4 Vamos usar o Metodo de Newton-Raphson para encontrar a raiz de f(x) = ex 1x.

    a) Primeiro implemente uma funcao que recebe como entrada os valores x0 e eretorna uma aproximacao da raiz de f(x) = ex 1

    xpelo metodo de Newton-

    Raphson. Como nesse caso sabemos que antes da raiz a funcao e negativa edepois dela a funcao e positiva (como sabemos disso?), use como criterio deparada o fato de f(x? )f(x? + ) < 0 |x? r| < .

    b) Escolha um valor inicial x0 e um erro e encontra uma aproximacao para a raizde f pelo metodo de Newton-Raphson com precisao de .

    c) Refaca agora o item 4a usando recursao. Ou seja, implemente uma funcaorecursiva que recebe como entrada os valores x0 e e retorna uma aproxima-cao da raiz de f(x) = ex 1

    xpelo metodo de Newton-Raphson.

    d) Vamos ver com mais detalhes como esse metodo funciona. Para isso modifique afuncao implementada no item 4a de forma que ela retorne todos os pontos mediosdos intervalos encontrados.

    e) Repita o exerccio 1f mas agora a variavel saida sera os pontos fornecidos pelafuncao implementada em 4d.

    11.5 Use o metodo de Newton-Raphson para encontrar uma aproximacao para

    10 comprecisao de 108. Qual seria a funcao f para a qual estamos buscando uma raiz?Qual seria uma boa escolha de x0 inicial?

    11.6 Encontre aproximacoes para as solucoes da equacao e2x = x + 6 usando o metodode Newton-Raphson. Forneca aproximacoes que coincidam em pelo menos 4 casasdecimais com a real solucao. Antes de fazer o exerccio pense em: Quantas solucoesa equacao possui? Qual a funcao f considerada no metodo? Qual seria uma boaescolha de x0 inicial? Como garantir que a aproximacao vai coincidir em 4 casasdecimais com a solucao?

    Departamento de Estatstica - UFF 95

  • Semana 12: Derivacao Numerica

    Nesse captulo vamos estudar como usar o computador para encontrar uma aproximacaopara f (x0) supondo que sabemos avaliar f em uma vizinhanca de x0, ou pelo menosuma aproximacao para isso. Veja que nao necessariamente conhecemos a derivada de f ,apenas conhecemos f e x0 e a partir dessas informacoes queremos uma aproximacao paraf (x0).

    12.1 Metodos Numericos

    12.1.1 Primeiro Metodo

    Ja estudamos em calculo que a derivada de uma funcao f em x0 e a inclinacao da retatangente a` f em x0. E para encontrar o valor de f

    (x0) temos que calcular o seguintelimite:

    f (x0) = limh0

    f(x0 + h) f(x0)h

    .

    Figura 12.1: Ilustracao para a derivada em x0.

    Esse limite ja sugere uma aproximacao para a derivada de f em x0. Se escolhemos hbem pequeno podemos afirmar que:

    f (x0) f(x0 + h) f(x0)h

    .

    96

  • Derivacao Numerica

    O que estamos fazendo nesse caso e aproximando a inclinacao da reta tangente a` f noponto x0 (reta em azul na Figura 12.1) pela inclinacao da reta secante a f que passa pelospontos (x0, f(x0)) e (x1, f(x1)), com x1 = x0 + h (reta em preto na Figura 12.1). Vejaque quanto menor o valor de h mais proxima esta uma reta da outra, logo mais proximaesta uma inclinacao de uma reta da inclinacao da outra.

    Podemos usar h positivo ou negativo. Caso h > 0 a reta secante em questao passa por(x0, f(x0)) e (x1, f(x1)), com x1 = x0 + h sendo um ponto a` direita de x0, como mostraa Figura 12.1. Ja se h < 0 a reta considerada na aproximacao passa em (x0, f(x0)) e(x2, f(x2)), com x2 = x0 h sendo um ponto a` esquerda de x0.

    12.1.2 Segundo Metodo

    Uma outra alternativa para calcular uma aproximacao para f (x0) e usar a reta secanteque passa pelos pontos (x0h, f(x0h)) e (x0+h, f(x0+h)), nesse caso vamos consideraro seguinte limite:

    f (x0) = limh0

    f(x0 + h) f(x0 h)2h

    .

    Se escolhemos h bem pequeno podemos afirmar que:

    f (x0) f(x0 + h) f(x0 h)2h

    .

    Figura 12.2: Ilustracao para a derivada em x0.

    Esse novo metodo esta ilustrado na Figura 12.2. Nesse caso a reta secante usada naaproximacao nao leva em consideracao (x0, f(x0)) e sim (x1, f(x1)) e (x2, f(x2)), comx1 = x0 + h e x2 = x0 h, pontos a` direita e a` esquerda de x0, respectivamente.

    12.2 Analise dos erros

    A vantagem em usar o segundo metodo e que o erro cometido nesse caso cai mais rapidodo que no primeiro. Isto e, para um mesmo valor de h conseguimos uma aproximacao

    Departamento de Estatstica - UFF 97

  • Derivacao Numerica

    mais precisa usando o segundo metodo apresentado. Para entender melhor isso vamoslembrar do polinomio de Taylor de f em torno de x0.

    Ja vimos no captulo 10 que o polinomio de Taylor de grau n para f em torno de x0e definido por:

    pTn (x) = f(x0) + f(x0)(x x0) + f (x0)(x x0)

    2

    2!+ . . .+ f (n)(x0)

    (x x0)nn!

    Ja vimos tambem que se n temos pTn (x) n

    f(x). Entao podemos escrever:

    f(x) = f(x0) + f(x0)(x x0) + f (x0)(x x0)

    2

    2!+ f (3)(x0)

    (x x0)33!

    + . . . (12.1)

    Substituindo x por x0 + h na equacao 12.1 temos:

    f(x0 + h) = f(x0) + f(x0)(h) + f (x0)

    h2

    2!+ f (3)(x0)

    h3

    3!+ . . . (12.2)

    Desenvolvendo essa expressao de forma a isolar f (x0) chegamos em:

    f (x0) =f(x0 + h) f(x0)

    h(f (x0)

    h

    2!+ f (3)(x0)

    h2

    3!+ . . .

    )

    erro no primeiro metodo

    E assim conclumos que o erro cometido pela aproximacao a partir do primeiro metodoapresentado e:

    erro1 = f(x0)

    h

    2!+ f (3)(x0)

    h2

    3!+ f (4)(x0)

    h3

    4!+ f (5)(x0)

    h4

    5!+ . . . (12.3)

    Vamos agora determinar o erro cometido pelo segundo metodo. Para isso substitua xpor x0 h na equacao 12.1.

    f(x0 h) = f(x0) f (x0)(h) + f (x0)h2

    2! f (3)(x0)h

    3

    3!+ . . . (12.4)

    Subtraindo a equacao 12.2 pela a equacao 12.4 podemos escrever:

    f(x0 + h) f(x0 h) = 2f (x0)(h) + 2f (3)(x0)h3

    3!+ 2f (5)(x0)

    h5

    5!+ . . .

    Desenvolvendo essa expressao de forma a isolar f (x0) chegamos em:

    f (x0) =f(x0 + h) f(x0 h)

    2h(f (3)(x0)

    h2

    3!+ f (5)(x0)

    h4

    5!+ . . .

    )

    erro no segundo metodo

    E assim conclumos que o erro cometido pela aproximacao a partir do segundo metodoapresentado e:

    erro2 = f(3)(x0)

    h2

    3!+ f (5)(x0)

    h4

    5!+ f (7)(x0)

    h6

    7!+ f (9)(x0)

    h8

    9!. . . (12.5)

    Departamento de Estatstica - UFF 98

  • Derivacao Numerica

    Comparando as equacoes 12.3 e 12.5 podemos ver que conforme h 0 temos erro1 0 e erro2 0, porem a convergencia para o erro2 acontece de forma mais rapida umavez que ele depende de potencias maiores de h. Por isso vamos sempre preferir o segundometodo apresentado.

    Antes de apresentar o algoritmo que fornece uma aproximacao para a derivada vejamosum exemplo feito a mao.

    Exemplo 12.2.1 Considere f(x) = ln(x). Para cada um dois dois metodos apresentadosencontre uma aproximacao para f (1.8) usando o mesmo valor de h. Depois compare como valor real.

    Vamos usar h = 0.1. A partir do primeiro metodo chegamos em:

    f (1.8) f(1.9) f(1.8)0.1

    =0.64185389 0.58778667

    0.1= 0.5406722.

    Agora partindo do segundo metodo chegamos em:

    f (1.8) f(1.9) f(1.7)0.2

    =0.64185389 0.53062825

    0.2= 0.55612817.

    Ja o valor exato e: f (1.8) = 11.8

    = 1018

    = 0.555. Veja que de fato o segundo metodo foimais preciso.

    12.3 Algoritmo

    Vamos ao algoritmo. Para aproximar f (x0) vamos comecar com um h qualquer, quepode ou nao ser informado pelo usuario. A partir desse valor de h calculamos umaprimeira aproximacao. Depois diminumos o valor de h, por exemplo dividindo por 2,e calculamos uma nova aproximacao. Realizamos esse procedimento diversas vezes ateque aproximacoes consecutivas tenham um erro menor do que o erro determinado pelousuario.

    Entrada: x0, f e .Sada: uma aproximacao para f (x0).Nome: DerivadaNumerica

    Defina h = 1;1Defina x1 = x0 + h e x2 = x0 h;2Se x1 / D(f) ou x2 / D(f), pare e retorne erro.3Calcule d = f(x1)f(x2)

    2h;4

    Atualize o valor de h: h = h2;5

    Atualize x1 e x2: x1 = x0 + h e x2 = x0 h;6Calcule d = f(x1)f(x2)

    2h;7

    Se |d d| < , retorne d;8Faca d = d e volte para a linha 5.9

    Dica: Talvez fique mais simples se o algoritmo for implementado usando o repeat.Veja agora uma possibilidade de realizar o algoritmo de forma recursiva. Nesse caso

    vai ser bem mais simples de h tambem for passado como entrada.

    Departamento de Estatstica - UFF 99

  • Derivacao Numerica

    Entrada: x0, f , e h.Sada: uma aproximacao para f (x0).Nome: DerivadaNumericaRec

    Defina x1 = x0 + h e x2 = x0 h;1Se x1 / D(f) ou x2 / D(f), pare e retorne erro.2Calcule d = f(x1)f(x2)

    2h;3

    Atualize o valor de h: h = h2;4

    Atualize x1 e x2: x1 = x0 + h e x2 = x0 h;5Calcule d = f(x1)f(x2)

    2h;6

    Se |d d| < , retorne d;7Retorne DerivadaNumericaRec(x0, , h).8

    Departamento de Estatstica - UFF 100

  • Derivacao Numerica

    Exerccios - 12 Semana

    12.1 Em cada item a seguir considere que as unicas informacoes disponveis sobre a funcaof estejam na tabela apresentada. Complete a terceira coluna de cada tabela comaproximacoes para a derivada no ponto em questao. Faca as contas na mao. Paracada linha use o metodo mais apropriador de acordo com as informacoes disponveis.

    a)

    x f(x) f (x)1.1 9.0250131.2 11.023181.3 13.463741.4 16.44465

    b)

    x f(x) f (x)7.4 -68.319297.6 -71.698247.8 -75.157628.0 -78.69741

    12.2 Sabendo que as tabelas do exerccio 1 foram criadas a partir das funcoes a seguir,calcule agora o valor exato para a terceira coluna e compare com os valores aproxi-mados encontrados em 1.

    a) f(x) = e2x

    b) f(x) = ln(x+ 2) (x+ 1)2

    12.3 Vamos agora implementar o metodo visto em sala de aula. Para isso considere afuncao f(x) = 1

    x2+1.

    a) Qual o domnio da funcao f?

    b) Implemente uma funcao que recebe como entrada x0 Dom(f) e um erro eretorna uma aproximacao para f (x0) a partir do segundo metodo visto em salade aula.

    c) A partir da funcao implementada encontre aproximacoes para f (0), f (15) e

    f (13). Compare as aproximacoes encontradas com os valores reais, para isso sera

    necessario derivar a funcao f .

    d) Vamos implementar agora o algoritmo de forma recursiva. Para facilitar considereh um argumento de entrada da sua funcao. Dessa forma, implemente uma funcaorecursiva que recebe como entrada x0 Dom(f), um erro e h retorna umaaproximacao para f (x0) a partir do segundo metodo visto em sala de aula.

    e) A partir da funcao recursiva encontre aproximacoes para f (0), f (15) e f (1

    3).

    Quando for chamar a funcao para encontrar as aproximacoes use h = 1.

    Departamento de Estatstica - UFF 101

  • Derivacao Numerica

    12.4 Considere agora a funcao f(x) = ln(x2 + x 2).a) Qual o domnio da funcao f?

    b) Implemente uma funcao que recebe como entrada x0 Dom(f) e um erro eretorna uma aproximacao para f (x0) a partir do segundo metodo visto em salade aula.Dica: Nesse caso sera necessario ter cuidado com: (i) o x0 informado pelo usuario,se ele nao estiver no domnio interrompa o processo e envie uma mensagem deerro; (ii) a escolha de h inicial, atencao para nao acontecer de x0 h ou x0 + hnao pertencer ao domnio.

    c) A partir da funcao implementada encontre aproximacoes para f (3), f (52) e

    f (43). Compare as aproximacoes encontradas com os valores reais, para isso sera

    necessario derivar a funcao f .

    d) Vamos implementar agora o algoritmo de forma recursiva. Para facilitar considerenovamente h um argumento de entrada da sua funcao. Dessa forma, implementeuma funcao recursiva que recebe como entrada x0 Dom(f), um erro e hretorna uma aproximacao para f (x0) a partir do segundo metodo visto em salade aula.

    e) A partir da funcao recursiva encontre aproximacoes para f (3), f (52) e f (4

    3).

    12.5 Considere agora f(x) = ex/3(1 + x

    x2+1

    ) 1.a) Qual o domnio da funcao f?

    b) Primeiro implemente uma funcao que recebe como entrada x e retorna f(x).Vamos chamar essa funcao de f.

    c) Implemente agora uma funcao que recebe como entrada x e retorna uma aproxi-macao para f (x) considerando um erro de 103. Vamos chamar esse funcao dedf.

    d) Nosso objetivo agora e usar o metodo de Newton-Raphson para encontrar asrazes f sem derivar a funcao na mao. Para isso siga os itens a seguir.

    i) Digite plot(f,xlim=c(-3,5));abline(h=0) e veja como e o grafico de f .Veja que f tem tres razes. Sao elas que queremos encontrar.

    ii) Use o metodo de Newton-Rapson para encontrar uma aproximacao para amenor raiz de f . A partir do grafico escolha x0 de forma a garantir que ometodo converge para a raiz procurada. Faca a sua funcao de forma que elachame f e df implementadas em 5b e 5c.

    iii) Use o metodo de Newton-Rapson para encontrar uma aproximacao para asegunda menor raiz de f . A partir do grafico escolha x0 de forma a garantirque o metodo converge para a raiz procurada. Faca a sua funcao de formaque ela chame f e df implementadas em 5b e 5c.

    iv) Use o metodo de Newton-Rapson para encontrar uma aproximacao para amaior raiz de f . A partir do grafico escolha x0 de forma a garantir que ometodo converge para a raiz procurada. Faca a sua funcao de forma que elachame f e df implementadas em 5b e 5c.

    v) Vamos testar se deu certo. Guarde nos objetos r1, r2 e r3 as aproximacoesencontradas para as tres razes de f . Agora digite a seguinte sequencia decomandos e discuta o grafico gerado.

    Departamento de Estatstica - UFF 102

  • Derivacao Numerica

    > plot(f,xlim=c(-3,5));abline(h=0)

    > segments(x0=r1,y0=1,x1=r1,y1=-1,lty=2)

    > points(r1,0,pch=19,cex=1.2)

    > segments(x0=r2,y0=1,x1=r2,y1=-1,lty=2)

    > points(r2,0,pch=19,cex=1.2)

    > segments(x0=r3,y0=1,x1=r3,y1=-1,lty=2)

    > points(r3,0,pch=19,cex=1.2)

    e) Nosso objetivo agora e usar o metodo da bissecao para encontrar os pontos demaximo e mnimo locais de f sem derivar a funcao na mao. Para isso siga ositens a seguir.

    i) Digite plot(df,xlim=c(-3,5));abline(h=0) e veja como e o grafico daderivada de f . Veja que os pontos de maximo e mnimo locais de f sao ospontos em que a derivada de f se anula. Por isso vamos buscar as razes daderivada de f .

    ii) Use o metodo da bissecao para encontrar uma aproximacao para o mnimolocal de f . A partir dos graficos escolha valores para a e b de forma a garantirque o metodo converge para o mnimo local. Faca a sua funcao de formaque ela chame df.

    iii) Use o metodo da bissecao para encontrar uma aproximacao para o maximolocal de f . A partir dos graficos escolha valores para a e b de forma a garantirque o metodo converge para o maximo local. Faca a sua funcao de formaque ela chame df.

    iv) Vamos testar se deu certo. Guarde no objeto xmin a aproximacao para omnimo local e no objeto xmax a aproximacao para o maximo local de f .Agora digite a seguinte sequencia de comandos e discuta o grafico gerado.

    > plot(df,xlim=c(-3,5))

    > abline(h=0)

    > segments(x0=xmin,y0=2,x1=xmin,y1=-2,lty=2)

    > points(xmin,0,pch=19,cex=1.2)

    > segments(x0=xmax,y0=1,x1=xmax,y1=-1,lty=2)

    > points(xmax,0,pch=19,cex=1.2)

    Departamento de Estatstica - UFF 103

  • Semana 13: Integracao Numerica

    Suponha que nosso problema seja calcular a seguinte integral: baf(x)dx. Existem fun-

    coes para as quais nao e possvel encontrar a sua primitiva, ou seja, nao existe F talque d

    dxF (x) = f(x). Nesses casos nao conseguimos calcular a integral de f , logo nao

    conseguimos resolver nosso problema de forma analtica.Um exemplo de funcao que nao possui primitiva e a funcao densidade de probabilidade

    da variavel aleatoria normal de media 0 e variancia 1:

    f(x) =12pie

    x2

    2 .

    Apesar de nao ser possvel calcular a sua integral de forma analtica existe a area em baixo

    da sua curva. Ou seja, podemos mesmo assim querer encontrar o valor de ba

    12pie

    x2

    2 dxque esta indicado na Figura 13.1 como a area pintada de cinza.

    Figura 13.1: Ilustracao para a area de ba

    12pie

    x2

    2 dx.

    E como vamos fazer isso se nao existe a sua primitiva? Vamos procurar aproximacoespara a area em cinza a partir de metodos numericos. A ideia principal e usar a soma deRiemann para aproximar o valor dessa integral.

    Ja vimos (ou veremos) em calculo que baf(x)dx e o valor numerico referente a` area

    embaixo da curva de f entre os pontos a e b do domnio, lembrando que a area seraconsiderada negativa para os intervalos em que f(x) < 0. Baseados nessa ideia vamosconstruir um algoritmo que nos forneca uma aproximacao para essa area. Podemosaproximar por retangulos ou trapezios, como veremos nas Secoes 13.1 e 13.2 a seguir.

    104

  • Integracao Numerica

    13.1 Aproximacao por retangulos

    Para fazer a aproximacao por retangulos primeiro vamos dividirmos o intervalo (a, b) em nsubintervalos de mesmo tamanho: (a = x0, x1 = x0+, x2 = x1+, . . . , b = xn = xn1+),com = ba

    n. Para cada subintervalo (xi1, xi) vamos definir um retangulo com base dada

    por esse subintervalo e altura f(xi1), como mostra a Figura 13.2(b).

    (a) Valor exato. (b) Valor aproximado.

    Figura 13.2: Aproximacao por retangulos.

    Veja que podemos aproximar a area embaixo da curva de f pela soma das areas dosn retangulos. Veja tambem que quanto maior o numero de intervalos mais proxima aaproximacao esta do real valor da area. Entao para encontrar uma aproximacao para aarea embaixo da curva de f precisamos saber calcular a area dos retangulos.

    Veja que o i-esimo retangulo tem base = xi xi1 e altura f(xi1). Logo a area doi-esimo retangulo pode ser expressa por ARi = f(xi1). Dessa forma, podemos encontraro valor da soma das areas dos n retangulos da seguinte maneira:

    S1 =ni=1

    f(xi1)

    Veja que poderamos ter definido de outras formas a altura dos retangulos, por exem-plo, em vez de escolher como altura o valor da funcao no ponto a` esquerda do intervalo(xi1, xi), f(xi1), poderamos ter escolhido como altura o valor da funcao no ponto a`direita desse intervalo, f(xi), ou entao o valor da funcao no ponto medio desse intervalo,f(xi1+xi

    2). Veja esses duas outras possibilidades na Figura 13.3. Nesses casos teramos a

    soma das areas dos n retangulos definida por:

    S2 =n

    i=1 f(xi) (ponto a` direita)S3 =

    ni=1 f(

    xi1+xi2

    ) (ponto medio).

    Nao importa como foi definida a altura do retangulo, a soma das areas dos retangulossempre converge para a integral quando o numero de subdivisoes no domnio cresce, ouseja, quando n.

    Departamento de Estatstica - UFF 105

  • Integracao Numerica

    (a) Ponto a` direita. (b) Ponto medio.

    Figura 13.3: Aproximacao por retangulos.

    Outra possibilidade de definir a altura dos retangulos e, em vez de pensar nos retan-gulos a` direita ou a` esquerda, pensar nos retangulos acima ou abaixo da curva, comomostra a Figura 13.4.

    (a) Retangulos acima de f . (b) Retangulos abaixo de f .

    Figura 13.4: Aproximacao por retangulos.

    Veja que no caso dos retangulos acima da curva (Figura 13.4(a)) a altura do i-esimo retangulo sera max(f(xi1), f(xi)), mesmo que f seja negativa em xi ou xi1. Japara os retangulos abaixo da curva (Figura 13.4(b)) a altura do i-esimo retangulo seramin(f(xi1), f(xi)). Logo a soma das areas dos retangulos acima (SU) e (SL) abaixopodem ser expressas por:

    SU =n

    i=1 max (f(xi1), f(xi))SL =

    ni=1 min(f(xi1), f(xi))

    Departamento de Estatstica - UFF 106

  • Integracao Numerica

    A vantagem em trabalhar com os retangulos acima e abaixo e que dessa forma podemosgarantir que:

    SL Area Real SU .Mas por que isso e interessante? Porque assim sabemos se ja estamos com uma

    aproximacao boa ou nao. Por exemplo, se os valores de SL e SU forem muito proximos,isto e, SU SL < , entao o numero de subdivisoes do intervalo (a, b) ja e grande osuficiente para gerar uma boa aproximacao. Caso contrario, ainda nao temos uma boaaproximacao e por isso e recomendavel aumentar o numero de subdivisoes.

    13.2 Aproximacao por trapezios

    Uma outra alternativa para aproximar a area em baixo da curva de f e usar trapeziosem vez de retangulos. Essa alternativa torna o calculo mais preciso, isto e, com menor nconseguimos melhores aproximacoes. Veja uma ilustracao dessa aproximacao na Figura13.5.

    (a) Valor exato. (b) Valor aproximado.

    Figura 13.5: Aproximacao por trapezios.

    A area de um trapezio e definida por A = (h1 +h2)b2, onde h1 e h2 sao as duas alturas

    e b a base do trapezio. Logo, o i-esimo trapezio definido pela curva f temos os seguintesvalores: h1 = f(xi1), h2 = f(xi) e b = (xi xi1). Logo a area do i-esimo trapezio podeser expressa por ATi = (f(xi1) + f(xi))

    2.

    Entao a soma das areas dos trapezios, que sera uma aproximacao para a integral, podeser definida por:

    ST =ni=1

    (f(xi1) + f(xi))

    2.

    Vejamos agora um resultado interessante. Sejam ALi = min (f(xi1), f(xi)) e AUi =

    max (f(xi1), f(xi)) as areas dos i-esimos retangulos abaixo e acima da curva de f ,respectivamente. Veja que o valor medio entre essas duas areas pode ser calculado daseguinte maneira:

    Departamento de Estatstica - UFF 107

  • Integracao Numerica

    ALi + AUi

    2=

    1

    2(min (f(xi1), f(xi)) + max (f(xi1), f(xi)))

    =

    2(min (f(xi1), f(xi)) + max (f(xi1), f(xi)))

    =

    2(f(xi1) + f(xi))

    = ATi

    Logo, a media entre a area dos retangulos acima e abaixo da curva de f e a area dotrapezio. Entao o mesmo acontecera com a soma das areas:

    ST =SL + SU

    2.

    13.3 Algoritmo

    Como ja foi discutido, serao usados os retangulos e trapezios para aproximar a area embaixo da curva de f . Mas como determinar o numero de subintervalos n que ira forneceruma aproximacao relativamente boa?

    Veja que quanto mais subdivisoes tem o intervalo [a, b] mais precisa sera a aproxi-macao. Alem disso sabemos calcular SL e SU tais que SL Area Real SU , ou seja,conhecemos uma conta inferir (SL) e uma cota superior (SU) para o real valor da area.O que vamos fazer e buscar n tal que essas duas cotas ja estejam perto os suficiente.

    A ideia do algoritmo sera comecar com um n qualquer, por exemplo n = 100, e calcularpara esse numero de subintervalos os valores de SL e SU . Se ja estivermos perto do valorprocurado teremos SU SL < , onde um erro pre-estabelecido. Se isso nao acontecersignifica que precisamos fazer as contas com mais subintervalos. Entao o processo serarepetido para um valor maior de n.

    Veja a seguir como fica o algoritmo que fornece uma aproximacao para baf(x)dx a

    partir dessa ideia.

    Entrada: a, b, f e .Sada: uma aproximacao para

    baf(x)dx .

    Nome: IntegralNumerica

    Defina n = 100;1Defina = ba

    n;2

    Defina SL = 0 e SU = 0;3Inicie x = a;4Faca SL = SL + min(f(x), f(x+ ));5Faca SU = SU + max(f(x), f(x+ ));6Incremente x = x+ ;7Se x < b, volte para a linha 5;8Se SU SL < , retorne ST = SL+SU2 ;9Faca n = n+ 10 e volte para a linha 2.10

    Departamento de Estatstica - UFF 108

  • Integracao Numerica

    Veja que o que o algoritmo de fato faz e calcular a area dos retangulos abaixo e acimapara n = 100. Se elas ja estiverem proximas o suficiente, isto e, se SU SL < , fim. Senao, repete o processo para n maior, ou seja, para mais divisoes no domnio. Depois dedeterminado o valor para n o que vamos retornar e a area referente a soma das areas dostrapezios.

    Veja o mesmo algoritmo de forma recursiva. Nesse caso sera necessario passar onumero de subdivisoes do intervalo (a, b) como parametro de entrada.

    Entrada: a, b, f , e n.Sada: uma aproximacao para

    baf(x)dx .

    Nome: IntegralNumericaRec

    Defina = ban

    ;1Defina SL = 0 e SU = 0;2Inicie x = a;3Faca SL = SL + min(f(x), f(x+ ));4Faca SU = SU + max(f(x), f(x+ ));5Incremente x = x+ ;6Se x < b, volte para a linha 4;7Se SU SL < , retorne ST = SL+SU2 ;8Retorne IntegralNumericaRec(a, b, , n+ 10).9

    Departamento de Estatstica - UFF 109

  • Integracao Numerica

    Exerccios - 13 Semana

    13.1 Primeiro vamos aplicar o metodo em uma funcao que sabemos integrar. Considerea funcao f(x) = x2 x 1. Calcule na mao o valor de 11 f(x)dx. Esse e o valorque queremos aproximar.

    a) Implemente uma funcao que recebe como entrada a, b e n e retorna a soma daarea dos n retangulos definidos em sala de aula. Veja que a sada dessa funcao euma aproximacao para

    baf(x)dx usando a area de n retangulos

    OBS: use retangulos com a altura que preferir: o ponto medio, ponto a` direitaou ponto a` esquerda.

    b) Usando a funcao implementada no item 1a encontre uma aproximacao para 11 f(x)dx com 50 retangulos.

    c) Implemente uma funcao que recebe como entrada a, b e n e retorna a soma daarea dos n trapezios definidos em sala de aula. Veja que a sada dessa funcao euma aproximacao para

    baf(x)dx usando a area de n trapezios.

    d) Usando a funcao implementada no item 1c encontre uma aproximacao para 11 f(x)dx com 50 trapezios.

    e) O que podemos dizer sobre as aproximacoes encontradas nos itens 1b e 1d?Qual das duas e mais precisa? Para responder isso compare com o valor exatoencontrado no incio do exerccio.

    f) Agora vamos implementar o pseudo-codigo visto em sala de aula. Implementeuma funcao que recebe como entrada a, b e e retorna uma aproximacao para baf(x)dx com erro menor que .

    g) Usando a funcao implementada no item 1f encontre uma aproximacao para 11 f(x)dx com erro menor que 0, 001.

    h) Refaca a questao 1f de forma que ela retorne alem da aproximacao para a integralo numero de subintervalos usado.

    i) Usando a funcao implementada no item 1h encontre uma aproximacao para 11 f(x)dx com erro menor que 0, 001 e veja quantos subintervalos foram ne-

    cessarios para se conseguir essa precisao. Compare a aproximacao encontradacom o valor real e com as aproximacoes encontradas em 1b e 1d.

    j) Refaca a questao 1f de forma recursiva.

    k) Refaca a questao 1h de forma recursiva.

    Departamento de Estatstica - UFF 110

  • Integracao Numerica

    13.2 Considere f(x) = 12pie

    x2

    2 . Voce conhece essa funcao? Sabe calcular baf(x)dx de

    forma exata? Nao. Por isso vamos buscar uma aproximacao para essa integral.

    a) Implemente uma funcao que recebe como entrada a, b e e retorna uma aproxi-

    macao para baf(x)dx com erro menor que .

    b) Usando a funcao implementada no item 2a encontre uma aproximacao para 0,50

    f(x)dx, 12 f(x)dx e

    33 f(x)dx com erro menor que 0, 001.

    c) Usando a funcao implementada no item 2a vamos construir uma (mini) TabelaNormal, ou seja, preencha a tabela a seguir com aproximacoes para

    z0f(x)dx

    para diferentes valores de z.

    z ,0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,90,1, ?2,3,

    OBS: na posicao ? da tabela deve entrar 1,20 f(x)dx.

    Para isso comece com uma matriz nula com 4 linhas e 10 colunas. Cada posicaoda matriz guarda uma entrada da tabela. Vamos preencher essa matriz porlinhas. Para fazer isso de forma automatica comece com i = 1, j = 1 e z = 0.Cada vez que mudamos de posicao na matriz a variavel z deve ser incrementada:z = z + 0.1. Para cada posicao (i, j) dessa matriz sera calculado o valor de z0f(x)dx.

    Departamento de Estatstica - UFF 111

    PrefcioI Conceitos Bsicos de ProgramaoObjetos e ClassesNmerosTextosLgicosArrayMatrizesListasExerccios

    Controle de Fluxoif/elseforwhilerepeat/breakExerccios

    Funes e o Conceito de Varivel LocalFunesVariveis LocaisExerccios

    Algoritmos para Clculos EstatsticosMximoMnimoMdiaMedianaQuartisFrequnciasModaAmplitude TotalDistncia InterquartlicaVarincia AmostralDesvio MdioCovarincia AmostralExerccios

    Algoritmos para Clculos MatriciaisMultiplicao de vetor por escalarSoma entre vetoresSubtrao entre vetoresProduto internoMultiplicao de matriz por escalarSoma entre matrizesSubtrao entre MatrizesTransposio de MatrizesMultiplicao entre matriz e vetorMultiplicao entre matrizesExerccios

    II RecursoAlgoritmos RecursivosFatorialVetoresSequncias Definidas a partir de Equaes de DiferenasPadres geomtricosMatemtica FinanceiraFibonacci

    Exerccios

    Algoritmos Recursivos (continuao)SriesMaior Divisor ComumTorre de HanoiExerccios

    Algoritmos de OrdenaoOrdenao Bolha (Bubble Sort)Ordenao Rpida (Quick Sort)Exerccios

    Complexidade de AlgoritmosNoo IntrodutriaA Notao OExemplos Bsicos de ComplexidadeComplexidade Constante - O(1)Complexidade Logartmica- O(log(n))Complexidade Linear - O(n)Complexidade nlog(n) - O(nlog(n))Complexidade quadrtica - O(n2)Complexidade cbica - O(n3)Complexidade exponencial - O(cn)

    Exerccios

    III Uma Introduo ao Clculo NumricoAproximao de Funes por Sries de TaylorSrie de TaylorAproximao para a funo exponencialAproximao para a funo logaritmoExerccios

    Aproximao de Razes de Funes ReaisPreliminaresMtodo da BisseoMtodo de Newton-RaphsonComentrios GeraisExerccios

    Derivao NumricaMtodos NumricosPrimeiro MtodoSegundo Mtodo

    Anlise dos errosAlgoritmoExerccios

    Integrao NumricaAproximao por retngulosAproximao por trapziosAlgoritmoExerccios