Fundamentals Of Computer Engineering 2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Fundamentals Of Computer Engineering 2 as PDF for free.
More details
- Words: 3,896
- Pages: 33
Fundamentals of Computer Engineering 2
Algorithms
Bernhard Westfechtel
Summer 2004
Fundamentals of Computer Engineering 2
Summer 2004
Contents of this chapter
The notion of „algorithm“
Pseudo code: an informal notation for algorithms
Examples of algorithms
Properties of algorithms
Control structures: controlling the sequence of algorithmic steps
Functional abstraction: reuse of algorithms
Note: This chapter provides an intuitive introduction into algorithms and programming. The topics introduced here will be studied in depth in subsequent chapters!
Bernhard Westfechtel
2
Fundamentals of Computer Engineering 2
Summer 2004
The notion of “algorithm”
Algorithm » Description of a procedure which is Ö finite (i.e., consists of a finite sequence of characters) Ö complete (i.e., describes all computation steps) Ö unique (i.e., there are no ambiguities) Ö effective (i.e., each step has a defined effect and can be executed in finite time)
Desired properties of algorithms » Correctness Ö For each input, the algorithm calculates the requested value » Termination Ö For each input, the algorithm performs only a finite number of steps » Efficiency Ö Runtime: The algorithm runs as fast as possible Ö Storage space: The algorithm requires as little storage space as posssible
Bernhard Westfechtel
3
Fundamentals of Computer Engineering 2
Summer 2004
Examples of algorithms
Adding a sequence of numbers digit by digit
Scalar product of two vectors
Matrix product of two matrices
Factorial of a natural number
Greatest common divisor of two natural numbers
Least common multiple of two numbers
Sorting a sequence of elements in ascending or descending order
Placing queens on a chess board in a conflict-free manner
(and many more!)
Bernhard Westfechtel
4
Fundamentals of Computer Engineering 2
Summer 2004
Mathematical definition of the factorial function Factorial of a natural number
1
n=0
n * (n-1)!
n>0
n! =
n! = n * (n-1)! = n * (n-1) * (n-2)! = …= n * (n-1) * (n-2) * … * 1 (i.e., n! is the product of all natural numbers from 1 to n)
Bernhard Westfechtel
5
Fundamentals of Computer Engineering 2
Summer 2004
Instructing a human to compute the factorial Alternative A If n is equal to 0, the result is 1. If n is greater than 0, then calculate the factorial of n-1 and multiply the result by n, giving the factorial of n.
Alternative B If n is equal to 0, the result is 1. Otherwise, multiply all natural numbers between 1 and n, giving the factorial of n. or (described in a more detailed way) If n = 0, result is 1. Otherwise: 1. Initialize result with 1, i with 1. 2. i ≤ n fi new result = old result * i, add 1 to i, repeat 2. 3. i > n fi stop. Bernhard Westfechtel
6
Fundamentals of Computer Engineering 2
Summer 2004
Example of a computation: fac(5) Alternative B
Alternative A 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
5 > 0 fi fac(5) = 5 * fac(4) 4 > 0 fi fac(4) = 4 * fac(3) 3 > 0 fi fac(3) = 3 * fac(2) 2 > 0 fi fac(2) = 2 * fac(1) 1 > 0 fi fac(1) = 1 * fac(0) 0 = 0 fi fac(0) = 1 fac(1) = 1 * fac(0) = 1 * 1 = 1 fac(2) = 2 * fac(1) = 2 * 1 = 2 fac(3) = 3 * fac(2) = 3 * 2 = 6 fac(4) = 4 * fac(3) = 4 * 6 = 24 fac(5) = 5 * fac(4) = 5 * 24 = 120
Bernhard Westfechtel
1. 2. 3. 4. 5. 6. 7. 8.
7
5 ≠ 0 fi goto step 2. result = 1, i = 1 1 ≤ 5 fi result = 1 * 1 = 1, i = 2 2 ≤ 5 fi result = 1 * 2 = 2, i = 3 3 ≤ 5 fi result = 2 * 3 = 6, i = 4 4 ≤ 5 fi result = 6 * 4 = 24, i = 5 5 ≤ 5 fi result = 24 * 5 = 120, i = 6 6 > 5 fi stop, fac(5) = result = 120
Fundamentals of Computer Engineering 2
Summer 2004
Comparing the computations Algorithm A
Algorithm B
Algorithm A is divided into two phases » 1. Reduce fac(n) to fac(n-1) » 2. Compute fac(0), ..., fac(n)
Computation is recursive » The problem of computing fac(n) is reduced to a problem of the same kind (fac(n-1)), but for a “simpler” argument » Computation terminates for the case n = 0
Algorithm A is based on an inductive mathematical definition » n! = n * (n-1)! for n > 0, n! = 1 for n = 0
Bernhard Westfechtel
8
Algorithm B consists of one phase only (multiplying the natural numbers from 1 to n) Algorithm B is more efficient since it saves the reduction phase Computation is non-recursive » For n = 5, the numbers 1..5 are multiplied » For n = 6, the numbers 1..6 are multiplied » The computation for n = 6 does not “know” that it contains the computation for n = 5 Algorithm B is based on a noninductive mathematical definition » n! = ∏ i (1 ≤ i ≤ n)
Fundamentals of Computer Engineering 2
Summer 2004
Recursion and induction Recursion
Induction
Reduce the computation of some function f(x) to the computation of f(x´), which is “easier to compute” than f(x)
For arguments x which are “simple enough”, compute f(x) by an elementary rule
Induction is a mathematical principle applied to both definition and proofs for natural numbers Induction start: » Define f(x) for x = 0 or prove p(x) for x = 0 Induction step: » Define f(x+1) in terms of f(x) or prove p(x+1), assuming that p(x) holds
Inductive definitions naturally result in recursive computations!
Bernhard Westfechtel
9
Fundamentals of Computer Engineering 2
Summer 2004
Equivalence of Algorithm A and Algorithm B
Definition » n! = 1 (n = 0), n! = n * (n-1)! (n > 0)
Proposition » n! = ∏ i (1 ≤ i ≤ n)
Proof » By induction Ö Induction start – n! = 1 = ∏ i (1 ≤ i ≤ 0) (by definition of ∏) Ö Induction step – n! = n * (n-1)! (by definition of !) = n * ∏ i (1 ≤ i ≤ n-1) (induction assumption) = ∏ i (1 ≤ i ≤ n) (by definition of ∏)
Bernhard Westfechtel
10
Fundamentals of Computer Engineering 2
Summer 2004
Pseudo code: a semi-formal notation for algorithms
Intent: description of algorithms in a standard notation » Natural language is not well suited for describing algorithms » Pseudo code introduces a notation which precisely defines Ö Inputs Ö Outputs Ö Steps of the computation » Notation is similar to programming languages such as Pascal, Ada, etc.
Example: computation of the factorial » An algorithm is divided into three parts Ö Input, output, and computation » return denotes the computed value » if, then, else, end are keywords » Computations are defined by control structures (here: conditional statement)
Bernhard Westfechtel
11
input: a natural number n output: n! computation: if n = 0 then return 1 else return n * fac(n-1) end
Fundamentals of Computer Engineering 2
Summer 2004
Another example: greatest common divisor
Mathematical definition » Let m, n be two natural numbers. The greatest common divisor gcd of m, n is defined such that 1. m mod gcd = 0 2. n mod gcd = 0 (j mod k = the rest of dividing j by k) 3. For each number cd dividing both m and n, cd ≤ gcd
Algorithm
Bernhard Westfechtel
input: two natural numbers m, n output: greatest common divisor of m, n computation: if m < n then return gcd(n, m) else if n = 0 then return m else return gcd(n, m mod n) end end 12
Fundamentals of Computer Engineering 2
Summer 2004
Example computations
gcd(45, 75) = gcd(75, 45) = gcd(45, 75 mod 45) = gcd(45, 30) = gcd(30, 45 mod 30) = gcd(30, 15) = gcd(15, 30 mod 15) = gcd(15, 0) = 15
Bernhard Westfechtel
gcd(89, 53) = gcd(53, 89 mod 53) = gcd(53, 36) = gcd(36, 53 mod 36) = gcd(36, 17) = gcd(17, 36 mod 17) = gcd(17, 2) = gcd(2, 17 mod 2) = gcd(2, 1) = gcd(1, 2 mod 1) = gcd(1, 0) = 1
13
gcd(40, 100) = gcd(100, 40) = gcd(40, 100 mod 40) = gcd(40, 20) = gcd(20, 40 mod 20) = gcd(20, 0) = 20
Fundamentals of Computer Engineering 2
Summer 2004
Properties of algorithms Termination
Correctness
If the algorithm terminates, it returns the required result
Correctness may be checked as follows » Testing: run the algorithm against selected test cases » Verification: prove the correctness of the algorithms for all inputs
Testing can show the correctness only for a subset of the inputs But verification may be difficult and laborious
Bernhard Westfechtel
14
For each allowed input, the algorithm stops after a finite sequence of steps As for correctness, termination may be tested or proved How to discover non-terminating computations by testing? » The tester cannot wait forever » At some time, the tester has to interrupt the computation and check the algorithm » Maybe the tester stops the computation “too early”
Fundamentals of Computer Engineering 2
Summer 2004
Example of a non-terminating algorithm Algorithm
Computation
input: a natural number n output: n! computation: if n = 0 then return 1 else return n * fac(n+1) end
fac(1) = 1 * fac(2) = 1 * 2 * fac(3) = 1 * 2 * 3 * fac(4) = 1 * 2 * 3 * 4 * fac(5) = 1 * 2 * 3 * 4 * 5 * fac(6) = ....
Typing error (“+” instead of “-”)
Bernhard Westfechtel
15
Fundamentals of Computer Engineering 2
Summer 2004
Greatest common divisor: correctness
Proposition » If algorithm gcd terminates, it computes the greatest common divisor
Proof » Let m, n be two natural numbers. Three cases have to be distinguished: 1. m < n: Algorithm gcd computes gcd(n, m), i.e., the arguments are exchanged. Since the definition of greatest common divisor is symmetric with respect to m and n, this step does not affect the result. 2. n = 0: Algorithm gcd returns m. Since 0 is divided by any natural number and the greatest divisor of m is m itself, the result is correct. 3. m ≥ n > 0: Algorithm gcd returns gcd(n, m mod n). Let gc divide both m and n. Then it divides 0 ≤ m – i*n < n, i.e., m mod n. Conversely, let gc divide both n and m mod n. Then it divides n*i + m – i*n = m. Thus, m and n have the same dividers as n and m mod n.
Bernhard Westfechtel
16
Fundamentals of Computer Engineering 2
Summer 2004
Greatest common divisor: termination
Proposition » Algorithm gcd terminates for any pair of natural numbers m and n.
Proof » General idea of a termination proof Ö Demonstrate for each recursive call that the value of at least one of its arguments decreases and remains non-negative Ö Starting with some number n, there may be at most n-1 recursive calls » Proof for the gcd algorithm Ö gcd(m, n) is reduced to gcd(m´, n´) Ö To demonstrate: n´ < n 1. m < n: gcd(m, n) = gcd(n, m) = gcd(m´, n´) n´= m < n 2. n = 0: gcd(m, n) = m, and the algorithm terminates 3. m ≥ n > 0: gcd(m, n) = gcd(n, m mod n) = gcd(m´, n´) n´ = m mod n < n
Bernhard Westfechtel
17
Fundamentals of Computer Engineering 2
Summer 2004
Pseudo code for non-recursive version of factorial input: a natural number n output: n! variables: i, result (both natural numbers) computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
18
Variables are used during the computation Unlike a variable in mathematics, a variable may change its value A variable receives a value through an assignment » result := 1 assigns the value 1 to the variable result » General form of an assignment: variable := expression » Note: the expression refers to the old value of the variable Ö result := result * i: multiply result by i Ö i := i +1: increase i by 1 goto denotes a jump to another point in the computation Here, goto is used for a loop (a part of the computation which is repeated)
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = ?, result = ? computation: current if n = 0 then statement return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = ?, result = ? computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 19
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 1, result = ? computation: if n = 0 then result of return 1 assignment else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
20
input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 21
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 input: n = 4 output: ? (unknown yet) output: ? (unknown yet) variables: i = 2, result = 1 variables: i = 2, result = 1 computation: computation: if n = 0 then if n = 0 then value has return 1 return 1 been else else increased i := 1; i := 1; result := 1; result := 1; loop: loop: if i ≤ n then if i ≤ n then result := result * i; result := result * i; i := i + 1; i := i + 1; goto loop goto loop return to else beginning else return result return result of loop end end end end Bernhard Westfechtel
22
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 2, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 2, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 23
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 24
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 3, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 25
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 26
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 4, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 27
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 28
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: 24 variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 29
Fundamentals of Computer Engineering 2
Summer 2004
A more convenient notation for the loop input: a natural number n output: n! variables: i, result (both natural numbers) computation: if n = 0 then return 1 else result := 1; for i from 1 to n do result := result * i end; return result end
Bernhard Westfechtel
30
The keyword for indicates a loop » for lv from iv to fv do body end
The part between do and end is called the body of the loop
The body is executed for all values of the loop variable lv ranging from the initial value iv to the value fv
Termination is guaranteed since the body is executed a finite number of times (fv – iv)
Fundamentals of Computer Engineering 2
Summer 2004
A further simplification of the algorithm
input: a natural number n output: n! variables: i, result (both natural numbers) computation: result := 1; for i from 1 to n do result := result * i end; return result
Bernhard Westfechtel
31
The special case n = 0 may be eliminated » for loop is not executed at all if fv < iv » Initial value 1 already happens to be the correct result
Fundamentals of Computer Engineering 2
Summer 2004
Functional abstraction function: lcm input: two natural numbers m, n output: least common multiple computation: return m * n / gcd(m, n) function: gcd input: two natural numbers m, n output: greatest common divisor of m, n computation: if m < n then return gcd(n, m) else if n = 0 then return m else return gcd(n, m mod n) end end Bernhard Westfechtel
32
Goal » Reuse of computations
Functional abstraction » Abstract from the way a function is calculated » Frequently used in mathematics » Required for defining recursive functions
Realization » Assign a name to a function » Define its inputs (also called arguments or parameters) » Define its result » Call the function by supplying actual values (actual parameters) for the inputs
Fundamentals of Computer Engineering 2
Summer 2004
Literature
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms, MIT Press, Cambridge, Massachusetts, 1994 (Comprehensive textbook on algorithms.)
Robert Sedgewick: Algorithms, Addison Wesley, Reading, Massachusetts, 1989 (Another textbook on algorithms. Many other textbooks are available from the same author - for Java, C++, and Modula-3)
Bernhard Westfechtel
33
Algorithms
Bernhard Westfechtel
Summer 2004
Fundamentals of Computer Engineering 2
Summer 2004
Contents of this chapter
The notion of „algorithm“
Pseudo code: an informal notation for algorithms
Examples of algorithms
Properties of algorithms
Control structures: controlling the sequence of algorithmic steps
Functional abstraction: reuse of algorithms
Note: This chapter provides an intuitive introduction into algorithms and programming. The topics introduced here will be studied in depth in subsequent chapters!
Bernhard Westfechtel
2
Fundamentals of Computer Engineering 2
Summer 2004
The notion of “algorithm”
Algorithm » Description of a procedure which is Ö finite (i.e., consists of a finite sequence of characters) Ö complete (i.e., describes all computation steps) Ö unique (i.e., there are no ambiguities) Ö effective (i.e., each step has a defined effect and can be executed in finite time)
Desired properties of algorithms » Correctness Ö For each input, the algorithm calculates the requested value » Termination Ö For each input, the algorithm performs only a finite number of steps » Efficiency Ö Runtime: The algorithm runs as fast as possible Ö Storage space: The algorithm requires as little storage space as posssible
Bernhard Westfechtel
3
Fundamentals of Computer Engineering 2
Summer 2004
Examples of algorithms
Adding a sequence of numbers digit by digit
Scalar product of two vectors
Matrix product of two matrices
Factorial of a natural number
Greatest common divisor of two natural numbers
Least common multiple of two numbers
Sorting a sequence of elements in ascending or descending order
Placing queens on a chess board in a conflict-free manner
(and many more!)
Bernhard Westfechtel
4
Fundamentals of Computer Engineering 2
Summer 2004
Mathematical definition of the factorial function Factorial of a natural number
1
n=0
n * (n-1)!
n>0
n! =
n! = n * (n-1)! = n * (n-1) * (n-2)! = …= n * (n-1) * (n-2) * … * 1 (i.e., n! is the product of all natural numbers from 1 to n)
Bernhard Westfechtel
5
Fundamentals of Computer Engineering 2
Summer 2004
Instructing a human to compute the factorial Alternative A If n is equal to 0, the result is 1. If n is greater than 0, then calculate the factorial of n-1 and multiply the result by n, giving the factorial of n.
Alternative B If n is equal to 0, the result is 1. Otherwise, multiply all natural numbers between 1 and n, giving the factorial of n. or (described in a more detailed way) If n = 0, result is 1. Otherwise: 1. Initialize result with 1, i with 1. 2. i ≤ n fi new result = old result * i, add 1 to i, repeat 2. 3. i > n fi stop. Bernhard Westfechtel
6
Fundamentals of Computer Engineering 2
Summer 2004
Example of a computation: fac(5) Alternative B
Alternative A 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
5 > 0 fi fac(5) = 5 * fac(4) 4 > 0 fi fac(4) = 4 * fac(3) 3 > 0 fi fac(3) = 3 * fac(2) 2 > 0 fi fac(2) = 2 * fac(1) 1 > 0 fi fac(1) = 1 * fac(0) 0 = 0 fi fac(0) = 1 fac(1) = 1 * fac(0) = 1 * 1 = 1 fac(2) = 2 * fac(1) = 2 * 1 = 2 fac(3) = 3 * fac(2) = 3 * 2 = 6 fac(4) = 4 * fac(3) = 4 * 6 = 24 fac(5) = 5 * fac(4) = 5 * 24 = 120
Bernhard Westfechtel
1. 2. 3. 4. 5. 6. 7. 8.
7
5 ≠ 0 fi goto step 2. result = 1, i = 1 1 ≤ 5 fi result = 1 * 1 = 1, i = 2 2 ≤ 5 fi result = 1 * 2 = 2, i = 3 3 ≤ 5 fi result = 2 * 3 = 6, i = 4 4 ≤ 5 fi result = 6 * 4 = 24, i = 5 5 ≤ 5 fi result = 24 * 5 = 120, i = 6 6 > 5 fi stop, fac(5) = result = 120
Fundamentals of Computer Engineering 2
Summer 2004
Comparing the computations Algorithm A
Algorithm B
Algorithm A is divided into two phases » 1. Reduce fac(n) to fac(n-1) » 2. Compute fac(0), ..., fac(n)
Computation is recursive » The problem of computing fac(n) is reduced to a problem of the same kind (fac(n-1)), but for a “simpler” argument » Computation terminates for the case n = 0
Algorithm A is based on an inductive mathematical definition » n! = n * (n-1)! for n > 0, n! = 1 for n = 0
Bernhard Westfechtel
8
Algorithm B consists of one phase only (multiplying the natural numbers from 1 to n) Algorithm B is more efficient since it saves the reduction phase Computation is non-recursive » For n = 5, the numbers 1..5 are multiplied » For n = 6, the numbers 1..6 are multiplied » The computation for n = 6 does not “know” that it contains the computation for n = 5 Algorithm B is based on a noninductive mathematical definition » n! = ∏ i (1 ≤ i ≤ n)
Fundamentals of Computer Engineering 2
Summer 2004
Recursion and induction Recursion
Induction
Reduce the computation of some function f(x) to the computation of f(x´), which is “easier to compute” than f(x)
For arguments x which are “simple enough”, compute f(x) by an elementary rule
Induction is a mathematical principle applied to both definition and proofs for natural numbers Induction start: » Define f(x) for x = 0 or prove p(x) for x = 0 Induction step: » Define f(x+1) in terms of f(x) or prove p(x+1), assuming that p(x) holds
Inductive definitions naturally result in recursive computations!
Bernhard Westfechtel
9
Fundamentals of Computer Engineering 2
Summer 2004
Equivalence of Algorithm A and Algorithm B
Definition » n! = 1 (n = 0), n! = n * (n-1)! (n > 0)
Proposition » n! = ∏ i (1 ≤ i ≤ n)
Proof » By induction Ö Induction start – n! = 1 = ∏ i (1 ≤ i ≤ 0) (by definition of ∏) Ö Induction step – n! = n * (n-1)! (by definition of !) = n * ∏ i (1 ≤ i ≤ n-1) (induction assumption) = ∏ i (1 ≤ i ≤ n) (by definition of ∏)
Bernhard Westfechtel
10
Fundamentals of Computer Engineering 2
Summer 2004
Pseudo code: a semi-formal notation for algorithms
Intent: description of algorithms in a standard notation » Natural language is not well suited for describing algorithms » Pseudo code introduces a notation which precisely defines Ö Inputs Ö Outputs Ö Steps of the computation » Notation is similar to programming languages such as Pascal, Ada, etc.
Example: computation of the factorial » An algorithm is divided into three parts Ö Input, output, and computation » return denotes the computed value » if, then, else, end are keywords » Computations are defined by control structures (here: conditional statement)
Bernhard Westfechtel
11
input: a natural number n output: n! computation: if n = 0 then return 1 else return n * fac(n-1) end
Fundamentals of Computer Engineering 2
Summer 2004
Another example: greatest common divisor
Mathematical definition » Let m, n be two natural numbers. The greatest common divisor gcd of m, n is defined such that 1. m mod gcd = 0 2. n mod gcd = 0 (j mod k = the rest of dividing j by k) 3. For each number cd dividing both m and n, cd ≤ gcd
Algorithm
Bernhard Westfechtel
input: two natural numbers m, n output: greatest common divisor of m, n computation: if m < n then return gcd(n, m) else if n = 0 then return m else return gcd(n, m mod n) end end 12
Fundamentals of Computer Engineering 2
Summer 2004
Example computations
gcd(45, 75) = gcd(75, 45) = gcd(45, 75 mod 45) = gcd(45, 30) = gcd(30, 45 mod 30) = gcd(30, 15) = gcd(15, 30 mod 15) = gcd(15, 0) = 15
Bernhard Westfechtel
gcd(89, 53) = gcd(53, 89 mod 53) = gcd(53, 36) = gcd(36, 53 mod 36) = gcd(36, 17) = gcd(17, 36 mod 17) = gcd(17, 2) = gcd(2, 17 mod 2) = gcd(2, 1) = gcd(1, 2 mod 1) = gcd(1, 0) = 1
13
gcd(40, 100) = gcd(100, 40) = gcd(40, 100 mod 40) = gcd(40, 20) = gcd(20, 40 mod 20) = gcd(20, 0) = 20
Fundamentals of Computer Engineering 2
Summer 2004
Properties of algorithms Termination
Correctness
If the algorithm terminates, it returns the required result
Correctness may be checked as follows » Testing: run the algorithm against selected test cases » Verification: prove the correctness of the algorithms for all inputs
Testing can show the correctness only for a subset of the inputs But verification may be difficult and laborious
Bernhard Westfechtel
14
For each allowed input, the algorithm stops after a finite sequence of steps As for correctness, termination may be tested or proved How to discover non-terminating computations by testing? » The tester cannot wait forever » At some time, the tester has to interrupt the computation and check the algorithm » Maybe the tester stops the computation “too early”
Fundamentals of Computer Engineering 2
Summer 2004
Example of a non-terminating algorithm Algorithm
Computation
input: a natural number n output: n! computation: if n = 0 then return 1 else return n * fac(n+1) end
fac(1) = 1 * fac(2) = 1 * 2 * fac(3) = 1 * 2 * 3 * fac(4) = 1 * 2 * 3 * 4 * fac(5) = 1 * 2 * 3 * 4 * 5 * fac(6) = ....
Typing error (“+” instead of “-”)
Bernhard Westfechtel
15
Fundamentals of Computer Engineering 2
Summer 2004
Greatest common divisor: correctness
Proposition » If algorithm gcd terminates, it computes the greatest common divisor
Proof » Let m, n be two natural numbers. Three cases have to be distinguished: 1. m < n: Algorithm gcd computes gcd(n, m), i.e., the arguments are exchanged. Since the definition of greatest common divisor is symmetric with respect to m and n, this step does not affect the result. 2. n = 0: Algorithm gcd returns m. Since 0 is divided by any natural number and the greatest divisor of m is m itself, the result is correct. 3. m ≥ n > 0: Algorithm gcd returns gcd(n, m mod n). Let gc divide both m and n. Then it divides 0 ≤ m – i*n < n, i.e., m mod n. Conversely, let gc divide both n and m mod n. Then it divides n*i + m – i*n = m. Thus, m and n have the same dividers as n and m mod n.
Bernhard Westfechtel
16
Fundamentals of Computer Engineering 2
Summer 2004
Greatest common divisor: termination
Proposition » Algorithm gcd terminates for any pair of natural numbers m and n.
Proof » General idea of a termination proof Ö Demonstrate for each recursive call that the value of at least one of its arguments decreases and remains non-negative Ö Starting with some number n, there may be at most n-1 recursive calls » Proof for the gcd algorithm Ö gcd(m, n) is reduced to gcd(m´, n´) Ö To demonstrate: n´ < n 1. m < n: gcd(m, n) = gcd(n, m) = gcd(m´, n´) n´= m < n 2. n = 0: gcd(m, n) = m, and the algorithm terminates 3. m ≥ n > 0: gcd(m, n) = gcd(n, m mod n) = gcd(m´, n´) n´ = m mod n < n
Bernhard Westfechtel
17
Fundamentals of Computer Engineering 2
Summer 2004
Pseudo code for non-recursive version of factorial input: a natural number n output: n! variables: i, result (both natural numbers) computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
18
Variables are used during the computation Unlike a variable in mathematics, a variable may change its value A variable receives a value through an assignment » result := 1 assigns the value 1 to the variable result » General form of an assignment: variable := expression » Note: the expression refers to the old value of the variable Ö result := result * i: multiply result by i Ö i := i +1: increase i by 1 goto denotes a jump to another point in the computation Here, goto is used for a loop (a part of the computation which is repeated)
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = ?, result = ? computation: current if n = 0 then statement return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = ?, result = ? computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 19
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 1, result = ? computation: if n = 0 then result of return 1 assignment else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
20
input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 1, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 21
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 input: n = 4 output: ? (unknown yet) output: ? (unknown yet) variables: i = 2, result = 1 variables: i = 2, result = 1 computation: computation: if n = 0 then if n = 0 then value has return 1 return 1 been else else increased i := 1; i := 1; result := 1; result := 1; loop: loop: if i ≤ n then if i ≤ n then result := result * i; result := result * i; i := i + 1; i := i + 1; goto loop goto loop return to else beginning else return result return result of loop end end end end Bernhard Westfechtel
22
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 2, result = 1 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 2, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 23
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 24
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 3, result = 2 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 3, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 25
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 26
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 4, result = 6 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 4, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 27
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 28
Fundamentals of Computer Engineering 2
Summer 2004
Sample computation input: n = 4 output: ? (unknown yet) variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end Bernhard Westfechtel
input: n = 4 output: 24 variables: i = 5, result = 24 computation: if n = 0 then return 1 else i := 1; result := 1; loop: if i ≤ n then result := result * i; i := i + 1; goto loop else return result end end 29
Fundamentals of Computer Engineering 2
Summer 2004
A more convenient notation for the loop input: a natural number n output: n! variables: i, result (both natural numbers) computation: if n = 0 then return 1 else result := 1; for i from 1 to n do result := result * i end; return result end
Bernhard Westfechtel
30
The keyword for indicates a loop » for lv from iv to fv do body end
The part between do and end is called the body of the loop
The body is executed for all values of the loop variable lv ranging from the initial value iv to the value fv
Termination is guaranteed since the body is executed a finite number of times (fv – iv)
Fundamentals of Computer Engineering 2
Summer 2004
A further simplification of the algorithm
input: a natural number n output: n! variables: i, result (both natural numbers) computation: result := 1; for i from 1 to n do result := result * i end; return result
Bernhard Westfechtel
31
The special case n = 0 may be eliminated » for loop is not executed at all if fv < iv » Initial value 1 already happens to be the correct result
Fundamentals of Computer Engineering 2
Summer 2004
Functional abstraction function: lcm input: two natural numbers m, n output: least common multiple computation: return m * n / gcd(m, n) function: gcd input: two natural numbers m, n output: greatest common divisor of m, n computation: if m < n then return gcd(n, m) else if n = 0 then return m else return gcd(n, m mod n) end end Bernhard Westfechtel
32
Goal » Reuse of computations
Functional abstraction » Abstract from the way a function is calculated » Frequently used in mathematics » Required for defining recursive functions
Realization » Assign a name to a function » Define its inputs (also called arguments or parameters) » Define its result » Call the function by supplying actual values (actual parameters) for the inputs
Fundamentals of Computer Engineering 2
Summer 2004
Literature
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms, MIT Press, Cambridge, Massachusetts, 1994 (Comprehensive textbook on algorithms.)
Robert Sedgewick: Algorithms, Addison Wesley, Reading, Massachusetts, 1989 (Another textbook on algorithms. Many other textbooks are available from the same author - for Java, C++, and Modula-3)
Bernhard Westfechtel
33
Related Documents
Fundamentals Of Computer Engineering 2
June 2020 8
Fundamentals Of Computer Engineering 2
June 2020 6
Computer Fundamentals
November 2019 18
Computer Fundamentals
June 2020 7
Computer Fundamentals
November 2019 11