1 00:00:00,298 --> 00:00:09,167 Hello everyone,we start to learn the Data Structures and Algorithms courses. 2 00:00:09,167 --> 00:00:18,804 In this section,we firstly introduce a very important concept in Data Structures and Algorithms, that is problem solving. 3 00:00:18,804 --> 00:00:24,080 Data Structures and Algorithms mainly focus on problem solving. 4 00:00:24,080 --> 00:00:29,987 Firstly, what is the purpose of writing computer programs? 5 00:00:29,987 --> 00:00:39,929 Our goal is to solve some problems that occurs in daily life or school life. 6 00:00:39,929 --> 00:00:43,263 How to express this problem ? 7 00:00:43,263 --> 00:00:54,796 Generally speaking, we'll give you some data input,then results can be got after the processing of your program. 8 00:00:54,796 --> 00:01:01,285 How to describe the problem? 9 00:01:01,285 --> 00:01:12,807 We need a data structure to describe the relationship between data of this problem. 10 00:01:12,807 --> 00:01:31,911 After getting the data struture,which is also mathematical model, we can use corresponding algorithms to process the data appropriately and finally get an answer. 11 00:01:31,911 --> 00:01:40,342 That is the process of transforming from question to data then to algorithm. 12 00:01:40,342 --> 00:01:51,253 The programming is implemented by the interaction between data structure and algorithms. 13 00:01:51,253 --> 00:01:58,531 In other words, algorithms can be included in the definition of data. 14 00:01:58,531 --> 00:02:11,813 For example, in the description of Object-Oriented programming ,methods of how to process data can be implemented by using member function in object. 15 00:02:11,813 --> 00:02:17,660 Our data structure can not be separated from data structure as well. 17 00:02:17,660 --> 00:02:24,554 Data structure consists of logic、storage and operation. 18 00:02:24,554 --> 00:02:29,597 In fact, the operation can be seen as the algorithms. 19 00:02:29,597 --> 00:02:39,176 We look at an example and use it to understand the whole process of problem solving. 20 00:02:39,176 --> 00:02:45,317 The farmer accross the river problem is described as below: 21 00:02:45,317 --> 00:02:57,234 At first, one bank of the river is empty while there are three things on the other side of the bank, that is a wolf,a sheep and some vegetables. 22 00:02:57,234 --> 00:03:09,509 The farmer rows a boat, and the boat can load one thing at one point, the farmer is not included of course. 23 00:03:09,509 --> 00:03:18,310 The farmer takes one thing to across the river and then returns. 24 00:03:18,310 --> 00:03:23,033 He can take one thing back or returns with an empty boat. 25 00:03:23,033 --> 00:03:31,026 The farmer constraints these three things. 26 00:03:31,026 --> 00:03:46,384 It means that, these things remains safe altogether while the farmer is beside. But when the farmer is not beside, wolf can not stay with the sheep and the sheep can not stay with the vegetables. 27 00:03:46,384 --> 00:04:06,170 We need to describe all the constraints of the problem to describe it. 31 00:04:06,170 --> 00:04:09,291 Then how to describe the data structure? 32 00:04:09,291 --> 00:04:15,940 We can stand in the view of the original bank to think about this problem. 33 00:04:15,940 --> 00:04:27,403 It means the status of the original bank will be changed from farmer,sheep,wolf,vegetables to empty. 34 00:04:27,403 --> 00:04:33,072 That is to say, all the things are transfered successfully to the opposite side of the original bank include the farmer. 35 00:04:33,072 --> 00:04:45,797 In the process of transfering, the statuses of the two banks will be changed, then which statuses are reasonable? 36 00:04:45,797 --> 00:04:55,352 There is a constraint that wolf and sheep can not stay alone, as well as sheep and vegetables. 37 00:04:55,352 --> 00:05:01,889 The complementary set of it is that the farmer can not stay alone with the vegetables, as well as the farmer and the wolf. 38 00:05:01,889 --> 00:05:05,796 On the other hand, sheep,wolf and vegetables can not stay together without the farmer beside. 39 00:05:05,796 --> 00:05:11,888 Six unreasonable status can be got then. 40 00:05:11,888 --> 00:05:19,809 Besides, there are initial-state and end-state, the other statuses are reasonable. 41 00:05:19,809 --> 00:05:29,016 Ten statuses are finally got at last. And how are these ten statuses associate with each other? 42 00:05:29,016 --> 00:05:38,614 The statuses are associated by the transferring of the farmer or the famerr rows the empty boat to come and return. 43 00:05:38,614 --> 00:05:48,902 So every time the farmer across the river reasonably, these statuses are associated. 44 00:05:48,902 --> 00:05:58,053 For example, for the original status,if the farmer transfer the sheep to the opposite side of the bank, then wolf and vegetables are left. 45 00:05:58,053 --> 00:06:11,461 Then the farmer rows the empty boat back, the status of the original bank is changed to farmer,wolf and vegetables, that is reasonable too. 46 00:06:11,461 --> 00:06:21,567 All the reasonable transferring can be seen as the connection of the corresponding nodes. 47 00:06:21,567 --> 00:06:28,509 We connect the lines with deep colour, and get the answer of this problem. 48 00:06:28,509 --> 00:06:35,456 It means the farmer,sheep,wolf and vegetables is the initial-state. 49 00:06:35,456 --> 00:06:39,155 Then the farmer takes the sheep to the opposite side of the bank, with the wolf and vegetables left. 50 00:06:39,155 --> 00:06:46,614 Then the farmer rows the empty boat back, and the status of the original bank is changed to farmer,wolf and vegetables. 51 00:06:46,614 --> 00:06:59,788 Then the farmer takes the wolf with him, and takes the sheep back, then the status of the original bank is changed to farmer,shhep and vegetables. 52 00:06:59,788 --> 00:07:07,758 Then the vegetables are taken to the opposite side of the bank, then the status of the opposite bank is changed to farmer,wolf and vegetables. 53 00:07:07,758 --> 00:07:17,249 The farmer then comes back and transfer the sheep and finally finish the work of transferring. 54 00:07:17,249 --> 00:07:26,273 Our data structure can be described by an adjacent matrix. 55 00:07:26,273 --> 00:07:41,308 All the reasonable nodes can be seen as position of one column or one row of the matrix. 56 00:07:41,308 --> 00:07:52,037 The position between one row and one column means that a correlation happens between two statuses. 57 00:07:52,037 --> 00:08:00,286 For example,accoring to the sequential number we arranged here, it is the first node. 58 00:08:00,286 --> 00:08:09,459 Farmer,wolf,sheep and vegetables is the first node, while wolf and vegetables is the sixth node, there is an edge between them. 59 00:08:09,459 --> 00:08:17,118 Accordingly, there is a value one in the sixth row of the first column. 60 00:08:17,118 --> 00:08:20,907 If there is no association, the value will be zero. 61 00:08:20,907 --> 00:08:24,443 In that way, we build a data structure. 62 00:08:24,443 --> 00:08:29,210 The data structure can be expressed very well in the memory of our computer. 63 00:08:29,210 --> 00:08:36,113 Then we'll try to find solutions for the data structure. 64 00:08:36,113 --> 00:08:50,058 The process is to find an accessible path of the graph structure from the initial-state to the end-state. 65 00:08:50,058 --> 00:08:55,885 In the data structures of computer, we mostly concerns about finding the best solution, that is to find the shortest path. 66 00:08:55,885 --> 00:09:05,530 In the section of graph, we'll introduce the algorithm of Dijkstra to figure it out, so it will not be introduced here. 67 00:09:05,530 --> 00:09:26,016 We introduce this example mainly to show you when a problem comes about, how to analyse the problem and construct a reasonable data structure to describe the association between data of the problem. 68 00:09:26,016 --> 00:09:39,881 Then we find a classical algorithm or we redesign an appropriate algorithm to solve the problem and programming implementation is the final part of the process. 69 00:09:39,881 --> 00:09:57,424 Your can think about what are the process of the Problem Abstration,Data Abstraction and Algorithm Abstraction? 70 00:09:57,424 --> 00:10:10,715 Besides, if you analyse one problem in different ways, you may get different data structures. 71 00:10:10,715 --> 00:10:15,637 Different algorithms will be needed accordingly. 72 00:10:15,637 --> 00:10:18,557 You can also think about if there are some other solution for the farmer across the river problem. 73 00:10:18,557 --> 00:10:19,270 Thank you!