离散数学北京邮电大学

1、AlgorithmsRosen 6th ed., 3.1Abu 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 & Division Some basic number theory. 3.5: Primes and Greatest

2、 Common Divisors 3.6: Integers & Algorithms Alternate bases, algorithms for basic arithmetic 3.7: Applications of Number theory Public-Key Cryptography 3.8: Matrices Some basic linear algebra.3.1: Algorithms The foundation of computer programming. Most generally, an algorithm just means a defini

3、te procedure for performing some sort of task. A computer program is simply a description of an algorithm, in a language precise enough for a computer to understand, requiring only operations that the computer already knows how to do. We say that a program implements (or “is an implementation of”) i

4、ts algorithm.Algorithms You Already Know Grade-school arithmetic algorithms: How to add any two natural numbers written in decimal on paper, using carries. Similar: Subtraction using borrowing. Multiplication & long division. Your favorite cooking recipe. How to register for classes at BUPT.Prog

5、ramming Languages Some common programming languages: Newer: Java, C, C+, C#, Visual Basic, JavaScript, Perl, Tcl, Pascal, many others Older: Fortran, Cobol, Lisp, Basic Assembly languages, for low-level coding. In this class we will use an informal, Pascal-like “pseudo-code” language. You should kno

6、w at least 1 real language!Algorithm Example (English) Task: Given a sequence ai=a1,an, aiN, say what its largest element is. One algorithm for doing this, in English: Set the value of a temporary variable v (largest element seen so far) to a1s value. Look at the next element ai in the sequence. If

7、aiv, then re-assign v to the number ai. Repeat then previous 2 steps until there are no more elements in the sequence, & return v.Executing an Algorithm When you start up a piece of software, we say the program or its algorithm are being run or executed by the computer. Given a description of an

8、 algorithm, you can also execute it by hand, by working through all of its steps with pencil & paper. Before 1940, “computer” meant a person whose job was to execute algorithms!Executing the Max algorithm Let ai=7,12,3,15,8. Find its maximum Set v = a1 = 7. Look at next element: a2 = 12. Is a2v?

9、 Yes, so change v to 12. Look at next element: a2 = 3. Is 312? No, leave v alone. Is 1512? Yes, v=15Algorithm CharacteristicsSome important general features of algorithms: Input. Information or data that comes in. Output. Information or data that goes out. Definiteness. Algorithm is precisely define

10、d. Correctness. Outputs correctly relate to inputs. Finiteness. Wont take forever to describe or run. Effectiveness. Individual steps are all do-able. Generality. Works for many possible inputs. Efficiency. Takes little time & memory to run.Pseudocode Language: A3procedurename(argument: type)var

11、iable := expressioninformal statementbegin statements endcommentif condition then statement else statementfor variable := initial value to final value statementwhile condition statementprocname(arguments) Not defined in book:return expressionprocedure procname(arg: type) Declares that the following

12、text defines a procedure named procname that takes inputs (arguments) named arg which are data objects of the type type. Example:procedure maximum(L: list of integers)statements defining maximumvariable := expression An assignment statement evaluates the expression expression, then reassigns the var

13、iable variable to the value that results. Example assignment statement:v := 3x+7 (If x is 2, changes v to 13.) In pseudocode (but not real code), the expression might be informally stated: x := the largest integer in the list LInformal statement Sometimes we may write a statement as an informal Engl

14、ish imperative, if the meaning is still clear and precise: e.g.,“swap x and y” Keep in mind that real programming languages never allow this. When we ask for an algorithm to do so-and-so, writing “Do so-and-so” isnt enough! Break down algorithm into detailed steps.begin statements end Groups a seque

15、nce of statements together:begin statement 1 statement 2 statement n end Allows the sequence to be used just like a single statement. Might be used: After a procedure declaration. In an if statement after then or else. In the body of a for or while loop.Curly braces are used insteadin many ment Not

16、executed (does nothing). Natural-language text explaining some aspect of the procedure to human readers. Also called a remark in some real programming languages, e.g. BASIC. Example, might appear in a max program: Note that v is the largest integer seen so far.if condition then statement Evaluate th

17、e propositional expression condition. If the resulting truth value is True, then execute the statement statement; otherwise, just skip on ahead to the next statement after the if statement. Variant: if cond then stmt1 else stmt2 Like before, but iff truth value is False, executes stmt2.while conditi

18、on statement Evaluate the propositional (Boolean) expression condition. If the resulting value is True, then execute statement. Continue repeating the above two actions over and over until finally the condition evaluates to False; then proceed to the next statement.while condition statement Also equ

19、ivalent to infinite nested ifs, like so: if condition begin statement if condition begin statement (continue infinite nested ifs) end endfor var := initial to final stmt Initial is an integer expression. Final is another integer expression. Semantics: Repeatedly execute stmt, first with variable var

20、 := 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 value that initial or final evaluates to?for var := initial to final stmt For can be exactly defined in terms of while, like so:b

21、egin var := initial while var final begin stmt var := var + 1 endendprocedure(argument) A procedure call statement invokes the named procedure, giving it as its input the value of the argument expression. Various real programming languages refer to procedures as functions (since the procedure call n

22、otation works similarly to function application f(x), or as subroutines, subprograms, or methods.Max procedure in pseudocodeprocedure max(a1, a2, , an: integers) v := 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

23、 as the largest integer in the list return vInventing an Algorithm Requires a lot of creativity and intuition Like writing proofs. Unfortunately, we cant give you an algorithm for inventing algorithms. Just look at lots of examples And practice (preferably, on a computer) And look at more examples A

24、nd 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 natural number is a prime number. First, start with a correct predicate-logic definition of the desired function:n: IsPrime(n) 1dn: d|nM

25、eans d divides nevenly (without remainder)IsPrime example, cont. Notice that the negated exponential can be rewritten as a universal:1dn: d|n 1d1 & 1 is a, and let b : n/a. Then n = ab, but if a n1/2 then b n1/2 (since a is ns smallest divisor) and so n = ab (n1/2)2 = n, an absurdity.Further opt

26、imizations are possible: - E.g., only try divisors that are primes 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

27、, Determine whether x appears in the list, and if so, return its index (position) in the list. Problem occurs often in many contexts. Lets find an efficient algorithm!Search alg. #1: Linear Searchprocedure linear search(x: integer, a1, a2, , an: distinct integers)i := 1 start at beginning of listwhi

28、le (i n x ai) not done, not foundi := i + 1 go to the next positionif i n then location := i it was foundelse location := 0 it wasnt foundreturn location index or 0 if not foundSearch alg. #2: Binary Search Basic idea: On each step, look at the middle element of the remaining list to eliminate half

29、of it, and quickly zero in on the desired element.xx xSearch alg. #2: Binary Searchprocedure binary search(x:integer, a1, a2, , an: distinct integers) i := 1 left endpoint of search intervalj := n right endpoint of search intervalwhile i1 itemm := (i+j)/2 midpointif xam then i := m+1 else j := mendi

30、f x = ai then location := i else location := 0return locationPractice exercises 3.1.3: Devise an algorithm that finds the sum of all the integers in a list. 2 min procedure sum(a1, a2, , an: integers)s := 0 sum of elems so farfor i := 1 to n go thru all elemss := s + ai add current itemat this point

31、 s is the sum of all itemsreturn s Sorting Algorithms Sorting is a common operation in many applications. E.g. spreadsheets and databases It is also widely used as a subroutine in other data-processing algorithms. Two sorting algorithms shown in textbook: Bubble sort Insertion sortHowever, these are

32、 notvery efficient, and you shouldnot use them on large data sets!Well see some more efficient algorithms later in the course. Smallest elements “float” up to the top of the list, like bubbles in a container of liquid.Bubble Sort30311323323433013132233334130312323333413023133233341230331323334123303

33、1323334Insertion Sort Algorithm English description of algorithm: For each item in the input list, “Insert” it into the correct place in the sorted output list generated so far. Like so: Use linear or binary search to find the location where the new item should be inserted. Then, shift the items fro

34、m that position onwards down by one position. Put the new item in the hole remaining.Greedy Algorithms Many algorithms are designed to solve optimization problems, and one of the simplest approaches often leads to a solution of an optimization problem Algorithms that make what seems to be the best c

35、hoice at each step are called “Greedy Algorithms” instead of considering all sequences of steps. But, “Greedy Algorithms” dont works well for all optimization problemsGreedy Chang-Making Algorithm Procedure change(c1,c2,cr:values of denominations of coins,where c1c2cr;n: a positive integer) For i:=1

36、 to r while nci begin add a coin with value ci to the change n:=n-ci endThe 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,I) : the truth value of this statem

37、ent: “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 predictive analysis of arbitrary comp

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

39、lse 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)=?停机问题证明 矛盾？矛盾！ 如果Trouble(t)停机返回了，也就是Halt(t,t)=Fa

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

41、y-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-of-growth concepts from 3.3.Orders of

42、 GrowthRosen 6th ed., 3.2Orders 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 enough values of x). Useful in engineering

43、 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 records, while program B takes fB(n)=n2+1 mic

44、roseconds to process the n records. Which program do you choose, knowing youll want to support millions of users?Visualizing Orders of Growth On a graph, asyou go to theright, the faster-growing func-tion always eventuallybecomes thelarger one. fA(n)=30n+8Increasing n fB(n)=n2+1Value of function Exa

45、mple: 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. nf(n)g(n)1010,00010,00050250,0006,250,0001001,000,000100,000,0001502,250,000506,250,000 Concept of order of growth We say fA(n)=30n+8 is (at most) order n, or O(n)

46、. It is, at most, roughly proportional 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 record

47、s, the exactly order n2 function will always take more time.Definition: O(g), at most order gLet 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

48、 order g”, or “f is O(g)”, or “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

49、 larger value of c and/or k will 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

50、. Let c=31, k=8. Assume nk=8. Thencn = 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 evenless than 31neverywhere. But it is less than31n everywhere tothe right of n=8. nk=8 Big-O example, graphicallyIncreasing n Value of function

51、n30n+8cn =31n30n+8O(n)Useful 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(

52、cf)=O(f+c)=O(fc)=O(f) f1O(g1) 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

53、. f2(n) k2. We must find a k3 and c3 such that 3. f1(n)f2(n) k3.Proof of f1f2 is O(g1g2) We use the inequality if 0 a b and 0 c d then ac bd to conclude that f1(n)f2(n) 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

54、of Growth For any g:RR, “at most order g”,O(g) f:RR | c,k xk |f(x)| |cg(x)|. Often, 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

55、)” when used as a term in an arithmetic expression means: “some function f such 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

56、E1 and E2 are order-of-growth expressions corresponding to the sets of functions S and T, respectively. Then the “equation” E1=E2 really means fS, gT : f=gor 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 & constants a,bR, with b0, af = O(f);

57、(e.g. 3x2 = O(x2) f+O(f) = O(f); (e.g. x2+x = O(x2) Also, if f=(1) (at least order 1), then: |f|1-b = O(f); (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(f) (e.g. 3 = O(x)Big - Omega and Big - Theta Big-oh concerns with the less th

58、an 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-theta is for the latter. Definition (big-omega): Let f and g be functions from

59、 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) | whenever x n0 . Definition: (g), exactly order g If fO(g) and gO(f), then we say

60、 “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 of 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