Análise e Projeto de Algoritmos - Revisão Matemática

Análise e Projeto de Algoritmos Márcia Cappelle e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás Ciência da Computação 2021 INFUFG APA 20202 M Cappelle H Coelho 1 1 de 79 Funções Funções Monotônicas f é monotonicamente crescente se m n fm fn f é monotonicamente decrescente se m n fm fn f é estritamente crescente se m n fm fn f é estritamente decrescente se m n fm fn INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 79 79 de 79 Funções Piso e Teto A função piso oor mapeia um número x R para um número y Z tal que y é o maior inteiro menor ou igual a x 3 32 35 38 3 A função teto ceil mapeia um número x R para um número y Z tal que y é o menor inteiro maior ou igual a x 7 64 65 67 7 INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 80 79 de 79 Funcdes Piso e Teto Propriedades Dadosx Rin ZeabeE Ztal que ab 40 l a1laa fa a1 2 a a e a 2 3 an e nelatn24n 4 nenanstl 5 aJneaulnka 6 faJnenlaKn 7 feJeneacnaettl 8 3 3 n 9 HBL 35 e 81 1 eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 81 79 de 79 Exponenciais 1 1t1 ra e a qm Pe aa a x x oo gt P lel loeltaee14e2r4a Pe la r0Ka 2 Se 1K xe lim 1 4 e eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 82 79 de 79 Logaritmos Notação lg n ou log2 n base 2 log n ou log10 n base 10 logb n base b ln n logaritmo natural logk n log nk log log n loglog n lgi n n se i 0 lglgi1 n se i 0 e lgi1 n 0 indenido se i 0 e lgi1 n 0 ou lgi1 n é indenido lg n mini 0 lgi n 1 log estrela INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 83 79 de 79 Logaritmos Propriedades n a b c R e a b c 0 a blogb a logcab logc a logc b logb an n logb a logb a logc a logc b logb 1 a logb a logb a 1 loga b alogb n nlogb a INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 84 79 de 79 Logaritmos Propriedades x 1 ln1 x x x2 2 x3 3 x4 4 x5 5 x 1 ln1 x x ln1 x x 1x ln1 x x 1δ para δ x 0 INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 85 79 de 79 Regra de LHôpital Para se determinar o limite lim n fn gn quando lim n fn e lim n gn podese considerar o limite das derivadas das funções fn e gn lim n fn gn lim n fn gn Essa estratégia pode ser repetida quantas vezes necessário INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 86 79 de 79 Logaritmos Crescimento de funções Funções exponenciais crescem mais rápido do que qualquer função polinomial ou seja lim n en nd para qualquer d 0 Logaritmos devem crescer mais lentamente do que qualquer função polinomial conforme mostrado pela regra de LHôpital lim n logb n nd lim n 1 n ln bdnd1 1 d ln b lim n 1 nd 0 A função lnn cresce mais lentamente do que n ou mesmo n001 INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 87 79 de 79 Logaritmos Crescimento Logaritmos crescem mais lentamente do que qualquer função polinomial fn a partir de um certo n n0 2 4 6 8 10 2 4 n fn lnn n INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 88 79 de 79 Logaritmos Crescimento Logaritmos crescem mais lentamente do que qualquer função polinomial fn a partir de um certo n n0 20 40 60 80 100 120 2 4 6 933544536 n fn lnn 3n INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 89 79 de 79 Logaritmos Crescimento Logaritmos crescem mais lentamente do que qualquer função polinomial fn a partir de um certo n n0 1000 2000 3000 4000 5000 6000 7000 5 10 550366861 n fn lnn 4n INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 90 79 de 79 Logaritmos Crescimento Todos os logaritmos são múltiplos escalares uns dos outros lgn log2n cresce a um fator de 1 ln2 1 4427 139 mais rápido do que lnn 2 4 6 8 10 2 n fn log10x lnx lgx INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 91 79 de 79 Logaritmos Crescimento Todos os logaritmos são múltiplos escalares uns dos outros lgn log2n cresce a um fator de 1 ln2 1 4427 139 mais rápido do que lnn 200 400 600 800 1000 2 4 6 8 10 n fn log10x lnx lgx INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 92 79 de 79 Logaritmos Curiosidades 210 1024 é próximo de 1000 e lg210 lg1024 10 lg220 lg1048576 20 Portanto lg103 lg1000 10 K Kilo lg106 lg1000000 20 M Mega lg109 30 G Giga lg1012 40 T Tera INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 93 79 de 79 Séries aritméticas Séries importantes n Py i1424n 2a alk n 2 nn12n1 ns alk n 2 2 3 nn1 a alk n 4 nn12n13n3n1 alk eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 94 79 de 79 Séries aritméticas Boas aproximacées n muito grande be 2 on ime i1 n 2 3 2 on i 3 i1 n 3 4 3 nt rye Fs il n 4 5 A nb em i1 n d nati dt wy d41 8 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 95 79 de 79 Séries aritméticas Justificativa s d s d dq goth nitl ttl nit was x ax a a 0 d19 d1 d1 d1 fn 400 Seen ea U Dex 7 300 200 100 5 10 15 20 n st 8 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 96 79 de 79 Séries aritméticas Outra série importante n i dnd1n1d41 Pp id ey i1 Justificativa Woska Pires da Costa EDPA20161 1d 2d S 323 n1d1 ne nd poet en non Vid foe 4 vivid il k1ik 28 9 INE UrGLUSTAH GBT VAn WaskarRinesilacGorte EDPA20161 Revisdo Matematica 97 79 de 79 Séries aritméticas Outra série importante n i dnd1n1d41 Pp id ey i1 Justificativa Woska Pires da Costa EDPA20161 1d 2d S 323 n1d1 ne nd poet en non Vid foe 4 vivid il k1ik 28 9 INE UrGLUSTAH GBT VAn WaskarRinesilacGorte EDPA20161 Revisio Matematica 98 79 de 79 Séries aritméticas Outra série importante n i dnd1n1d41 Pp id ey i1 Justificativa Woska Pires da Costa EDPA20161 1d 2d S 323 n1d1 ne nd poet en non Vid foe 4 vivid il k1ik 28 9 INE UrGLUSTAH GBT VAn WaskarRinesilacGorte EDPA20161 Revisio Matematica 99 79 de 79 Séries aritméticas Outra série importante n 4 dndt1n1d1 Pp id ey i1 Justificativa Woska Pires da Costa EDPA20161 1d 2d S 323 n1d1 ne nd poet en non Vid foe 4 vivid il k1ik 28 9 INE UrGLUSTAH GBT VAn WaskarRinesilacGorte EDPA20161 Revisio Matematica 100 79 de 79 Séries aritméticas Outra série importante n 4 dndt1n1d1 Pp id ey i1 Justificativa Woska Pires da Costa EDPA20161 1d 2d S 323 n1d1 ne nd poet en non Vid foe 4 vivid il k1ik 28 9 INE UrGLUSTAH GBT VAn WaskarRinesilacGorte EDPA20161 Revisio Matematica 101 79 de 79 Séries aritméticas Limitacdo de somatorios por integrais Dada uma funcdo fx monotonicamente crescente n n nl fees Yrs peae m1 m eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 102 79 de 79 Séries geométricas O valor de uma série geométrica finita pode ser obtido utilizandose a seguinte formula a pntl1 n1 Sor 1 r r 1 lr r1l 10 P Se r 1 entdo 1 yra é lr 10 eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 103 79 de 79 Séries geométricas Pm Se r 2 entdo n i0 Se r 4 entéo n i 1 3 22 2 10 co i 1 5 2 2 10 o8 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 104 79 de 79 Somat6orios Divisdo de Somatérios Objetivo limitante assintdtico de somatérios n n2 n St Vit Vi il il in21 n2 n YOt DY i1 in21 3 Qn 8 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 105 79 de 79 Somat6orios Divisio de Somatérios Eliminacdo de termos independentes da variavel n no1l n Yea Ya a no constante il il ino n 1N0 3 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 106 79 de 79 Somatorios Divisdo de Somatorios Coa PE SS x k0 Razdo entre dois termos consecutivos k 121 k1 8 k 12 eae para k 3 oe 2k 9 Logo oo 2 2 2 oo 2 doe de et Do oe k0 k0 k3 O13 k0 9 1 99 O1 O1 3 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 107 79 de 79 Somatorios Expansdo e Contracdo de Somatérios n n n S RPaYk k1 jl kj n YAS nFh jl 1X 2 3 dUnn15s7 jl n grn1gnntl3 FP jl 5nn14nn15S 5nn5n158S S nQn41n1 eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 108 79 de 79 Fatoriais n 2πn n e n1 Θ 1 n Aproximação de Stirling n onn n ω2n logn Θn log n 2πn n e n n 2πn n e n112n INFUFG APA 20202 M Cappelle H Coelho Revisão Matemática 109 79 de 79 Polinémios d Pm Pn do ajn ag 0 dé 0 grau do polindmio i0 f élimitada polinomialmente se fn On para alguma constante k 0 b lim 4 Oparaabe Rea1 noco Pe n oa Uma funcdo exponencial cresce muito mais rapido que qualquer funcdo limitada polinomialmente eS 9 INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 110 79 de 79 Série Harménica od Hn Inn7O01n il Hn é0 nsimo nimero harménico 0577 a constante de Euler Inn An 14 Inn n P SS Ali n 1An n il eS INFUFG APA 20202 M Cappelle H Coelho Revisdo Matematica 111 79 de 79 Limites assintoticos para somatorios n Sie On Vee Rc1 il il Ss Z Ologn veja a série harmonica l1 n Sic Oc Vee Rcl l1 oe INFUFG APA 20202 M Cappelle H Coelho Revisio Matematica 112 79 de 79 Limites assintoticos para somatorios n S logi On logn Vee R c0 l1 n So i logi On logn VedeR cd0 l1 n S bit logi Obnlogn VbER b1lecd0 l1 oe INFUFG APA 20202 M Cappelle H Coelho Revisio Matematica 113 79 de 79 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20202 M Cappelle H Coelho Bibliograa 114 79 de 79