ancakeswithaproblem：有問題的煎餅-資料下載頁
2025-01-12 07:26本頁面
【正文】 ) = 5 p(4) = 2 p(4) = 1 p(6) =3 A Permutation is a NOUN An ordering S of a stack of pancakes is a permutation. A Permutation is a NOUN. A permutation can also be a VERB. An ordering S of a stack of pancakes is a permutation. We can permute S to obtain a new stack S’. Permute also means to rearrange so as to obtain a permutation of the original. Permute A Permutation. I start with a permutation S of pancakes. I continue to use a flip operation to permute my current permutation, so as to obtain the sorted permutation. There are n! = 1*2*3*4*…*n permutations on n elements. Easy proof in the first counting lecture. Pancake Network: Definition For n! Nodes For each node, assign it the name of one of the n! stacks of n pancakes. Put a wire between two nodes if they are one flip apart. Network For n=3 123 321 213 312 231 132 Network For n=4 Pancake Network: Message Routing Delay What is the maximum distance between two nodes in the work? Pn Pancake Network: Reliability If up to n2 nodes get hit by lightning the work remains connected, even though each node is connected to only n1 other nodes. The Pancake Network is optimally reliable for its number of edges and nodes. Mutation Distance High Level Point Computer Science is not merely about puters and programming, it is about mathematically modeling our world, and about finding better and better ways to solve problems. This lecture is a microcosm of this exercise. One “Simple” Problem A host of problems and applications at the frontiers of science Study Bee Please read the course document carefully. You must hand in a signed cheating policy page. Study Bee Definitions of: nth pancake number lower bound upper bound permutation Proof of: ANY to ANY in ≤ Pn Important Technique: Bracketing References Bill Gates amp。 Christos Papadimitriou: Bounds For Sorting By Prefix Reversal. Discrete Mathematics, vol 27, pp 4757, 1979. H. Heydari amp。 H. I. Sudborough: On the Diameter of he Pancake Network. Journal of Algorithms, vol 25, pp 6794, 1997
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1