/ Adam Kapralski / Associate Professor
The common feature of computations performed in a digital machine, which are independent of applications and modeling, is performance of basic arithmetic or logic operations on integers. The historical development of humanity determined the mathematics that we currently have, that is, mathematics operating with many abstract notions which have no direct representation in integers. This mathematics supports general reasoning of a human being and his hand made calculations, but generally is pretty far from the nature of computers. A computer calculates very fast but certain concepts like infinity, real numbers, and so on still create problems for organization of proper machine calculations. In order to promote machine "thinking" we have to have completely different mathematics whose roots would be oriented for a machine but not for a human being. We need mathematics for modeling existing reality which would take advantage of fast and massive calculations on integers and simultaneously not referring to notions highly abstracted from integers. Such mathematics will allow us to make a better organization of computer calculations, it will also allow us to construct better computers. On the other hand, if we are improving the organization of computations, we have a chance to note some very fundamental properties of calculations, which can help us to better understand the whole universe. That understanding promotes the development of new and maybe even more compact mathematics. Therefore, we need new mathematics for constructing a better computer, and better organized computations give another possibility of mathematics development.
In there general classes of problems, the Mathematical Foundations of
Computer Science Laboratory finds its main task. The goal is to produce
much more efficient mathematical tools for AI, database
management, expert systems, computational geometry and for
processing widely understood combinatorial tasks including
NP-complete and isomorphic complete problems. All those tasks are
seen as related to development of Depth Search Machines, which
represent a new concept of computations, oriented mainly on
massively parallel organization. Several new mathematical concepts
for development of calculations in DSMs have already been produced.
These concern DATABASES, Binary Matrix Problems,
Geometry of Extrema, New Combinatorics, and a new widely understood
approach to pattern recognition and image classification. The
results obtained up till now also give a lot of material for
constructing a more compact and more logical understanding of the
universal.
The laboratory is currently conducting two projects:
(i) Depth Search Machines,
(ii) The Geometrical Processing in Depth Search Machines.
In the first project, research is oriented on architecture and on general representations of many problems and tasks; the new representation will promote development of the processing conducted in DSMs. To support processing intractable problems in DSMs, the generation of combinatorial objects and synthesis of dedicated hardware systems is developing. The second project is oriented on geometrical and related calculations in DSMs. We are concerned with development of the geometry of extrema, top-down geometry, pattern recognition and image classification using image transforms.
Laboratory is also offering a Student Extracurricular Project (SCCP) ``Generation of combinatorial objects in parallel''.
Refereed Journal Papers
The paper gives results which have important theoretical meaning for deep understanding whole combinatorics, besides many technical results for supporting parallel processing there are produced. Those theoretical results create foundations for seeing whole combinatorics as the branch of mathematics dealing with choice functions of indexed families. It is shown that any set of permutations and combinations can be represented by suitable set of choice functions of dedicated indexed families, it is mentioned also that any set of partitions or other combinatorial objects can be represented similarly. The investigation of layers and theorem 1 supply general method for splitting any indexed family into subfamilies so that any choice function of the given family and satisfying given requirement becomes corresponding choice function of exactly one its layer. The proof of theorem 5 reveals new relations in between Pascal's triangle and combinations. The given algorithm for the generation of the next specified choice function of indexed families has important meaning as far as technical results are concerned. That one and earlier mentioned results enabled to develop parallel algorithms for generating regular and irregular sets of permutations or combinations both for MIMD and SIMD models. It is also worthwhile to mention that new fast algorithm for finding any k-th combination of m out of n items has been given.
Technical Reports
Unpublished Textbooks
Academic Activities
I served several times as a referee making reviews of papers and books for international journals.