What is your goal?

People use computers as a matter of course to solve various problems of modern society. Yet, even when solving the same problem, the calculation time may vary by tens of times depending on ingenuities in algorithms (calculation procedures). Some may believe that the time taken does not matter as long as the problem is solved. However, the difference in time is important as it greatly affects how the computer is used (if it takes three seconds to obtain an answer, you can interactively carry out your work referring to the calculation results; however, if it takes three minutes, you may want to leave your seat to do other things). As an easier-to-understand example, the difference between whether a calculation to determine the cause of failure of a product takes a day or month can continue or bankrupt a company.

With advances in electronic circuit technologies, the speed of basic computer operations (the number of operations per second) is gradually increasing every year. In contrast, algorithm technologies are ingenuities to solve the same problem using as few basic operations as possible. In other words, even with the same computer, the calculation speed may vary by tens of times due to the algorithm alone. Thus, I would like to clarify what kinds of ingenuities can reduce the number of operations and speed up calculations in certain situations, outlining specific methods and providing them to society at large.

 

What techniques are you studying?

I am studying Binary Decision Diagram (BDD), an algorithm that uses the structures of “branching” and “compression.” Have you ever seen a personality test, in which the respondent answers a series of Yes/No questions to reach a goal? By considering this test to be an expression of calculation procedures that include all conceivable possibilities of branching, BDD can be considered to be what is obtained by simplifying (compressing) the above calculation procedures to the point where they cannot be more compact.

BDD is a technique involving speeding up calculations by “branching” and “compression.” Ingenuities in the branching method can reduce the BDD, speeding up calculations. Furthermore, branching can create a repetition of similar intermediate computations, which can be economically expressed using the “compression” technique to further speed up calculations. While the figures below illustrate extreme examples, even with the same data, a change in the order of branching questions can make the BDD more compact or explosively complex. The calculation time can change by tens or hundreds of times by this alone.

 

How is this related to our lives?

Algorithm techniques that use the “logics” and “combinations” as described above can be utilized in problems of “data mining,” in which useful knowledge is discovered from a huge amount of data. For example, various applications exist as follows:

- Identifying combinations of products frequently bought together from supermarket sales data;
- Identifying a dangerous combination of elements that is likely to result in accidents from analysis of traffic accident data; and
- Identifying a characteristic sequence related to the occurrence of a disease from the gene sequence data of an organism.

Apart from the above, one could argue that algorithm techniques constitute important core technologies that affect all sorts of problems in a computer-powered society, including reducing manufacturing costs and improving quality through the optimization of industrial processes, along with automating failure analysis and diagnosis of large-scale systems, such as power plants, and electricity and communication networks. In addition, in more familiar contexts, they are also deeply related to Sudoku, mazes, Shogi problems, and other puzzles.