Taller Uno - Curso de Algoritmia

UNIVERSIDAD TECNOLGICA DE PEREIRAFacultad de Ingenieras: Elctrica, Electrnica, Fsica y Ciencias de la Computacin

Maestra en Ingeniera de Sistemas y ComputacinProfesor Hugo Humberto Morales Pea

Fecha de entrega del enunciado del taller a los estudiantes: Domingo 7 de Diciembre de 2014.Fecha de entrega del taller resuelto al profesor: Sbado 13 de Diciembre de 2014.

Ejercicios para el equipo de Mauricio Crdenas: 1.a, 1.f, 2.a, 3.a, 4.a y 4.e

Ejercicios para el equipo de Jhadderson Yency Hoyos: 1.b, 1.g, 2.b, 3.b, 4.b y 4.g

Ejercicios para el equipo de Juan Carlos Gutirrez: 1.c, 1.h, 2.c, 3.c, 4.c y 4.d

Ejercicios para el equipo de Juan Pablo Ramrez: 1.d, 1.i, 2.d, 3.d, 4.d y 4.i

Ejercicios para el equipo de Katherine Silva: 1.e, 1.j, 2.e, 3.e, 4.e y 4.h

Ejercicios para el equipo de Carlos Mario Trivio: 1.f, 1.k, 2.f, 3.a, 4.f y 4.i

Ejercicios para el equipo de Juan Manuel Velsquez: 1.g, 1.l, 2.a, 3.b, 4.g y 4.l

Ejercicios para el equipo Ocho: 1.h, 1.m, 2.b, 3.c, 4.h y 4.k

EJERCICIOS:

1. Probar o refutar cada uno de los siguientes tems utilizando el mtodo de demostracinpor Induccin Matemtica:

a) 0 + 7 + 26 + : : :+ (n3 1) = n(n(n+1)2 4)4

, para n 2 Z+, n 1.b) 1(2) + 2(3) + 3(4) + 4(5) + : : :+ n(n+ 1) = n(n+1)(n+2)

3, para n 2 Z+, n 1.

c) 0 + 3 + 8 + : : :+ (n2 1) = n(2n+5)(n1)6

, para n 2 Z+, n 1.d) 1 1

4+ 4 5

4+ 9 9

4+ : : :+ n2 (n 3

4) = n(n+1)(2n

21)8

, para n 2 Z+, n 1.e) 1 1

5+ 2 16

5+ 3 41

5+ : : :+ n (n2 4

5) = n(n+1)(5n(n+1)8)

20, para n 2 Z+, n 1.

f ) 1 23+ 2 5

3+ : : :+ n (n 1

3) = n

2(n+1)3

, para n 2 Z+, n 1.g) 3 + 6 + 20 + : : :+ (n(n!) + 2) = (n+ 1)! + 2n 1, para n 2 Z+, n 1.h) 1 21 + 2 22 + 3 23 + : : :+ n 2n = (n 1) 2n+1 + 2, para n 2 Z+, n 1.i) 12 + 32 + 52 + : : :+ (2n 1)2 = n(2n1)(2n+1)

3, para n 2 Z+, n 1.

1

j ) 32 + 42 + 52 + 62 + : : :+ (n+ 2)2 = (n+2)(n+3)(2n+5)6

5, para n 2 Z+, n 1.k) 12 + 42 + 72 + 102 + : : :+ (3n 2)2 = n[3n(2n1) 1]

2, para n 2 Z+, n 1.

l) 11(2)

+ 12(3)

+ 13(4)

+ 14(5)

+ : : :+ 1n(n+1)

= nn+1

, para n 2 Z+, n 1.m) 3

1(3)+ 3

3(5)+ 3

5(7)+ 3

7(9)+ : : :+ 3

(2n1)(2n+1) =3n

2n+1, para n 2 Z+, n 1.

2. Resolver las siguientes relaciones de recurrencia utilizando el Mtodo de Iteracin:

a) P (1) = 1

P (n) = 4P (n3) + n, para n = 3m, m 2 Z+.

b) P (1) = 1

P (n) = 5P (n3) + n, para n = 3m, m 2 Z+.

c) P (1) = 1

P (n) = 5P (n2) + n, para n = 2m, m 2 Z+.

d) P (1) = 1

P (n) = 3P (n2) + n, para n = 2m, m 2 Z+.

e) P (1) = 1

P (n) = 3P (n4) + n, para n = 4m, m 2 Z+.

f ) P (1) = 1

P (n) = 2P (n3) + n, para n = 3m, m 2 Z+.

3. Demostrar o refutar por induccin matemtica que las relaciones de recurrencia siguientestienen la solucin que se plantea para cada una de ellas :

a) P (1) = 0P (n) = P (n 1) + n2 1, para n 2, n 2 Z+.Solucin:P (n) = n(2n+5)(n1)

6, para n 1

b) P (1) = 1P (n) = 3P (n 1) + 2n 1, para n 2, n 2 Z+.Solucin:

2

P (n) = 3n+1+1

2 2n+1, para n 1

c) P (1) = 1P (n) = P (n 1) + 4n 3, para n 2, n 2 Z+.Solucin:P (n) = 2n2 n, para n 1

d) P (1) = 2P (n) = P (n 1) + n2 + n, para n 2, n 2 Z+.Solucin:P (n) = n(n+1)(n+2)

3, para n 1

e) P (1) = 23

P (n) = P (n 1) + n2 13n, para n 2, n 2 Z+.

Solucin:P (n) = n

2(n+1)3

, para n 1

4. Para cada uno de los siguientes tems, dar notaciones O, y . Para cada una delas notaciones dar las ms cercanas. Justificar claramente sus respuestas. Se debeobtener primero la solucin de la sumatoria para cada tem?.

a) 1(2) + 2(3) + 3(4) + 4(5) + : : :+ n(n+ 1), donde n 2 Z+.b) 0 + 3 + 8 + : : :+ (n2 1), donde n 2 Z+.c) 0 + 7 + 26 + : : :+ (n3 1), donde n 2 Z+.d) 12 + 32 + 52 + : : :+ (2n 1)2, donde n 2 Z+.e) 13 + 33 + 53 + : : :+ (2n 1)3, donde n 2 Z+.f ) 12 + 42 + 72 + 102 + : : :+ (3n 2)2?, donde n 2 Z+.g) 13 + 43 + 73 + 103 + : : :+ (3n 2)3?, donde n 2 Z+.h) 32 + 42 + 52 + 62 + : : :+ (n+ 2)2, donde n 2 Z+.i) 33 + 43 + 53 + 63 + : : :+ (n+ 2)3, donde n 2 Z+.j ) 42 + 72 + 102 + 132 + : : :+ (3n+ 1)2?, donde n 2 Z+.k) 43 + 73 + 103 + 133 + : : :+ (3n+ 1)3, donde n 2 Z+.l) 52 + 82 + 112 + 142 + : : :+ (3n+ 2)2?, donde n 2 Z+.

m) 53 + 83 + 113 + 143 + : : :+ (3n+ 2)3?, donde n 2 Z+.n) 1 2

3+ 2 5

3+ : : :+ n (n 1

3), donde n 2 Z+.

) 1 14+ 4 5

4+ 9 9

4+ : : :+ n2 (n 3

4), donde n 2 Z+.

3

o) 1 12+ 2 3

2+ : : :+ n (n 1

2), donde n 2 Z+.

p) 1 15+ 2 16

5+ 3 41

5+ : : :+ n (n2 4

5), donde n 2 Z+.

4