metodos numericos

Matemática
Discreta
y sus
Aplicaciones
5. 0 edición

Matemática
Discreta
y sus
Aplicaciones
S.a edición

Kenneth H. Rosen
laboratorios AT&T

Traducción:
José Monuef Pérez Morales
Inves'godo< ,rulo, del C1EMAT
Profesor asociado
Universidod (0,10$ 111 de Madrid

Julio Moro Carreña
Titular de Universidad
Departamento de Matemáticas
Universidad Carlos III de IVoodrid

AnoIsabel Uos Quintero
Dep:1l1omento de Niotemótico Aplicado

Universidod Politécnico de Madrid
pedro Antonio Ramos A10nc
Departamento de M.otemóticas
Universidad de Alcalá

In

MADRID' BUENOS AIRES' CARACAS' GUATEMALA' USeDA' MElUCO
NUEVA YORK' PANANA. SAN JUAN' SANTAFE DE BOGOTÁ' SANTIAGO' SAO PAULD
AUCKlAND· HAMBUAGO • LONDRES • MIlÁN' MONTREAl' NUEVA DELHI' PARJS
SAN FRANCISCO' SIONEY• 51NGAPUR· SAN LUIS' TOKIO, TORONTO

Contenido
Soh,.~,./Dular

Ix

Prólugu

xl

Lo pdgina weh dt ayuda
i4lesrudiante

l.

. xix
ni

Los Cundamentos: lógica y demostraci6n, conjuntos y Cunclones ...

1

1.1.

Lógica

_._............................................................................

1

1.2.
1.3.
1.4.
1.5.
1.6.
1.7.

Equivalenciasproposicionales
_
__ __._._
_ _..__
Predicados y cuanl.ificadores
Cuantificadores anidados _.............................................................................
Métodos de detnostración
_
_
_.....................
Conjuntos
_ _
Operaciones con conjuntos
Funciones
Material fin del Capítulo

19
26

1.8.

2.

Los fundamentos: algoritmos, números enteros y matrices

2.4.
2.5.2.6.
2.7.

• : 3.

90
103

109

Crecimiento de funciones
COIt1plejidad de a1goritInOS
Enteros y división
Enteros y algoritmos
Aplicaciones de la teoría de números

120
J32

140
I SS
161
181

Matrices
Malerial fin del Capítulo

52
71
79

109

2.1. Algo"""",
2.2.
2.3.

40

_..............

191

199

3.1.
3.2.
3.3.
3.4.
3.5.
3.6.

4.

Razonamientomatemático, inducción y recursividad

199
210
222
239
255
264
270

&lrategias de dernoslración
Sucesiones y sumatorios
Inducción maleml1tica
DefIniciones recursivas e inducciÓD estnletural
Algoritmos recursivos
Verificación de programas
Material fin del Capflulo

_...........

Recuento

279

4.1,

279
290
297
303
31l

4.2.
4.3.
4.4.
4.5.

Fundwnentos decombinatoria
Principios del palomar
Permutaciones y combinaciones
Coeficientes binomiales
Permutaciones y combinaciones generalizadas

•

vi Corumido

4.6.

5.

Generación de permutaciones y combinaciones
Material fin del Capitulo

320
324

329

5.1.
5.2.
5.3.

6.

Probabilidad discreta

329
336
352
366

Técnicas avanzadas de
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.

7.Una introducción a la probabilidad discreta
Teoría de la probabilidad
Valor esperado y varianza
Material fin del Capftulo

r~uerdo................................................................... 373

Relaciones de recurrencia
Resolución de relaciones de recurrencia
Algoritmos de divide y vencerás y relaciones de recurrencia
Funciones generatrices
Principio de inclusi6n~xclusiónAplicaciones del principio de inclusión~xclusi6n
Material fin del Capítulo

373

384
396
405
420
426
433

Relaciones............................................................................................................... 439
7.1.
7.2.
7.3.
7.4.
7.5.
7.6.

Relaciones y sus propiedades
Relaciones n-arias y sus aplicaciones
Representación de relaciones
CietTt: de relacionesRelaciones de equivalencia
órdenes parciales
Material fin del Capítulo

439
449
456
463
473
481
495

•

8. Grafos.......................................................................................................................
8.1.
8.2.
8.3.
8.4.
8.5.
8.6.
8.7.
8.8.

9.

lntnxlucción a los grafos
Tenninología en teoria de grafos
Representación de grafos e...