第2章計算論的思考と設計の再利用性

TECHNOLOGY IN EVERYDAY LIFE日常生活の中の技術

Computational Thinking in Our Life暮らしの中の計算論的思考

Computational thinking is a method of problem-solving that is extremely useful in everyday life. It involves breaking down complex issues into manageable parts, identifying patterns, extracting essential information, and devising systematic solutions. This process not only applies to technical fields, but also to everyday situations.

英語のヒント

計算論的思考は、日常生活で非常に役立つ問題解決の方法である。複雑な問題を扱いやすい部分に分け、パターンを見つけ、不可欠な情報を取り出し、体系的な解決策を考案する。この過程は、技術分野だけでなく、日常のさまざまな場面にも適用できる。

For example, imagine someone trying to manage their monthly expenses within a tight budget. Here's how you might apply computational thinking to this common problem of managing a monthly budget:

英語のヒント

たとえば、限られた予算の中で毎月の支出を管理しようとしている人を思い浮かべよう。この身近な月々の予算管理の問題には、計算論的思考を次のように適用できる。

1. Decomposition: Break down the financial challenge into different categories such as rent, groceries, utilities, and entertainment.

英語のヒント

1. 分解：家賃、食料品、光熱費、娯楽費などのカテゴリーに、お金の問題を分ける。

2. Pattern recognition: Analyze past spending to identify patterns.

2. パターン認識：過去の支出を分析し、パターンを見つける。

3. Abstraction: Focus on key areas where costs can be reduced.

3. 抽象化：費用を削減できる重要な領域に注目する。

4. Algorithmic thinking: Develop a systematic approach to allocate monthly income.

英語のヒント

4. アルゴリズム的思考：毎月の収入を配分するための体系的な方法を作る。

By using computational thinking, you can manage your finances more effectively, ensuring they cover essential costs while maximizing their savings.

英語のヒント

計算論的思考を使えば、家計をより効果的に管理し、不可欠な費用を賄いながら、貯蓄を最大限に増やせる。

Abstraction抽象化

Abstraction makes it possible to pull out the important details and identify principles that apply to other problems or situations. When applying abstraction, it may be useful to write down some notes or draw diagrams to help understand how to resolve the problem. In the jam sandwich example, abstraction means forming an idea of what the sandwich should look like. To apply abstraction here, you would create a model or draw a picture representing the final appearance of the jam sandwich once it is made. This simplifies the details, providing a clearer image of the desired outcome. Simple tools like the Windows Paint program can be used to do this, as shown in Figure 2.5.

英語のヒント

抽象化によって、重要な細部を取り出し、ほかの問題や状況にも当てはまる原理を見いだせる。抽象化を行う際は、問題の解き方を理解するため、メモを書いたり図を描いたりすると役立つことがある。ジャムサンドイッチの例で抽象化とは、完成したサンドイッチがどのような姿になるべきか、イメージを作ることである。ここで抽象化を適用するには、完成時の見た目を表す模型を作るか、絵を描く。こうすれば細部が単純化され、望む結果がより明確に見える。図2.5のように、Windowsのペイントなどの簡単な道具を使って行える。

Figure 2.5 This jam sandwich abstraction example illustrates what the final product should look like. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図2.5 ジャムサンドイッチを抽象化したこの例は、完成品がどのような姿になるべきかを示す。（出典：著作権Rice University、OpenStax。CC BY 4.0ライセンス）

In technology, data are represented at different levels of abstraction to simplify user interaction and manage complex operations efficiently. Users interact with a web application through a straightforward interface, like requesting help from a GenAI tool, without seeing the underlying complexity. This GenAI prompt is then processed by the application’s logic, which validates and directs it appropriately, often invisibly to the user. Finally, at the back end, the prompt is processed and a GenAI-generated response is provided. Each layer of abstraction serves a separate role, making the entire process efficient for both the user and the system (Figure 2.6).

英語のヒント

技術では、利用者の操作を簡単にし、複雑な処理を効率よく管理するために、データをさまざまな抽象化の水準で表現する。利用者は、生成AI（GenAI）ツールに支援を頼むときのように、わかりやすいインターフェースを通じてウェブアプリケーションを操作し、その背後の複雑さを目にすることはない。生成AIへのこのプロンプトは、次にアプリケーションのロジックによって処理される。ロジックはプロンプトを検証し、適切な先へ送るが、その処理は利用者から見えないことが多い。最後にバックエンドでプロンプトが処理され、生成AIの応答が提供される。抽象化の各層は別々の役割を果たし、利用者にもシステムにも、過程全体を効率のよいものにする（図2.6）。

Figure 2.6 When using GenAI, a user interacts with the interface while the application processes the prompt with layers of abstraction on the back end. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図2.6 生成AIを使うとき、利用者はインターフェースを操作し、その間にアプリケーションはバックエンドの抽象化の層を通じてプロンプトを処理する。（出典：著作権Rice University、OpenStax。CC BY 4.0ライセンス）

Algorithmアルゴリズム

An algorithm is a sequence of steps/instructions that must be followed in a specific order to solve a problem. Algorithms make it possible to describe a solution to a problem by writing down the instructions that are required to solve the problem. Computer programs typically execute algorithms to perform certain tasks. In the jam sandwich example, the algorithm technique is about writing instructions that the robot can follow to make the jam sandwich. As you will learn in Chapter 3 Data Structures and Algorithms, algorithms are most commonly written as either pseudocode or a flowchart. An outline of the logic of algorithms using a combination of language and high-level programming concepts is called pseudocode. Each step is shown in a clearly ordered, written structure. A flowchart clearly shows the flow and direction of decisions in a visual way using a diagram. Either way is fine, and it is a matter of personal preference. Basic templates for the flowchart and pseudocode are in Figure 2.7.

英語のヒント

アルゴリズムは、問題を解決するために特定の順番で従わなければならない、手順や指示の並びである。解決に必要な指示を書き出すことで、問題の解決策を記述できる。コンピュータープログラムは通常、特定の作業を行うためにアルゴリズムを実行する。ジャムサンドイッチの例では、ロボットが従ってサンドイッチを作れる指示を書くことが、アルゴリズムの技法に当たる。第3章「データ構造とアルゴリズム」で学ぶように、アルゴリズムは、疑似コードかフローチャートで書くことが最も多い。言葉と高水準のプログラミング概念を組み合わせてアルゴリズムの論理の概要を示したものを、疑似コードという。各手順を、順番が明確な文章の構造で示す。フローチャートは、意思決定の流れと方向を、図によって視覚的にわかりやすく示す。どちらの方法でもよく、好みの問題である。図2.7に、フローチャートと疑似コードの基本的なひな型を示す。

Figure 2.7 Pseudocode lists each step, while a flowchart visually outlines the process of decision-making. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図2.7 疑似コードは各手順を列挙し、フローチャートは意思決定の過程を視覚的に示す。（出典：著作権Rice University、OpenStax。CC BY 4.0ライセンス）

Writing algorithms requires practice. Not everyone likes butter in their jam sandwich. The robot needs a method of making sure it adds or does not add butter, depending on preferences. It is therefore necessary to account for the following steps in the pseudocode and flowchart:

英語のヒント

アルゴリズムを書くには練習が必要である。誰もがジャムサンドイッチにバターを入れたいわけではない。ロボットには、好みに応じてバターを加えるか加えないかを確実にする方法が必要となる。そのため、疑似コードとフローチャートには、次の手順を盛り込む必要がある。

1. Ask whether there should be butter on the bread.

1. パンにバターを塗るべきかどうかを尋ねる。

2. Either spread butter on the bread,

2. パンにバターを塗るか、

3. Or, do not use butter.

3. またはバターを使わない。

These steps can be added as actions in the table previously shown and expressed as steps in the pseudocode using programming keywords such as INPUT, OUTPUT, IF, THEN, ELSE, and START. The corresponding instructions can then be converted into a flowchart using the symbols in Figure 2.8.

英語のヒント

これらの手順は、先ほどの表に動作として追加できる。また、INPUT、OUTPUT、IF、THEN、ELSE、STARTといったプログラミングのキーワードを使い、疑似コードの手順として表せる。対応する指示は、図2.8の記号を使ってフローチャートに変換できる。

Figure 2.8 The symbols used in a flowchart are associated with their instructions. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図2.8 フローチャートで使う記号は、それぞれの指示に対応している。（出典：著作権Rice University、OpenStax。CC BY 4.0ライセンス）

Algorithm Execution Model Patterns

アルゴリズムの実行モデルのパターン

Various patterns of execution models may be used to step through the instructions provided in an algorithm. So far, we have only considered the traditional sequential (i.e., step-by-step) execution model for algorithm instructions. However, it is also possible to leverage parallelism/concurrency and recursion as alternative models to drive the execution of algorithms’ instructions.

英語のヒント

アルゴリズムに記述された指示を順に実行するには、さまざまな実行モデルのパターンを使える。ここまでは、アルゴリズムの指示を一段階ずつ実行する従来の逐次実行モデルだけを考えてきた。しかし、並列性・並行性や再帰を利用して、別のモデルでアルゴリズムの指示を実行させることもできる。

Parallel/concurrent execution models are typically used to optimize algorithm execution efficiency. As an example, if you and a friend are buying tickets for a movie and there are three independent lines, you may opt for a parallel processing model of execution by having you and your friend join two separate lines to buy the tickets. In that case, you are guaranteed to be able to obtain the tickets quicker assuming one of the lines operating in parallel with the other ends up serving customers faster, which is most often the case. Note that executing the same algorithm simultaneously on a computer may not be possible if you only have one central processing unit (CPU) in your machine. In that case, you can simulate parallelism by having the operating system running on the machine execute the two algorithms concurrently as separate tasks while sharing the single processor resources. This approach is less efficient than true parallelism. More detail on the differences between concurrency and parallelism will be provided in Chapter 4 Linguistic Realization of Algorithms: Low- Level Programming Languages.

英語のヒント

並列・並行実行モデルは、通常、アルゴリズムの実行効率を最適化するために使う。たとえば、友人と映画のチケットを買おうとしていて、独立した列が三つあるとする。自分と友人がそれぞれ別の列に並べば、並列処理の実行モデルを選んだことになる。この場合、並行して進む列の一方で、もう一方よりも速く客への対応が進むと仮定すれば、チケットをより早く入手できることが保証される。そして多くの場合、実際にそうなる。ただし、コンピューターに中央処理装置（CPU）が一つしかなければ、同じアルゴリズムを同時に実行することはできない場合がある。その場合は、その機械上で動くオペレーティングシステムに、単一のプロセッサーの資源を共有しながら、二つのアルゴリズムを別々のタスクとして並行に実行させることで、並列性を模擬できる。この方法は、真の並列実行ほど効率的ではない。並行性と並列性の違いは、第4章「アルゴリズムを言語で実現する：低水準プログラミング言語」で詳しく説明する。

Recursive models of execution provide another elegant and effective alternative to the traditional sequential model of execution. The problem-solving technique where a process calls itself in order to solve smaller instances of the same problem is called recursion. It can be a powerful tool in programming because it allows for elegant solutions to complex problems by breaking them down into smaller, more manageable parts. By leveraging recursion, programmers can write concise and efficient code to solve a wide range of problems.

英語のヒント

再帰的な実行モデルは、従来の逐次実行モデルに代わる、別の簡潔で効果的な方法である。同じ問題の、より小さな場合を解くために、処理が自分自身を呼び出す問題解決の技法を、再帰という。複雑な問題をより小さく扱いやすい部分へ分解し、簡潔に解決できるため、プログラミングの強力な道具となりうる。再帰を活用することで、プログラマーは幅広い問題を解く簡潔で効率的なコードを書ける。

One of the key advantages of recursion is its ability to handle complex tasks with minimal code. Instead of writing lengthy iterative loops to solve repetitive tasks, recursion allows programmers to define a process that calls itself with modified input parameters, effectively reducing the amount of code needed. However, it’s essential to be cautious when using recursion, as improper implementation can lead to stack overflow errors due to excessive process calls. Programmers should ensure that recursive processes have proper base cases to terminate the recursion and avoid infinite loops. Example:

英語のヒント

再帰の主な利点の一つは、ごく少ないコードで複雑な作業を扱えることである。繰り返しの作業を解くために長い反復ループを書く代わりに、入力パラメーターを変えて自分自身を呼ぶ処理を定義することで、必要なコード量を効果的に減らせる。ただし、再帰を使うときは注意が必要である。実装が不適切だと、処理の呼び出しが多くなりすぎ、スタックオーバーフローのエラーにつながることがある。プログラマーは、再帰的な処理に適切な基底ケースを設け、再帰が終了し、無限ループを避けられるようにしなければならない。例を示す。

#include <iostream>
using namespace std;


int recursiveSum (int x) {
  // Base case
  if (x == 0) {
    return 0;
  } else {
    // Recursive step
    return x + recursiveSum (x - 1);
  }
}
int main() {
  cout << recursiveSum (10);
  // Answer is 55
  return 0;
}

In this scenario, the process involves gradually adding values to the total variable as you iterate through a loop. However, a different approach involves leveraging computational thinking to deconstruct the problem, breaking it down into smaller subcomponents. This method tackles these subcomponents individually to address the overarching issue. When these smaller parts represent scaled-down versions of the original problem, recursion becomes a valuable tool.

英語のヒント

この場合は、ループを繰り返すにつれて、total変数に値を少しずつ加えていく。しかし、計算論的思考によって問題を分析し、より小さな下位の構成要素に分解する、別の方法もある。この方法では、小さな構成要素を個別に解くことで、全体の問題に対処する。それぞれの小さな部分が元の問題を縮小したものになっているとき、再帰は有用な道具となる。

In practical scenarios, recursion often manifests as a function, which is a set of commands that can be repeatedly executed. It may accept an input and may return an output. The base case represents the function’s most straightforward operation for a given input. To effectively implement recursion, two primary steps must be followed: (a) identify the base case, and (b) outline the recursive steps. In the context of a recursive function, when n is 0, the cumulative sum from 0 to 0 is intuitively 0, representing the most fundamental subproblem of the main issue. Armed with this base case, you can commence crafting the initial part of the function.

英語のヒント

実際の場面では、再帰は関数という形をとることが多い。関数とは、繰り返し実行できる一組の命令である。入力を受け取ったり、出力を返したりすることがある。基底ケースは、与えられた入力に対して関数が行う最も単純な処理を表す。再帰を効果的に実装するには、主に二つの手順に従う必要がある。（a）基底ケースを特定し、（b）再帰の手順の概要を定めることである。再帰関数において、nが0なら、0から0までの累積和は直感的に0となる。これは、中心となる問題の最も基本的な部分問題である。この基底ケースを手がかりに、関数の最初の部分を書き始められる。

int recursiveSum (int x) {
  // Base case
  if (x == 0)
    return 0;
}

Recursion operates through a process of simplification, progressively reducing the value of x until it meets the base condition, where x equals 0. This technique presents an alternative method, offering a refined and effective algorithmic solution for the current problem:

英語のヒント

再帰は単純化の過程によって動作する。xの値を段階的に減らし、xが0に等しいという基底条件に到達させる。この技法は、現在の問題に対して、洗練された効果的なアルゴリズムによる解法を与える、別の方法である。

#include <iostream>
using namespace std;


int recursiveSum (int x) {
  // Base case
  if (x == 0) {
    return 0;
  }
  else {
    // Recursive step
    return x + recursiveSum (x - 1);
  }
}
int main() {
cout << recursiveSum(10); // Output will be the sum = 55.
  return 0;
}

While it looks like recursion amounts to calling the same function repeatedly, it is only partially true, and you should not think about it that way. What happens is much more than repeating the call of a function. It is more useful to think of it as a chain of deferred operations. These deferred operations are not visible in your code or your output—they are in memory. The program needs to hold them somehow, to be able to execute them at the end. In fact, if you had not specified the base case, the recursive process would never end. Figure 2.9 illustrates a flowchart for an iterative solution that adds N numbers.

英語のヒント

再帰は同じ関数を繰り返し呼ぶことにすぎないように見えるが、それは一部しか捉えていない。そのように考えるべきではない。実際に起こることは、単なる関数呼び出しの反復を大きく超えている。後回しにされた処理の連なりと考えるほうが役に立つ。これらの後回しの処理は、コードや出力には見えない。メモリの中にある。プログラムは、最後に実行できるよう、それらを何らかの形で保持しなければならない。実際、基底ケースを指定していなければ、再帰の処理はいつまでも終わらない。図2.9に、N個の数を足す反復による解法のフローチャートを示す。

Figure 2.9 A flowchart represents an iterative solution for adding N numbers. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図2.9 N個の数を足す、反復による解法を表したフローチャート。（出典：著作権Rice University、OpenStax。CC BY 4.0ライセンス）