Search

A complete introduction to the many mathematical tools used to solve practical problems in coding. Mathematicians have been fascinated with the theory of error-correcting codes since the publication of Shannon's classic papers fifty years ago. With the proliferation of communications systems, computers, and digital audio devices that employ error-correcting codes, the theory has taken on practical importance in the solution of coding problems. This solution process requires the use of a wide variety of mathematical tools and an understanding of how to find mathematical techniques to solve applied problems. Introduction to the Theory of Error-Correcting Codes, Third Edition demonstrates this process and prepares students to cope with coding problems. Like its predecessor, which was awarded a three-star rating by the Mathematical Association of America, this updated and expanded edition gives readers a firm grasp of the timeless fundamentals of coding as well as the latest theoretical advances. This new edition features: • A greater emphasis on nonlinear binary codes • An exciting new discussion on the relationship between codes and combinatorial games • Updated and expanded sections on the Vashamov-Gilbert bound, van Lint-Wilson bound, BCH codes, and Reed-Muller codes • Expanded and updated problem sets. Introduction to the Theory of Error-Correcting Codes, Third Edition is the ideal textbook for senior-undergraduate and first-year graduate courses on error-correcting codes in mathematics, computer science, and electrical engineering.

A pioneering look at the fundamental role of logic in optimization and constraint satisfaction While recent efforts to combine optimization and constraint satisfaction have received considerable attention, little has been said about using logic in optimization as the key to unifying the two fields. Logic-Based Methods for Optimization develops for the first time a comprehensive conceptual framework for integrating optimization and constraint satisfaction, then goes a step further and shows how extending logical inference to optimization allows for more powerful as well as flexible modeling and solution techniques. Designed to be easily accessible to industry professionals and academics in both operations research and artificial intelligence, the book provides a wealth of examples as well as elegant techniques and modeling frameworks ready for implementation. Timely, original, and thought-provoking, Logic-Based Methods for Optimization: • Demonstrates the advantages of combining the techniques in problem solving • Offers tutorials in constraint satisfaction/constraint programming and logical inference • Clearly explains such concepts as relaxation, cutting planes, nonserial dynamic programming, and Bender's decomposition • Reviews the necessary technologies for software developers seeking to combine the two techniques • Features extensive references to important computational studies • And much more

The comprehensive introduction to the art and science of locating facilities to make your organization more efficient, effective, and profitable. For the professional siting facilities, the task of translating organizational goals and objectives into concrete facilities requires a working familiarity with the theoretical and practical fundamentals of facility location planning and modeling. The first hands-on guide to using and developing facility location models, Network and Discrete Location offers a practiceoriented introduction to model-building methods and solution algorithms, complete with software to solve classical problems of realistic size and end-of-chapter exercises to enhance the reader's understanding. The text introduces the reader to the key classical location problems (covering, center, median, and fixed charge) which form the nucleus of facility location modeling. It also discusses real-life extensions of the basic models used in locating: production and distribution facilities, interacting services and facilities, and undesirable facilities. The book outlines a host of methodological tools for solving location models and provides insights into when each approach is useful and what information it provides. Designed to give readers a working familiarity with the basic facility location model types as well as an intuitive knowledge of the uses and limits of modeling techniques, Network and Discrete Location brings students and professionals alike swiftly from basic theory to technical fluency.

An accessible and multidisciplinaryintroduction to cellular automata As the applicability of cellular automata broadens and technology advances, there is a need for a concise, yet thorough, resource that lays the foundation of key cellularautomata rules and applications. In recent years, Stephen Wolfram's A New Kind of Science has brought the modeling power that lies in cellular automata to the attentionof the scientific world, and now, Cellular Automata: A Discrete View of the World presents all the depth, analysis, and applicability of the classic Wolfram text in a straightforward, introductory manner. This book offers an introduction to cellular automata as a constructive method for modeling complex systems where patterns of self-organization arising from simple rules are revealed in phenomena that exist across a wide array of subject areas, including mathematics, physics, economics, and the social sciences. The book begins with a preliminary introduction to cellular automata, including a brief history of the topic along with coverage of sub-topics such as randomness, dimension, information, entropy, and fractals. The author then provides a complete discussion of dynamical systems and chaos due to their close connection with cellular automata and includes chapters that focus exclusively on one- and two-dimensional cellular automata. The next and most fascinating area of discussion is the application of these types of cellular automata in order to understand the complex behavior that occurs in natural phenomena. Finally, the continually evolving topic of complexity is discussed with a focus on how to properly define, identify, and marvel at its manifestations in various environments. The author's focus on the most important principles of cellular automata, combined with his ability to present complex material in an easy-to-follow style, makes this book a very approachable and inclusive source for understanding the concepts and applications of cellular automata. The highly visual nature of the subject is accented with over 200 illustrations, including an eight-page color insert, which provide vivid representations of the cellular automata under discussion. Readers also have the opportunity to follow and understand the models depicted throughout the text and create their own cellular automata using Java applets and simple computer code, which are available via the book's FTP site. This book serves as a valuable resource for undergraduate and graduate students in the physical, biological, and social sciences and may also be of interest to any reader with a scientific or basic mathematical background.

Praise for the Second Edition:'Serious researchers in combinatorics or algorithm design will wish to read the book in its entirety...the book may also be enjoyed on a lighter level since the different chapters are largely independent and so it is possible to pick out gems in one's own area...'—Formal Aspects of Computing This Third Edition of The Probabilistic Method reflects the most recent developments in the field while maintaining the standard of excellence that established this book as the leading reference on probabilistic methods in combinatorics. Maintaining its clear writing style, illustrative examples, and practical exercises, this new edition emphasizes methodology, enabling readers to use probabilistic techniques for solving problems in such fields as theoretical computer science, mathematics, and statistical physics. The book begins with a description of tools applied in probabilistic arguments, including basic techniques that use expectation and variance as well as the more recent applications of martingales and correlation inequalities. Next, the authors examine where probabilistic techniques have been applied successfully, exploring such topics as discrepancy and random graphs, circuit complexity, computational geometry, and derandomization of randomized algorithms. Sections labeled'The Probabilistic Lens'offer additional insights into the application of the probabilistic approach, and the appendix has been updated to include methodologies for finding lower bounds for Large Deviations. The Third Edition also features: A new chapter on graph property testing, which is a current topic that incorporates combinatorial, probabilistic, and algorithmic techniques An elementary approach using probabilistic techniques to the powerful Szemerédi Regularity Lemma and its applications New sections devoted to percolation and liar games A new chapter that provides a modern treatment of the Erdös-Rényi phase transition in the Random Graph Process Written by two leading authorities in the field, The Probabilistic Method, Third Edition is an ideal reference for researchers in combinatorics and algorithm design who would like to better understand the use of probabilistic methods. The book's numerous exercises and examples also make it an excellent textbook for graduate-level courses in mathematics and computer science.

Praise from the Second Edition'...an excellent introduction to optimization theory...'(Journal of Mathematical Psychology, 2002)'A textbook for a one-semester course on optimization theory and methods at the senior undergraduate or beginning graduate level.'(SciTech Book News, Vol. 26, No. 2, June 2002) Explore the latest applications of optimization theory and methods Optimization is central to any problem involving decision making in many disciplines, such as engineering, mathematics, statistics, economics, and computer science. Now, more than ever, it is increasingly vital to have a firm grasp of the topic due to the rapid progress in computer technology, including the development and availability of user-friendly software, high-speed and parallel processors, and networks. Fully updated to reflect modern developments in the field, An Introduction to Optimization, Third Edition fills the need for an accessible, yet rigorous, introduction to optimization theory and methods. The book begins with a review of basic definitions and notations and also provides the related fundamental background of linear algebra, geometry, and calculus. With this foundation, the authors explore the essential topics of unconstrained optimization problems, linear programming problems, and nonlinear constrained optimization. An optimization perspective on global search methods is featured and includes discussions on genetic algorithms, particle swarm optimization, and the simulated annealing algorithm. In addition, the book includes an elementary introduction to artificial neural networks, convex optimization, and multi-objective optimization, all of which are of tremendous interest to students, researchers, and practitioners. Additional features of the Third Edition include: New discussions of semidefinite programming and Lagrangian algorithms A new chapter on global search methods A new chapter on multipleobjective optimization New and modified examples and exercises in each chapter as well as an updated bibliography containing new references An updated Instructor's Manual with fully worked-out solutions to the exercises Numerous diagrams and figures found throughout the text complement the written presentation of key concepts, and each chapter is followed by MATLAB exercises and drill problems that reinforce the discussed theory and algorithms. With innovative coverage and a straightforward approach, An Introduction to Optimization, Third Edition is an excellent book for courses in optimization theory and methods at the upper-undergraduate and graduate levels. It also serves as a useful, self-contained reference for researchers and professionals in a wide array of fields.

An'applications first'approach to discrete wavelet transformations Discrete Wavelet Transformations provides readers with a broad elementary introduction to discrete wavelet transformations and their applications. With extensive graphical displays, this self-contained book integrates concepts from calculus and linear algebra into the construction of wavelet transformations and their various applications, including data compression, edge detection in images, and signal and image denoising. The book begins with a cursory look at wavelet transformation development and illustrates its allure in digital signal and image applications. Next, a chapter on digital image basics, quantitative and qualitative measures, and Huffman coding equips readers with the tools necessary to develop a comprehensive understanding of the applications. Subsequent chapters discuss the Fourier series, convolution, and filtering, as well as the Haar wavelet transform to introduce image compression and image edge detection. The development of Daubechies filtersis presented in addition to coverage of wavelet shrinkage in the area of image and signal denoising. The book concludes with the construction of biorthogonal filters and also describes their incorporation in the JPEG2000 image compression standard. The author's'applications first'approach promotes a hands-on treatment of wavelet transforma-tion construction, and over 400 exercises are presented in a multi-part format that guide readers through the solution to each problem. Over sixty computer labs and software development projects provide opportunities for readers to write modules and experiment with the ideas discussed throughout the text. The author's software package, DiscreteWavelets, is used to perform various imaging and audio tasks, compute wavelet transformations and inverses, and visualize the output of the computations. Supplementary material is also available via the book's related Web site, which includes an audio and video repository, final project modules, and softwarefor reproducing examples from the book. All software, including the DiscreteWavelets package, is available for use with Mathematica®, MATLAB®, and Maple. Discrete Wavelet Transformations strongly reinforces the use of mathematics in digital data applications, sharpens programming skills, and provides a foundation for further study of more advanced topics, such as real analysis. This book is ideal for courses on discrete wavelet transforms and their applications at the undergraduate level and also serves as an excellent reference for mathematicians, engineers, and scientists who wish to learn about discrete wavelet transforms at an elementary level.

A modern, up-to-date introduction to optimization theory and methods This authoritative book serves as an introductory text to optimization at the senior undergraduate and beginning graduate levels. With consistently accessible and elementary treatment of all topics, An Introduction to Optimization, Second Edition helps students build a solid working knowledge of the field, including unconstrained optimization, linear programming, and constrained optimization. Supplemented with more than one hundred tables and illustrations, an extensive bibliography, and numerous worked examples to illustrate both theory and algorithms, this book also provides: • A review of the required mathematical background material • A mathematical discussion at a level accessible to MBA and business students • A treatment of both linear and nonlinear programming • An introduction to recent developments, including neural networks, genetic algorithms, and interior-point methods • A chapter on the use of descent algorithms for the training of feedforward neural networks • Exercise problems after every chapter, many new to this edition • MATLAB(r) exercises and examples • Accompanying Instructor's Solutions Manual available on request An Introduction to Optimization, Second Edition helps students prepare for the advanced topics and technological developments that lie ahead. It is also a useful book for researchers and professionals in mathematics, electrical engineering, economics, statistics, and business. An Instructor's Manual presenting detailed solutions to all the problems in the book is available from the Wiley editorial department.

A lively invitation to the flavor, elegance, and power of graph theory This mathematically rigorous introduction is tempered and enlivened by numerous illustrations, revealing examples, seductive applications, and historical references. An award-winning teacher, Russ Merris has crafted a book designed to attract and engage through its spirited exposition, a rich assortment of well-chosen exercises, and a selection of topics that emphasizes the kinds of things that can be manipulated, counted, and pictured. Intended neither to be a comprehensive overview nor an encyclopedic reference, this focused treatment goes deeply enough into a sufficiently wide variety of topics to illustrate the flavor, elegance, and power of graph theory. Another unique feature of the book is its user-friendly modular format. Following a basic foundation in Chapters 1-3, the remainder of the book is organized into four strands that can be explored independently of each other. These strands center, respectively, around matching theory; planar graphs and hamiltonian cycles; topics involving chordal graphs and oriented graphs that naturally emerge from recent developments in the theory of graphic sequences; and an edge coloring strand that embraces both Ramsey theory and a self-contained introduction to Pólya's enumeration of nonisomorphic graphs. In the edge coloring strand, the reader is presumed to be familiar with the disjoint cycle factorization of a permutation. Otherwise, all prerequisites for the book can be found in a standard sophomore course in linear algebra. The independence of strands also makes Graph Theory an excellent resource for mathematicians who require access to specific topics without wanting to read an entire book on the subject.

A timely book on a topic that has witnessed a surge of interest over the last decade, owing in part to several novel applications, most notably in data compression and computational molecular biology. It describes methods employed in average case analysis of algorithms, combining both analytical and probabilistic tools in a single volume. • Tools are illustrated through problems on words with applications to molecular biology, data compression, security, and pattern matching. • Includes chapters on algorithms and data structures on words, probabilistic and analytical models, inclusion-exclusion principles, first and second moment methods, subadditive ergodic theorem and large deviations, elements of information theory, generating functions, complex asymptotic methods, Mellin transform and its applications, and analytic poissonization and depoissonization. • Written by an established researcher with a strong international reputation in the field.

The leading reference on probabilistic methods in combinatorics-now expanded and updated When it was first published in 1991, The Probabilistic Method became instantly the standard reference on one of the most powerful and widely used tools in combinatorics. Still without competition nearly a decade later, this new edition brings you up to speed on recent developments, while adding useful exercises and over 30% new material. It continues to emphasize the basic elements of the methodology, discussing in a remarkably clear and informal style both algorithmic and classical methods as well as modern applications. The Probabilistic Method, Second Edition begins with basic techniques that use expectation and variance, as well as the more recent martingales and correlation inequalities, then explores areas where probabilistic techniques proved successful, including discrepancy and random graphs as well as cutting-edge topics in theoretical computer science. A series of proofs, or'probabilistic lenses,'are interspersed throughout the book, offering added insight into the application of the probabilistic approach. New and revised coverage includes: • Several improved as well as new results • A continuous approach to discrete probabilistic problems • Talagrand's Inequality and other novel concentration results • A discussion of the connection between discrepancy and VC-dimension • Several combinatorial applications of the entropy function and its properties • A new section on the life and work of Paul Erdös-the developer of the probabilistic method

A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume: • Provides complete proofs of recent breakthroughs in complexity theory • Presents results in well-defined form with complete proofs and numerous exercises • Includes scores of graphs and figures to clarify difficult material An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.

A unified, modern treatment of the theory of random graphs-including recent results and techniques Since its inception in the 1960s, the theory of random graphs has evolved into a dynamic branch of discrete mathematics. Yet despite the lively activity and important applications, the last comprehensive volume on the subject is Bollobas's well-known 1985 book. Poised to stimulate research for years to come, this new work covers developments of the last decade, providing a much-needed, modern overview of this fast-growing area of combinatorics. Written by three highly respected members of the discrete mathematics community, the book incorporates many disparate results from across the literature, including results obtained by the authors and some completely new results. Current tools and techniques are also thoroughly emphasized. Clear, easily accessible presentations make Random Graphs an ideal introduction for newcomers to the field and an excellent reference for scientists interested in discrete mathematics and theoretical computer science. Special features include: • A focus on the fundamental theory as well as basic models of random graphs • A detailed description of the phase transition phenomenon • Easy-to-apply exponential inequalities for large deviation bounds • An extensive study of the problem of containing small subgraphs • Results by Bollobas and others on the chromatic number of random graphs • The result by Robinson and Wormald on the existence of Hamilton cycles in random regular graphs • A gentle introduction to the zero-one laws • Ample exercises, figures, and bibliographic references

A cutting-edge look at the emerging distributional theory of sorting Research on distributions associated with sorting algorithms has grown dramatically over the last few decades, spawning many exact and limiting distributions of complexity measures for many sorting algorithms. Yet much of this information has been scattered in disparate and highly specialized sources throughout the literature. In Sorting: A Distribution Theory, leading authority Hosam Mahmoud compiles, consolidates, and clarifies the large volume of available research, providing a much-needed, comprehensive treatment of the entire emerging distributional theory of sorting. Mahmoud carefully constructs a logical framework for the analysis of all standard sorting algorithms, focusing on the development of the probability distributions associated with the algorithms, as well as other issues in probability theory such as measures of concentration and rates of convergence. With an emphasis on narrative rather than technical explanations, this exceptionally well-written book makes new results easily accessible to a broad spectrum of readers, including computer professionals, scientists, mathematicians, and engineers. Sorting: A Distribution Theory: • Contains introductory material on complete and partial sorting • Explains insertion sort, quick sort, and merge sort, among other methods • Offers verbal descriptions of the mechanics of the algorithms as well as the necessary code • Illustrates the distribution theory of sorting using a broad array of both classical and modern techniques • Features a variety of end-of-chapter exercises

Rave reviews for INTEGER AND COMBINATORIAL OPTIMIZATION'This book provides an excellent introduction and survey of traditional fields of combinatorial optimization... It is indeed one of the best and most complete texts on combinatorial optimization... available. [And] with more than 700 entries, [it] has quite an exhaustive reference list.'-Optima'A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such formulations, as well as for understanding the structure of and solving the resulting integer programming problems.'-Computing Reviews'[This book] can serve as a basis for various graduate courses on discrete optimization as well as a reference book for researchers and practitioners.'-Mathematical Reviews'This comprehensive and wide-ranging book will undoubtedly become a standard reference book for all those in the field of combinatorial optimization.'-Bulletin of the London Mathematical Society'This text should be required reading for anybody who intends to do research in this area or even just to keep abreast of developments.'-Times Higher Education Supplement, London Also of interest... INTEGER PROGRAMMING Laurence A. Wolsey Comprehensive and self-contained, this intermediate-level guide to integer programming provides readers with clear, up-to-date explanations on why some problems are difficult to solve, how techniques can be reformulated to give better results, and how mixed integer programming systems can be used more effectively. 1998 (0-471-28366-5) 260 pp.

A timely, accessible introduction to the mathematics of chaos. The past three decades have seen dramatic developments in the theory of dynamical systems, particularly regarding the exploration of chaotic behavior. Complex patterns of even simple processes arising in biology, chemistry, physics, engineering, economics, and a host of other disciplines have been investigated, explained, and utilized. Introduction to Discrete Dynamical Systems and Chaos makes these exciting and important ideas accessible to students and scientists by assuming, as a background, only the standard undergraduate training in calculus and linear algebra. Chaos is introduced at the outset and is then incorporated as an integral part of the theory of discrete dynamical systems in one or more dimensions. Both phase space and parameter space analysis are developed with ample exercises, more than 100 figures, and important practical examples such as the dynamics of atmospheric changes and neural networks. An appendix provides readers with clear guidelines on how to use Mathematica to explore discrete dynamical systems numerically. Selected programs can also be downloaded from a Wiley ftp site (address in preface). Another appendix lists possible projects that can be assigned for classroom investigation. Based on the author's 1993 book, but boasting at least 60% new, revised, and updated material, the present Introduction to Discrete Dynamical Systems and Chaos is a unique and extremely useful resource for all scientists interested in this active and intensely studied field.

Merging logic and mathematics in deductive inference-an innovative, cutting-edge approach. Optimization methods for logical inference? Absolutely, say Vijay Chandru and John Hooker, two major contributors to this rapidly expanding field. And even though'solving logical inference problems with optimization methods may seem a bit like eating sauerkraut with chopsticks... it is the mathematical structure of a problem that determines whether an optimization model can help solve it, not the context in which the problem occurs.'Presenting powerful, proven optimization techniques for logic inference problems, Chandru and Hooker show how optimization models can be used not only to solve problems in artificial intelligence and mathematical programming, but also have tremendous application in complex systems in general. They survey most of the recent research from the past decade in logic/optimization interfaces, incorporate some of their own results, and emphasize the types of logic most receptive to optimization methods-propositional logic, first order predicate logic, probabilistic and related logics, logics that combine evidence such as Dempster-Shafer theory, rule systems with confidence factors, and constraint logic programming systems. Requiring no background in logic and clearly explaining all topics from the ground up, Optimization Methods for Logical Inference is an invaluable guide for scientists and students in diverse fields, including operations research, computer science, artificial intelligence, decision support systems, and engineering.

This gradual, systematic introduction to the main concepts of combinatorics is the ideal text for advanced undergraduate and early graduate courses in this subject. Each of the book's three sections--Existence, Enumeration, and Construction--begins with a simply stated first principle, which is then developed step by step until it leads to one of the three major achievements of combinatorics: Van der Waerden's theorem on arithmetic progressions, Polya's graph enumeration formula, and Leech's 24-dimensional lattice. Along the way, Professor Martin J. Erickson introduces fundamental results, discusses interconnection and problem-solving techniques, and collects and disseminates open problems that raise new and innovative questions and observations. His carefully chosen end-of-chapter exercises demonstrate the applicability of combinatorial methods to a wide variety of problems, including many drawn from the William Lowell Putnam Mathematical Competition. Many important combinatorial methods are revisited several times in the course of the text--in exercises and examples as well as theorems and proofs. This repetition enables students to build confidence and reinforce their understanding of complex material. Mathematicians, statisticians, and computer scientists profit greatly from a solid foundation in combinatorics. Introduction to Combinatorics builds that foundation in an orderly, methodical, and highly accessible manner.

The first comprehensive review of the theory and practice of one oftoday's most powerful optimization techniques. The explosive growth of research into and development of interiorpoint algorithms over the past two decades has significantlyimproved the complexity of linear programming and yielded some oftoday's most sophisticated computing techniques. This book offers acomprehensive and thorough treatment of the theory, analysis, andimplementation of this powerful computational tool. Interior Point Algorithms provides detailed coverage of all basicand advanced aspects of the subject. Beginning with an overview offundamental mathematical procedures, Professor Yinyu Ye movesswiftly on to in-depth explorations of numerous computationalproblems and the algorithms that have been developed to solve them.An indispensable text/reference for students and researchers inapplied mathematics, computer science, operations research,management science, and engineering, Interior Point Algorithms: • Derives various complexity results for linear and convexprogramming • Emphasizes interior point geometry and potential theory • Covers state-of-the-art results for extension, implementation,and other cutting-edge computational techniques • Explores the hottest new research topics, including nonlinearprogramming and nonconvex optimization.

A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade. Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include: • Network flow problems • Optimal matching • Integrality of polyhedra • Matroids • NP-completeness Featuring logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come.