Discrete mathematics Books
Springer International Publishing AG Mathematical Foundations of Data Science
Book SynopsisThis textbook aims to point out the most important principles of data analysis from the mathematical point of view. Specifically, it selected these questions for exploring: Which are the principles necessary to understand the implications of an application, and which are necessary to understand the conditions for the success of methods used? Theory is presented only to the degree necessary to apply it properly, striving for the balance between excessive complexity and oversimplification. Its primary focus is on principles crucial for application success. Topics and features: Focuses on approaches supported by mathematical arguments, rather than sole computing experiences Investigates conditions under which numerical algorithms used in data science operate, and what performance can be expected from them Considers key data science problems: problem formulation including optimality measure; learning and generalization in relationships to training set size and number of free parameters; and convergence of numerical algorithms Examines original mathematical disciplines (statistics, numerical mathematics, system theory) as they are specifically relevant to a given problem Addresses the trade-off between model size and volume of data available for its identification and its consequences for model parametrization Investigates the mathematical principles involves with natural language processing and computer vision Keeps subject coverage intentionally compact, focusing on key issues of each topic to encourage full comprehension of the entire book Although this core textbook aims directly at students of computer science and/or data science, it will be of real appeal, too, to researchers in the field who want to gain a proper understanding of the mathematical foundations “beyond” the sole computing experience.Table of Contents1. Data Science and its Tasks.- 2. Application Specific Mappings and Measuring the Fit to Data.- 3. Data Processing by Neural Networks.- 4. Learning and Generalization.- 5. Numerical Algorithms for Network Learning.- 6. Specific Problems of Natural Language Processing.- 7. Specific Problems of Computer Vision.
£67.49
Springer International Publishing AG Generating Functions in Engineering and the
Book SynopsisGenerating function (GF) is a mathematical technique to concisely represent a known ordered sequence into a simple continuous algebraic function in dummy variable(s). This Second Edition introduces commonly encountered generating functions (GFs) in engineering and applied sciences, such as ordinary GF (OGF), exponential GF (EGF), as also Dirichlet GF (DGF), Lambert GF (LGF), Logarithmic GF (LogGF), Hurwitz GF (HGF), Mittag-Lefler GF (MLGF), etc. This book is intended mainly for beginners in applied science and engineering fields to help them understand single-variable GFs and illustrate how to apply them in various practical problems. Specifically, the book discusses probability GFs (PGF), moment and cumulant GFs (MGF, CGF), mean deviation GFs (MDGF), survival function GFs (SFGF), rising and falling factorial GFs, factorial moment, and inverse factorial moment GFs. Applications of GFs in algebra, analysis of algorithms, bioinformatics, combinatorics, economics, finance, genomics, geometry, graph theory, management, number theory, polymer chemistry, reliability, statistics and structural engineering have been added to this new edition. This book is written in such a way that readers who do not have prior knowledge of the topic can easily follow through the chapters and apply the lessons learned in their respective disciplines.Table of ContentsTypes of Generating Functions.- Operations on Generating Functions.- Generating Functions in Statistics.- Applications of Generating Functions.- Bibliography.
£31.49
Springer International Publishing AG Discrete Mathematics with Graph Theory
Book SynopsisThis book is designed to meet the requirement of undergraduate and postgraduate students pursuing computer science, information technology, mathematical science, and physical science course. No formal prerequisites are needed to understand the text matter except a very reasonable background in college algebra. The text contains in-depth coverage of all major topics proposed by professional institutions and universities for a discrete mathematics course. It emphasizes on problem-solving techniques, pattern recognition, conjecturing, induction, applications of varying nature, proof technique, algorithmic development, algorithm correctness, and numeric computations. A sufficient amount of theory is included for those who enjoy the beauty in development of the subject and a wealth of applications as well as for those who enjoy the power of problem-solving techniques. Biographical sketches of nearly 25 mathematicians and computer scientists who have played a significant role in the development of the field are threaded into the text to provide a human dimension and attach a human face to major discoveries. Each section of the book contains a generous selection of carefully tailored examples to classify and illuminate various concepts and facts. Theorems are backbone of mathematics. Consequently, this book contains the various proof techniques, explained and illustrated in details. Most of the concepts, definitions, and theorems in the book are illustrated with appropriate examples. Proofs shed additional light on the topic and enable students to sharpen thin problem-solving skills. Each chapter ends with a summary of important vocabulary, formulae, properties developed in the chapter, and list of selected references for further exploration and enrichment.Table of Contents0. PRELIMINARIES 1–140.1 Numbers 10.2 Euclid’s Algorithm 30.3 Fundamental Theorem of Arithmetic 40.4 Euclid’s Theorem 60.5 Congruence Modulo m 60.6 Chinese Remainder Theorem 70.7 Fermat’s and Euler’s Theorems 90.8 Exponents and Logarithms 100.9 Sums 110.10 Mapping 12Suggested Readings 141. THE LANGUAGE OF SETS 15–661.1 Introduction 151.2 Elements and Notations of Sets 161.3 Construction of Sets 171.4 Types of Sets 191.5 Set Operations 251.5.1 Intersection of Sets 251.5.2 Union of Sets 261.5.3 Disjoint Set (Mutually Exclusive) 271.5.4 Ordinary Difference of Sets (A – B) 271.5.5 Complementation of Sets 27Contentsxii Contents1.5.6 Universal Set and its Complement 271.5.7 Symmetric Difference (Boolean Sum) 281.6 Venn Diagrams 281.7 Some Basic Results 321.8 Properties of Set Operations 341.8.1 Properties of Intersection on Sets 341.8.2 Properties of Union of Sets 351.8.3 Number of Elements in a Union of two or more Sets 391.9 De-Morgan’s Laws 401.10 General form of Principle of Inclusion and Exclusion 441.11 Laws of Sets 63Summary 63Suggested Readings 652. BASIC COMBINATORICS 67–1142.1 Introduction 672.2 Basic Counting Principles 682.2.1 The Principle of Disjunctive Counting (Sum Rule) 682.2.2 The Principle of Sequential Counting (Product Rule) 692.3 Factorial 712.4 Permutation and Combination 732.4.1 Cyclic Permutation 762.4.2 Pascal’s Identity 762.4.3 Vandermonde’s Identity 772.4.4 Pigeonhole Principle 782.4.5 Inclusion–Exclusion Principle 792.5 The Binomial Theorem 932.6 nth Catalan Number 952.7 Principle of Mathematical Induction (P.M.I) 962.8 Recurrence Relations 99Summary 110Suggested Readings 113Contents xiii3. MATHEMATICAL LOGIC 115–1803.1 Introduction 1153.2 Propositions (Statements) 1173.3 Connectives 1173.3.1 Negation 1183.3.2 Conjunction 1193.3.3 Disjunction 1193.3.4 Conditional 1203.3.5 Biconditional 1203.4 Equivalence of Formulae 1213.5 Well-Formed Formulae (WFF) 1223.6 Tautologies 1223.7 Principle of Duality 1233.8 Two State Devices 1283.9 The Relay-Switching Devices 1293.10 Logic Gates and Modules 1303.10.1 OR, AND and NOT Gates 1303.10.2 Two-Level Networks 1323.10.3 NOR and NAND Gates 1323.11 Normal Forms (Decision Problems) 1413.11.1 Disjunctive Normal Form (DNF) 1413.11.2 Conjunctive Normal Form (CNF) 1453.11.3 Principal Disjunctive Normal Form (PDNF) 1463.11.4 Principal Conjuctive Normal Forms (PCNF) 1483.12 Rules of Inference 1513.13 Automatic Proving System (Theorems) 1523.14 The Predicate Calculus 1643.14.1 Statement Functions, Variables and Quantifiers 1663.14.2 Free and Bound Variables 1663.14.3 Special Valid Formulae using Quantifiers 1673.14.4 Theory of Inference for the Predicate Calculus 1683.14.5 Formulae Involving More than one Quantifier 169Summary 175Suggested Readings 179xiv Contents4. RELATIONS 181–2364.1 Introduction 1814.2 Product Sets 1824.3 Partitions 1824.4 Relations 1834.5 Binary Relations in a Set 1834.6 Domain and Range of a Relation 1844.6.1 Number of Distinct Relation From set A to B 1854.6.2 Solution sets and Graph of Relations 1894.6.3 Relation as Sets of Ordered Pairs 1904.7 The Matrix of a Relation and Digraphs 1904.8 Paths in Relations and Digraphs 1914.9 Boolean Matrices 1944.9.1 Boolean Operations AND and OR 1954.9.2 Joint and Meet 1954.9.3 Boolean Product 1954.9.4 Boolean Power of a Boolean Matrix 1954.10 Adjacency Matrix of a Relation 1984.11 Gray Code 1984.12 Properties of Relations 2004.12.1 Reflexive and Irreflexive Relations 2014.12.2 Symmetric, Asymmetric and AntisymmetricRelations 2014.12.3 Transitive Relation 2024.13 Equivalence Relations 2054.14 Closure of Relations 2074.15 Manipulation and Composition of Relations 2084.16 Warshall’s Algorithm 2164.17 Partial Order Relation 2254.17.1 Totally Ordered Set 2264.17.2 Lexicographic Order 2264.17.3 Hasse Diagrams 228Summary 230Suggested Readings 235Contents xv5. FUNCTIONS 237–2705.1 Introduction 2385.1.1 Sum and Product of Functions 2395.2 Special Types of Functions 2425.2.1 Polynomial Function 2445.2.2 Exponential and Logarithmic Function 2445.2.3 Floor and Ceiling Functions 2455.2.4 Transcedental Function 2475.2.5 Identity Function 2475.2.6 Integer Value and Absolute Value Functions 2475.2.7 Remainder Function 2485.3 Composition of Functions 2485.4 Inverse of a Function 2505.5 Hashing Functions 2565.6 Countable and Uncountable Sets 2575.7 Characteristic Function of a Set 2595.8 Permutation Function 2615.9 Growth of Functions 2625.10 The Relation Θ 262Summary 267Suggested Readings 2696. LATTICE THEORY 271–3046.1 Introduction 2716.2 Partial Ordered Sets 2726.2.1 Some Important Terms 2736.2.2 Diagramatical Representation of a Poset(Hasse Diagram) 2756.2.3 Isomorphism 2766.2.4 Duality 2786.2.5 Product of two Posets 2806.3 Lattices as Posets 2826.3.1 Some Properties of Lattices 2836.3.2 Lattices as Algebraic Systems 284xvi Contents6.3.3 Complete Lattice 2906.3.4 Bounded Lattice 2906.3.5 Sublattices 2916.3.6 Ideals of Lattices 2916.4 Modular and Distributive Lattices 292Summary 302Suggested Readings 3047. BOOLEAN ALGEBRAS AND APPLICATIONS 305–3547.1 Introduction 3057.2 Boolean Algebra (Analytic Approach) 3067.2.1 Sub-Boolean Algebra 3087.2.2 Boolean Homomorphism 3097.3 Boolean Functions 3187.3.1 Equality of Boolean Expressions 3197.3.2 Minterms and Maxterms 3197.3.3 Functional Completeness 3207.3.4 NAND and NOR 3207.4 Combinatorial Circuits (Synthesis of Circuits) 3267.4.1 Half-Adder and Full-Adder 3267.4.2 Equivalent Combinatorial Circuits 3287.5 Karnaugh Map 3317.5.1 Don’t Care Conditions 3347.5.2 Minimization Process 3357.6 Finite State Machines 344Summary 347Suggested Readings 3528. FUZZY ALGEBRA 355–3928.1 Introduction 3558.2 Crisp Sets and Fuzzy Sets 3578.3 Some Useful Definitions 3608.4 Operations of Fuzzy Sets 3628.5 Interval-Valued Fuzzy Sets (I-V Fuzzy Sets) 3678.5.1 Union and Intersection of two I–V Fuzzy Sets 368Contents xvii8.6 Fuzzy Relations 3698.6 Fuzzy Measures 3738.7.1 Belief and Plausibility Measures 3738.7.2 Probability Measure 3748.7.3 Uncertainty and Measures of Fuzziness 3748.7.4 Uncertainty and Information 3758.8 Applications of Fuzzy Algebras 3768.8.1 Natural, Life and Social Sciences 3768.8.2 Engineering 3788.8.3 Medical Sciences 3818.8.4 Management Sciences and Decision MakingProcess 3828.8.5 Computer Science 3838.9 Uniqueness of Uncertainty Measures 3848.9.1 Shannon’s Entropy 3848.9.2 U-uncertainty 3868.9.3 Uniqueness of the U-uncertainty forTwo-Value Possibility Distributions 388Summary 389Suggested Readings 3909. FORMAL LANGUAGES AND AUTOMATATHEORY 393–4289.1 Introduction 3939.2 Formal Languages 3969.2.1 Equality of Words 3979.2.2 Concatenation of Languages 3989.2.3 Kleene Closure 3999.3 Grammars 4039.3.1 Phase-structure Grammar 4069.3.2 Derivations of Grammar 4069.3.3 Backus-Normal Form (BNF) or BackusNaur Form 4079.3.4 Chomsky Grammar 4109.3.5 Ambiguous Grammar 411xviii Contents9.4 Finite-State Automation (FSA) 4139.4.1 Counting to Five 4149.4.2 Process of Getting up in the Morning (Alarm) 4149.4.3 Traffic Light 4159.4.4 Vending Machine 4169.5 Finite-State Machine (FSM) 4169.6 Finite-State Automata 4189.6.1 Deterministic Finite-State Automata (DFSA) 4189.6.2 Nondeterministic Finite-State Automata 4199.6.3 Equivalent Nondeterministic Finite StateAutomata 420Summary 424Suggested Readings 42810. THE BASICS OF GRAPH THEORY 429–48010.1 Introduction 42910.2 Graph. What is it? 43010.2.1 Simple Graph 43010.2.2 Graph 43310.2.3 Loops 43610.2.4 Degree of Vertices 43610.2.5 Equivalence Relation 44110.2.6 Random Graph Model 44210.2.7 Isolated Vertex, Pendent Vertex and Null Graph 44210.3 Digraphs 44310.4 Path, Trail, Walk and Vertex Sequence 44610.5 Subgraph 44710.6 Circuit and Cycle 44710.7 Cycles and Multiple Paths 44910.8 Connected Graph 44910.9 Spanning Subgraph and Induced Subgraph 45010.10 Eulerian Graph (Eulerian Trail and Circuit) 45010.11 Hamiltonian Graph 45110.12 Biconnected Graph 452Contents xix10.13 Algebraic terms and operations used in Graph Theory 45310.13.1 Graphs Isomorphism 45310.13.2 Union of two Graphs 45510.13.3 Intersection of two Graphs 45510.13.4 Addition of two Graphs 45610.13.5 Direct Sum or Ring Sum of two Graphs 45610.13.6 Product of two Graphs 45710.13.7 Composition of two Graphs 45710.13.8 Complement of a Graph 45710.13.9 Fusion of a Graph 45810.13.10 Rank and Nullity 45910.13.11 Adjacency Matrix 45910.13.12 Some Important Theorems 46010.14 Some Popular Problems in Graph Theory 46510.14.1 Tournament Ranking Problem 46510.14.2 The Königsberg Bridge Problem 46710.14.3 Four Colour Problem 46710.14.4 Three Utilities Problem 46810.14.5 Traveling - Salesman Problem 46810.14.6 MTNL’S Networking Problem 47010.14.7 Electrical Network Problems 47010.14.8 Satellite Channel Problem 47110.15 Applications of Graphs 471Summary 475Suggested Readings 48011. TREES 481–52011.1 Introduction 48111.2 Definitions of a Tree 48211.3 Forest 48311.4 Rooted Graph 48411.5 Parent, Child, Sibling and Leaf 48511.6 Rooted Plane Tree 48511.7 Binary Trees 492xx Contents11.8 Spanning Trees 49411.9 Breadth – First Search and Depth – FirstSearch (BFS and DFS) 49611.10 Minimal Spanning Trees 50411.10.1 Kruskal’s Algorithm (for Finding a MinimalSpanning Tree) 50411.10.2 Prim’s Algorithm 50911.11 Directed Trees 511Summary 516Suggested Readings 51812. PLANAR GRAPHS 521–54412.1 Introduction 52112.2 Geometrical Representation of Graphs 52212.3 Bipertite Graph 52412.4 Homeomorphic Graph 52512.5 Kuratowski’s Graphs 52612.6 Dual Graphs 53012.7 Euler’s Formula 53212.8 Outerplanar Graphs 53512.8.1 k-outerplanar Graphs 536Summary 542Suggested Readings 54313. DIRECTED GRAPHS 545–57413.1 Introduction 54513.2 Directed Paths 54713.3 Tournament 54913.4 Directed Cycles 55013.5 Acyclic Graph 55413.6 Di-Orientable Graph 55513.7 Applications of Directed Graphs 55813.7.1 Job Sequencing Problem 55813.7.2 To Design an Efficient Computer Drum 56013.7.3 Ranking of the Participants in a Tournament 562Contents xxi13.8 Network Flows 56413.9 Improvable Flows 56513.10 Max-Flow Min-Cut Theorem 56713.11 k-flow 56813.12 Tutte’s Problem 569Summary 571Suggested Readings 57414. MATCHING AND COVERING 575–60814.1 Introduction 57514.2 Matching and Covering in Bipertite Graphs 57714.2.1 Covering 58214.3 Perfect Matching 58414.4 Factor-critical Graph 58814.5 Complete Matching 59014.6 Matrix Method to Find Matching of a Bipertite Graph 59214.7 Path Covers 59514.8 Applications 59614.8.1 The Personnel Assignment Problem 59614.8.2 The Optimal Assignment Problem 60114.8.3 Covering to Switching Functions 602Summary 604Suggested Readings 60715. COLOURING OF GRAPHS 609–64015.1 Introduction 60915.2 Vertex Colouring 61215.3 Chromatic Polynomial 61315.3.1 Bounds of the Chromatic Number 61415.4 Exams Scheduling Problem 61715.5 Edge Colouring 62515.6 List Colouring 63015.7 Greedy Colouring 63115.8 Applications 63515.8.1 The Time Table Problem 635xxii Contents15.8.2 Scheduling of Jobs 63615.8.3 Ramsey Theory 63715.8.4 Storage Problem 637Summary 638Suggested Readings 639References 641–642Index 643–648
£89.99
Springer International Publishing AG Graph Drawing and Network Visualization: 30th International Symposium, GD 2022, Tokyo, Japan, September 13–16, 2022, Revised Selected Papers
Book SynopsisThis book constitutes the proceedings of the 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, held in Tokyo, Japan, during September 13-16, 2022. The 25 full papers, 7 short papers, presented together with 2 invited talks, one report on graph drawing contest, and one obituary in these proceedings were carefully reviewed and selected from 70 submissions. The abstracts of 5 posters presented at the conference can be found in the back matter of the volume. The contributions were organized in topical sections as follows: properties of drawings of complete graphs; stress-based visualizations of graphs; planar and orthogonal drawings; drawings and properties of directed graphs; beyond planarity; dynamic graph visualization; linear layouts; and contact and visibility graph representations. Table of ContentsProperties of Drawings of Complete Graphs.- Stress-based Visualizations of Graphs.- Planar and Orthogonal Drawings.- Drawings and Properties of Directed Graphs.- Beyond Planarity.- Dynamic Graph Visualization.- Linear Layouts.- Contact and Visibility Graph Representations.
£58.49
Springer International Publishing AG Advanced Graph Theory
Book Synopsis
£49.49
Springer International Publishing AG A Guide to Penrose Tilings
Book SynopsisThis book provides an elementary introduction, complete with detailed proofs, to the celebrated tilings of the plane discovered by Sir Roger Penrose in the '70s. Quasi-periodic tilings of the plane, of which Penrose tilings are the most famous example, started as recreational mathematics and soon attracted the interest of scientists for their possible application in the description of quasi-crystals. The purpose of this survey, illustrated with more than 200 figures, is to introduce the curious reader to this beautiful topic and be a reference for some proofs that are not easy to find in the literature. The volume covers many aspects of Penrose tilings, including the study, from the point of view of Connes' Noncommutative Geometry, of the space parameterizing these tilings.Table of ContentsIntroduction.- Tilings and puzzles.- Robinson triangles.- Penrose tilings.- De Bruijn’s pentagrids.- The noncommutative space of Penrose tilings.-Some useful formulas.
£49.49
Springer International Publishing AG Discrete Mathematics: A Concise Introduction
Book SynopsisThis book is ideal for a first or second year discrete mathematics course for mathematics, engineering, and computer science majors. The author has extensively class-tested early conceptions of the book over the years and supplements mathematical arguments with informal discussions to aid readers in understanding the presented topics. “Safe” – that is, paradox-free – informal set theory is introduced following on the heels of Russell’s Paradox as well as the topics of finite, countable, and uncountable sets with an exposition and use of Cantor’s diagonalisation technique. Predicate logic “for the user” is introduced along with axioms and rules and extensive examples. Partial orders and the minimal condition are studied in detail with the latter shown to be equivalent to the induction principle. Mathematical induction is illustrated with several examples and is followed by a thorough exposition of inductive definitions of functions and sets. Techniques for solving recurrence relations including generating functions, the O- and o-notations, and trees are provided. Over 200 end of chapter exercises are included to further aid in the understanding and applications of discrete mathematics. Table of ContentsElementary Informal Set Theory.- Safe Set Theory.- Relations and Functions.- A Tiny Bit of Informal Logic.- Inductively Defined Sets and Structural Induction.- Recurrence Equations.- Trees and Graphs.
£33.24
Springer International Publishing AG Integer Programming and Combinatorial
Book SynopsisThis book constitutes the refereed proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, held in Madison, WI, USA, during June 21–23, 2023. The 33 full papers presented were carefully reviewed and selected from 119 submissions. IPCO is under the auspices of the Mathematical Optimization Society, and it is an important forum for presenting present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
£61.74
Springer International Publishing AG Variable Neighborhood Search: 9th International
Book SynopsisThis volume constitutes the proceedings of the 9th International Conference on Variable Neighborhood Search, ICVNS 2023, held in Abu Dhabi, United Arab Emirates, in October 2022.The 11 full papers presented in this volume were carefully reviewed and selected from 29 submissions. The papers describe recent advances in methods and applications of variable neighborhood search.Table of ContentsA metaheuristic approach for solving Monitor Placement Problem.- A VNS-based heuristic for the minimum number of resources under a perfect schedule.- BVNS for Overlapping Community Detection.- A Simulation-Based Variable Neighborhood Search Approach for Optimizing Cross-Training Policies.- Multi-Objective Variable Neighborhood Search for improving software modularity.- An Effective VNS for Delivery Districting.- BVNS for the Minimum Sitting Arrangement problem in a cycle.- Assigning Multi-Skill Confgurations to Multiple Servers with a Reduced VNS.- Multi-Round Infuence Maximization: A Variable Neighborhood Search Approach.- A VNS based heuristic for a 2D Open Dimension Problem.- BVNS for the bi-objective multi row equal facility layout problem.
£42.74
Springer International Publishing AG Frontiers of Algorithmics: 17th International
Book SynopsisThis book constitutes the refereed proceedings of the 17th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom (IJTCS-FAW 2023), consisting of the 17th International Conference on Frontier of Algorithmic Wisdom (FAW) and the 4th International Joint Conference on Theoretical Computer Science (IJTCS), held in Macau, China, during August 14–18, 2023.FAW started as the Frontiers of Algorithmic Workshop in 2007 at Lanzhou, China, and was held annually from 2007 to 2021 and published archival proceedings. IJTCS, the International joint theoretical Computer Science Conference, started in 2020, aimed to bring in presentations covering active topics in selected tracks in theoretical computer science. To accommodate the diversified new research directions in theoretical computer science, FAW and IJTCS joined their forces together to organize an event for information exchange of new findings and work of enduring value in the field. The 21 full papers included in this book were carefully reviewed and selected from 34 submissions. They were organized in topical sections as follows: algorithmic game theory; algorithms and data structures; combinatorial optimization; and computational economics.Table of ContentsUnderstanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions.- An Improved Analysis of the Greedy+Singleton Algorithm for k-Submodular Knapsack Maximization.- Generalized Sorting with Predictions Revisited.- Eliciting Truthful Reports with Partial Signals in Repeated Games.- On the NP-hardness of two scheduling problems under linear constraints.- On the Matching Number of k-Uniform Connected Hypergraphs with Maximum Degree.- Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant.- Approximate Core Allocations for Edge Cover Games.- Random Approximation Algorithms for Monotone k-Submodular Function Maximization with Size Constraints.- Additive Approximation Algorithms for Sliding Puzzle.- Differential Game Analysis for Cooperation Models in Automotive Supply Chain under Low-Carbon Emission Reduction Policies.- Adaptivity Gap for Influence Maximization with Linear Threshold Model on Trees.- Physically Verifying the First Nonzero Term in a Sequence: Physical ZKPs for ABC End View and Goishi Hiroi.- Mechanism Design in Fair Sequencing.- Red-Blue Rectangular Annulus Cover Problem.- Applying Johnson's Rule in Scheduling Multiple Parallel Two-Stage Flowshops.- The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations.- Constrained Graph Searching on Trees.- EFX Allocations Exist for Binary Valuations.- Maximize Egalitarian Welfare for Cake Cutting.- Stackelberg Strategies on Epidemic Containment Games.
£56.99
Springer International Publishing AG Hypergroups
Book SynopsisThis book provides a comprehensive algebraic treatment of hypergroups, as defined by F. Marty in 1934. It starts with structural results, which are developed along the lines of the structure theory of groups. The focus then turns to a number of concrete classes of hypergroups with small parameters, and continues with a closer look at the role of involutions (modeled after the definition of group-theoretic involutions) within the theory of hypergroups. Hypergroups generated by involutions lead to the exchange condition (a genuine generalization of the group-theoretic exchange condition), and this condition defines the so-called Coxeter hypergroups. Coxeter hypergroups can be treated in a similar way to Coxeter groups. On the other hand, their regular actions are mathematically equivalent to buildings (in the sense of Jacques Tits). A similar equivalence is discussed for twin buildings. The primary audience for the monograph will be researchers working in Algebra and/or Algebraic Combinatorics, in particular on association schemes.Table of Contents1 Basic Facts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11.1 Neutral Elements and Inverse Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Complex Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Thin Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Groups and Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.6 Actions of Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 Hypergroups Admitting Regular Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.8 Association Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Closed Subsets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 272.1 Basic Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.2 Dedekind Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Generating Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 Commutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.5 Conjugation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.6 The Thin Radical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.7 Foldings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Elementary Structure Theory: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 473.1 Centralizers and Normalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2 Su cient Conditions for Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.3 Strong Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.4 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.5 Computations in Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.6 Homomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.7 The Homomorphism Theorem and the Isomorphism Theorems . . . . . . . . . . 714 Subnormality and Thin Residues : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 794.1 Subnormal Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.2 Composition Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.3 The Thin Residue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884.4 Thin Residues of Thin Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.5 Residually Thin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944.6 Finite Residually Thin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.7 Solvable Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045 Tight Hypergroups : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1075.1 Tight Hypergroup Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075.2 The Set S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.3 The Sets a b \ Fc and Sa;b(Fc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135.4 The Sets bf1b \ Fa and Sb;(f1;:::;fn)(Fa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175.5 Structure Constants of Finite Tight Hypergroups . . . . . . . . . . . . . . . . . . . . . 1225.6 Rings Arising from Certain Finite Tight Hypergroups . . . . . . . . . . . . . . . . . 1265.7 Finite Metathin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.8 Finite Metathin Hypergroups with Restricted Thin Residue . . . . . . . . . . . . 1326 Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1376.1 Basic Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.2 Cosets of Closed Subsets Generated by an Involution, I . . . . . . . . . . . . . . . . 1426.3 Cosets of Closed Subsets Generated by an Involution, II . . . . . . . . . . . . . . . 1456.4 Cosets of Closed Subsets Generated by an Involution, III . . . . . . . . . . . . . . . 1476.5 Length Functions De ned by Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . 1526.6 Hypergroups Generated by Two Distinct Involutions . . . . . . . . . . . . . . . . . . 1566.7 Dichotomy and the Exchange Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616.8 Projective Hypergroups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1647 Hypergroups with a Small Number of Elements : : : : : : : : : : : : : : : : : : : : : : 1717.1 Hypergroups of Cardinality at Most 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1727.2 Non-Symmetric Hypergroups of Cardinality 4 . . . . . . . . . . . . . . . . . . . . . . . . 1797.3 Hypergroups of Cardinality 6 with a Non-Normal Closed Subset, I . . . . . . 1907.4 Hypergroups of Cardinality 6 with a Non-Normal Closed Subset, II . . . . . . 2027.5 Non-Normal Closed Subsets Missing Four Elements . . . . . . . . . . . . . . . . . . . 2157.6 Non-Normal Closed Subsets Missing Four Elements and Thin Elements . . 2218 Constrained Sets of Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2238.1 Basic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2248.2 Constrained Sets of Involutions and Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 2288.3 Constrained Sets of Involutions and the Thin Radical . . . . . . . . . . . . . . . . . . 2308.4 Constrained Sets of Involutions and Dichotomy . . . . . . . . . . . . . . . . . . . . . . . 2338.5 Constrained Sets of Non-Thin Involutions and Dichotomy . . . . . . . . . . . . . . 2398.6 Constrained Sets of Involutions and Foldings . . . . . . . . . . . . . . . . . . . . . . . . . 2448.7 Dichotomic Constrained Sets of Involutions and Foldings . . . . . . . . . . . . . . . 2489 Coxeter Sets of Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2519.1 General Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2529.2 The Sets V1(U) for Subsets U of Coxeter Sets V of Involutions . . . . . . . . . . 2569.3 The Sets V����1(U) for Subsets U of Coxeter Sets V of Involutions . . . . . . . . . 2639.4 Sets of Subsets of Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . . . 2659.5 Spherical Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2689.6 Subsets of Spherical Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . 2739.7 Coxeter Sets of Involutions and Foldings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2779.8 Coxeter Sets of Involutions and Their Coxeter Numbers . . . . . . . . . . . . . . . . 2809.9 Coxeter Sets of Involutions and Type Preserving Bijections . . . . . . . . . . . . . 28610 Regular Actions of (Twin) Coxeter Hypergroups: : : : : : : : : : : : : : : : : : : : : 29310.1 Buildings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29310.2 Twin Buildings, I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29810.3 Twin Buildings, II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30110.4 Regular Actions of Coxeter Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30510.5 Regular Actions of Twin Coxeter Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . 315References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 333
£107.99
Springer International Publishing AG Graph-Theoretic Concepts in Computer Science:
Book SynopsisThis volume constitutes the thoroughly refereed proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2023. The 33 full papers presented in this volume were carefully reviewed and selected from a total of 116 submissions. The WG 2022 workshop aims to merge theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications.Table of ContentsProportionally Fair Matching with Multiple Groups.- Reconstructing Graphs from Connected Triples.- Parameterized Complexity of Vertex Splitting to Pathwidth at most 1.- Odd Chromatic Number of Graph Classes.- Deciding the Erdos-P osa property in 3-connected digraphs.- New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth.- Computational Complexity of Covering Colored Mixed Multigraphswith Degree Partition Equivalence Classes of Size at Most Two.- Cutting Barnette graphs perfectly is hard.- Metric dimension parameterized by treewidth in chordal graphs.- Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs.- Generating faster algorithms for d-Path Vertex Cover.- A new width parameter of graphs based on edge cuts: -edge-crossing width.- Snakes and Ladders: a Treewidth Story.- Parameterized Results on Acyclic Matchings with Implications for Related Problems.- P-matchings Parameterized by Treewidth.- Algorithms and hardness for Metric Dimension on digraphs.- Degreewidth : a New Parameter for Solving Problems on Tournaments.- Approximating Bin Packing with Con ict Graphs via Maximization Techniques.- i-Metric Graphs: Radius, Diameter and all Eccentricities.- Maximum edge colouring problem on graphs that exclude a xed minor.- Bounds on Functionality and Symmetric Di erence { Two Intriguing Graph Parameters.- Cops and Robbers on Multi-layer Graphs.- Parameterized Complexity of Broadcasting in Graphs.- Turan's Theorem Through Algorithmic Lens.- On the Frank number and nowhere-zero ows on graphs.- On the minimum number of arcs in 4-dicritical oriented graphs.- Tight Algorithms for Connectivity Problems Parameterized byModular-Treewidth.
£61.74
Springer International Publishing AG Reshaping Convex Polyhedra
Book Synopsis^ the= study= of= convex= polyhedra= in= ordinary= space= is= a= central= piece= classical= and= modern= geometry= that= has= had= significant= impact= on= many= areas= mathematics= also= computer= science.= present= book= project= by= joseph= o'rourke= costin= vîlcu= brings= together= two= important= strands= subject= = combinatorics= polyhedra,= intrinsic= underlying= surface.= this= leads= to= remarkable= interplay= concepts= come= life= wide= range= very= attractive= topics= concerning= polyhedra.= gets= message= across= thetheory= although= with= roots,= still= much= alive= today= continues= be= inspiration= basis= lot= current= research= activity.= work= presented= manuscript= interesting= applications= discrete= computational= geometry,= as= well= other= mathematics.= treated= detail= include= unfolding= onto= surfaces,= continuous= flattening= convexity= theory= minimal= length= enclosing= polygons.= along= way,= open= problems= suitable= for= graduate= students= are= raised,=
£98.99
Springer International Publishing AG SOFSEM 2024: Theory and Practice of Computer
Book SynopsisThis book constitutes the proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, held in Cochem, Germany, in February 2024. The 33 full papers presented in this book were carefully reviewed and selected from 81 submissions. The book also contains one invited talk in full paper length. They focus on original research and challenges in foundations of computer science including algorithms, AI-based methods, computational complexity, and formal models.Table of ContentsThe Information Extraction Framework of Document Spanners - A Very Informal Survey.- Generalized Distance Polymatrix Games.- Relaxed agreement forests.- On the Computational Complexity of Generalized Common Shape Puzzles.- Fractional Bamboo Trimming and Distributed Windows Scheduling.- New support size bounds and proximity bounds for integer linear programming.- On the Parameterized Complexity of Minus Domination.- Exact and Parameterized Algorithms for Choosability.- Parameterized Algorithms for Covering by Arithmetic Progressions.- Row-column combination of Dyck words.- Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures.- On the parameterized complexity of the Perfect Phylogeny problem.- Data reduction for directed feedback vertex set on graphs without long induced cycles.- Visualization of Bipartite Graphs in Limited Window Size.- Outerplanar and Forest Storyplans.- The Complexity of Cluster Vertex Splitting and Company.- Morphing Graph Drawings in the Presence of Point Obstacles.- Word-Representable Graphs from a Word’s Perspective.- Removable Online Knapsack with Bounded Size Items.- The Complexity of Online Graph Games.- Faster Winner Determination Algorithms for (Colored) Arc Kayles.- Automata Classes Accepting Languages Whose Commutative Closure is Regular.- Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching.- Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages.- Apportionment with Thresholds: Strategic Campaigns Are Easy in the Top-Choice But Hard in the Second-Chance Mode.- Local Certification of Majority Dynamics.- Complexity of Spherical Equations in Finite Groups.- Positive Characteristic Sets for Relational Pattern Languages.- Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs.- The Weighted HOM-Problem over Fields.- Combinatorics of block-parallel automata networks.- On the piecewise complexity of words and periodic words.- Distance Labeling for Families of Cycles.- On the induced problem for fixed-template CSPs.
£61.74
Springer Mathematics of Computer Science Cybersecurity and
Book Synopsis- Mathematics and computer science in the information revolution.- NLP and some research results in Senegal.- On absolute valued algebras with nonzero central element.- On algebraic algebras without divisors of zero satisfying (xp, xq, xr) = 0.- Computing minimal free resolutions over monomial semirings with coefficients in D-A rings.- Schur complement and inequalities of eigenvalues on block Hadamard product.- A perturbed Mann-type algorithm for zeros of maximal monotone mappings.- On Rickart and Baer semimodules.- Completion fractions modules of filtered modules over non-necessarily commutative filtered rings.- On S-lifting semimodules over semirings.- A contribution to the study of a class of noncommutative ideals admitting finite Gröbner bases.- Construction of numbers with the same normality properties as a given number. - Robustness of imputation methods with backpropagation algorithm in nonlinear multiple regression.- A better random forest classifier: Labels guided Mondrian forest.- Remote sensing of artisanal mines buried in the ground by infrared thermography using UAV.- Implementation of EdDSA in the Ethereum blockchain.- Vulnerability prediction of web applications from source code based on machine learning and deep learning: Where are we at?.- Business process management and process mining on the large: Overview, challenges and research directions.
£143.99
Springer Discrete Structures
Book SynopsisPreface.- Notation.- I. Discrete Structures.- 1. Introduction.-2. Mathematical Arguments.-3. Sets.- 4. Proof by Induction.- 5. Equivalence Relations.- 6. Partial Orders and Lattices.- 7. Floor and Ceiling Functions.- 8. Number Theory.- II. Summation and Asymptotics.- 10. Asymptotic Analysis.- III. Combinatorics.- 11. Counting.- 12. Generating Functions.- 13. Recurrence Relations.- 14. Graphs.- 15. Probability.- Bibliography.- Index.
£49.49
Springer GraphTheoretic Concepts in Computer Science
Book Synopsis
£58.49
Springer Diagrammatic Algebra
Book Synopsis
£49.49
Birkhauser Verlag AG Problem-Solving Methods in Combinatorics: An Approach to Olympiad Problems
Book SynopsisEvery year there is at least one combinatorics problem in each of the major international mathematical olympiads. These problems can only be solved with a very high level of wit and creativity. This book explains all the problem-solving techniques necessary to tackle these problems, with clear examples from recent contests. It also includes a large problem section for each topic, including hints and full solutions so that the reader can practice the material covered in the book. The material will be useful not only to participants in the olympiads and their coaches but also in university courses on combinatorics.Trade ReviewFrom the reviews: “Soberón (Univ. College London, UK) presents tools, techniques, and some tricks to tackle problems of varying difficulty in combinatorial mathematics in this well-written book. … Salient features include the wealth of examples, exercises, and problems and two additional chapters with hints and solutions to the problems. Valuable for all readers interested in combinatorics and useful as a course resource on the subject. Summing Up: Highly recommended. Upper-division undergraduate through professional mathematics collections.” (D. V. Chopra, Choice, Vol. 51 (4), December, 2013)Table of ContentsIntroduction.- 1 First concepts.- 2 The pigeonhole principle.- 3 Invariants.- 4 Graph theory.- 5 Functions.- 6 Generating Functions.- 7 Partitions.- 8 Hints for the problems.- 9 Solutions to the problems.- Notation.- Further reading.- Index.
£61.74
Birkhauser Verlag AG Positional Games
Book SynopsisThis text is based on a lecture course given by the authors in the framework of Oberwolfach Seminars at the Mathematisches Forschungsinstitut Oberwolfach in May, 2013. It is intended to serve as a thorough introduction to the rapidly developing field of positional games. This area constitutes an important branch of combinatorics, whose aim it is to systematically develop an extensive mathematical basis for a variety of two player perfect information games. These ranges from such popular games as Tic-Tac-Toe and Hex to purely abstract games played on graphs and hypergraphs. The subject of positional games is strongly related to several other branches of combinatorics such as Ramsey theory, extremal graph and set theory, and the probabilistic method. These notes cover a variety of topics in positional games, including both classical results and recent important developments. They are presented in an accessible way and are accompanied by exercises of varying difficulty, helping the reader to better understand the theory. The text will benefit both researchers and graduate students in combinatorics and adjacent fields.Trade Review“The present book recalls the main points of the classical theory, and describes some recent results. The text … can be taught in a regular university class. At the end of each chapter there are exercises that help the reader to practice the trade. The intention of that structure is to provide a textbook rather than just a pure record of the lecture notes of the Oberwolfach Seminar. It certainly can be used as a textbook … .” (András Sándor Pluhár, Mathematical Reviews, July, 2017)Table of ContentsPreface.- 1 Introduction.- 2 Maker-Breaker Games.- 3 Biased Games.- 4 Avoider-Enforcer Games.- 5 The Connectivity Game.- 6 The Hamiltonicity Game.- 7 Fast and Strong.- 8 Random Boards.- 9 The Neighborhood Conjecture.- Bibliography.
£21.84
De Gruyter The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal
Book SynopsisThe starting point for this monograph is the previously unknown connection between the Continuum Hypothesis and the saturation of the non-stationary ideal on ω1; and the principle result of this monograph is the identification of a canonical model in which the Continuum Hypothesis is false. This is the first example of such a model and moreover the model can be characterized in terms of maximality principles concerning the universal-existential theory of all sets of countable ordinals. This model is arguably the long sought goal of the study of forcing axioms and iterated forcing but is obtained by completely different methods, for example no theory of iterated forcing whatsoever is required. The construction of the model reveals a powerful technique for obtaining independence results regarding the combinatorics of the continuum, yielding a number of results which have yet to be obtained by any other method. This monograph is directed to researchers and advanced graduate students in Set Theory. The second edition is updated to take into account some of the developments in the decade since the first edition appeared, this includes a revised discussion of Ω-logic and related matters.
£206.15
De Gruyter A Course in Mathematical Cryptography
Book SynopsisCryptography has become essential as bank transactions, credit card infor-mation, contracts, and sensitive medical information are sent through inse-cure channels. This book is concerned with the mathematical, especially algebraic, aspects of cryptography. It grew out of many courses presented by the authors over the past twenty years at various universities and covers a wide range of topics in mathematical cryptography. It is primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area. Besides the classical methods of symmetric and private key encryption, the book treats the mathematics of cryptographic protocols and several unique topics such as Group-Based Cryptography Gröbner Basis Methods in Cryptography Lattice-Based Cryptography
£43.22
De Gruyter Geometry and Discrete Mathematics: A Selection of Highlights
Book SynopsisIn the two-volume set ‘A Selection of Highlights’ we present basics of mathematics in an exciting and pedagogically sound way. This volume examines many fundamental results in Geometry and Discrete Mathematics along with their proofs and their history. In the second edition we include a new chapter on Topological Data Analysis and enhanced the chapter on Graph Theory for solving further classical problems such as the Traveling Salesman Problem.
£47.02
De Gruyter Elements of Discrete Mathematics: Numbers and
Book Synopsis
£51.78
de Gruyter Graphmetriken und Isometrieprobleme zugehöriger
Book Synopsis
£134.09
Springer International Publishing AG Hypergraph Theory: An Introduction
Book SynopsisThis book provides an introduction to hypergraphs, its aim being to overcome the lack of recent manuscripts on this theory. In the literature hypergraphs have many other names such as set systems and families of sets. This work presents the theory of hypergraphs in its most original aspects, while also introducing and assessing the latest concepts on hypergraphs. The variety of topics, their originality and novelty are intended to help readers better understand the hypergraphs in all their diversity in order to perceive their value and power as mathematical tools. This book will be a great asset to upper-level undergraduate and graduate students in computer science and mathematics. It has been the subject of an annual Master's course for many years, making it also ideally suited to Master's students in computer science, mathematics, bioinformatics, engineering, chemistry, and many other fields. It will also benefit scientists, engineers and anyone else who wants to understand hypergraphs theory.Trade ReviewFrom the reviews:“This book addresses the mathematics and theory of hypergraphs. The target audience includes graduate students and researchers with an interest in math and computer science (CS). … I expect readers of this book will be motivated to advance this field, which in turn can advance other sciences.” (Hsun-Hsien Chang, Computing Reviews, January, 2014)“The aim of this book is to introduce the basic concepts of hypergraphs, to present the knowledge of the theory and applications of hypergraphs in other fields. … This book is useful for anyone who wants to understand the basics of hypergraph theory. It is mainly for math and computer science majors, but it may also be useful for other fields which use the theory. … appropriate for both researchers and graduate students. It is very well-written and proofs are stated in a clear manner.” (Somayeh Moradi, zbMATH, Vol. 1269, 2013)Table of ContentsHypergraphs: basic concepts.- Hypergraphs: first properties.- Hypergraph coloring.- Some particular hypergraphs.- Reduction-contraction of Hypergraph.- Dirhypergraphs: basic concepts.- Applications of hypergraph theory : a brief overview.
£52.24
Springer International Publishing AG Concise Computer Mathematics: Tutorials on Theory and Problems
Book SynopsisAdapted from a modular undergraduate course on computational mathematics, Concise Computer Mathematics delivers an easily accessible, self-contained introduction to the basic notions of mathematics necessary for a computer science degree. The text reflects the need to quickly introduce students from a variety of educational backgrounds to a number of essential mathematical concepts. The material is divided into four units: discrete mathematics (sets, relations, functions), logic (Boolean types, truth tables, proofs), linear algebra (vectors, matrices and graphics), and special topics (graph theory, number theory, basic elements of calculus). The chapters contain a brief theoretical presentation of the topic, followed by a selection of problems (which are direct applications of the theory) and additional supplementary problems (which may require a bit more work). Each chapter ends with answers or worked solutions for all of the problems.Trade ReviewFrom the reviews:“The book is ideally suited as an adjunct to a course in computer mathematics or as a refresher for someone with some background in computer mathematics. … The book fulfills its purpose of providing a distilled treatment of the mathematics most commonly used in computer science. It is of most value to computer science students who need a place to find a succinct treatment of the topics covered.” (Marlin Thomas, Computing Reviews, April, 2014)“Each of the chapters opens with a short summary followed by a set of essential problems and then a set of supplementary problems. … it would be very useful for someone that needs a quick and effective review that includes problems.” (Charles Ashbacher, MAA Reviews, January, 2014)Table of ContentsSets and NumbersRelations and DatabasesFunctionsBoolean Algebra, Logic and QuantifiersNormal Forms, Proof and ArgumentVectors and Complex NumbersMatrices and ApplicationsMatrix Transformations for Computer GraphicsElements of Graph TheoryElements of Number Theory and CryptographyElements of CalculusElementary Numerical Methods
£49.49
Springer International Publishing AG Markov's Theorem and 100 Years of the Uniqueness
Book SynopsisThis book takes the reader on a mathematical journey, from a number-theoretic point of view, to the realm of Markov’s theorem and the uniqueness conjecture, gradually unfolding many beautiful connections until everything falls into place in the proof of Markov’s theorem. What makes the Markov theme so attractive is that it appears in an astounding variety of different fields, from number theory to combinatorics, from classical groups and geometry to the world of graphs and words.On the way, there are also introductory forays into some fascinating topics that do not belong to the standard curriculum, such as Farey fractions, modular and free groups, hyperbolic planes, and algebraic words. The book closes with a discussion of the current state of knowledge about the uniqueness conjecture, which remains an open challenge to this day.All the material should be accessible to upper-level undergraduates with some background in number theory, and anything beyond this level is fully explained in the text.This is not a monograph in the usual sense concentrating on a specific topic. Instead, it narrates in five parts – Numbers, Trees, Groups, Words, Finale – the story of a discovery in one field and its many manifestations in others, as a tribute to a great mathematical achievement and as an intellectual pleasure, contemplating the marvellous unity of all mathematics.Trade ReviewFrom the book reviews:“The topic, and its presentation, does make it a fine source for seminar usage. … this is a fine text for students who are ready to see material connecting various areas of mathematics. It reveals the beauty and hints at the excitement of ‘live’ mathematics.” (Thomas A. Schmidt, Mathematical Reviews, September, 2014)“In number theory, Markov’s theorem (1879) reveals surprising structure within a set of real numbers, called the Lagrange spectrum, which collects precise information about approximability of irrational numbers. … Summing Up: Highly recommended. Upper-division undergraduates and above.” (D. V. Feldman, Choice, Vol. 51 (8), April, 2014)“Book tells the story of a celebrated theorem and an intriguing conjecture: Markov’s theorem from 1879 and the uniqueness conjecture formulated by Frobenius … . author takes the opportunity to look at this theorem and this conjecture from many different viewpoints … . He offers a journey through the mathematical world around Markov’s theorem in a leisurely and relaxed style, making his book very pleasant to read. … An undergraduate student will certainly enjoy this reading and learn a lot.” (Yann Bugeaud, Jahresbericht der Deutschen Mathematiker-Vereinigung, Vol. 116, 2014)“This beautiful book gives readers a chance to familiarize themselves with a very simple and yet very difficult problem in number theory, and teaches them that it pays to look at a problem from many different angles. I recommend it to all students who are already hooked to number theory, and perhaps even more to those who are not.” (Franz Lemmermeyer, zbMATH, Vol. 1276, 2014)Table of ContentsApproximation of Irrational Numbers.- Markov's Theorem and the Uniqueness Conjecture.- The Markov Tree.- The Cohn Tree.- The Modular Group SL(2,Z).- The Free Group F2.- Christoffel Words.- Sturmian Words.- Proof of Markov's Theorem.- The Uniqueness Conjecture.
£104.49
Springer International Publishing AG Hypergraph Theory: An Introduction
Book SynopsisThis book provides an introduction to hypergraphs, its aim being to overcome the lack of recent manuscripts on this theory. In the literature hypergraphs have many other names such as set systems and families of sets. This work presents the theory of hypergraphs in its most original aspects, while also introducing and assessing the latest concepts on hypergraphs. The variety of topics, their originality and novelty are intended to help readers better understand the hypergraphs in all their diversity in order to perceive their value and power as mathematical tools. This book will be a great asset to upper-level undergraduate and graduate students in computer science and mathematics. It has been the subject of an annual Master's course for many years, making it also ideally suited to Master's students in computer science, mathematics, bioinformatics, engineering, chemistry, and many other fields. It will also benefit scientists, engineers and anyone else who wants to understand hypergraphs theory.Trade ReviewFrom the reviews:“This book addresses the mathematics and theory of hypergraphs. The target audience includes graduate students and researchers with an interest in math and computer science (CS). … I expect readers of this book will be motivated to advance this field, which in turn can advance other sciences.” (Hsun-Hsien Chang, Computing Reviews, January, 2014)“The aim of this book is to introduce the basic concepts of hypergraphs, to present the knowledge of the theory and applications of hypergraphs in other fields. … This book is useful for anyone who wants to understand the basics of hypergraph theory. It is mainly for math and computer science majors, but it may also be useful for other fields which use the theory. … appropriate for both researchers and graduate students. It is very well-written and proofs are stated in a clear manner.” (Somayeh Moradi, zbMATH, Vol. 1269, 2013)Table of ContentsHypergraphs: basic concepts.- Hypergraphs: first properties.- Hypergraph coloring.- Some particular hypergraphs.- Reduction-contraction of Hypergraph.- Dirhypergraphs: basic concepts.- Applications of hypergraph theory : a brief overview.
£52.24
Springer International Publishing AG Integer Programming
Book SynopsisThis book is an elegant and rigorous presentation of integer programming, exposing the subject’s mathematical depth and broad applicability. Special attention is given to the theory behind the algorithms used in state-of-the-art solvers. An abundance of concrete examples and exercises of both theoretical and real-world interest explore the wide range of applications and ramifications of the theory. Each chapter is accompanied by an expertly informed guide to the literature and special topics, rounding out the reader’s understanding and serving as a gateway to deeper study.Key topics include: formulations polyhedral theory cutting planes decomposition enumeration semidefinite relaxations Written by renowned experts in integer programming and combinatorial optimization, Integer Programming is destined to become an essential text in the field.Trade Review“Integer Programming begins by introducing the subject and giving several examples of integer programming problems. … This book would be suitable for a graduate level course on the mathematics of cutting plane methods. … This book might also be of interest as a reference for researchers working in this area. … This book offers a more focused presentation that makes it better suited for use as a textbook.” (Brian Borchers, MAA Reviews, maa.org, December, 2015)“The book is written in a very clear and didactic style. … very useful for mathematically mature undergraduates, graduate students, postdocs, and established researchers who are interested in the techniques. …This is an excellent and impressive book. We wholeheartedly recommend it as a textbook for advanced undergraduate and introductory graduate courses on integer programming.” (Jakub Marecek, Interfaces, Vol. 45 (5), September-October, 2015)“The authors deliver a comprehensive presentation of integer programming. … Everything is presented in a rigorous way, but on the other hand, the form makes it easy to understand for everyone. Each chapter is followed by the exercises, that allow to recall the contents. … the book is an essential text in the field of integer programing, that should be recommended as a very useful textbook for students, but also a valuable introduction for the researchers in this area.” (Marcin Anholcer, zbMATH 1307.90001, 2015)Table of ContentsPreface.- 1 Getting Started.- 2 Integer Programming Models.- 3 Linear Inequalities and Polyhedra.- 4 Perfect Formulations.- 5 Split and Gomory Inequalities.- 6 Intersection Cuts and Corner Polyhedra.- 7 Valid Inequalities for Structured Integer Programs.- 8 Reformulations and Relaxations.- 9 Enumeration.- 10 Semidefinite Bounds.- Bibliography.- Index.
£42.74
Springer International Publishing AG Transaction Processing: Management of the Logical Database and its Underlying Physical Structure
Book SynopsisTransactions are a concept related to the logical database as seen from the perspective of database application programmers: a transaction is a sequence of database actions that is to be executed as an atomic unit of work. The processing of transactions on databases is a well- established area with many of its foundations having already been laid in the late 1970s and early 1980s.The unique feature of this textbook is that it bridges the gap between the theory of transactions on the logical database and the implementation of the related actions on the underlying physical database. The authors relate the logical database, which is composed of a dynamically changing set of data items with unique keys, and the underlying physical database with a set of fixed-size data and index pages on disk. Their treatment of transaction processing builds on the “do-redo-undo” recovery paradigm, and all methods and algorithms presented are carefully designed to be compatible with this paradigm as well as with write-ahead logging, steal-and-no-force buffering, and fine-grained concurrency control.Chapters 1 to 6 address the basics needed to fully appreciate transaction processing on a centralized database system within the context of our transaction model, covering topics like ACID properties, database integrity, buffering, rollbacks, isolation, and the interplay of logical locks and physical latches. Chapters 7 and 8 present advanced features including deadlock-free algorithms for reading, inserting and deleting tuples, while the remaining chapters cover additional advanced topics extending on the preceding foundational chapters, including multi-granular locking, bulk actions, versioning, distributed updates, and write-intensive transactions.This book is primarily intended as a text for advanced undergraduate or graduate courses on database management in general or transaction processing in particular.Table of Contents1 Transactions on the Logical Database.- 2 Operations on the Physical Database.- 3 Logging and Buffering.- 4 Transaction Rollback and Restart Recovery.- 5 Transactional Isolation.- 6 Lock-Based Concurrency Control.- 7 B-Tree Traversals.- 8 B-Tree Structure Modifications.- 9 Advanced Locking Protocols.- 10 Bulk Operations on B-Trees.- 11 Online Index Construction and Maintenance.- 12 Concurrency Control by Versioning.- 13 Distributed Transactions.- 14 Transactions in Page-Server Systems.- 15 Processing of Write-Intensive Transactions.
£61.18
Springer International Publishing AG How to Count: An Introduction to Combinatorics
Book SynopsisProviding a self-contained resource for upper undergraduate courses in combinatorics, this text emphasizes computation, problem solving, and proof technique. In particular, the book places special emphasis the Principle of Inclusion and Exclusion and the Multiplication Principle. To this end, exercise sets are included at the end of every section, ranging from simple computations (evaluate a formula for a given set of values) to more advanced proofs. The exercises are designed to test students' understanding of new material, while reinforcing a working mastery of the key concepts previously developed in the book. Intuitive descriptions for many abstract techniques are included. Students often struggle with certain topics, such as generating functions, and this intuitive approach to the problem is helpful in their understanding. When possible, the book introduces concepts using combinatorial methods (as opposed to induction or algebra) to prove identities. Students are also asked to prove identities using combinatorial methods as part of their exercises. These methods have several advantages over induction or algebra.Trade Review“The book is an excellent introduction to combinatorics. … The author uses a clear language and often provides an easy intuitive access to abstract subjects. The presentation is well motivated, the explanations are transparent and illustrated by carefully selected examples. Each section ends with a list of well formulated exercises which make the book ideally suited for self-instruction.” (Astrid Reifegerste, zbMATH 1328.05001, 2016)“This book by Beeler … is an excellent introductory text on combinatorics. The author gives the right balance of theory, computation, and applications, and he presents introductory-level topics, such as the multiplication principle, binomial theorem, and distribution problems in a clear manner. … Summing Up: Highly recommended. Upper-division undergraduates through researchers and faculty.” (S. L. Sullivan, Choice, Vol. 53 (1), September, 2015)Table of ContentsPreliminaries.- Basic Counting.- The Binomial Coefficient.- Distribution Problems.- Generating Functions.- Recurrence Relations.- Advanced Counting - Inclusion and Exclusion.- Advanced Counting - Polya Theory.- Application: Probability.- Application: Combinatorial Designs.- Application: Graph Theory.- Appendices.
£49.49
Springer International Publishing AG Measures of Symmetry for Convex Sets and Stability
Book SynopsisThis textbook treats two important and related matters in convex geometry: the quantification of symmetry of a convex set—measures of symmetry—and the degree to which convex sets that nearly minimize such measures of symmetry are themselves nearly symmetric—the phenomenon of stability. By gathering the subject’s core ideas and highlights around Grünbaum’s general notion of measure of symmetry, it paints a coherent picture of the subject, and guides the reader from the basics to the state-of-the-art. The exposition takes various paths to results in order to develop the reader’s grasp of the unity of ideas, while interspersed remarks enrich the material with a behind-the-scenes view of corollaries and logical connections, alternative proofs, and allied results from the literature. Numerous illustrations elucidate definitions and key constructions, and over 70 exercises—with hints and references for the more difficult ones—test and sharpen the reader’s comprehension.The presentation includes: a basic course covering foundational notions in convex geometry, the three pillars of the combinatorial theory (the theorems of Carathéodory, Radon, and Helly), critical sets and Minkowski measure, the Minkowski–Radon inequality, and, to illustrate the general theory, a study of convex bodies of constant width; two proofs of F. John’s ellipsoid theorem; a treatment of the stability of Minkowski measure, the Banach–Mazur metric, and Groemer’s stability estimate for the Brunn–Minkowski inequality; important specializations of Grünbaum’s abstract measure of symmetry, such as Winternitz measure, the Rogers–Shepard volume ratio, and Guo’s Lp -Minkowski measure; a construction by the author of a new sequence of measures of symmetry, the kth mean Minkowski measure; and lastly, an intriguing application to the moduli space of certain distinguished maps from a Riemannian homogeneous space to spheres—illustrating the broad mathematical relevance of the book’s subject.Trade Review“The book under review is a graduate-level textbook on convexity, which presents the topic from a new and interesting point of view. … The book offers the reader a new approach to the study of convexity, focusing on the important topics of measures of symmetry and stability. It moves from the very beginning background to recent research, and therefore both students and researchers can benefit from it.” (María A. Hernández Cifre, Mathematical Reviews, December, 2016) “This is a graduate-level textbook on convex geometry in finite-dimensional Euclidean spaces, which has some interesting special features. … Each chapter has illustrating figures and concludes with exercises … . The book has a surprising appendix, where certain of the symmetry measures are applied to convex bodies … . This book is an unconventional introduction to convexity, full of appealing intuitive geometry; it may equally well serve the beginner and the experienced researcher in the field.” (Rolf Schneider, zbMATH 1335.52002, 2016)Table of ContentsFirst Things First on Convex Sets.- Affine Diameters and the Critical Set.- Measures of Stability and Symmetry.- Mean Minkowski Measures.
£41.24
Birkhauser Verlag AG An Introduction to Catalan Numbers
Book SynopsisThis textbook provides an introduction to the Catalan numbers and their remarkable properties, along with their various applications in combinatorics. Intended to be accessible to students new to the subject, the book begins with more elementary topics before progressing to more mathematically sophisticated topics. Each chapter focuses on a specific combinatorial object counted by these numbers, including paths, trees, tilings of a staircase, null sums in Zn+1, interval structures, partitions, permutations, semiorders, and more. Exercises are included at the end of book, along with hints and solutions, to help students obtain a better grasp of the material. The text is ideal for undergraduate students studying combinatorics, but will also appeal to anyone with a mathematical background who has an interest in learning about the Catalan numbers.“Roman does an admirable job of providing an introduction to Catalan numbers of a different nature from the previous ones. He has made an excellent choice of topics in order to convey the flavor of Catalan combinatorics. [Readers] will acquire a good feeling for why so many mathematicians are enthralled by the remarkable ubiquity and elegance of Catalan numbers.” - From the foreword by Richard StanleyTrade Review“The pace of this book is of an introductory nature, the coverage of Catalan numbers is rigorous and will provide the reader with a firm grasp of many of the properties of these numbers. … a scholarly work and one that number theorists will find well worth reading.” (James Van Speybroeck, Computing Reviews, April, 2016)“The book is supplemented by a set of exercises for those who want to go further. The reader is helped by 70 carefully designed figures throughout the book. The 24 enumeration problems are selected carefully to show Catalan numbers from very different viewpoints. Several of these problems likely have their most readable write-up in this book. A must for anyone, who wants to understand the significance of Catalan numbers!” (László Székely, zbMATH 1342.05002, 2016)Table of ContentsIntroduction.- Dyck Words.- The Catalan Numbers.- Catalan Numbers and Paths.- Catalan Numbers and Trees.- Catalan Numbers and Geometric Widgits.- Catalan Numbers and Algebraic Widgits.- Catalan Numbers and Interval Structures.- Catalan Numbers and Partitions.- Catalan Numbers and Permutations.- Catalan Numbers and Semiorders.- Exercises.- Solutions and Hints.- Appendix A: A Brief Introduction to Partially Ordered Sets.- Appendix B: A Brief Introduction to Graphs and Trees.- Index.
£32.39
Birkhauser Verlag AG A Primer for Undergraduate Research: From Groups
Book SynopsisThis highly readable book aims to ease the many challenges of starting undergraduate research. It accomplishes this by presenting a diverse series of self-contained, accessible articles which include specific open problems and prepare the reader to tackle them with ample background material and references. Each article also contains a carefully selected bibliography for further reading.The content spans the breadth of mathematics, including many topics that are not normally addressed by the undergraduate curriculum (such as matroid theory, mathematical biology, and operations research), yet have few enough prerequisites that the interested student can start exploring them under the guidance of a faculty member. Whether trying to start an undergraduate thesis, embarking on a summer REU, or preparing for graduate school, this book is appropriate for a variety of students and the faculty who guide them. Trade Review“This book is a superb resource for students and faculty mentors embarking on undergraduate research in mathematics. Its focus is on topics and applications rarely covered in the traditional undergraduate math curriculum, offering novice researchers a sturdy jumping-off point to a broad array of research problems. … A valuable resource for students and faculty mentors interested in undergraduate research.” (V. K. Chellamuthu, Choice, Vol. 56 (2), October, 2018)Table of ContentsCoxeter Groups and the Davis Complex (T.A. Schroeder).- A Tale of Two Symmetries: Embeddable and Non-Embeddable Group Actions on Surfaces (V. Peterson, A. Wootton).- Tile Invariants for Tackling Tiling Questions (M.P. Hitchman).- Forbidden Minors: Finding the Finite Few (T.W. Mattman).- Introduction to competitive graph coloring (C. Dunn, V. Larsen, J.F. Nordstrom).- Matrioids (E. McNicholas, N.A. Neudauer, C. Starr).- Finite Frame Theory (S. Datta, J. Oldroyd).- Mathematical decision-making with linear and convex programming (J. Kotas).- Computing weight multiplicities (P. E. Harris).- Vaccination strategies for small worlds. (W. Just, H. C. Highlander).- Steady and Stable: Numerical Investigations of Nonlinear Partial Differential Equations (R. C. Harwood).
£58.89
Springer International Publishing AG An Excursion through Elementary Mathematics,
Book SynopsisThis book provides a comprehensive, in-depth overview of elementary mathematics as explored in Mathematical Olympiads around the world. It expands on topics usually encountered in high school and could even be used as preparation for a first-semester undergraduate course. This third and last volume covers Counting, Generating Functions, Graph Theory, Number Theory, Complex Numbers, Polynomials, and much more.As part of a collection, the book differs from other publications in this field by not being a mere selection of questions or a set of tips and tricks that applies to specific problems. It starts from the most basic theoretical principles, without being either too general or too axiomatic. Examples and problems are discussed only if they are helpful as applications of the theory. Propositions are proved in detail and subsequently applied to Olympic problems or to other problems at the Olympic level.The book also explores some of the hardest problems presented at National and International Mathematics Olympiads, as well as many essential theorems related to the content. An extensive Appendix offering hints on or full solutions for all difficult problems rounds out the book.Table of Contents
£58.49
Springer International Publishing AG The Discrete Math Workbook
Book SynopsisThis practically-oriented textbook presents an accessible introduction to discrete mathematics through a substantial collection of classroom-tested exercises. Each chapter opens with concise coverage of the theory underlying the topic, reviewing the basic concepts and establishing the terminology, as well as providing the key formulae and instructions on their use. This is then followed by a detailed account of the most common problems in the area, before the reader is invited to practice solving such problems for themselves through a varied series of questions and assignments.Topics and features: provides an extensive set of exercises and examples of varying levels of complexity, suitable for both laboratory practical training and self-study; offers detailed solutions to many problems, applying commonly-used methods and computational schemes; introduces the fundamentals of mathematical logic, the theory of algorithms, Boolean algebra, graph theory, sets, relations, functions, a
£49.49
Springer Fachmedien Wiesbaden Grundlagen der Mathematischen Optimierung:
Book SynopsisDas Buch stellt wesentliche Ansätze, Ergebnisse und Methoden der linearen und ganzzahligen Optimierung dar. Ziel ist es, eine solide mathematische Grundlage des Gebietes und seiner wichtigsten algorithmischen Ansätze zu entwickeln. Methodisch zentral ist der geometrische Zugang.Table of ContentsEinleitung. - Einstiege: Ungleichungssysteme und diskrete Strukturen. - Einstiege: Algorithmen und Komplexität. - Konvexitätstheorie - Der Simplex-Algorithmus. - LP-Dualität.
£32.99
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Improved Bonferroni Inequalities via Abstract
Book SynopsisThis introduction to the recent theory of abstract tubes describes the framework for establishing improved inclusion-exclusion identities and Bonferroni inequalities, which are provably at least as sharp as their classical counterparts while involving fewer terms. All necessary definitions from graph theory, lattice theory and topology are provided. The role of closure and kernel operators is emphasized, and examples are provided throughout to demonstrate the applicability of this new theory. Applications are given to system and network reliability, reliability covering problems and chromatic graph theory. Topics also covered include Zeilberger's abstract lace expansion, matroid polynomials and Möbius functions.Table of Contents1. Introduction and Overview.- 2. Preliminaries.- 3.Bonferroni Inequalities via Abstract Tubes.- 4. Abstract Tubes via Closure and Kernel Operators.- 5. Recursive Schemes.- 6. Reliability Applications.- 7. Combinatorial Applications and Related Topics.- Bibliography.- Index.
£30.39
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Introduction to Coding Theory
Book SynopsisIt is gratifying that this textbook is still sufficiently popular to warrant a third edition. I have used the opportunity to improve and enlarge the book. When the second edition was prepared, only two pages on algebraic geometry codes were added. These have now been removed and replaced by a relatively long chapter on this subject. Although it is still only an introduction, the chapter requires more mathematical background of the reader than the remainder of this book. One of the very interesting recent developments concerns binary codes defined by using codes over the alphabet 7l.4• There is so much interest in this area that a chapter on the essentials was added. Knowledge of this chapter will allow the reader to study recent literature on 7l. -codes. 4 Furthermore, some material has been added that appeared in my Springer Lec ture Notes 201, but was not included in earlier editions of this book, e. g. Generalized Reed-Solomon Codes and Generalized Reed-Muller Codes. In Chapter 2, a section on "Coding Gain" ( the engineer's justification for using error-correcting codes) was added. For the author, preparing this third edition was a most welcome return to mathematics after seven years of administration. For valuable discussions on the new material, I thank C.P.l.M.Baggen, I. M.Duursma, H.D.L.Hollmann, H. C. A. van Tilborg, and R. M. Wilson. A special word of thanks to R. A. Pellikaan for his assistance with Chapter 10.Table of Contents1 Mathematical Background.- 1.1. Algebra.- 1.2. Krawtchouk Polynomials.- 1.3. Combinatorial Theory.- 1.4. Probability Theory.- 2 Shannon’s Theorem.- 2.1. Introduction.- 2.2. Shannon’s Theorem.- 2.3. On Coding Gain.- 2.4. Comments.- 2.5. Problems.- 3 Linear Codes.- 3.1. Block Codes.- 3.2. Linear Codes.- 3.3. Hamming Codes.- 3.4. Majority Logic Decoding.- 3.5. Weight Enumerators.- 3.6. The Lee Metric.- 3.7. Comments.- 3.8. Problems.- 4 Some Good Codes.- 4.1. Hadamard Codes and Generalizations.- 4.2. The Binary Golay Code.- 4.3. The Ternary Golay Code.- 4.4. Constructing Codes from Other Codes.- 4.5. Reed—Muller Codes.- 4.6. Kerdock Codes.- 4.7. Comments.- 4.8. Problems.- 5 Bounds on Codes.- 5.1. Introduction: The Gilbert Bound.- 5.2. Upper Bounds.- 5.3. The Linear Programming Bound.- 5.4. Comments.- 5.5. Problems.- 6 Cyclic Codes.- 6.1. Definitions.- 6.2. Generator Matrix and Check Polynomial.- 6.3. Zeros of a Cyclic Code.- 6.4. The Idempotent of a Cyclic Code.- 6.5. Other Representations of Cyclic Codes.- 6.6. BCH Codes.- 6.7. Decoding BCH Codes.- 6.8. Reed—Solomon Codes.- 6.9. Quadratic Residue Codes.- 6.10. Binary Cyclic Codes of Length 2n(n odd).- 6.11. Generalized Reed—Muller Codes.- 6.12. Comments.- 6.13. Problems.- 7 Perfect Codes and Uniformly Packed Codes.- 7.1. Lloyd’s Theorem.- 7.2. The Characteristic Polynomial of a Code.- 7.3. Uniformly Packed Codes.- 7.4. Examples of Uniformly Packed Codes.- 7.5. Nonexistence Theorems.- 7.6. Comments.- 7.7. Problems.- 8 Codes over ?4.- 8.1. Quaternary Codes.- 8.2. Binary Codes Derived from Codes over ?4.- 8.3. Galois Rings over ?4.- 8.4. Cyclic Codes over ?4.- 8.5. Problems.- 9 Goppa Codes.- 9.1. Motivation.- 9.2. Goppa Codes.- 9.3. The Minimum Distance of Goppa Codes.- 9.4. Asymptotic Behaviour of Goppa Codes.- 9.5. Decoding Goppa Codes.- 9.6. Generalized BCH Codes.- 9.7. Comments.- 9.8. Problems.- 10 Algebraic Geometry Codes.- 10.1. Introduction.- 10.2. Algebraic Curves.- 10.3. Divisors.- 10.4. Differentials on a Curve.- 10.5. The Riemann—Roch Theorem.- 10.6. Codes from Algebraic Curves.- 10.7. Some Geometric Codes.- 10.8. Improvement of the Gilbert—Varshamov Bound.- 10.9. Comments.- 10.10.Problems.- 11 Asymptotically Good Algebraic Codes.- 11.1. A Simple Nonconstructive Example.- 11.2. Justesen Codes.- 11.3. Comments.- 11.4. Problems.- 12 Arithmetic Codes.- 12.1. AN Codes.- 12.2. The Arithmetic and Modular Weight.- 12.3. Mandelbaum—Barrows Codes.- 12.4. Comments.- 12.5. Problems.- 13 Convolutional Codes.- 13.1. Introduction.- 13.2. Decoding of Convolutional Codes.- 13.3. An Analog of the Gilbert Bound for Some Convolutional Codes.- 13.4. Construction of Convolutional Codes from Cyclic Block Codes.- 13.5. Automorphisms of Convolutional Codes.- 13.6. Comments.- 13.7. Problems.- Hints and Solutions to Problems.- References.
£94.99
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Geometry Revealed: A Jacob's Ladder to Modern
Book SynopsisBoth classical geometry and modern differential geometry have been active subjects of research throughout the 20th century and lie at the heart of many recent advances in mathematics and physics. The underlying motivating concept for the present book is that it offers readers the elements of a modern geometric culture by means of a whole series of visually appealing unsolved (or recently solved) problems that require the creation of concepts and tools of varying abstraction. Starting with such natural, classical objects as lines, planes, circles, spheres, polygons, polyhedra, curves, surfaces, convex sets, etc., crucial ideas and above all abstract concepts needed for attaining the results are elucidated. These are conceptual notions, each built "above" the preceding and permitting an increase in abstraction, represented metaphorically by Jacob's ladder with its rungs: the 'ladder' in the Old Testament, that angels ascended and descended... In all this, the aim of the book is to demonstrate to readers the unceasingly renewed spirit of geometry and that even so-called "elementary" geometry is very much alive and at the very heart of the work of numerous contemporary mathematicians. It is also shown that there are innumerable paths yet to be explored and concepts to be created. The book is visually rich and inviting, so that readers may open it at random places and find much pleasure throughout according their own intuitions and inclinations. Marcel Berger is the author of numerous successful books on geometry, this book once again is addressed to all students and teachers of mathematics with an affinity for geometry.Trade Review“It is a must own book for anyone serious about developing a conceptual understanding of the interconnected web of modern geometry and the ever-growing intertwining of geometry with practically all other branches of mathematics. … It is remarkable for a book to provide such a detailed glimpse of contemporary geometry via well developed discussions of so many questions of current interest. It provides the most extensive exposition of geometric thinking I’ve ever seen in a book at this level.” (William H. Barker, MAA Reviews, August, 2017)“Geometry Revealed is to give the reader a feel for the conceptual frameworks of modern geometry, attempting to reach as far as possible with a minimum of assumed knowledge and formal scaffolding. … Geometry Revealed being useful for research mathematicians as a still reasonably up-to-date survey. … Geometry Revealed offered an ascent into the wonders of a new world.” (Danny Yee, Danny Yee’s Book Reviews, dannyreviews.com, July, 2015)“By considering a hierarchy of ‘natural’ geometrical objects … it sets out to investigate significant geometrical problems which are either unsolved or were solved only recently. … it is undoubtedly a major tour de force, and if you really want to gain an idea of where geometry is going in the 21st century, you will find plenty of exquisite material here.” (Gerry Leversha, The Mathematical Gazette, Vol. 96 (356), July, 2012)“The book contains twelve chapters, each of them is a collection of such problems about geometric objects with more and more complexity … . The chapters are independent from each other, any of them can serve as a course. Researchers in geometry can use it as a source for further research. … the book is accessible to a wide audience of people who are interested in geometry.” (János Kincses, Acta Scientiarum Mathematicarum (Szeged), Vol. 78 (1-2), 2012)“‘Geometry Revealed’ is a massive text of 831 pages which is organized in twelve chapters and which additionally provides indices for names, subjects and symbols … throughout the author quite carefully lays out the historical perspective. … a typical chapter starts with an observation or a problem in elementary geometry. Large parts of the text are very accessible, and a reader who likes (mathematical) physics will often get something extra.” (Michael Joswig, Zentralblatt MATH, Vol. 1232, 2012)“The author provides the reader with an enormous amount of detailed information and thus yields deep insight into the various topics. … All in all an overwhelming book which is a must … for everyone having sufficient mathematical knowledge.” (G. Kowol, Monatshefte für Mathematik, Vol. 164 (2), October, 2011)“The book is a very readable account of several branches of geometry, classical and modern, elementary and advanced. … Every chapter is extremely interesting and alive. … The book is rich in ideas, written in an informal style, with no formulae and no unnecessary technical details. … Every part of this book is interesting and should be accessible to a wide audience of mathematicians. … Every mathematician will experience great pleasure in reading this book.” (Athanase Papadopoulos, Mathematical Reviews, Issue 2011 m)Table of ContentsPoints and lines in the plane.- Circles and spheres.- The sphere by itself: can we distribute points on it evenly?.- Conics and quadrics.- Plane curves.- Smooth surfaces.- Convexity and convex sets.- Polygons, polyhedra, polytopes.- Lattices, packings and tilings in the plane.- Lattices and packings in higher dimensions.- Geometry and dynamics I: billiards.- Geometry and dynamics II: geodesic flow on a surface.
£51.29
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Matrices and Matroids for Systems Analysis
Book SynopsisA matroid is an abstract mathematical structure that captures combinatorial properties of matrices. This book offers a unique introduction to matroid theory, emphasizing motivations from matrix theory and applications to systems analysis. This book serves also as a comprehensive presentation of the theory and application of mixed matrices, developed primarily by the present author in the 1990's. A mixed matrix is a convenient mathematical tool for systems analysis, compatible with the physical observation that "fixed constants" and "system parameters" are to be distinguished in the description of engineering systems. This book will be extremely useful to graduate students and researchers in engineering, mathematics and computer science. From the reviews: "…The book has been prepared very carefully, contains a lot of interesting results and is highly recommended for graduate and postgraduate students." András Recski, Mathematical Reviews Clippings 2000m:93006Table of ContentsPreface I. Introduction to Structural Approach --- Overview of the Book 1 Structural Approach to Index of DAE 1.1 Index of differential-algebraic equations 1.2 Graph-theoretic structural approach 1.3 An embarrassing phenomenon 2 What Is Combinatorial Structure? 2.1 Two kinds of numbers 2.2 Descriptor form rather than standard form 2.3 Dimensional analysis 3 Mathematics on Mixed Polynomial Matrices 3.1 Formal definitions 3.2 Resolution of the index problem 3.3 Block-triangular decomposition II. Matrix, Graph and Matroid 4 Matrix 4.1 Polynomial and algebraic independence 4.2 Determinant 4.3 Rank, term-rank and generic-rank 4.4 Block-triangular forms 5 Graph 5.1 Directed graph and bipartite graph 5.2 Jordan-Holder-type theorem for submodular functions 5.3 Dulmage-Mendelsohn decomposition 5.4 Maximum flow and Menger-type linking 5.5 Minimum cost flow and weighted matching 6 Matroid 6.1 From matrix to matroid 6.2 Basic concepts 6.3 Examples 6.4 Basis exchange properties 6.5 Independent matching problem 6.6 Union 6.7 Bimatroid (linking system) III. Physical Observations for Mixed Matrix Formulation 7 Mixed Matrix for Modeling Two Kinds of Numbers 7.1 Two kinds of numbers 7.2 Mixed matrix and mixed polynomial matrix 8 Algebraic Implications of Dimensional Consistency 8.1 Introductory comments 8.2 Dimensioned matrix 8.3 Total unimodularity of dimensioned matrices 9 Physical Matrix 9.1 Physical matrix 9.2 Physical matrices in a dynamical system IV. Theory and Application of Mixed Matrices 10 Mixed Matrix and Layered Mixed Matrix 11 Rank of Mixed Matrices 11.1 Rank identities for LM-matrices 11.2 Rank identities for mixed matrices 11.3 Reduction to independent matching problems 11.4 Algorithms for the rank 11.4.1 Algorithm for LM-matrices 11.4.2 Algorithm for mixed matrices 12 Structural Solvability of Systems of Equations 12.1 Formulation of structural solvability 12.2 Graphical conditions for structural solvability 12.3 Matroidal conditions for structural solvability 13. Combinatorial Canonical Form of LM-matrices 13.1 LM-equivalence 13.2 Theorem of CCF 13.3 Construction of CCF 13.4 Algorithm for CCF 13.5 Decomposition of systems of equations by CCF 13.6 Application of CCF 13.7 CCF over rings 14 Irreducibility of LM-matrices 14.1 Theorems on LM-irreducibility 14.2 Proof of the irreducibility of determinant 15 Decomposition of Mixed Matrices 15.1 LU-decomposition of invertible mixed matrices 15.2 Block-triangularization of general mixed matrices 16 Related Decompositions 16.1 Partition as a matroid union 16.2 Multilayered matrix 16.3 Electrical network with admittance expression 17 Partitioned Matrix 17.1 Definitions 17.2 Existence of proper block-triangularization 17.3 Partial order among blocks 17.4 Generic partitioned matrix 18 Principal Structures of LM-matrices 18.1 Motivations 18.2 Principal structure of submodular systems 18.3 Principal structure of generic matrices 18.4 Vertical principal structure of LM-matrices 18.5 Horizontal principal structure of LM-matrices V. Polynomial Matrix and Valuated Matroid 19 Polynomial/Rational Matrix 19.1 Polynomial matrix and Smith form 19.2 Rational matrix and Smith-McMillan form at infinity 19.3 Matrix pencil and Kronecker form 20 Valuated Matroid 20.1 Introduction 20.2 Examples 20.3 Basic operations 20.4 Greedy algorithms 20.5 Valuated bimatroid 20.6 Induction through bipartite graphs 20.7 Characterizations 20.8 Further exchange properties 20.9 Valuated independent assignment problem 20.10 Optimality criteria 20.10.1 Potential criterion 20.10.2 Negative-cycle criterion 20.10.3 Proof of the optimality criteria 20.10.4 Extension to VIAP(k) 20.11 Application to triple matrix product 20.12 Cycle-canceling algorithms 20.12.1 Algorithms 20.12.2 Validity of the minimum-ratio cycle algorithm 20.13 Augmenting algorithms 20.13.1 Algorithms 20.13.2 Validity of the augmenting algorithm VI. Theory and Application of Mixed Polynomial Matrices 21 Descriptions of Dynamical Systems 21.1 Mixed polynomial mat
£104.49
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Algebraic Complexity Theory
Book SynopsisThe algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the intensive search for a precise and sufficiently general formalization of the notions of computability and algorithm. In the 1930s, a number of quite different concepts for this purpose were pro posed, such as Turing machines, WHILE-programs, recursive functions, Markov algorithms, and Thue systems. All these concepts turned out to be equivalent, a fact summarized in Church's thesis, which says that the resulting definitions form an adequate formalization of the intuitive notion of computability. This had and continues to have an enormous effect. First of all, with these notions it has been possible to prove that various problems are algorithmically unsolvable. Among of group these undecidable problems are the halting problem, the word problem theory, the Post correspondence problem, and Hilbert's tenth problem. Secondly, concepts like Turing machines and WHILE-programs had a strong influence on the development of the first computers and programming languages. In the era of digital computers, the question of finding efficient solutions to algorithmically solvable problems has become increasingly important. In addition, the fact that some problems can be solved very efficiently, while others seem to defy all attempts to find an efficient solution, has called for a deeper under standing of the intrinsic computational difficulty of problems.Trade ReviewP. Bürgisser, M. Clausen, M.A. Shokrollahi, and T. Lickteig Algebraic Complexity Theory "The book contains interesting exercises and useful bibliographical notes. In short, this is a nice book."—MATHEMATICAL REVIEWS From the reviews: "This book is certainly the most complete reference on algebraic complexity theory that is available hitherto. … superb bibliographical and historical notes are given at the end of each chapter. … this book would most certainly make a great textbook for a graduate course on algebraic complexity theory. … In conclusion, any researchers already working in the area should own a copy of this book. … beginners at the graduate level who have been exposed to undergraduate pure mathematics would find this book accessible." (Anthony Widjaja, SIGACT News, Vol. 37 (2), 2006)Table of Contents1. Introduction.- I. Fundamental Algorithms.- 2. Efficient Polynomial Arithmetic.- 3. Efficient Algorithms with Branching.- II. Elementary Lower Bounds.- 4. Models of Computation.- 5. Preconditioning and Transcendence Degree.- 6. The Substitution Method.- 7. Differential Methods.- III. High Degree.- 8. The Degree Bound.- 9. Specific Polynomials which Are Hard to Compute.- 10. Branching and Degree.- 11. Branching and Connectivity.- 12. Additive Complexity.- IV. Low Degree.- 13. Linear Complexity.- 14. Multiplicative and Bilinear Complexity.- 15. Asymptotic Complexity of Matrix Multiplication.- 16. Problems Related to Matrix Multiplication.- 17. Lower Bounds for the Complexity of Algebras.- 18. Rank over Finite Fields and Codes.- 19. Rank of 2-Slice and 3-Slice Tensors.- 20. Typical Tensorial Rank.- V. Complete Problems.- 21. P Versus NP: A Nonuniform Algebraic Analogue.- List of Notation.
£104.49
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Algebra und Diskrete Mathematik 1: Grundbegriffe der Mathematik, Algebraische Strukturen 1, Lineare Algebra und Analytische Geometrie, Numerische Algebra und Kombinatorik
Book SynopsisAlgebra und Diskrete Mathematik gehören zu den wichtigsten mathematischen Grundlagen der Informatik. In diese mathematischen Teilgebiete führt Band 1 des zweibändigen Lehrbuchs umfassend ein. Dabei ermöglichen klar herausgearbeitete Lösungsalgorithmen, viele Beispiele und ausführliche Beweise einen raschen Zugang zum Thema. Die umfangreiche Sammlung von Übungsaufgaben hilft bei der Erarbeitung des Stoffs und zeigt darüber hinaus, welche unterschiedlichen Anwendungsmöglichkeiten es gibt. Die 3. Auflage wurde korrigiert und erweitert.Table of ContentsTeil I Grundbegriffe der Mathematik und Algebraische Strukturen.- Teil II Lineare Algebra und analytische Geometrie.- Teil III Numerische Algebra und Kombinatorik.- Teil IV Übungsaufgaben.
£36.09
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Algebraic Topology of Finite Topological Spaces and Applications
Book SynopsisThis volume deals with the theory of finite topological spaces and its relationship with the homotopy and simple homotopy theory of polyhedra. The interaction between their intrinsic combinatorial and topological structures makes finite spaces a useful tool for studying problems in Topology, Algebra and Geometry from a new perspective. In particular, the methods developed in this manuscript are used to study Quillen's conjecture on the poset of p-subgroups of a finite group and the Andrews-Curtis conjecture on the 3-deformability of contractible two-dimensional complexes. This self-contained work constitutes the first detailed exposition on the algebraic topology of finite spaces. It is intended for topologists and combinatorialists, but it is also recommended for advanced undergraduate students and graduate students with a modest knowledge of Algebraic Topology.Trade ReviewFrom the reviews:“This book deals with the algebraic topology of finite topological spaces and its applications, and includes well-known results on finite spaces and original results developed by the author. The book is self-contained and well written. It is understandable and enjoyable to read. It contains a lot of examples and figures which help the readers to understand the theory.” (Fumihiro Ushitaki, Mathematical Reviews, March, 2014)“This book illustrates convincingly the idea that the study of finite non-Hausdorff spaces from a homotopical point of view is useful in many areas and can even be used to study well-known problems in classical algebraic topology. … This book is a revised version of the PhD Thesis of the author. … All the concepts introduced with the chapters are usefully illustrated by examples and the recollection of all these results gives a very nice introduction to a domain of growing interest.” (Etienne Fieux, Zentralblatt MATH, Vol. 1235, 2012)Table of Contents1 Preliminaries.- 2 Basic topological properties of finite spaces.- 3 Minimal finite models.- 4 Simple homotopy types and finite spaces.- 5 Strong homotopy types.- 6 Methods of reduction.- 7 h-regular complexes and quotients.- 8 Group actions and a conjecture of Quillen.- 9 Reduced lattices.- 10 Fixed points and the Lefschetz number.- 11 The Andrews-Curtis conjecture.
£32.99
Springer Fachmedien Wiesbaden Mathematik für Informatiker: Band 1: Diskrete
Book SynopsisIn diesem Lehrbuch werden die mathematischen Grundlagen exakt und dennoch anschaulich und gut nachvollziehbar vermittelt. Sie werden durchgehend anhand zahlreicher Musterbeispiele illustriert, durch Anwendungen in der Informatik motiviert und durch historische Hintergründe oder Ausblicke in angrenzende Themengebiete aufgelockert. Am Ende jedes Kapitels befinden sich Kontrollfragen, die das Verständnis testen und typische Fehler bzw. Missverständnisse ausräumen. Zusätzlich helfen zahlreiche Aufwärmübungen (mit vollständigem Lösungsweg) und weiterführende Übungsaufgaben das Erlernte zu festigen und praxisrelevant umzusetzen. Dieses Lehrbuch ist daher auch sehr gut zum Selbststudium geeignet. Ergänzend wird in eigenen Abschnitten das Computeralgebrasystem Mathematica vorgestellt und eingesetzt, wodurch der Lehrstoff visualisiert und somit das Verständnis erleichtert werden kann.Table of ContentsLogik und Mengen.- Zahlenmengen und Zahlensysteme.- Elementare Begriffe der Zahlentheorie.- Relationen und Funktionen.- Folgen und Reihen.- Kombinatorik.- Rekursionen.- Vektorräume.- Lineare Abbildungen.- Lineare Gleichungen und Ungleichungen.- Skalarprodukt und Orthogonalität.- Eigenwerte und Eigenvektoren.- Grundlagen der Graphentheorie.- Bäume und kürzeste Wege.- Flüsse in Netzwerken und Matchings.- Einführung in Mathematica.
£39.99
Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Geometric Algorithms and Combinatorial Optimization
Book SynopsisSince the publication of the first edition of our book, geometric algorithms and combinatorial optimization have kept growing at the same fast pace as before. Nevertheless, we do not feel that the ongoing research has made this book outdated. Rather, it seems that many of the new results build on the models, algorithms, and theorems presented here. For instance, the celebrated Dyer-Frieze-Kannan algorithm for approximating the volume of a convex body is based on the oracle model of convex bodies and uses the ellipsoid method as a preprocessing technique. The polynomial time equivalence of optimization, separation, and membership has become a commonly employed tool in the study of the complexity of combinatorial optimization problems and in the newly developing field of computational convexity. Implementations of the basis reduction algorithm can be found in various computer algebra software systems. On the other hand, several of the open problems discussed in the first edition are still unsolved. For example, there are still no combinatorial polynomial time algorithms known for minimizing a submodular function or finding a maximum clique in a perfect graph. Moreover, despite the success of the interior point methods for the solution of explicitly given linear programs there is still no method known that solves implicitly given linear programs, such as those described in this book, and that is both practically and theoretically efficient. In particular, it is not known how to adapt interior point methods to such linear programs.Table of Contents0. Mathematical Preliminaries.- 0.1 Linear Algebra and Linear Programming.- Basic Notation.- Hulls, Independence, Dimension.- Eigenvalues, Positive Definite Matrices.- Vector Norms, Balls.- Matrix Norms.- Some Inequalities.- Polyhedra, Inequality Systems.- Linear (Diophantine) Equations and Inequalities.- Linear Programming and Duality.- 0.2 Graph Theory.- Graphs.- Digraphs.- Walks, Paths, Circuits, Trees.- 1. Complexity, Oracles, and Numerical Computation.- 1.1 Complexity Theory: P and NP.- Problems.- Algorithms and Turing Machines.- Encoding.- Time and Space Complexity.- Decision Problems: The Classes P and NP.- 1.2 Oracles.- The Running Time of Oracle Algorithms.- Transformation and Reduction.- NP-Completeness and Related Notion.- 1.3 Approximation and Computation of Numbers.- Encoding Length of Numbers.- Polynomial and Strongly Polynomial Computations.- Polynomial Time Approximation of Real Numbers.- 1.4 Pivoting and Related Procedures.- Gaussian Elimination.- Gram-Schmidt Orthogonalization.- The Simplex Method.- Computation of the Hermite Normal Form.- 2. Algorithmic Aspects of Convex Sets: Formulation of the Problems.- 2.1 Basic Algorithmic Problems for Convex Sets.- 2.2 Nondeterministic Decision Problems for Convex Sets.- 3. The Ellipsoid Method.- 3.1 Geometric Background and an Informal Description.- Properties of Ellipsoids.- Description of the Basic Ellipsoid Method.- Proofs of Some Lemmas.- Implementation Problems and Polynomiality.- Some Examples.- 3.2 The Central-Cut Ellipsoid Method.- 3.3 The Shallow-Cut Ellipsoid Method.- 4. Algorithms for Convex Bodies.- 4.1 Summary of Results.- 4.2 Optimization from Separation.- 4.3 Optimization from Membership.- 4.4 Equivalence of the Basic Problems.- 4.5 Some Negative Results.- 4.6 Further Algorithmic Problems for Convex Bodies.- 4.7 Operations on Convex Bodies.- The Sum.- The Convex Hull of the Union.- The Intersection.- Polars, Blockers, Antiblockers.- 5. Diophantine Approximation and Basis Reduction.- 5.1 Continued Fractions.- 5.2 Simultaneous Diophantine Approximation: Formulation of the Problems.- 5.3 Basis Reduction in Lattices.- 5.4 More on Lattice Algorithms.- 6. Rational Polyhedra.- 6.1 Optimization over Polyhedra: A Preview.- 6.2 Complexity of Rational Polyhedra.- 6.3 Weak and Strong Problems.- 6.4 Equivalence of Strong Optimization and Separation.- 6.5 Further Problems for Polyhedra.- 6.6 Strongly Polynomial Algorithms.- 6.7 Integer Programming in Bounded Dimension.- 7. Combinatorial Optimization: Some Basic Examples.- 7.1 Flows and Cuts.- 7.2 Arborescences.- 7.3 Matching.- 7.4 Edge Coloring.- 7.5 Matroids.- 7.6 Subset Sums.- 7.7 Concluding Remarks.- 8. Combinatorial Optimization: A Tour d’Horizon.- 8.1 Blocking Hypergraphs and Polyhedra.- 8.2 Problems on Bipartite Graphs.- 8.3 Flows, Paths, Chains, and Cuts.- 8.4 Trees, Branchings, and Rooted and Directed Cuts.- Arborescences and Rooted Cuts.- Trees and Cuts in Undirected Graphs.- Dicuts and Dijoins.- 8.5 Matchings, Odd Cuts, and Generalizations.- Matching.- b-Matching.- T-Joins and T-Cuts.- Chinese Postmen and Traveling Salesmen.- 8.6 Multicommodity Flows.- 9. Stable Sets in Graphs.- 9.1 Odd Circuit Constraints and t-Perfect Graphs.- 9.2 Clique Constraints and Perfect Graphs.- Antiblockers of Hypergraphs.- 9.3 Orthonormal Representations.- 9.4 Coloring Perfect Graphs.- 9.5 More Algorithmic Results on Stable Sets.- 10. Submodular Functions.- 10.1 Submodular Functions and Polymatroids.- 10.2 Algorithms for Polymatroids and Submodular Functions.- Packing Bases of a Matroid.- 10.3 Submodular Functions on Lattice, Intersecting, and Crossing Families.- 10.4 Odd Submodular Function Minimization and Extensions.- References.- Notation Index.- Author Index.
£104.49
Springer Fachmedien Wiesbaden Diskrete Mathematik mit Grundlagen: Lehrbuch für
Book SynopsisDieses Lehrbuch wendet sich an Leser ohne Studienvorkenntnisse, gibt eine elementare Einführung in die Diskrete Mathematik und die Welt des mathematischen Denkens und führt den Leser auf ein solides Hochschulniveau. Im Einzelnen werden elementare Logik, Mengenlehre, Beweiskonzepte und die mathematische Terminologie dafür ausführlich erklärt und durch Anwendungsbeispiele motiviert. Darauf aufbauend werden die wichtigsten Disziplinen der Diskreten Mathematik behandelt in einem Umfang, der für jedes MINT-Studium außer der Mathematik selbst ausreicht. Zahlreiche Übungsaufgaben runden das Angebot ab, die Lösungen dazu werden online zur Verfügung gestellt. Das Buch ist zum Selbststudium, als Vorlesungsbegleitung und zum Nachschlagen geeignet. Die zweite Auflage wurde vollständig überarbeitet. Das Kapitel zur Logik wurde erheblich ausgeweitet, unter anderem durch eine allgemeinverständliche Anleitung mit vielen Beispielen, wie Alltagssprache in logische Sprache übersetzt wird.Table of ContentsLogik.- Mengenlehre.- Beweisverfahren.- Zahlentheorie.- Algebraische Strukturen.- Kombinatorik.- Graphentheorie.
£27.99
