Which letter is mute in the pseudocode

Computer science ideas and concepts

Transcript

1 Ideas and Concepts of Computer Science Programs and Algorithms Antonios Antoniadis October 23, 2017

2 Algorithms and Programs Algorithm step-by-step rule for solving a problem. You formulate it colloquially, but still precisely (pseudocode). 23 October / 19

3 Algorithms and Programs Algorithm step-by-step rule for solving a problem. You formulate it colloquially, but still precisely (pseudocode). Program, detailed calculation rule for solving a problem. Machine executable. Formulated in a programming language (code). 23 October / 19

4 Algorithms and Programs Algorithm step-by-step rule for solving a problem. You formulate it colloquially, but still precisely (pseudocode). Program, detailed calculation rule for solving a problem. Machine executable. Formulated in a programming language (code). Programming language Artificial language for the formulation of programs with precisely defined syntax and semantics. Syntax = what is a valid sentence Semantics = what does a sentence mean October 23/19

5 Today's topic: Pseudocode for formulating algorithms. Our first two algorithms addition of decimal numbers Test whether a given word occurs in a text October 23/19

6 Origin of the word Algorithm Muhammad ibn Musa al- Khwarizmi Persian mathematician, The concise book on the computational methods by supplementing and balancing October 23/19

7 Origin of the word Algorithm Muhammad ibn Musa al- Khwarizmi Persian mathematician, The concise book on the computational methods by supplementing and balancing Contains, among other things, an algorithm for solving quadratic equations. 23 October / 19

8 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = October / 19

9 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = October / 19

10 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = October / 19

11 Example: Quadratic equation algorithm embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = October / 19

12 Example: Quadratic equation algorithm embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) October 23/19

13 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) - remove 2 on LS, replace RS with ± RS x + 4 = ± October / 19

14 Example: Quadratic equation algorithm embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) - remove 2 on LS, replace RS with ± RS x + 4 = ± 25 - move constant term from LS to RS x = 4 ± October / 19

15 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) - remove 2 on LS, replace RS with ± RS x + 4 = ± 25 - move constant term from LS to RS x = 4 ± 5 ​​x = 1 or x = October / 19

16 Example: Quadratic equation algorithm embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) - remove 2 on LS, replace RS with ± RS x + 4 = ± 25 - Move constant term from LS to RS x = 4 ± 5 ​​x = 1 or x = 9. Algorithm is contained in the book by Al-Khwarizmi. 23 October / 19

17 Example: Quadratic Equation Algorithm Embodiment - Write the equation as x 2 + bx + c = 0 x 2 + 8x 9 = 0 - Bring the constant term to the other side x 2 + 8x = 9 - Add (b / 2) 2 on both sides x 2 + 8x = write LS as (x + b / 2) 2, simplify RS (x + 4) 2 = 25 - if RS is negative, STOP (no solution) - remove 2 on LS, replace RS with ± RS x + 4 = ± 25 - Move constant term from LS to RS x = 4 ± 5 ​​x = 1 or x = 9. Algorithm is contained in the book by Al-Khwarizmi. Algorithm is intended for a human computer, programs for real computers are much more detailed. 23 October / 19

18 A Few Remarks Algorithms were developed several centuries ago, long before the first computer. How can we be sure that the algorithm always delivers the promised solution? 23 October / 19

19 A Few Remarks Algorithms were developed centuries ago, long before the first computer. How can we be sure that the algorithm always delivers the promised solution? e.g. does the QG algorithm give the correct solution for every equation? 23 October / 19

20 Structure of programs Allocations assign values ​​to memory cells. In order to be able to refer to memory cells easily, they are given names. Memory cells with names are called variables. 23 October / 19

21 Structure of programs Allocations assign values ​​to memory cells. In order to be able to refer to memory cells easily, they are given names. Memory cells with names are called variables. Control structures determine which assignments are carried out. Example: If conditions make this, otherwise that. 23 October / 19

22 Variables, expressions, assignments Variables (memory cells with names) have a name, e.g. x, y, salary, i, x 0, x 1, x 2, ... and at each point in time a value, e.g. x has the value 5. The value can be changed by assigning a value, e.g. x 7 reads: x gets the value 7. Value assignment: Variable expression Examples: x 5; y 7; x x + y; Before the assignment xx + y, x and y have the values ​​5 and 7. To determine the value of the expression x + y, the variables are replaced by their current values ​​and then calculated x + y = 12. The value determined in this way becomes the new value from x. 23 October / 19

23 A first program n 3; s 0; i 1; while i n s s + i; i i + 1; print s; The Execution The above is called a While Loop. As long as the condition i n is true, execute the body of the loop from October 23/19

24 A first program n 3; s 0; i 1; while i n s s + i; i i + 1; print s; The above is called a while loop. The execution n 3; s 0; i 1; i n is true (since 1 3 is true) s s + i = = 1; i i + 1 = = 2; i n is true ;. As long as the condition i n is true, execute the body of the loop from October 23/19

25 A first program n 3; s 0; i 1; while i n s s + i; i i + 1; print s; The above is called a while loop. As long as the condition i n is met, execute the body of the loop. Execution n 3; s 0; i 1; i n is true (since 1 3 is true) s s + i = = 1; i i + 1 = = 2; i n is true ;. print s outputs 6. The output of the invoice is the total October / 19

26 A first interesting program n input; s 0; i 1; while i n s s + i; i i + 1; print s; We no longer assign n a fixed value, but read it in. If you enter 3, the program calculates the sum = October / 19

27 A first interesting program n input; s 0; i 1; while i n s s + i; i i + 1; print s; We no longer assign n a fixed value, but read it in. If you enter 3, the program calculates the sum = 6. If you enter 4, the program calculates the sum. 23 October / 19

28 A first interesting program n input; s 0; i 1; while i n s s + i; i i + 1; print s; We no longer assign n a fixed value, but read it in. If you enter 3, the program calculates the sum = 6. If you enter 100, the program calculates the total. 23 October / 19

29 A first interesting program n input; s 0; i 1; while i n s s + i; i i + 1; print s; We no longer assign n a fixed value, but read it in. If you enter 3, the program calculates the sum = 6. If you enter 100, the program calculates the sum. The flowchart for the loop and as a for loop October 23/19

30 Conditional statements if condition then-if else else-if Values ​​the condition off; the condition is a logical expression that evaluates to true or false. If true, do the then-fall. If wrong, do the else-case. 23 October / 19

31 Conditional statements if condition then-if else else-if Values ​​the condition off; the condition is a logical expression that evaluates to true or false. If true, do the then-fall. If wrong, do the else-case. i 1; if i is odd i i + 1; else i i + 2; Version i 1; (i is odd) is true; therefore the then-case is carried out; i i + 1 = = 2; and now with initial value 2 i 2; 23 October / 19

32 A somewhat complicated program execution s 0; i 1; while i 4 s s + i; i i + 1; if i is odd print s else i i + 1 print s; 23 October / 19

33 A somewhat complicated program s 0; i 1; while i 4 s s + i; i i + 1; if i is odd print s else i i + 1 print s; Execution s 0; i 1; i 4 is true s s + i = = 1; i i + 1 = = 2; i is odd is wrong i i + 1 = = 3; i 4 is true; s s + i = = 4; i i + 1 = = 4; i is odd is wrong i i + 1 = = 5; i 4 is wrong; print s outputs 4. 23 October / 19

34 Even short programs can be tricky (Lothar Collatz) n is a natural number while n> 1 if n is even n n / 2; else n 3n + 1; Execution October / 19

35 Even short programs can be tricky (Lothar Collatz) n is a natural number while n> 1 if n is even n n / 2; else n 3n + 1; It is not known if this program holds for every input. Try the starting value 27. Executions October / 19

36 Even short programs can be tricky (Lothar Collatz) n is a natural number while n> 1 if n is even n n / 2; else n 3n + 1; Executions It is not known if this program holds for every input. Try the starting value, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206 , 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377 , 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102 , 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35 , 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, October / 19

37 Adding decimal numbers A first algorithm. Summand Summand Carries 0 Total 23 October / 19

38 Adding decimal numbers A first algorithm. Summand Summand Carries 0 Sum The carry over to the last column is 0. We add the three digits in one column. Call the sum S. S 10: Carry over is 1, and the sum digit is S 10. S 9: Carry over is 0, and the sum digit is p. 23 October / 19

39 Adding decimal numbers A first algorithm. Summand Summand Carries 0 Sum The carry over to the last column is 0. We add the three digits in one column. Call the sum S. S 10: Carry is 1, and sum digit is S 10. S 9: Carry is 0, and sum digit is S. Number 1 has digits a 3, ..., a 0. Number 2 has digits b 3 , ..., b 0. Sum has digits s 4, s 3, ..., s 0. We also have a carry c. c 0; for i from 0 to 3 S a i + b i + c; if S 9 s i S; c 0; else s i S 10; c 1; s 4 c; 23 October / 19

40 Adding decimal numbers And now with any number of digits. Number 1 has digits at 1, ..., a 0. Number 2 has digits bn 1, ..., b 0. Sum has digits sn, sn 1, ..., s 0. We also have a carry c . c 0; for i from 0 to n 1 S a i + b i + c; if S 9 s i S; c 0; else s i S 10; c 1; s n c; 23 October / 19

41 You can not only calculate with numbers A word is a sequence of letters, e.g., hope. We want to determine whether a word (the pattern) occurs in another word (the text). To do this, we apply the pattern to each point of the text and compare letter by letter. 23 October / 19

42 Calculate with letters. Pattern = Hope Text = It was the best time, it was the worst time. It was the time of wisdom, it was the time of stupidity. It was a time of belief, it was a time of disbelief. It was a time of enlightenment, it was a time of darkness. It was the spring of hope, it was the winter of hopelessness. A story from two cities (Charles Dickens) Text has letters t 0, ..., t n 1. Pattern has letters p 0, ..., p k 1. for i from 0 to n k matches true; for j from 0 to k 1 if t i + j p j does not match; if matches = true print i; 23 October / 19

43 Comments Comments are used to improve intelligibility. They have no effect, they are only used for explanatory purposes. # Text has letters t 0, ..., t n 1. # Pattern has letters p 0, ..., p k 1. # have to rewrite the program October 23/19

44 Summary The value of variables can be changed by assigning values. Programs are formulated in programming languages ​​(C, C ++, Java, Python, etc.). Our example programs would look similar in the programming languages ​​mentioned, but with historically confusing notations: x = 5 instead of x 5 and Is x == y? instead of Is x = y ?. Algorithms are formulated in pseudocode. The level of detail depends on the readership. 23 October / 19