Algorithms are an important concept in the field of computer science, including the field of machine learning. An algorithm is a means of solving a computational problem using well-defined instructions, and it must be designed to satisfy various conditions, such as input/output specifications of problems to be solved. Formulating computational problems like optimization and inference problems is also part of the targets of design in computer science. Once an algorithm is designed for a computational problem, a computer program is designed to implement it in practice. Therefore, we can say that computer science is the activity of designing various objects and producing products like softwares. The creation of computational problems, algorithms, and programs can be described as “designing,” but in addition to this term, other expressions such as “definition,” “formulation,” and “modeling” are often used to clarify the meaning and context. In the following, we will give an overview of the design of computational problems, algorithms, and computer programs.

Defining a computational problem can be considered as an act of translating a real problem into a well-defined problem by abstracting it and describing it in mathematical terms. For example, we consider the following situation; you are a salesman, and you have to visit N cities given by your boss and return to your starting city at the end of the trip with the minimum travel cost. This problem is known as the traveling salesman problem, and its input instance is often represented by an edge-weighted undirected graph between two vertices, u and v, where e = {u, v} is assigned a travel cost w(e). Then, if we consider a closed path p visiting all vertices (cities), the travel cost of p is defined as the sum of the weights of the edges in p (the sum of the travel costs). Thus, the task of this problem is to find a closed path with the minimum travel cost. In this way, the computational problem is formally defined. Now, we have to design an algorithm, which is a computational procedure to find a closed path with a minimum cost or an approximate solution for an arbitrary input instance.

Algorithms are closely related to the concept of design, so much so that there is a famous book entitled “Algorithm Design.” Algorithm design can be described in general terms as follows. First, the relation between input x and output y is determined by the computational problem under consideration. In general, we design procedure (algorithm) A to satisfy this relationship, i.e., y=A(x) for all x in the domain. When the algorithm is realized and the computer program based on it is executed, it will be used repeatedly and will be a useful tool. Therefore, efficiency in two respects, computation time and storage space, is of great importance in design. Today, many people run computer programs and applications on their computers and smartphones, and the fact that their executions can present instantly and without error messages about insufficient memory is the achievements of long-term research efforts of algorithm design. Designing an algorithm also requires the art of giving a mathematical proof that given conditions like input-output relationship are satisfied. Many examples can be found in a book entitled The Art of Computer Programming by Donald N. Knuth.

The process of putting an algorithm into practice on a computer is called computer programming. In a computer program, it is necessary to design parts like data structures, functions, and class objects. The concept of “design patterns” is particularly relevant for the design of “classes.” This is a set of typical design patterns for class in object-oriented languages, based on frequently encountered conditions that classes must satisfy. In addition to algorithm design, program design also requires art.

The book entitled The Art of Readable Code: Simple and Practical Techniques for Writing Better Code addresses how to design readable codes. Even if you have written the code yourself, you may not know what you have written when you look at it a month later. This is especially true if you have written it hastily. It should also be obvious that writing readable code is important when sharing that code with collaborators or students. Furthermore, when you publish your source code on a public repository, you should obviously code with the expectation that others will read it. As the saying goes, “good habits make for a better life,” and perhaps we could say that “readable code makes for better results.” Writing readable code is a good habit in program design.

(MARUYAMA Osamu)

References

• Boswell, Dustinand, Trevor Foucher（2011）The Art of Readable Code: Simple and Practical Techniques for Writing Better Code, O’Reilly Media（ダスティン・ボズウェル、トレバー・フォシェ（2012）『リーダブルコード より良いコードを書くためのシンプルで実践的なテクニック』角征典訳、オライリージャパン）
• Gamma, Erich, Richard Helm, Ralph Johnson, John Vlissides, Grady Booch（1994）Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley Professional（エリック・ガンマ、ラルフ・ジョンソン、リチャード・ヘルム、ジョン・ブリシディース（1999）『オブジェクト指向における再利用のためのデザインパターン』吉田和樹・本位田真一監修、ソフトバンククリエイティブ）
• John, Kleinberg, Eva Tardos（2005）Algorithm Design, Pearson（クラインバーグ・ジョン、タルドシュ・エーバ（2008）『アルゴリズムデザイン』浅野孝夫・浅野泰仁・小野孝男・平田富夫訳、共立出版）
• Knuth, Donald E.（1997）The Art of Computer Programming Volume 1: Fundamental Algorithms, Third Edition, Addison-Wesley Professional（ドナルド・クヌース（2015）『アルゴリズムのバイブル』有澤誠・和田英一監訳、KADOKAWA）