Name: 0.2 數據結構和算法：計算問題 (0.2 Data Structures and Algorithms: Computational Problems)
Uploaded: 2025-01-06T13:31:52.000Z
Duration: 6 min 33 s

Okay, so let's talk about computational problems and develop a definition for computational problems.

好了，讓我們來談談計算問題，併為計算問題下一個定義。

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.

不過，我們要做得更精確一些，我們將只關注整數。

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

是以，我們不妨將計算問題分解為兩個不同的部分，即輸入數據的結構化集合。

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

讓我們來談談這對我們的分類問題意味著什麼。

是以，我們的輸入是一個數字列表。

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.

好了，現在讓我們對這兩點說得更準確些。

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.

對於任意兩個元素，我們都可以確定其中一個是否在另一個之前。

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?

好吧，那麼我們的第二個標準，即正確解決方案的標準又是什麼呢？

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

剛才我們說的 "有序 "似乎很簡單，但讓我們把它說得更精確一些。

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，如果 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.

其中一個問題是最短路徑問題，在這個問題中，你試圖最小化兩地之間的距離概念。

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.

事實證明，這是一個異常困難的問題。

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.

是以，讓我們來分析一下這三個部分。

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.

好，第三部分是找到正確的解決方案。

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

是以，在 247 的語境中，我們指的是它始終保持 100% 的完全正確。

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.

好了，讓我們來具體看看我們的排序問題，並談談解決這個問題的幾種不同方法。