Combinatorial and Algorithmic Mathematics : From Foundation to Optimization.

Format:

Book

Author/Creator:

Alzalg, Baha.

Language:

English

Subjects (All):

Mathematical optimization.

Combinatorial analysis.

Physical Description:

1 online resource (531 pages)

Edition:

1st ed.

Place of Publication:

Wiley 2024

Summary:

This book by Baha Alzalg is a comprehensive resource on combinatorial and algorithmic mathematics, with a focus on optimization. It is designed for undergraduate students in mathematics and computer science, providing foundational knowledge and advanced concepts in logical structures, set theory, graph theory, recursion, and algorithm analysis. The book also covers various optimization techniques, including linear programming, second-order cone programming, and semidefinite programming. Alzalg aims to supply a clear and digestible text for courses in combinatorial mathematics, enhancing students' understanding of algorithms and their application in mathematical problem-solving. Generated by AI.

Contents:

Cover

Title Page

Copyright

Contents

About the Author

Preface

Acknowledgments

About the Companion Website

Part I Foundations

Chapter 1 Mathematical Logic

1.1 Propositions

1.1.1 Notations

1.2 Logical Operators

1.2.1 Negation, Conjunction, and Disjunction

1.2.1.1 Negation

1.2.1.2 Double Negation

1.2.1.3 Logical Equivalence

1.2.1.4 Conjunction

1.2.1.5 Disjunction

1.2.1.6 Exclusive Disjunction

1.2.2 Implication and Double Implication

1.2.2.1 Implication

1.2.2.2 Why Implications Are Important in Mathematics?

1.2.2.3 Contrapositive of an Implication

1.2.2.4 Converse of an Implication

1.2.2.5 Inverse of an Implication

1.2.2.6 Double Implication

1.3 Propositional Formulas

1.3.1 Order of Logical Operations

1.3.2 Tautologies, Contradictions, and Contingencies

1.3.3 Negating Compound Propositions

1.3.3.1 Negating Negations

1.3.3.2 Negating Conjunctions

1.3.3.3 Negating Disjunctions

1.3.3.4 Negating Implications

1.3.3.5 Universal Sets

1.3.4 Modeling Using Propositional Logic

1.3.4.1 Propositional Formulas in Computer Programs

1.3.5 Deriving Logical Equivalences

1.3.5.1 Using Truth Tables to Prove Logical Equivalences

1.3.5.2 Applying Earlier Equivalences to prove logical equivalences

1.4 Logical Normal Forms

1.4.1 Disjunctive Normal Forms

1.4.2 Conjunctive Normal Forms

1.5 The Boolean Satisfiability Problem

1.6 Predicates and Quantifiers

1.6.1 Predicates

1.6.2 Quantifiers

1.6.3 Multiple Quantifiers

1.6.4 Multiple Predicates

1.6.5 Mixing Quantifiers

1.6.6 Negating Quantified Statements

1.6.6.1 Negating Propositions with Multiple Quantifiers

1.6.6.2 Expressing Propositions Using Only One Type of Quantifiers

1.7 Symbolizing Statements of the Form "All P Are Q"

Exercises

Notes and Sources.

References

Chapter 2 Set‐Theoretic Structures

2.1 Induction

2.1.1 Principle of Induction for Predicates

2.1.2 Induction Proves Recursion

2.2 Sets

2.2.1 Set Membership

2.2.2 Cardinality of Sets

2.2.3 Set Equality

2.2.4 Subsets and Proper Subsets

2.2.5 The Empty Set

2.2.6 The Powerset Operator

2.2.7 Manipulating Sets

2.2.8 Sets Defined by Predicates

2.3 Relations

2.3.1 Equivalence Relations

2.3.2 Ordering Relations

2.4 Partitions

2.5 Functions

2.5.1 Surjections

2.5.2 Injections

2.5.3 Bijections

Notes and Sources

References

Chapter 3 Analytic and Algebraic Structures

3.1 Sequences

3.2 Summations and Series

3.3 Matrices, Subspaces, and Bases

3.3.1 Matrices

3.3.2 Subspaces and Bases

3.4 Convexity, Polyhedra, and Cones

3.5 Farkas' Lemma and Its Variants

Part II Combinatorics

Chapter 4 Graphs

4.1 Basic Graph Definitions

4.1.1 Directed and Undirected Graphs

4.1.2 Simple and Multigraphs

4.1.3 The Vertex Degree

4.1.4 Paths and Cycles

4.1.5 Subgraphs and Connected Components

4.1.6 Trees and Spanning Trees

4.1.7 Complete and Bipartite Graphs

4.2 Isomorphism and Properties of Graphs

4.2.1 Graph Isomorphism

4.2.2 Graph Properties

4.3 Eulerian and Hamiltonian Graphs

4.3.1 Königsberg Bridge Problem

4.3.2 Eulerian Paths and Cycles

4.3.3 Hamiltonian Paths and Cycles

4.4 Graph Coloring

4.5 Directed Graphs

4.5.1 Vertex In‐Degree and Out‐Degree

4.5.2 Directed Paths, Cycles, and Trees

4.5.3 Connectedness

Chapter 5 Recurrences

5.1 Guess‐and‐Confirm

5.2 Recursion‐Iteration

5.2.1 Change of Variables

5.3 Generating Functions

5.4 Recursion‐Tree

References.

Chapter 6 Counting

6.1 Binomial Coefficients and Identities

6.1.1 The Binomial Theorem and Coefficients

6.1.2 Binomial Identities

6.2 Fundamental Principles of Counting

6.2.1 The Product Principle of Counting

6.2.2 The Sum Principle of Counting

6.2.3 The Subtraction Principle of Counting

6.3 The Pigeonhole Principle

6.4 Permutations

6.4.1 Permutations Without Repetition

6.4.2 Permutations with Repetition

6.5 Combinations

6.5.1 Combinations Without Repetition

6.5.2 Combinations with Repetition

6.5.2.1 Using Combinations to Find Permutations with Indistinguishable Objects

6.5.3 Distributing Objects into Distinguishable Boxes

6.5.3.1 Distributing Distinguishable Objects into Distinguishable Boxes

6.5.3.2 Distributing Indistinguishable Objects into Distinguishable Boxes

Part III Algorithms

Chapter 7 Analysis of Algorithms

7.1 Constructing and Comparing Algorithms

7.1.1 Basic Tools for Constructing Algorithms

7.1.1.1 Simple Statements

7.1.1.2 If‐Statement

7.1.1.3 For‐Statement

7.1.1.4 While‐Statement

7.1.1.5 Do‐While‐Statement

7.1.1.6 Block

7.1.2 Choosing and Comparing Algorithms

7.2 Running Time of Algorithms

7.2.1 Line‐by‐Line Runtime Analysis

7.2.2 Types of Runtime Analysis

7.2.3 Summation Representations for Looping

7.2.4 Upper and Lower Bounds for Running Time

7.3 Asymptotic Notation

7.3.1 The Notations

7.3.2 Properties of the Notations

7.3.3 The Notations in Terms of Limits

7.3.4 Complexity Classification of Algorithms

7.3.4.1 Choosing Big‐Oh for Algorithms

7.3.4.2 Classification of Algorithms Based on the Notations

7.4 Analyzing Decision‐Making Statements

7.4.1 Simple Statements

7.4.2 If‐Statement

7.4.3 For‐Statement

7.4.4 While‐Statement

7.4.5 Do‐While‐Statement.

7.4.6 Block

7.5 Analyzing Programs Without Function Calls

7.6 Analyzing Programs with Function Calls

7.6.1 Analyzing Nonrecursive Programs

7.6.2 Analyzing Recursive Programs

7.7 The Complexity Class NP‐Complete

Chapter 8 Array and Numeric Algorithms

8.1 Array Multiplication Algorithms

8.1.1 Matrix-Vector Multiplication

8.1.2 Matrix-Matrix Multiplication

8.2 Array Searching Algorithms

8.2.1 Linear Search

8.2.2 Binary Search

8.3 Array Sorting Algorithms

8.3.1 Insertion Sort

8.3.2 Selection Sort

8.3.3 Merge Sort

8.4 Euclid's Algorithm

8.5 Newton's Method Algorithm

8.5.1 Newton's Method for Nonlinear Systems

8.5.2 Newton's Method for Optimization

Chapter 9 Elementary Combinatorial Algorithms

9.1 Graph Representations

9.1.1 The Adjacency List Representation

9.1.2 The Adjacency Matrix Representation

9.2 Breadth‐First Search Algorithm

9.3 Applications of Breadth‐First Search

9.3.1 Computing Spanning Trees (Forests)

9.3.2 Computing Shortest Paths

9.3.3 Testing Bipartiteness

9.4 Depth‐First Search Algorithm

9.5 Applications of Depth‐First Search

9.5.1 Computing Spanning Trees (Forests)

9.5.2 Detecting Cycles

9.5.3 Finding Connected Components

9.6 Topological Sort

Part IV Optimization

Chapter 10 Linear Programming

10.1 Linear Programming Formulation and Examples

10.1.1 General Form Linear Programs

10.1.2 Examples of Linear Programming Problems

10.2 The Graphical Method

10.3 Standard Form Linear Programs

10.4 Geometry of Linear Programming

10.4.1 Extreme Points, Vertices, and Basic Feasible Solutions

10.4.2 Finding Basic Feasible Solutions

10.4.2.1 Degeneracy

10.4.3 Pointedness.

10.4.4 Optimality

10.5 The Simplex Method

10.5.1 Simplex Method for Maximization

10.5.2 The Full Tableau Method

10.5.2.1 Simplex Tableau for Maximization

10.5.2.2 Detecting the Existence of Alternative Optimal Solutions

10.5.2.3 Detecting Unboundedness

10.5.2.4 Breaking Ties

10.5.2.5 Simplex Tableau for Minimization

10.5.2.6 Problems with Nonpositive Variables and/or Free Variables

10.5.3 The Big‐M Method

10.5.3.1 Problems with "Greater‐than" and/or "Equal" Constraints

10.5.3.2 Detecting Infeasibility

10.5.3.3 Summary of the Simplex Method Steps

10.5.4 Anticycling

10.5.4.1 Bland's Rule

10.5.5 Complexity

10.6 Duality in Linear Programming

10.6.1 Lagrangian Duality and LP Duality

10.6.2 The Duality Theorem

10.6.3 Complementary Slackness

10.6.4 The Dual Optimal Solution via the Primal Simplex Tableau

10.7 A Homogeneous Interior‐Point Method

Chapter 11 Second‐Order Cone Programming

11.1 The Second‐Order Cone and Its Algebraic Structure

11.2 Second‐Order Cone Programming Formulation

11.2.1 Problem Formulation

11.2.1 Formulating Problems as SOCPs

11.2.1.1 Linear Programming

11.2.1.2 Convex Quadratic Programming

11.2.1.3 Rotated Quadratic Cone Programming

11.3 Applications in Engineering and Finance

11.3.1 Euclidean Facility Location Problem

11.3.2 Portfolio Optimization with Loss Risk Constraints

11.3.3 Optimal Covering Ellipsoid Problem

11.4 Duality in Second‐Order Cone Programming

11.5 A Primal‐Dual Path‐Following Algorithm

11.5.1 Newton's Method and Commutative Directions

11.5.2 Path‐Following Algorithm

11.5.3 Complexity Estimates

11.6 A Homogeneous Self‐Dual Algorithm

Chapter 12 Semidefinite Programming and Combinatorial Optimization.

12.1 The Cone of Positive Semidefinite Matrices.

Notes:

Description based on publisher supplied metadata and other sources.

Part of the metadata in this record was created by AI, based on the text of the resource.

ISBN:

9781394235971

1394235976

9781394235957

139423595X

OCLC:

1450837493