The advent of fast computers and the search for efficient algorithms revolutionized combinatorics and brought about the field of discrete mathematics. This book is an introduction to the main ideas and results of discrete mathematics, and with its emphasis on algorithms it should be interesting to mathematicians and computer scientists alike. The book is organized into three parts: enumeration, graphs and algorithms, and algebraic systems. There are 600 exercises with hints and solutions to about half of them. The only prerequisites for understanding everything in the book are linear algebra and calculus at the undergraduate level. Martin Aigner is a professor of mathematics at the Free University of Berlin. He received his PhD at the University of Vienna and has held a number of positions in the USA and Germany before moving to Berlin. He is the author of several books on discrete mathematics, graph theory, and the theory of search. The Monthly article Turan's graph theorem earned him a 1995 Lester R. Ford Prize of the MAA for expository writing, and his book Proofs from the BOOK with Günter M. Ziegler has been an international success with translations into 12 languages.
Author(s): Martin Aigner
Publisher: American Mathematical Society
Year: 2007
Language: English
Pages: 402
Tags: Discrete Mathematics
Cover
Title
Copyright
Contents
Prefaces
Part 1. Counting
Chapter 1. Fundamentals
§1.1. Elementary Counting Principles
§1.2. The Fundamental Counting Coefficients
§1.3. Permutations
§1.4. Recurrence Equations
§1.5. Discrete Probability
§1.6. Existence Theorems
Exercises for Chapter 1
Chapter 2. Summation
§2.1. Direct Methods
§2.2. The Calculus of Finite Differences
§2.3. Inversion
§2.4. Inclusion-Exclusion
Exercises for Chapter 2
Chapter 3. Generating Functions
§3.1. Definitions and Examples
§3.2. Solving Recurrences
§3.3. Generating Functions of Exponential Type
Exercises for Chapter 3
Chapter 4. Counting Patterns
§4.1. Symmetries
§4.2. Statement of the Problem
§4.3. Patterns and the Cycle Indicator
§4.4. Polya's Theorem
Exercises for Chapter 4
Chapter 5. Asymptotic Analysis
§5.1. The Growth of Functions
§5.2. Order of Magnitude of Recurrence Relations
§5.3. Running Times of Algorithms
Exercises for Chapter 5
Bibliography for Part 1
Bibliography for Part 1
Part 2.Graphs and Algorithms
Chapter 6. Graphs
§6.1. Definitions and Examples
§6.2. Representation of Graphs
§6.3. Paths and Circuits
§6.4. Directed Graphs
Exercises for Chapter 6
Chapter 7. Trees
§7.1. What Is a Tree?
§7.2. Breadth- First and Depth-First Search
§7.3. Minimal Spanning Trees
§7.4. The Shortest Path in a Graph
Exercises for Chapter 7
Chapter 8. Matchings and Networks
§8.1. Matchings in Bipartite Graphs
§8.2. Construction of Optimal Matchings
§8.3. Flows in Networks
§8.4. Eulerian Graphs and the Traveling Salesman Problem
§8.5. The Complexity Classes P and NP
Exercises for Chapter 8
Chapter 9. Searching and Sorting
§9.1. Search Problems and Decision Trees
§9.2. The Fundamental Theorem of Search Theory
§9.3. Sorting Lists
§9.4. Binary Search Trees
Exercises for Chapter 9
Chapter 10. General Optimization Methods
§10.1. Backtracking
§10.2. Dynamic Programming
§10.3. The Greedy Algorithm
Exercises for Chapter 10
Bibliography for Part 2
Bibliography for Part 2
Part 3. Algebraic Systems
Chapter 11. Boolean Algebras
§11.1. Definition and Properties
§11.2. Propositional Logic and Boolean Functions
§11.3. Logical Nets
§11.4. Boolean Lattices, Orders, and Hypergraphs
Exercises for Chapter 11
Chapter 12. Modular Arithmetic
§12.1. Calculating with Congruences
§12.2. Finite Fields
§12.3. Latin Squares
§12.4. Combinatorial Designs
Exercises for Chapter 12
Chapter 13. Coding
§13.1. Statement of the Problem
§13.2. Source Encoding
§13.3. Error Detection and Correction
§13.4. Linear Codes
§13.5. Cyclic Codes
Exercises for Chapter 13
Chapter 14. Cryptography
§14.1. Cryptosystems
§14.2. Linear Shift Registers
§14.3. Public- Key Cryptosystems
§14.4. Zero-Knowledge Protocols
Exercises for Chapter 14
Chapter 15. Linear Optimization
§15.1. Examples and Definitions
§15.2. Duality
§15.3. The Fundamental Theorem of Linear Optimization
§15.4. Admissible Solutions and Optimal Solutions
§15.5. The Simplex Algorithm
§15.6. Integer Linear Optimization
Exercises for Chapter 15
Bibliography for Part 3
Solutions to Selected Exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Back Cover
