This book has been designed to deal with the topics which are indispensable in the advanced age of computer science. The first three chapters cover mathematical logic, sets, relations and function. Next come the chapters on ordered sets, Boolean albegra and switching circuits and matrices. Finally there are individual chapters on combinatorics, discrete numeric functions, generating functinos, recurrence relations, algebraic structures and graph theory; Graphs are binary trees. The purpose of this book is to present principles and concepts of discrete structures as relevant to student learning. The matter has been presented in as simple and lucid manner as possible and a large number of solved examples to understand the concept and principle of the theory have been introduced.

Since 1990 the German Research Society (Deutsche Forschungsgemeinschaft, DFG) has been funding PhD courses (Graduiertenkollegs) at selected universi- ties in the Federal Republic of Germany. TU Berlin has been one of the first universities joining that new funding program of DFG. The PhD courses have been funded over aperiod of 9 years. The grant for the nine years sums up to approximately 5 million DM. Our Grnduiertenkolleg on Communication-based Systems has been assigned to the Computer Science Department of TU Berlin although it is a joined effort of all three universities in Berlin, Technische Uni- versitat (TU), Freie Universitat (FU), and Humboldt Universitat (HU). The Graduiertenkolleg has been started its program in October 1991. The professors responsible for the program are: Hartmut Ehrig (TU), Gunter Hommel (TU), Stefan Jahnichen (TU), Peter Lohr (FU), Miroslaw Malek (RU), Peter Pep- per (TU), Radu Popescu-Zeletin (TU), Herbert Weber (TU), and Adam Wolisz (TU). The Graduiertenkolleg is a PhD program for highly qualified persons in the field of computer science. Twenty scholarships have been granted to fellows of the Graduiertenkolleg for a maximal period of three years. During this time the fellows take part in a selected educational program and work on their PhD thesis.

This first part presents chapters on models of computation, complexity theory, data structures, and efficient computation in many recognized sub-disciplines of Theoretical Computer Science.

2. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3. Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ., . . . . 60 4. Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 A Simple Proof for a Result of Ollerenshaw on Steiner Trees . . . . . . . . . . 68 Xiufeng Du, Ding-Zhu Du, Biao Gao, and Lixue Qii 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2. In the Euclidean Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3. In the Rectilinear Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4. Discussion . . . . . . . . . . . . -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Optimization Algorithms for the Satisfiability (SAT) Problem . . . . . . . . . 72 Jun Gu 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2. A Classification of SAT Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7:3 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV 4. Complete Algorithms and Incomplete Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5. Optimization: An Iterative Refinement Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6. Local Search Algorithms for SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7. Global Optimization Algorithms for SAT Problem . . . . . . . . . . . . . . . . . . . . . . . . 106 8. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Ergodic Convergence in Proximal Point Algorithms with Bregman Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Osman Guier 1. Introduction . . .: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2. Convergence for Function Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 3. Convergence for Arbitrary Maximal Monotone Operators . . . . . . . . . . . .

As is known, the book named "Multivariate spline functions and their applications" has been published by the Science Press in 1994. This book is an English edition based on the original book mentioned 1 above with many changes, including that of the structure of a cubic - interpolation in n-dimensional spline spaces, and more detail on triangu- lations have been added in this book. Special cases of multivariate spline functions (such as step functions, polygonal functions, and piecewise polynomials) have been examined math- ematically for a long time. I. J. Schoenberg (Contribution to the problem of application of equidistant data by analytic functions, Quart. Appl. Math., 4(1946), 45 - 99; 112 - 141) and W. Quade & L. Collatz (Zur Interpo- lations theories der reellen periodischen function, Press. Akad. Wiss. (PhysMath. KL), 30(1938), 383- 429) systematically established the the- ory of the spline functions. W. Quade & L. Collatz mainly discussed the periodic functions, while I. J. Schoenberg's work was systematic and com- plete. I. J. Schoenberg outlined three viewpoints for studing univariate splines: Fourier transformations, truncated polynomials and Taylor ex- pansions. Based on the first two viewpoints, I. J. Schoenberg deduced the B-spline function and its basic properties, especially the basis func- tions. Based on the latter viewpoint, he represented the spline functions in terms of truncated polynomials. These viewpoints and methods had significantly effected on the development of the spline functions.

This essential companion volume to Chaitin's highly successful "The Limits of Mathematics", also published by Springer, gives a brilliant historical survey of the work of this century on the foundations of mathematics, in which the author was a major participant. The Unknowable is a very readable and concrete introduction to Chaitin's ideas, and it includes a detailed explanation of the programming language used by Chaitin in both volumes. It will enable computer users to interact with the author's proofs and discover for themselves how they work. The software for The Unknowable can be downloaded from the author's Web site.

Studies in Logic and the Foundations of Mathematics, Volume 123: Constructivism in Mathematics: An Introduction, Vol. II focuses on various studies in mathematics and logic, including metric spaces, polynomial rings, and Heyting algebras. The publication first takes a look at the topology of metric spaces, algebra, and finite-type arithmetic and theories of operators. Discussions focus on intuitionistic finite-type arithmetic, theories of operators and classes, rings and modules, linear algebra, polynomial rings, fields and local rings, complete separable metric spaces, and located sets. The text then examines proof theory of intuitionistic logic, theory of types and constructive set theory, and choice sequences. The book elaborates on semantical completeness, sheaves, sites, and higher-order logic, and applications of sheaf models. Topics include a derived rule of local continuity, axiom of countable choice, forcing over sites, sheaf models for higher-order logic, and complete Heyting algebras. The publication is a valuable reference for mathematicians and researchers interested in mathematics and logic.

The expression of uncertainty in measurement poses a challenge since it involves physical, mathematical, and philosophical issues. This problem is intensified by the limitations of the probabilistic approach used by the current standard (the GUM Instrumentation Standard). This text presents an alternative approach. It makes full use of the mathematical theory of evidence to express the uncertainty in measurements. Coverage provides an overview of the current standard, then pinpoints and constructively resolves its limitations. Numerous examples throughout help explain the book 's unique approach.

The purpose of the book is to advance in the understanding of brain function by defining a general framework for representation based on category theory. The idea is to bring this mathematical formalism into the domain of neural representation of physical spaces, setting the basis for a theory of mental representation, able to relate empirical findings, uniting them into a sound theoretical corpus.

The innovative approach presented in the book provides a horizon of interdisciplinary collaboration that aims to set up a common agenda that synthesizes mathematical formalization and empirical procedures in a systemic way. Category theory has been successfully applied to qualitative analysis, mainly in theoretical computer science to deal with programming language semantics. Nevertheless, the potential of category theoretic tools for quantitative analysis of networks has not been tackled so far. Statistical methods to investigate graph structure typically rely on network parameters. Category theory can be seen as an abstraction of graph theory. Thus, new categorical properties can be added into network analysis and graph theoretic constructs can be accordingly extended in more fundamental basis. By generalizing networks using category theory we can address questions and elaborate answers in a more fundamental way without waiving graph theoretic tools. The vital issue is to establish a new framework for quantitative analysis of networks using the theory of categories, in which computational neuroscientists and network theorists may tackle in more efficient ways the dynamics of brain cognitive networks.

The intended audience of the book is researchers who wish to explore the validity of mathematical principles in the understanding of cognitive systems. All the actors in cognitive science: philosophers, engineers, neurobiologists, cognitive psychologists, computer scientists etc. are akin to discover along its pages new unforeseen connections through the development of concepts and formal theories described in the book. Practitioners of both pure and applied mathematics e.g., network theorists, will be delighted with the mapping of abstract mathematical concepts in the terra incognita of cognition.

Logic and Philosophy of Mathematics in the Early Husserl focuses on the first ten years of Edmund Husserl's work, from the publication of his Philosophy of Arithmetic (1891) to that of his Logical Investigations (1900/01), and aims to precisely locate his early work in the fields of logic, philosophy of logic and philosophy of mathematics. Unlike most phenomenologists, the author refrains from reading Husserl's early work as a more or less immature sketch of claims consolidated only in his later phenomenology, and unlike the majority of historians of logic she emphasizes the systematic strength and the originality of Husserl's logico-mathematical work.

The book attempts to reconstruct the discussion between Husserl and those philosophers and mathematicians who contributed to new developments in logic, such as Leibniz, Bolzano, the logical algebraists (especially Boole and Schroder), Frege, and Hilbert and his school. It presents both a comprehensive critical examination of some of the major works produced by Husserl and his antagonists in the last decade of the 19th century and a formal reconstruction of many texts from Husserl's Nachlass that have not yet been the object of systematical scrutiny.

This volume will be of particular interest to researchers working in the history, and in the philosophy, of logic and mathematics, and more generally, to analytical philosophers and phenomenologists with a background in standard logic."

This is a two-volume collection presenting the selected works of Herbert Busemann, one of the leading geometers of the twentieth century and one of the main founders of metric geometry, convexity theory and convexity in metric spaces. Busemann also did substantial work (probably the most important) on Hilbert's Problem IV. These collected works include Busemann's most important published articles on these topics. Volume I of the collection features Busemann's papers on the foundations of geodesic spaces and on the metric geometry of Finsler spaces. Volume II includes Busemann's papers on convexity and integral geometry, on Hilbert's Problem IV, and other papers on miscellaneous subjects. Each volume offers biographical documents and introductory essays on Busemann's work, documents from his correspondence and introductory essays written by leading specialists on Busemann's work. They are a valuable resource for researchers in synthetic and metric geometry, convexity theory and the foundations of geometry.

The theory of constructive (recursive) models follows from works of Froehlich, Shepherdson, Mal'tsev, Kuznetsov, Rabin, and Vaught in the 50s. Within the framework of this theory, algorithmic properties of abstract models are investigated by constructing representations on the set of natural numbers and studying relations between algorithmic and structural properties of these models. This book is a very readable exposition of the modern theory of constructive models and describes methods and approaches developed by representatives of the Siberian school of algebra and logic and some other researchers (in particular, Nerode and his colleagues). The main themes are the existence of recursive models and applications to fields, algebras, and ordered sets (Ershov), the existence of decidable prime models (Goncharov, Harrington), the existence of decidable saturated models (Morley), the existence of decidable homogeneous models (Goncharov and Peretyat'kin), properties of the Ehrenfeucht theories (Millar, Ash, and Reed), the theory of algorithmic dimension and conditions of autostability (Goncharov, Ash, Shore, Khusainov, Ventsov, and others), and the theory of computable classes of models with various properties. Future perspectives of the theory of constructive models are also discussed. Most of the results in the book are presented in monograph form for the first time. The theory of constructive models serves as a basis for recursive mathematics. It is also useful in computer science, in particular, in the study of programming languages, higher level languages of specification, abstract data types, and problems of synthesis and verification of programs. Therefore, the book will be usefulfor not only specialists in mathematical logic and the theory of algorithms but also for scientists interested in the mathematical fundamentals of computer science. The authors are eminent specialists in mathematical logic. They have established fundamental results on elementary theories, model theory, the theory of algorithms, field theory, group theory, applied logic, computable numberings, the theory of constructive models, and the theoretical computer science.

Anyone involved in the philosophy of science is naturally drawn into the study of the foundations of probability. Different interpretations of probability, based on competing philosophical ideas, lead to different statistical techniques, and frequently to mutually contradictory consequences.

This unique book presents a new interpretation of probability, rooted in the traditional interpretation that was current in the 17th and 18th centuries. Mathematical models are constructed based on this interpretation, and statistical inference and decision theory are applied, including some examples in artificial intelligence, solving the main foundational problems. Nonstandard analysis is extensively developed for the construction of the models and in some of the proofs. Many nonstandard theorems are proved, some of them new, in particular, a representation theorem that asserts that any stochastic process can be approximated by a process defined over a space with equiprobable outcomes.

One criterion for classifying books is whether they are written for a single pur pose or for multiple purposes. This book belongs to the category of multipurpose books, but one of its roles is predominant-it is primarily a textbook. As such, it can be used for a variety ofcourses at the first-year graduate or upper-division undergraduate level. A common characteristic of these courses is that they cover fundamental systems concepts, major categories of systems problems, and some selected methods for dealing with these problems at a rather general level. A unique feature of the book is that the concepts, problems, and methods are introduced in the context of an architectural formulation of an expert system referred to as the general systems problem solver or aSPS-whose aim is to provide users ofall kinds with computer-based systems knowledge and methodo logy. Theasps architecture, which is developed throughout the book, facilitates a framework that is conducive to acoherent, comprehensive, and pragmaticcoverage ofsystems fundamentals-concepts, problems, and methods. A course that covers systems fundamentals is now offered not only in sys tems science, information science, or systems engineering programs, but in many programs in other disciplines as well. Although the level ofcoverage for systems science or engineering students is surely different from that used for students in other disciplines, this book is designed to serve both of these needs."

This is a continuation of Vol. 7 of Trends in Logic. It wil cover the wealth of recent developments of Lukasiewicz Logic and their algebras (Chang MV-algebras), with particular reference to (de Finetti) coherent evaluation of continuously valued events, (Renyi) conditionals for such events, related algorithms.

This volume tackles Goedel's two-stage project of first using Husserl's transcendental phenomenology to reconstruct and develop Leibniz' monadology, and then founding classical mathematics on the metaphysics thus obtained. The author analyses the historical and systematic aspects of that project, and then evaluates it, with an emphasis on the second stage. The book is organised around Goedel's use of Leibniz, Husserl and Brouwer. Far from considering past philosophers irrelevant to actual systematic concerns, Goedel embraced the use of historical authors to frame his own philosophical perspective. The philosophies of Leibniz and Husserl define his project, while Brouwer's intuitionism is its principal foil: the close affinities between phenomenology and intuitionism set the bar for Goedel's attempt to go far beyond intuitionism. The four central essays are `Monads and sets', `On the philosophical development of Kurt Goedel', `Goedel and intuitionism', and `Construction and constitution in mathematics'. The first analyses and criticises Goedel's attempt to justify, by an argument from analogy with the monadology, the reflection principle in set theory. It also provides further support for Goedel's idea that the monadology needs to be reconstructed phenomenologically, by showing that the unsupplemented monadology is not able to found mathematics directly. The second studies Goedel's reading of Husserl, its relation to Leibniz' monadology, and its influence on his publishe d writings. The third discusses how on various occasions Brouwer's intuitionism actually inspired Goedel's work, in particular the Dialectica Interpretation. The fourth addresses the question whether classical mathematics admits of the phenomenological foundation that Goedel envisaged, and concludes that it does not. The remaining essays provide further context. The essays collected here were written and published over the last decade. Notes have been added to record further thoughts, changes of mind, connections between the essays, and updates of references.

Two prisoners are told that they will be brought to a room and seated so that each can see the other. Hats will be placed on their heads; each hat is either red or green. The two prisoners must simultaneously submit a guess of their own hat color, and they both go free if at least one of them guesses correctly. While no communication is allowed once the hats have been placed, they will, however, be allowed to have a strategy session before being brought to the room. Is there a strategy ensuring their release? The answer turns out to be yes, and this is the simplest non-trivial example of a hat problem.

This book deals with the question of how successfully one can predict the value of an arbitrary function at one or more points of its domain based on some knowledge of its values at other points. Topics range from hat problems that are accessible to everyone willing to think hard, to some advanced topics in set theory and infinitary combinatorics. For example, there is a method of predicting the value "f"("a") of a function f mapping the reals to the reals, based only on knowledge of "f"'s values on the open interval ("a" 1, "a"), and for every such function the prediction is incorrect only on a countable set that is nowhere dense.

The monograph progresses from topics requiring fewer prerequisites to those requiring more, with most of the text being accessible to any graduate student in mathematics. The broad range of readership includes researchers, postdocs, and graduate students in the fields of set theory, mathematical logic, and combinatorics. The hope is that this book will bring together mathematicians from different areas to think about set theory via a very broad array of coordinated inference problems. "

Primary Maths for Scotland Textbook 2A is the first of 3 second level textbooks. These engaging and pedagogically rigorous books are the first maths textbooks for Scotland completely aligned to the benchmarks and written specifically to support Scottish children in mastering mathematics at their own pace. Primary Maths for Scotland Textbook 2A is the first of 3 second level textbooks. The books are clear and simple with a focus on developing conceptual understanding alongside procedural fluency. They cover the entire second level mathematics Curriculum for Excellence in an easy-to-use set of textbooks which can fit in with teacher's existing planning, resources and scheme of work. - Packed with problem-solving, investigations and challenging problems - Diagnostic check lists at the start of each unit ensure that pupils possess the required pre-requisite knowledge to engage on the unit of work - Worked examples and non-examples help pupils fully understand mathematical concepts - Includes intelligent practice that reinforces pupils' procedural fluency

Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications focuses on discrete mathematics and combinatorial algorithms interacting with real world problems in computer science, operations research, applied mathematics and engineering. The book contains eleven chapters written by experts in their respective fields, and covers a wide spectrum of high-interest problems across these discipline domains. Among the contributing authors are Richard Karp of UC Berkeley and Robert Tarjan of Princeton; both are at the pinnacle of research scholarship in Graph Theory and Combinatorics. The chapters from the contributing authors focus on "real world" applications, all of which will be of considerable interest across the areas of Operations Research, Computer Science, Applied Mathematics, and Engineering. These problems include Internet congestion control, high-speed communication networks, multi-object auctions, resource allocation, software testing, data structures, etc. In sum, this is a book focused on major, contemporary problems, written by the top research scholars in the field, using cutting-edge mathematical and computational techniques.

The book is an authoritative and up-to-date introduction to the field of analysis and potential theory dealing with the distribution zeros of classical systems of polynomials such as orthogonal polynomials, Chebyshev, Fekete and Bieberbach polynomials, best or near-best approximating polynomials on compact sets and on the real line. The main feature of the book is the combination of potential theory with conformal invariants, such as module of a family of curves and harmonic measure, to derive discrepancy estimates for signed measures if bounds for their logarithmic potentials or energy integrals are known a priori.

Starting with a simple formulation accessible to all mathematicians, this second edition is designed to provide a thorough introduction to nonstandard analysis. Nonstandard analysis is now a well-developed, powerful instrument for solving open problems in almost all disciplines of mathematics; it is often used as a 'secret weapon' by those who know the technique. This book illuminates the subject with some of the most striking applications in analysis, topology, functional analysis, probability and stochastic analysis, as well as applications in economics and combinatorial number theory. The first chapter is designed to facilitate the beginner in learning this technique by starting with calculus and basic real analysis. The second chapter provides the reader with the most important tools of nonstandard analysis: the transfer principle, Keisler's internal definition principle, the spill-over principle, and saturation. The remaining chapters of the book study different fields for applications; each begins with a gentle introduction before then exploring solutions to open problems. All chapters within this second edition have been reworked and updated, with several completely new chapters on compactifications and number theory. Nonstandard Analysis for the Working Mathematician will be accessible to both experts and non-experts, and will ultimately provide many new and helpful insights into the enterprise of mathematics.

This book presents eleven peer-reviewed papers from the 3rd International Conference on Applications of Mathematics and Informatics in Natural Sciences and Engineering (AMINSE2017) held in Tbilisi, Georgia in December 2017. Written by researchers from the region (Georgia, Russia, Turkey) and from Western countries (France, Germany, Italy, Luxemburg, Spain, USA), it discusses key aspects of mathematics and informatics, and their applications in natural sciences and engineering. Featuring theoretical, practical and numerical contributions, the book appeals to scientists from various disciplines interested in applications of mathematics and informatics in natural sciences and engineering.

Intuitionistic type theory can be described, somewhat boldly, as a partial fulfillment of the dream of a universal language for science. This book expounds several aspects of intuitionistic type theory, such as the notion of set, reference vs. computation, assumption, and substitution. Moreover, the book includes philosophically relevant sections on the principle of compositionality, lingua characteristica, epistemology, propositional logic, intuitionism, and the law of excluded middle. Ample historical references are given throughout the book.