离散数学北京邮电大学

1、Algorithms,Rosen 6th ed., 3.1,Abu al-Khowarizmi (ca. 780-850),Chapter 3: More Fundamentals,3.1: Algorithms Formal procedures 3.2: Growth of Functions 3.3: Complexity of algorithms Analysis using order-of-growth notation. 3.4: The Integers otherwise, just skip on ahead to the next statement after the

2、 if statement. Variant: if cond then stmt1 else stmt2 Like before, but iff truth value is False, executes stmt2.,while condition statement,Evaluate the propositional (Boolean) expression condition. If the resulting value is True, then execute statement. Continue repeating the above two actions over

3、and over until finally the condition evaluates to False; then proceed to the next statement.,while condition statement,Also equivalent to infinite nested ifs, like so: if condition begin statement if condition begin statement (continue infinite nested ifs) end end,for var := initial to final stmt,In

4、itial is an integer expression. Final is another integer expression. Semantics: Repeatedly execute stmt, first with variable var := initial, then with var := initial+1, then with var := initial+2, etc., then finally with var := final. Question: What happens if stmt changes the value of var, or the v

5、alue that initial or final evaluates to?,for var := initial to final stmt,For can be exactly defined in terms of while, like so:,begin var := initial while var final begin stmt var := var + 1 end end,procedure(argument),A procedure call statement invokes the named procedure, giving it as its input t

6、he value of the argument expression. Various real programming languages refer to procedures as functions (since the procedure call notation works similarly to function application f(x), or as subroutines, subprograms, or methods.,Max procedure in pseudocode,procedure max(a1, a2, , an: integers) v :=

7、 a1 largest element so far for i := 2 to n go thru rest of elems if ai v then v := ai found bigger? at this point vs value is the same as the largest integer in the list return v,Inventing an Algorithm,Requires a lot of creativity and intuition Like writing proofs. Unfortunately, we cant give you an

8、 algorithm for inventing algorithms. Just look at lots of examples And practice (preferably, on a computer) And look at more examples And practice some more etc., etc.,Algorithm-Inventing Example,Suppose we ask you to write an algorithm to compute the predicate: IsPrime:NT,F Computes whether a given

9、 natural number is a prime number. First, start with a correct predicate-logic definition of the desired function: n: IsPrime(n) 1 n1/2 then b n1/2 (since a is ns smallest divisor) and so n = ab (n1/2)2 = n, an absurdity.,Further optimizations are possible: - E.g., only try divisors that are primes

10、less than n1/2.,Note smaller range of search.,Another example task,Problem of searching an ordered list. Given a list L of n elements that are sorted into a definite order (e.g., numeric, alphabetical), And given a particular element x, Determine whether x appears in the list, and if so, return its

11、index (position) in the list. Problem occurs often in many contexts. Lets find an efficient algorithm!,Search alg. #1: Linear Search,procedure linear search (x: integer, a1, a2, , an: distinct integers) i := 1 start at beginning of list while (i n x ai) not done, not found i := i + 1 go to the next

12、position if i n then location := i it was found else location := 0 it wasnt found return location index or 0 if not found,Search alg. #2: Binary Search,Basic idea: On each step, look at the middle element of the remaining list to eliminate half of it, and quickly zero in on the desired element.,x,c2

13、cr;n: a positive integer) For i:=1 to r while nci begin add a coin with value ci to the change n:=n-ci end,The Halting Problem (Turing36),The halting problem was the first mathematical function proven to have no algorithm that computes it! We say, it is uncomputable. The desired function is Halts(P,

14、I) : the truth value of this statement: “Program P, given input I, eventually terminates.” Theorem: Halts is uncomputable! I.e., there does not exist any algorithm A that computes Halts correctly for all possible inputs. Its proof is thus a non-existence proof. Corollary: General impossibility of pr

15、edictive analysis of arbitrary computer programs.,Alan Turing 1912-1954,停机问题Halting Problem,一个实际问题： 给定一个算法和相应的输入，判定这个算法是否能够完成？（还是进入死循环不能完成？） 由于算法都可以用图灵机描述，所以问题转变为，给定一个图灵机和相应的输入，判定是否停机？ 对于特定的算法，我们大概是可以判定的，但是否存在对一般的算法进行判定的方法？ 程序正确性证明：包括了给一段程序，判断这段程序是否会进入死循环 注意：这个方法本身也是一个算法，否则没有意义,停机问题,是否有算法能够判定某个图灵机M在

16、输入I下是否停机？ 即Halt(M,I)=True iif M在I处停机，False iif M在I处不停机 答案是否定的，不存在这样的算法 停机问题是不可计算问题,停机问题证明,假设存在这样的算法，对应的图灵机是Halt(a,k)，a是要判定的图灵机编码，k是输入的编码 我们构造这么一个图灵机Trouble(a) function Trouble(a) if Halt(a, a) = False then return True else loop forever Trouble图灵机自然也可以编码，记为t，我们来看把t作为Trouble输入会怎么样？ Trouble(t)=?,停机问题证明

17、,矛盾？矛盾！ 如果Trouble(t)停机返回了，也就是Halt(t,t)=False，但这样是说Trouble(t)不停机，矛盾 如果Trouble(t)不停机，也就是Halt(t,t)返回了True，但这样却是说Trouble(t)能停机，矛盾 消除矛盾的唯一途径就是否定假设，即不存在能一般性地判定图灵机停机的算法 人的智能就能解决停机问题么？至少目前还是否 对于太长的算法，或者输入太复杂的算法，不能 对于一些短而简单的算法，也不能（一些数论难题） 寻找大于给定N的孪生素数,Review 3.1: Algorithms,Characteristics of algorithms. Pse

18、udocode. Examples: Max algorithm, primality-testing, linear search & binary search algorithms. Sorting. Intuitively we see that binary search is much faster than linear search, but how do we analyze the efficiency of algorithms formally? Use methods of algorithmic complexity, which utilize the order

19、-of-growth concepts from 3.3.,Orders of Growth,Rosen 6th ed., 3.2,Orders of Growth (3.2),For functions over numbers, we often need to know a rough measure of how fast a function grows. If f(x) is faster growing than g(x), then f(x) always eventually becomes larger than g(x) in the limit (for large e

20、nough values of x). Useful in engineering for showing that one design scales better or worse than another.,Orders of Growth - Motivation,Suppose you are designing a web site to process user data (e.g., financial records). Suppose database program A takes fA(n)=30n+8 microseconds to process any n rec

21、ords, while program B takes fB(n)=n2+1 microseconds to process the n records. Which program do you choose, knowing youll want to support millions of users?,A,Visualizing Orders of Growth,On a graph, as you go to the right, the faster- growing func- tion always eventually becomes the larger one.,fA(n

22、)=30n+8,Increasing n ,fB(n)=n2+1,Value of function ,Example:,f(n) = 100 n2, g(n) = n4, the following table and figure show that g(n) grows faster than f(n) when n 10. We say f is big-Oh of g.,Concept of order of growth,We say fA(n)=30n+8 is (at most) order n, or O(n). It is, at most, roughly proport

23、ional to n. fB(n)=n2+1 is order n2, or O(n2). It is (at most) roughly proportional to n2. Any function whose exact (tightest) order is O(n2) is faster-growing than any O(n) function. Later we will introduce for expressing exact order. For large numbers of user records, the exactly order n2 function

24、will always take more time.,Definition: O(g), at most order g,Let g be any function RR. Define “at most order g”, written O(g), to be: f:RR | c,k: xk: f(x) cg(x). “Beyond some point k, function f is at most a constant c times g (i.e., proportional to g).” “f is at most order g”, or “f is O(g)”, or “

25、f=O(g)” all just mean that fO(g). Often the phrase “at most” is omitted.,Points about the definition,Note that f is O(g) so long as any values of c and k exist that satisfy the definition. But: The particular c, k, values that make the statement true are not unique: Any larger value of c and/or k wi

26、ll also work. You are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest values!),However, you should prove that the values you choose do work.,“Big-O” Proof Examples,Show that 30n+8 is O(n). Show c,k: nk: 30n+8 cn. Let c=31, k=8. Assume nk=8

27、. Then cn = 31n = 30n + n 30n+8, so 30n+8 k: n2+1 cn2. Let c=2, k=1. Assume n1. Then cn2 = 2n2 = n2+n2 n2+1, or n2+10). It isnt even less than 31n everywhere. But it is less than 31n everywhere to the right of n=8.,Big-O example, graphically,Increasing n ,Value of function ,n,30n+8,30n+8 O(n),Useful

28、 Facts about Big O,Big O, as a relation, is transitive: fO(g) gO(h) fO(h) O with constant multiples, roots, and logs. f (in (1) & constants a,bR, with b0, af, f 1-b, and (logb f)a are all O(f). Sums of functions: If gO(f) and hO(f), then g+hO(f).,More Big-O facts,c0, O(cf)=O(f+c)=O(fc)=O(f) f1O(g1)

29、f2O(g2) f1 f2 O(g1g2) f1+f2 O(g1+g2) = O(max(g1,g2) = O(g1) if g2O(g1) (Very useful!),Example,If f1 is O(g1) and f2 is O(g2) then f1f2 is O(g1g2) f1 + f2 is O(max g1, g2),Proof of f1f2 is O(g1g2),There is a k1 and c1 such that 1. f1(n) k1. There is a k2 and c2 such that 2. f2(n) k2. We must find a k

30、3 and c3 such that 3. f1(n)f2(n) k3.,Proof of f1f2 is O(g1g2),We use the inequality if 0 maxk1, k2 so that both inequalities 1 and 2. hold at the same time. Therefore, choose c3 = c1c2 and k3 = maxk1, k2. Q. E. D.,Orders of Growth,For any g:RR, “at most order g”, O(g) f:RR | c,k xk |f(x)| |cg(x)|. O

31、ften, one deals only with positive functions and can ignore absolute value symbols. “fO(g)” often written “f is O(g)” or “f=O(g)”. The latter form is an instance of a more general convention.,Order-of-Growth Expressions,“O(f)” when used as a term in an arithmetic expression means: “some function f s

32、uch that fO(f)”. E.g.: “x2+O(x)” means “x2 plus some function that is O(x)”. Formally, you can think of any such expression as denoting a set of functions: x2+O(x) : g | fO(x): g(x)= x2+f(x),Order of Growth Equations,Suppose E1 and E2 are order-of-growth expressions corresponding to the sets of func

33、tions S and T, respectively. Then the “equation” E1=E2 really means fS, gT : f=g or simply ST. Example: x2 + O(x) = O(x2) means fO(x): gO(x2): x2+f(x)=g(x),Useful Facts about Big O, f,g (e.g. x1 = O(x) (logb |f|)a = O(f). (e.g. log x = O(x) g=O(fg) (e.g. x = O(x log x) fg O(g) (e.g. x log x O(x) a=O

34、(f) (e.g. 3 = O(x),Big - Omega and Big - Theta,Big-oh concerns with the less than or equal to relation between functions for large values of the variable. It is also possible to consider the greater than or equal to relation and equal to relation in a similar way. Big-Omega is for the former and big

35、-theta is for the latter.,Definition (big-omega):,Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be ( g(x) ) , which is read as f(x) is big-omega of g(x) , if there are constants C and n0 such that | f(x) | C | g(x) | w

36、henever x n0 .,Definition: (g), exactly order g,If fO(g) and gO(f), then we say “g and f are of the same order” or “f is (exactly) order g” and write f(g). Another, equivalent definition: (g) f:RR | c1c2k0 xk: |c1g(x)|f(x)|c2g(x)| “Everywhere beyond some point k, f(x) lies in between two multiples o

37、f g(x).”,Rules for ,Mostly like rules for O( ), except: f,g0 & constants a,bR, with b0, af (f), but Same as with O. f (fg) unless g=(1) Unlike O. |f| 1-b (f), and Unlike with O. (logb |f|)c (f). Unlike with O. The functions in the latter two cases we say are strictly of lower order than (f)., exampl

38、e,Determine whether: Quick solution:,Other Order-of-Growth Relations,(g) = f | gO(f) “The functions that are at least order g.” o(g) = f | c0 k xk : |f(x)| 0 k xk : |cg(x)| 0. (na) is lower than (nb) if and only if 01. (an) is lower than (n!) for any a1. (n!) is lower than (nn),If r is not zero, the

39、n (rf) = (f) for any function f. If h is a nonzero function and (f) is lower than (or same order as) (g), then (fh) is lower than (or same order as) (gh). If (f) is lower than (g), then (f+g)= (g).,Determine the -class of each of the following.,(a) f(n)=4n2-6n7+25n3 (b) g(n)=lg(n)-3n (c) h(n)=1.1n+n

40、15,Arrange the following in order from lowest to highest,(1000000) (n0.2) (n+107) (nlg(n) (1000n2-n) (1.3n),(nlg(n) (1000n2-n) (n0.2) (1000000) (1.3n) (n+107),Example,Find the complexity class of the function (nn!+ 3n+2 + 3n100 )(nn + n2n ) Solution: This means to simplify the expression. Throw out

41、stuff which you know doesnt grow as fast. And at last: nn! nn,Why o(f)O(x)(x),A function that is O(x), but neither o(x) nor (x):,Strict Ordering of Functions,Temporarily lets write fg to mean fo(g), fg to mean f(g) Note that: Let k1. Then the following are true: 1 log log n log n logk n logk n n1/k

42、n n log n nk kn n! nn ,Review: Orders of Growth,Definitions of order-of-growth sets, g:RR O(g) : f | c0 k xk |f(x)| 0 k xk |f(x)| v then v := ai t3 return v t4 First, whats an expression for the exact total worst-case time? (Not its order of growth.),Times for each execution of each line.,Complexity

43、 analysis, cont.,procedure max(a1, a2, , an: integers) v := a1 t1 for i := 2 to n t2 if ai v then v := ai t3 return v t4 w.c.t.c.:,Times for each execution of each line.,Complexity analysis, cont.,Now, what is the simplest form of the exact () order of growth of t(n)?,Example 2: Linear Search,proced

44、ure linear search (x: integer, a1, a2, , an: distinct integers) i := 1 t1 while (i n x ai) t2 i := i + 1 t3 if i n then location := i t4 else location := 0 t5 return location t6,Linear search analysis,Worst case time complexity order: Best case: Average case, if item is present:,Review 3.3: Complexi

45、ty,Algorithmic complexity = cost of computation. Focus on time complexity for our course. Although space & energy are also important. Characterize complexity as a function of input size: Worst-case, best-case, or average-case. Use orders-of-growth notation to concisely summarize the growth propertie

46、s of complexity functions.,Example 3: Binary Search,procedure binary search (x:integer, a1, a2, , an: distinct integers, sorted smallest to largest) i := 1 j := n while iam then i := m+1 else j := m end if x = ai then location := i else location := 0 return location,(1),(1),(1),Key question: How man

47、y loop iterations?,Binary search analysis,Suppose that n is a power of 2, i.e., k: n=2k. Original range from i=1 to j=n contains n items. Each iteration: Size ji+1 of range is cut in half. Loop terminates when size of range is 1=20 (i=j). Therefore, the number of iterations is: k = log2n = (log2 n)=

48、 (log n) Even for n2k (not an integral power of 2), time complexity is still (log2 n) = (log n).,Names for some orders of growth,(1) Constant (logc n) Logarithmic (same order c) (logc n) Polylogarithmic (n) Linear (nc) Polynomial (for any c) (cn) Exponential (for c1) (n!) Factorial,(With c a constan

49、t.),Problem Complexity,The complexity of a computational problem or task is (the order of growth of) the complexity of the algorithm with the lowest order of growth of complexity for solving that problem or performing that task. E.g. the problem of searching an ordered list has at most logarithmic t

50、ime complexity. (Complexity is O(log n).),Tractable vs. intractable,A problem or algorithm with at most polynomial time complexity is considered tractable (or feasible). P is the set of all tractable problems. A problem or algorithm that has complexity greater than polynomial is considered intractab

51、le (or infeasible). Note that n1,000,000 is technically tractable, but really very hard. nlog log log n is technically intractable, but easy. Such cases are rare though.,Computer Time Examples,Assume time = 1 ns (109 second) per op, problem size = n bits, and #ops is a function of n, as shown.,(125 kB),(1.25 bytes),Unsolvable problems,Turing discovered in the 1930s that there are problems unsolvable by any algorithm. Or equivalently, there are undecidable yes/no questions, and uncomputable functions. Classic example: the halting problem. Given an arbitrary algorithm and its input,