So we won't dwell on a formal definition, that'll be covered in other courses like 347 and 547.

正式な定義については、347や547のような他のコースで学ぶことにしよう。

So informally, for our class, a computational problem describes a problem that has a structured collection of input data and criteria for correct solution.

だから非公式に、我々のクラスでは、計算問題とは、構造化された入力データの集まりと正しい解の基準を持つ問題を表す。

Okay, so let's look at an example computational problem.

では、計算問題の例を見てみよう。

So we're going to be looking at sorting as our first computational problem.

そこで、最初の計算問題としてソートを取り上げることにする。

So this applies to the example problem that we've already discussed.

つまり、これはすでに説明した例の問題に当てはまる。

You've got a big pile of books, you want to put it into order, you could sort it.

山積みになった本を整理したい。

So a lot of libraries use call numbers that are numbers, literally.

だから、多くの図書館では、文字通り数字であるコールナンバーを使っている。

So a sorting process that works with numbers seems like an appropriate choice.

だから、数字を扱うソート・プロセスは適切な選択のように思える。

We're going to be even more precise, though, we're going to focus just on integers.

ここではさらに正確に、整数だけに焦点を絞ることにする。

Okay, so sorting, sorting.

オーケー、では仕分け、仕分け。

So let's break the idea of a computational problem down into its two different parts, a structured collection of input data.

そこで、計算問題の考え方を、構造化された入力データの集まりという2つの異なる部分に分解してみよう。

And let's talk about what that means for our sorting problem.

そして、それが我々のソーティング問題にとって何を意味するかについて話そう。

So our input is a list of numbers.

つまり、入力は数字のリストだ。

But what does that mean?

しかし、それは何を意味するのか？

What do we mean by list?

リストとはどういう意味か？

Do we mean an array?

配列のことか？

Do we mean a linked list?

リンクリストのことか？

We need to be more precise.

もっと正確に言う必要がある。

We'll come back to that in just a second.

この話はまた後で。

But before we do, let's also think about our criteria for a correct solution.

しかし、その前に、正しい解決策の基準についても考えておこう。

Sorted seems pretty straightforward, right?

並べ替えは簡単だろう？

But again, we'll be a little bit more precise.

しかし、もう少し正確に言おう。

Okay, so now let's be more precise about both of those points.

では、この2点についてより正確に説明しよう。

So a structured collection of input data, what we really mean in this case today is an array of data.

つまり、構造化された入力データの集合体であり、今日このケースで本当に意味するのはデータの配列である。

And we want data that is of a data type that is totally orderable.

そして、完全にオーダー可能なデータ型のデータが欲しい。

Okay, so what this means is in terms of discrete math, the data type must be able to be a total order.

つまり、離散的な数学の場合、データ型は合計オーダーでなければならないということだ。

So a total order is a type that is a total order, is something that basically has the notion of a less than or equal to operation.

つまり、トータル・オーダーとは、基本的に小なりか等しいという概念を持つものである。

For any two elements, we can determine if one of them comes before the other one.

任意の2つの要素について、一方が他方より前に来るかどうかを判断することができる。

So there's some clear way to answer the question, does x come before y?

つまり、xはyの前に来るのか？

Okay, so let's be even more precise in our problem definition.

では、問題の定義をさらに正確にしよう。

Our structured collection of input data is an input array of integers, okay?

構造化された入力データのコレクションは、整数の入力配列だ。

Okay, so what about our second criteria, the criteria for correct solution?

では、2つ目の基準、正解の基準はどうだろう？

Earlier, we just said ordered seems simple enough, but let's be even more precise with that.

先ほど、注文は単純だと言ったが、さらに正確に言おう。

In fact, we overlooked something.

実は、私たちはあることを見落としていた。

Not only should it be sorted, ordered, it should contain the same values.

ソートされ、順番に並んでいるだけでなく、同じ値が含まれていなければならない。

So in a sense, we want some idea of the conservation of data.

つまり、ある意味、データの保存についてある程度の考えが欲しいのだ。

We don't wanna create or destroy data in our output data, okay?

出力データの中にデータを作ったり壊したりしたくないんだ。

And of course, the data should be sorted.

そしてもちろん、データはソートされていなければならない。

But we can fall back to our definition of a total order for our definition of sorted.

しかし、並べ替えの定義については、全順序の定義に立ち返ることができる。

Basically, for any two elements, x and y, if x is less than y, if x comes before y, we would expect x to come before y in our final array.

基本的に、xとyの2つの要素について、xがyより小さい場合、xがyより前に来る場合、最終的な配列ではxがyより前に来ることになる。

Okay, there are lots of other examples of computational problems that are really interesting, and many of them are pervasive in computer science.

さて、本当に興味深い計算問題の例は他にもたくさんあり、その多くはコンピュータ・サイエンスに広く浸透している。

So one of them is the shortest path problem, where you're trying to minimize some concept of distance between two places.

そのひとつが最短経路問題で、2つの場所間の距離を最小化しようとするものだ。

Could also be time between two places.

また、2つの場所の間の時間である可能性もある。

So Google Maps oftentimes does shortest path sorts of problems.

だからグーグルマップはしばしば最短経路のような問題を起こす。

Famous computer science problem is called the traveling salesperson problem.

有名なコンピュータサイエンスの問題に巡回販売員問題がある。

In the traveling salesperson problem, there's a salesperson who's going to travel amongst multiple cities and then return home.

巡回セールスマンの問題では、複数の都市を巡回して帰国するセールスマンがいる。

And the goal is to find a path amongst all those cities that's as short as possible, maybe takes as little time as possible or uses as little gas as possible, so on.

そしてゴールは、それらの都市の間で、できるだけ短い、あるいはできるだけ時間のかからない、あるいはできるだけガソリンを使わない経路を見つけることだ。

In fact, there are a whole bunch of different types of optimization problems that try and minimize a cost of some sort or maximize profit of some sort.

実際、ある種のコストを最小化したり、ある種の利益を最大化しようとする最適化問題には、さまざまな種類がある。

There are all sorts of subtle variations on the idea of minimization and maximization that all fall into the class of optimization problems.

最適化問題には、最小化と最大化という考え方にさまざまな微妙なバリエーションがある。

Another interesting class of problems is factoring.

もう一つの興味深い問題は、因数分解である。

So factoring prime numbers is an important part of modern cryptography.

つまり、素数の因数分解は現代暗号の重要な部分なのだ。

Another really interesting problem is called the halting problem.

もうひとつ、ハルティング問題と呼ばれる非常に興味深い問題がある。

So the basic premise of the halting problem is you've got some sort of a finite computer program.

つまり、ハルティング問題の大前提は、ある種の有限なコンピューター・プログラムを持っているということだ。

Basically, you're given a piece of code and you have to identify whether the code will ever finish or not on a given input set.

基本的には、コードの断片が与えられ、与えられた入力セットでそのコードが終了するかどうかを識別しなければならない。

It turns out that that's an unusually hard problem.

それが異常に難しい問題であることがわかった。

More on that in just a second.

それについてはまた後ほど。

Okay, so let's talk about our next major component here, an algorithm.

では、次の主要コンポーネントであるアルゴリズムについて話そう。

An algorithm is something that will solve a computational problem.

アルゴリズムとは、計算問題を解くものである。

So the term algorithm is named after a 9th century mathematician, one of the people who helped foster the numeric system that we currently use.

アルゴリズムという言葉は、9世紀の数学者にちなんで名付けられた。

The basic definition of an algorithm is that it's an effective procedure for taking any instance of a computational problem and finding a correct solution.

アルゴリズムの基本的な定義は、計算問題の任意のインスタンスを取り上げ、正しい解を見つけるための効果的な手順であるということだ。

So let's break down all three of those parts.

では、その3つのパーツを分解してみよう。

So first off, it's an effective procedure.

だからまず、効果的な処置なんだ。

What we really mean by that is this is something that can be turned into a computer program.

私たちが本当に言いたいのは、これはコンピュータープログラムに変えることができるものだということだ。

That halting problem that was mentioned just a minute ago, it turns out there's no real way to convert that into an algorithm, into a computer program.

先ほどのハルティング問題は、アルゴリズムやコンピュータープログラムに変換する方法がないことがわかった。

Our second point, for taking any instance of a computational problem.

第二のポイントは、計算問題のどのようなインスタンスでもよいということだ。

So that means that any valid input set should work, any.

つまり、有効な入力セットであれば、どんなものでも機能するはずだ。

Not just some, it shouldn't just work on some input sets, it should work on any.

一部の入力セットだけでなく、どの入力セットでも機能するはずだ。

Okay, and our third component, finding a correct solution.

そして3つ目の要素、正解を見つけることだ。

So in the context of 247, we mean it's 100% perfectly correct all the time.

つまり、247の文脈では、常に100％完璧に正しいということだ。

Not almost, not probably.

ほとんどでもなく、おそらくでもない。

In some contexts in computer science, we're looking for things that are probabilistically correct.

コンピュータ・サイエンスのある文脈では、私たちは確率的に正しいものを探している。

It's not the case for our definition in 247.

247での定義はそうではない。

Okay, so with that, let's take a concrete look at our sorting problem and talk about a couple of different ways it could be solved.

さて、それではソート問題を具体的に見て、それを解決するいくつかの異なる方法について話してみよう。