Ingeniería de trabajo

˜ ANALISIS Y DISENO DE ALGORITMOS
Guillermo Morales-Luna Secci´n de Computaci´n o o CINVESTAV-IPN gmorales@cs.cinvestav.mx M´xico, D.F., a 5 de mayo de 2003. e

2

Contenido
1 Introducci´n o 1.1 1.2 Medidas de complejidad para algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmos de “Divide y vencer´s” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . a 7 7 11 15 15 16 16 16 17 17 18 19 19 20 20 20 21 21 21 22 23 23 24 25 25 27

2 Ordenes de crecimiento y sumatorias 2.1 2.2 Ordenes de crecimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Algunas funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 2.2.7 Pisos y techos . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Potencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Logaritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Factoriales . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sucesi´n de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Funciones iteradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

Sumatorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 2.3.2 2.3.3 2.3.4 2.3.52.3.6 Sumas telesc´picas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Sumas de mismas potencias de los primeros enteros positivos . . . . . . . . . . . . . . Sumas de potencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Serie arm´nica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Productos . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acotamiento de sumas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Recurrencias 3.1 3.2 3.3 El m´todo de sustituci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e o M´todo de iteraci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . e o M´todo maestro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 3.3.1 3.4 Demostraci´n del Teorema Maestro o . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Resoluci´n mediante funciones generadoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 3

4 3.5 3.6 3.7

CONTENIDO Resoluci´n mediante potencias . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . o Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Programas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 30 33 35 35 35 36 38 39 40 40 40 41 41 42 43 43 45 45 47 49 49 50 54 54 54 55 55 56 56 57 58 60 65

4 Recuento y probabilidad 4.1Recuento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 4.1.2 4.1.3 4.2 4.3 Nociones elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Coeficientes binomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Coeficientes multinomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .

Principio de inclusi´n-exclusi´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o o Probabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 4.3.2 4.3.3 4.3.4 4.3.5 Conceptos b´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Probabilidad condicional . . . . . . . . . . . ....