Discrete analysis

The branch of mathematics whose subject is the study of finite properties of structures which arise both in mathematics itself and in applications. Such finite structures comprise, for example, finite groups (cf. Finite group), finite graphs (cf. Graph), as well as certain mathematical models of processors of discrete information, such as finite automata (cf. Automaton, finite); Turing machines (cf. Turing machine), etc. The scope of discrete analysis is sometimes extended to include arbitrary discrete structures; this yields discrete mathematics, which then becomes identical with discrete analysis. Such structures may include certain algebraic systems, infinite graphs, certain types of calculating media (e.g. homogeneous structures), etc. The name finite mathematics is sometimes used as a synonym for discrete mathematics and discrete analysis. In what follows the term "discrete analysis" is understood in the wide meaning of the word, including discrete mathematics.

As distinct from discrete analysis, classical mathematics deals mainly with continuous objects. The choice between classical and discrete mathematics and tools of investigation will depend on the objective of the study and on whether a discrete or continuous model of the phenomenon under study is to be considered. The differentiation between continuous and discrete mathematics is itself largely arbitrary, since, first, ideas and methods keep being actively interchanged between the two and, secondly, the models which must be used often display both discrete and continuous features. Moreover, in certain branches of mathematics the tools of discrete mathematics are used to study continuous models and vice versa — the methods and formulations of problems of classical mathematics are employed in the study of discrete structures. Thus, the two branches of mathematics merge to some extent.

Discrete analysis is an important mathematical subject, with its own subjects of study, methods and problems. Its distinctive feature is that certain basic concepts of classical mathematics — limit and continuity — must be discarded and, as a consequence, the powerful tools of classical mathematics are unsuitable for solving many problems in discrete analysis. Discrete analysis can also be described — in addition to specifying its subjects, methods and problems — by listing its constituent disciplines. These include, in the first place, combinatorial analysis; graph theory; the theory of coding and decoding; the theory of functional systems (cf. Functional system), and some other subjects. The term "discrete analysis" is often defined as the totality of the above disciplines, on the assumption that finite structures only are considered. The extension of this definition yields a broader interpretation of discrete analysis, which then includes both entire branches of mathematics such as mathematical logic and parts of them such as number theory; algebra; computational mathematics; probability theory, and certain other disciplines the subject of which is discrete.

The elements of discrete analysis date back to early antiquity, and, by growing side by side with other branches of mathematics, have become their constituent parts. Problems related to the properties of integers, which subsequently brought about number theory, were typical of this period. Later, elements of combinatorial analysis and discrete probability theory arose when solving problems in games, while the general problems in number theory, algebra and geometry gave rise to the most important mathematical concepts such as a group, a field, a ring, etc., which determined the subsequent development and content of algebra many years ahead, and are, in effect, of discrete nature. The striving for rigour in mathematical considerations and the analysis of its working tool — logic — gave birth to yet another branch of mathematics — mathematical logic. However, the most advanced development of discrete analysis is due to the appearance of cybernetics and its theoretical part — mathematical cybernetics. Mathematical cybernetics, which is the direct mathematical study of the various problems occurring in practice, provides important ideas and problems in discrete analysis, and even gives rise to altogether new trends. Thus, practical problems necessitating extensive numerical processing stimulated the appearance of strong numerical methods for problem solving, which subsequently merged to form computational mathematics, while the analysis of the concepts of computability and an algorithm generated an important branch of mathematical logic — the theory of algorithms (cf. Algorithms, theory of). The growing stream of information and the related problems of information storage, processing and transmission gave birth to coding theory; graph theory was developed to meet the needs of economics, electrical engineering and internal mathematical problems; problems on the construction and description of the functioning of complex control systems yield the theory of functional systems, etc. Moreover, mathematical cybernetics utilizes the results of discrete analysis in solving its own problems.

Discrete analysis also displays a number of other special features. Thus, together with problems of the "existence" type, which are of general mathematical nature, an important class of problems dealt with are related to algorithmic solvability and the construction of concrete solution algorithms, which is characteristic for discrete analysis. Another special feature is the fact that for the first time a thorough-going study had to be made of the so-called discrete multi-extremum problems which frequently occur in mathematical cybernetics. The corresponding methods of classical mathematics for finding extrema, which are mainly based on the smoothness of functions, proved largely ineffective in such cases. Typical problems of this kind in discrete analysis include, for example, finding what may be called optimal strategies in a game of chess with a restricted number of moves, and the important cybernetical problem of constructing minimal disjunctive normal forms for Boolean functions — the so-called problem of minimization of Boolean functions (cf. Boolean functions, minimization of). Another special feature of discrete analysis, related to problems in finite structures, is that algorithms by which these problems may be solved exist in most cases, while in classical mathematics their complete solution is only possible subject to serve restrictions. An example of such an algorithm is the algorithm of inspection of all possible variants, i.e. an algorithm of the "complete sampling" type. Such problems include the problem of chess strategy mentioned above, the minimization of Boolean functions, etc. As solutions of "complete sampling" type are very laborious and are rarely used in practice, a number of new problems related to the limitation of sampling arise, reducing individual problems with given parameter values to a decision problem with an infinite set of parameter values. Here also the question of natural restrictions on the methods used for solving problems of given class arise, etc. The formulation of problems of this type and the development of the appropriate methods is carried out on specific models by various branches of mathematics, such as models of minimization of Boolean functions and synthesis of control systems (cf. Control system) from mathematical cybernetics.

See also the collections "Problems in cybernetics" (in Russian) and "Discrete analysis" (in Russian), as well as the journal "Kibernetika" (translated as "Cybernetics" ).

References

[1]	S.V. Yablonskii, "A survey of some results in discrete mathematics" Informatsionnye Materialy , 5 (1970) pp. 5–15 (In Russian)
[2]	J. Kemeny, J. Snell, G.L. Thompson, "Introduction to finite mathematics" , Prentice-Hall (1966) MR1537787 MR0360048 MR0360049 MR1570877 MR1529779 MR0084454 Zbl 0143.26003

Comments

See also Finite mathematics; Classical combinatorial problems; Combinatorial analysis; Combinatorial geometry. The phrase "discrete analysis" is rarely used in the West, and as a rule problems from cybernetics and control, even if discrete, are not considered to be central to discrete mathematics.