1-30
The solution of combinatorial problems using Boolean equations: New challenges for teaching
Authors: Bernd Steinbach and Christian Posthoff
Number of views: 539
It will be shown that many finite combinatorial problems can be solved by using Boolean
equations. Therefore, it is necessary to teach how to transform the different problems into this area
in a correct way. We demonstrate the required modeling steps in the first part using very different
interesting examples. It is no longer necessary to develop different solution methods for different
tasks; Boolean equations can uniquely be used. Ternary vectors and ternary arrays are powerful
data structures that help to extenuate the complexity.
Naturally, problems of a reasonable size cannot be solved by hand, therefore existing software
systems must be used. The application of such a software system can require a huge amount
of details. We show how a simplified environment of the software supports the teaching process
because the key issues can be explored on a reasonable level of abstraction. Both the XBOOLEMonitor
and a SAT-solver will be used. It must be learned how to use these systems, i.e., the
structure and the working of the systems must be well understood.
It can, however, be that the complexity of the problem is beyond the size of the existing
systems. Then we have the last level that requires an excellent knowledge of Mathematics and
excellent programming skills. We take as an example the rectangle-free coloring of grids using
four colors. The solution of these last problems of the highest level show that only the unified
efforts of Mathematics and Computer Science can solve the problems of the highest complexity.
It is possible to solve problems that could not be solved before in a constructive way. You do not
only know whether solutions exist or not, it is possible to build a very large number of solutions or
even all the solutions.
Therefore, the education of Mathematicians, Computer Scientists and Engineers must take
this necessary cooperation into consideration. To be a specialist in one of these areas is not enough!