 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 4 | 1/1 | 返回列表 |
| 查看: 1254 | 回復: 3 | ||
| 【獎勵】 本帖被評價2次，作者conanwj增加金幣 2 個 | ||
[資源]
【分享】How to think about algorithms.Jeff Edmonds.Cambridge.2008[New]
|
||
|
本資源來自于互聯(lián)網，僅供學習研究之用，不可涉及任何商業(yè)用途，請在下載后24小時內刪除。 著作權歸原作者或出版社所有。未經發(fā)貼人conanwj許可，嚴禁任何人以任何形式轉貼本文，違者必究！ How to think about algorithms. Authors Jeff Edmonds Publisher: 2008 Cambridge University Press Pages: 462 ISBN 13: ISBN-13 978-0-511-41370-4 eBook (EBL) ISBN-13 978-0-521-84931-9 hardback ISBN-13 978-0-521-61410-8 paperback Introduction From determining the cheapest way to make a hot dog to monitoring the workings of a factory, there are many complex computational problems to be solved. Before executable code can be produced, computer scientists need to be able to design the algorithms that lie behind the code, be able to understand and describe such algorithms abstractly, and be confident that they work correctly and efficiently. These are the goals of computer scientists. A Computational Problem: A specification of a computational problem uses preconditions and postconditions to describe for each legal input instance that the computation might receive, what the required output or actions are. This may be a function mapping each input instance to the required output. It may be an optimization problem which requires a solution to be outputted that is “optimal” from among a huge set of possible solutions for the given input instance. It may also be an ongoing system or data structure that responds appropriately to a constant stream of input. Example: The sorting problem is defined as follows: Preconditions: The input is a list of n values, including possible repetitions. Postconditions: The output is a list consisting of the same n values in nondecreasing order. An Algorithm: An algorithm is a step-by-step procedure which, starting with an input instance, produces a suitable output. It is described at the level of detail and abstraction best suited to the human audience that must understand it. In contrast, code is an implementation of an algorithm that can be executed by a computer. Pseudocode lies between these two. An Abstract Data Type: Computers use zeros and ones, ANDs and ORs, IFs and GOTOs. This does not mean that we have to. The description of an algorithm may talk of abstract objects such as integers, reals, strings, sets, stacks, graphs, and trees; abstract operations such as “sort the list,” “pop the stack,” or “trace a path”; and abstract relationships such as greater than, prefix, subset, connected, and child. To be useful, the nature of these objects and the effect of these operations need to be understood. However, in order to hide details that are tedious or irrelevant, the precise implementations of these data structure and algorithms do not need to be specified. Formore on this see Chapter 3. Correctness: An algorithm for the problem is correct if for every legal input instance, the required output is produced. Though a certain amount of logical thinking is requireds, the goal of this text is to teach how to think about, develop, and describe algorithms in such way that their correctness is transparent. See Chapter 28 for the formal steps required to prove correctness, and Chapter 22 for a discussion of forall and exist statements that are essential formaking formal statements. Running Time: It is not enough for a computation to eventually get the correct answer. It must also do so using a reasonable amount of time and memory space. The running time of an algorithm is a function from the size n of the input instance given to a bound on the number of operations the computation must do. (See Chapter 23.) The algorithm is said to be feasible if this function is a polynomial like Time(n) = (n2), and is said to be infeasible if this function is an exponential like Time(n) = (2n). (See Chapters 24 and 25 formore on the asymptotics of functions.) To be able to compute the running time, one needs to be able to add up the times taken in each iteration of a loop and to solve the recurrence relation defining the time of a recursive program. (See Chapter 26 for an understanding of n i=1 i = (n2), and Chapter 27 for an understanding of T(n) = 2T(n2 ) +n = (n logn).) Meta-algorithms: Most algorithms are best described as being either iterative or recursive. An iterative algorithm (Part One) takes one step at a time, ensuring that each step makes progress whilemaintaining the loop invariant. A recursive algorithm (Part Two) breaks its instance into smaller instances, which it gets a friend to solve, and then combines their solutions into one of its own. Optimization problems (Part Three) form an important class of computational problems. The key algorithms for them are the following. Greedy algorithms (Chapter 16) keep grabbing the next object that looks best. Recursive backtracking algorithms (Chapter 17) try things and, if they don’t work, backtrack and try something else. Dynamic programming (Chapter 18) solves a sequence of larger and larger instances, reusing the previously saved solutions for the smaller instances, until a solution is obtained for the given instance. Reductions (Chapter 20) use an algorithm for one problem to solve another. Randomized algorithms (Chapter 21) flip coins to help them decide what actions to take. Finally, lower bounds (Chapter 7) prove that there are no faster algorithms. 本資源共7個可選網絡硬盤鏈接，6.04 MB，保質期2009-07-15。 ---------------------------------------------------------------------------- How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf How to think about algorithms.Jeff Edmonds.Cambridge.2008.pdf ---------------------------------------------------------------------------- |
回復此樓» 猜你喜歡
環(huán)境工程 085701，267求調劑
已經有14人回復
-
308求調劑
已經有12人回復
-
求調劑：085600材料與化工，考材科基，總分319
已經有21人回復
-
311求調劑
已經有8人回復
-
294分080500材料科學與工程求調劑
已經有13人回復
-
288求調劑 一志愿哈工大 材料與化工
已經有19人回復
-
288資源與環(huán)境專碩求調劑，不限專業(yè)，有學上就行
已經有23人回復
-
一志愿085600中科院寧波所276分求調劑
已經有17人回復
-
271求調劑
已經有11人回復
-
環(huán)境工程297分求調劑一志愿杭高院
已經有10人回復
» 本主題相關價值貼推薦，對您同樣有幫助:
- how to make our oral fluent series:exam
已經有20人回復
- how to make our oral fluent series:some interrogative sentences
已經有22人回復
- How_to_Write_a_Paper
已經有14人回復
- 【How to say】系列之---還是那樣牙尖嘴利��！~
已經有11人回復
- How do u think about it ?
已經有30人回復
- How do you think about the death of Mr. Osama bin laden?
已經有10人回復
- How do you think about the relationship between pressure and homesickness
已經有14人回復
- How do you think about your work and life?
已經有11人回復
- 【Discussion】How do you think about this sentence?
已經有6人回復
- 【Discussion】What topic do you think do you prefer to talk about during a date?
已經有14人回復
- Happy dragon boat festival to everyone!How about your vacation?
已經有20人回復
- 【分享】How to write SCI papers (朱興全教授-2009)(ppt)【已搜索無重復】
已經有15人回復
2樓2009-06-25 17:31:07
3樓2009-06-25 23:38:35
4樓2010-05-04 19:09:59
相關版塊跳轉
我要訂閱樓主 conanwj 的主題更新
| 4 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 311求調劑 +8 | 李芷新1 2026-03-31 | 8/400 |
|
|---|---|---|---|---|
|
[考研] 材料專碩306英一數(shù)二 +3 | z1z2z3879 2026-03-31 | 3/150 |
|
|
|
[論文投稿]
chinese chemical letters英文版投稿求助
 130+4
|
Yishengeryi 2026-03-30 | 4/200 |
|
|
|
[考研] 08開頭看過來�。�！ +3 | wwwwffffff 2026-03-31 | 5/250 |
|
|
|
[考研] 生物學296求調劑 +8 | 湯圓包 2026-03-29 | 12/600 |
|
|
|
[考研] 322求調劑：一志愿湖南大學 材料與化工（085600），已過六級。 +10 | XX小鄧 2026-03-29 | 10/500 |
|
|
|
[考研] 0856 335分 | 封裝or激光加工 老師看看我！！ +9 | cccchenso 2026-03-29 | 9/450 |
|
|
|
[考研] 343求調劑 +8 | 愛羈絆 2026-03-28 | 8/400 |
|
|
|
[考研] 353求調劑 +3 | 江上楓_26 2026-03-28 | 3/150 |
|
|
|
[考研] 277跪求調劑 +8 | 1915668 2026-03-27 | 13/650 |
|
|
|
[考研] 本科211安全工程，初試290分，求調劑 +3 | 2719846834 2026-03-28 | 3/150 |
|
|
|
[考研] 0817化工學碩調劑 +7 | 努力上岸中！ 2026-03-31 | 7/350 |
|
|
|
[考研] 297 地理學070500 復試求調劑 +3 | 小圓圈圈ooo 2026-03-30 | 3/150 |
|
|
|
[考研] 一志愿北京化工大學材料與化工（085600）296求調劑 +25 | 稻妻小編 2026-03-26 | 25/1250 |
|
|
|
[考研] 0703化學求調劑 +6 | 丹青奶蓋 2026-03-26 | 8/400 |
|
|
|
[考研] 0703 化學 求調劑，一志愿山東大學 342 分 +7 | Shern—- 2026-03-28 | 7/350 |
|
|
|
[考研] 290求調劑 +3 | dfffsar 2026-03-29 | 3/150 |
|
|
|
[考研] 08開頭275求調劑 +4 | 拉誰不重要 2026-03-26 | 4/200 |
|
|
|
[考研] 081200-11408-276學碩求調劑 +3 | 崔wj 2026-03-26 | 3/150 |
|
|
|
[考研] 07化學303求調劑 +5 | 睿08 2026-03-25 | 5/250 |
|