Interactive test mathematical foundations of computer science. Mathematical foundations of computer science
Syllabus
| №_NEWSPAPERS | Lecture |
Lecture 1.What is “mathematical foundations of computer science”. Why is computer science often considered akin to Information and its coding. Mathematics of codes. Error correction codes. Economical coding. |
|
| Lecture 2 .Mathematical models of formal performers. What is formal information processing? End- new machines. What comes first: the language or the performer? Grammar of the language. Recognized languages. Universal versions teli (Turing machine, Post machine). |
|
| Lecture 3 .Algorithm and its properties. Algorithmic undecidability. Computability. Complexity. | |
| Test No. 1. | |
| Lecture 4. Graphs. Graphs and digraphs. In what tasks do they arise? Various properties of graphs (Eulerian, Hamiltonian) news, planarity, bipartiteness). Networks. Flows in networks. Graph representation. Basic graph algorithms. |
|
| Lecture 5. Logic models in computer science. Algebra of propositions. Boolean functions. Normal forms. Full classes of Boolean functions. Relay contact diagrams. Valves. Mathematical models of computer processor and memory. Predicates and relations. Relational algebra. Theoretical foundations of relational DBMS. Logic programming languages and their mathematical basis. |
|
| Test No. 2. | |
| Lecture 6. Computer number theory and computational geometry. Why is number theory needed in computer science? sciences? Race for prime numbers. How to factor a number? What is the difference between theoretical geometry and computing? Why is it smooth on paper, but clumsy on the computer? Basic rules and algorithms of computing geometry. |
|
| 23/2007 | Lecture 7. Information protection. Protection of symbolic information. What needs to be protected? Electronic signature. Systems verification. Public key cryptosystems. Protection of graphic information. The mathematics of electronic watermarks. |
| 24/2007 | Lecture 8. Fundamentals of methods for teaching the mathematical foundations of computer science. |
| Final work |
Lecture 7. Computer number theory
Number theory and geometry... Two branches of mathematics, which from ancient times gave it the spirit of a game of high intelligence, in which the beauty of logical constructions reigned. To the student’s seemingly innocent and natural question, “What is the use of geometry?” Euclid ordered the slave to give the student a coin and drive him away. “He is looking for benefits in geometry!” - Euclid responded indignantly.
The uselessness of number theory for the national economy seems even more obvious. Well, tell me, who found it easier to live after receiving an answer to the question whether the equation has a solution in natural numbers? x n + y n = z n, If n> 2? But this question, known as Fermat’s Great Problem, has troubled mathematicians for more than 300 years. And even the fact, proven by Euclid, that there are infinitely many prime numbers, is unlikely to help increase the national gross product.
The computer is another matter. The thing is, without a doubt, useful. True, limited. And the number of memory cells, although large, is finite. And the capacity of each cell is also finite. So numbers like or p, due to their irrationality, “do not fit” into a computer. How can you see an infinite straight line on a computer screen? What if there are two straight lines, and to the eye they look parallel? What if there is still a point of intersection, but somewhere far, far away?
Finite and infinite, rational and irrational - these are the opposites presented in mathematics vividly, one might say, in naked form. The irrational and infinite fascinates, like looking into the bottomless depths of space or into the foundations of the universe. This is something that is inaccessible to sensation, but is subject only to reason. And a small, limited computer, no matter how powerful, seems useless here.
In 1742, Goldbach, in a letter to Euler, hypothesized that every odd number, starting with 7, can be represented as the sum of three prime numbers. For almost 200 years, the solution to the problem could not get off the ground. In 1934, Academician I.M. Vinogradov proved that there is a certain number N, such that all odd numbers greater than N, can be represented as the sum of three prime numbers. Moreover, this number N was calculated (K. Borozdkin): N = her 16,038. It has only 4,008,659 digits. And no infinity. It is enough to check the statement for all odd numbers less than N, and Goldbach's problem will be solved. A person, of course, cannot do this. But, unfortunately, computer systems are not yet up to the task.
In the second half of the 20th century, many number theory theorems accumulated, which claim that everything is fine, starting from a certain N, i.e. there, far away, where we are not. And, alas, we cannot reach this limit by simply using a computer. It turned out that number theory became a supplier of problems that were extreme for a computer in terms of memory capacity, speed, and efficiency of the algorithms being developed. In addition, mathematicians need proof that the created computer program works correctly. But you can’t double-check the results manually. It required the development of very sophisticated methods for proving the correctness of algorithms and programs (note that these are, generally speaking, not the same thing). We talked about some of these methods in Lecture 3. Here we will tell you how mathematicians help curb infinity and irrationality.
We can say that this lecture is about the collaboration of pure mathematics and computer science.
§ 24. Using a computer in number-theoretic research
The above general discussions about the use of computer calculations in proving mathematical statements are probably quite transparent. Nevertheless, it seems useful to see how they actually come to fruition. We, of course, will not undertake to solve this or that famous number-theoretic problem, but will demonstrate this using a not very difficult problem.
Problem 1. Is it true that for any digit N other than zero, there is a natural number ending with the digit N and such that moving it to the beginning of the number increases the number N times?
At N= 1 the positive answer is obvious: any number made up of more than one 1 is suitable, for example, 11. What about other values? N?
There are very few non-zero numbers; you can try to get an answer for each of them. Let's start with N= 2. The number ends in 2, and after moving this digit to the beginning, you should get a number 2 times larger, and therefore it ends in 4. This means that the original number ends in 42. Then, after moving the digit 2 to the beginning, you should get a number ending in by 84. This means that the original number ends in 842. Continuing the reasoning, we find that the previous number is 6. The process has begun. But where is the guarantee that it will end?
If the reader has enough patience, he will be convinced that in this case a happy ending awaits him - at the seventeenth step, the number 105,263,157,894,736,842 will be obtained, satisfying the requirements of the problem.
The process described above is not difficult to program, but how long does it take to wait for a response? What if for some N Doesn't such a number exist? Then the program will run forever 1.
And again we have to call on mathematics to help. First, let us slightly change the condition of the problem, proposing to consider a more general situation 2 .
Problem 2. It is known that a number increases by K times by moving the last digit to the beginning. At what K can this happen? For each such K, find the smallest number that satisfies the given condition.
In this problem, unlike Problem 1, it is not required that the number itself also begins with K; moreover, a natural number K does not have to be a number.
Solution. Let us denote by A original number, through B- the number resulting from A by moving the last digit to the beginning. Then K = B/A. Happening K= 1 is not of interest, because then A = B and the smallest number, as we noted, is 11. (Note, by the way, that in this case, the rearranged digit coincides with K.) Therefore, in what follows we will assume that K 2.
First of all, let's figure out how many digits can be K. Since the numbers B And A have the same number of digits, ratio B To A does not exceed 9. So K 9 (i.e. we can say that the very K is always a “digit”).
Let X- last digit of the number A(aka the first digit of the number B), A Y- a number formed by all the digits of a number A, except the last one. Let also n- number of digits in a number Y. Then A= 10 · Y + X, A B = X· 10 n + Y. Thus, we obtain the equality:
X 10 n + Y = K(10 Y + X),
.
Denominator 10 K– 1 is always two-digit. Here are the values it takes:
The third line of this table shows the value of the multiplier in front of it in the form of an irreducible fraction. X at n= 1. This means that for no digit X at n= 1 value Y doesn't work out whole. Means, n 2.
The fact that Y has on record n digits means 10 n–1 Y< 10n. From here for X we get a double inequality:
.
The left side of this inequality can easily be transformed to the form:
Because n 2 and K 9, fraction (10 n–1 – K) : (10n – K) is positive and less than 1. Considering that X is an integer, the left side of the inequality can be written K X.
Let us now deal with the right side of this inequality. Similar transformations show that it is equal
.
Because K 9 and n 2, fraction 9 K / (10 n – K) is positive and less than 1. Considering that X- an integer, the right side of the inequality can be written X 10K– 1. However, this inequality does not give us much, since by condition X and so less than 9.
So, we found out that the moved digit cannot be less than K. So in Problem 1 we simply take the smallest possible value for the digit being moved.
Now let’s deal with the main question of Problem 2: under what conditions? K there is something like this n that number Y will it be intact? In other words, for which K exists n, at which 10 n – K divisible by 10 K– 1? Here we will use the following idea. For the convenience of further discussion, let us denote the number 10 K– 1 letter m. It is clear that the number m has no common divisors other than 1 with the number 10. In particular, no power of the number 10 is divisible by m without a trace.
Consider the sequence of powers of the number 10:
1 = 10 0 ; 10 1 ; 10 2 ; 10 3 ; ...; 10m-1,
and the sequence of remainders from dividing these numbers by m. All these remainders, as was said, are nonzero. However, various non-zero remainders when divided by m just m– 1. This means that in this sequence of powers there are two numbers with identical remainders when divided by m. Let it be 10 a and 10 b, Where
0 a < b m– 1. Then 10 b – 10 a divided by m. But 10 b – 10 a = 10 a
(10 b-a– 1), and the number m has no non-unit common divisors with the number 10. Therefore on m in this product the number 10 is divided b-a– 1. Let us denote b – a through t.
Thus, we have proven that there is such a positive exponent t m– 1, which is 10 t– 1 is divided by m. We can assume that t is chosen to be the smallest with the property that 10 t– 1 is divided by m. In other words, among the powers of 10 1 ; 10 2 ; 10 3 ; ...; 10 t-1 none leaves a remainder of 1 when divided by m. And starting from 10 t the remainders will be repeated in the same sequence. Thus, no other remainders when divided by m powers of the number 10, except those found in the series 1 = 10 0 ; 10 1 ; 10 2 ; 10 3 ; ...; 10 t-1, No. To m the number 10 is divisible n – K, need to K have a remainder when dividing the appropriate power of 10 by m. And this can be found out by constructing a simple cyclic algorithm, since it is known what the largest number of powers will have to be considered in order to understand whether the required remainder will occur: no more than m– 1. Here is the corresponding algorithm:
alg task_2 ( arg int K)
given 2 K 9
necessary| print the exponent of the number 10,
| giving remainder K at
| dividing this power by 10K–1.
beginning intact X, N
nc Bye Not(X = K or N = M)
X:= mod(10*X, M)
That conclusion N
otherwise output"There is no such degree"
The results of this algorithm are presented in the following table:
Since under no acceptable value K the algorithm did not produce a message about the absence of a suitable degree, we proved the following theorem:
Theorem. For every natural K 9 there is a number that increases by K times when the last digit is moved to the beginning.
Notice how a computer was used to prove this theorem. Firstly, the finiteness of the number of options to be searched was proven, and secondly, using the compiled algorithm, we were not looking for the number itself, but were checking the fulfillment of some condition that is necessary and sufficient for the existence of a number with the desired property.
However, using the resulting table, it is easy to indicate the numbers themselves with the required property - as X need to take it K and use the resulting formula for Y to find the number required there A:
Those who wish can now obtain a record of the number A numbers (for example, when K= number 5 A= 510 204 081 632 653 061 224 489 795 918 367 346 938 775; and the longest number is obtained with K= 6 - it contains 58 digits).
Note that not all of the given answers to problem 1 are answers to our problem 2: when K= 5 (and only with this value K) 3 there is a smaller number that satisfies the conditions of the problem. This number is obtained if X take equal to 7. Then you will need to find the power of the number 10, which gives a remainder of 5 when divided not by 49, but only by 7. The exponent of such a power is equal to 5. The required number in this case is 10(10 5 – 5) / 7 + 7 = 142,857. This number is simply “tiny” in comparison with the 42-digit number given above, which is obtained as the answer to problem 1.
Of course, this is just a demonstration of how a computer can be applied to proving a theorem. In fact, if you think about it a little more, you can prove the following statement: if 10 t– 1 is divisible by 10 K– 1, then 10 t-1 when divided by 10 K– 1 necessarily gives the remainder K. Thus, in proving the theorem it was possible to do without a computer. However, today there are a number of mathematical statements, the proof of which cannot yet be obtained without a computer. Here's just one example. It has long been known (since the 17th century) and it is not difficult to prove using school algebra that the number 2 n– 1 can be prime only if the number itself n is simple. Numbers of type 2 n– 1 even received a special name - Mersenne numbers - after the name of the medieval monk who drew the attention of mathematicians to these numbers 4. Unfortunately, the converse is not true: not every number of the form 2 n– 1 when idle n is simple. For example, the number 2 11 – 1 = 2047 = 23 89 is composite. Although it is unknown whether there are an infinite number of Mersenne primes, they still serve as one of the sources of large primes today. Before the invention of computers, the largest known Mersenne prime number was 2127 – 1, which has 39 digits. And it was generally the largest prime number known at that time. The advent of computers immediately increased our knowledge of Mersenne primes. Already in 1952, 5 prime numbers were discovered at once: 2,521 – 1; 2 607 – 1; 2 1279 – 1; 2 2203 – 1; 2 2281 – 1. The last one has 687 digits; Even for modern computers, factoring such a number is a very stressful task. The way out of this difficult situation is to use the so-called “Luc criterion” to prove the primeness of the Mersenne number. It is as follows. For the selected prime number r the sequence is recursively constructed s 1 , s 2 ,s 3 , …, s n, where s 1 = 4, and s k+1 - remainder when divided by numbers – 2 by r. If s p-1 = 0, then the number is 2 r– 1 simple. Yes, for r= 2281 one has to carry out calculations with no more than seven-digit numbers (since 2280 2 = 5,198,400), and this can be done in the most ordinary computer arithmetic. The situation is quite similar to the one we had when solving problem 1 - instead of looking for a 58-bit number when K= 6, we chose a different form of writing such a number and made do with calculations with no more than two-digit numbers.
§ 25. Mathematics of computer arithmeticAlready in the previous paragraph we mentioned several times the difficulties of computer calculations associated with the limited bit grid. What is behind these words?
Physically, computer memory is a numbered collection of cells. In turn, each cell consists of eight devices, each of which can be in one of two states. One of the states is encoded by the symbol 0, and the other by the symbol 1. Thus, 1 byte of information is placed in one cell.
The contents of each cell, if we discard the possible leading zeros in it, can be considered as a record of a natural number in the binary number system. In this case, the code 00000000 is associated with the number 0.
However, in addition to positive integers, there are negative ones. To indicate the sign of a number, another bit is needed. At the same time, it is agreed that its zero value corresponds to the “+” sign, and its single value corresponds to the “–” sign. Typically, the leftmost bit of the cell is allocated for the sign. Then the code for the largest natural number that can be written in one cell is 01111111. It corresponds to the decimal number +127. And the code for the smallest negative number is 111111111; in decimal notation it corresponds to the number –127.
To find the sum of numbers 101 2 and 1011 2, with their codes, you can act according to the rules for adding binary numbers: 00000101 + 00001011 = 00010000. But an attempt by the same rules to fold the numbers 1010101 2 and 111101 2 will lead to a strange result: 01010101 + 001111101 = 100100010. The result was a negative number!
It is clear to everyone: the error arose due to the fact that the bit grid of the cell contains only seven places. However, if the cell had more digits, such an error would still occur every time you need to find the sum of sufficiently large numbers.
The phenomenon described above is called overflow effect. And you have to remember about it when you are dealing with fairly large integers.
Let's now try to add a positive number with a negative one. For example, the number 1010 2 with the number –101 2. Their codes, respectively, are as follows: 00001010 and 10000101. And the result should be the natural number 101 2. Even the algorithm itself for obtaining the result code is not so easy to formulate (try, for fun, to do this), and even more so to implement a simple device that would execute this algorithm. But the computer has to perform addition quite often, so everything should be as simple and fast as possible.
To make the addition operation simpler and not dependent on the sign of the terms, negative integers are encoded in a different way. But first, let's talk about zero.
What happens if you try to write the natural number 100000000 2 into an eight-bit cell? All eight digits will be zeros. This means that the computer perceives this number as 0. This is what we will use. Subtract 101 2 from the number 100000000 2. The result is 11111011 2. If we now add this number to the number 101 2, then the computer will perceive the result as 0. Therefore, it is natural to declare the number 11111011 2 as a code for the negative number –101 2. They call him additional code given negative number.
Let's talk about one code separately. Consider the code 10000000. First, it is a negative number code because the leftmost digit is 1. The computer treats it as a complementary code. Then the direct code of the positive number opposite to it coincides with the difference 100000000 2 – 10000000 2. It is equal to 10000000, i.e. 128 10. Thus, the smallest negative number that can be written into an eight-bit cell is –128.
The code for the number 0 is 00000000. What happens if you write down the additional code for the number –0? Subtract 0 2 from 100000000 2 and get 10000000 2 . When writing to a cell, it will again be 00000000. So the computer, like you and me, does not distinguish between the numbers +0 and –0.
Of course, to calculate a negative number's complement n you can subtract 2 modulus of numbers from 100000000 each time n. But there is another way. Here's what you can do to get a negative number's complement:
1. Write down the binary code of the modulus of the number.
2. In the resulting record, replace each digit 1 with a 0, and each digit 0 with a 1.
3. Add 1 to the resulting code, considered as a natural number in the binary system.
As you can see, building additional code is easy. And since subtraction can be replaced by addition with the opposite number, switching to the complement's complement code allows you to do without subtraction altogether.
Of course, the range from –128 to +127 is in many cases too small to solve emerging problems. But it is not at all necessary to store an integer in exactly one eight-bit cell. Typically, two cells are allocated for integers - this is exactly what happens if you declare the type of a variable to be Integer. If you declare the LongInt type, then 4 eight-bit cells will be allocated for the integer. But one cell is allocated if the ShortInt type is declared.
If two cells are allocated for recording a number, then they are perceived as a single whole. The coding principle is the same: the leftmost digit is allocated for the sign of the number, the remaining fifteen digits are for the code of the absolute value of the number. For positive numbers it is used direct code, for negative ones - additional. Thus, the range of integers is: from –32,768 to +32,767 = 2 15 – 1.
At all, if used to write integers m-bit binary code, then the range of encoded numbers is from –2 m–1 to 2 m–1 – 1, with the additional code of a negative number n from this range coincides with the binary representation of the number 2 m + n.
It is clear that when multiplying integers, the overflow effect occurs even more often. How does the computer react to this? Fixed-point overflows do not interrupt the processor. Depending on the language used, diagnostics may be absent (this, for example, happens when using most versions of the Turbo Pascal language), may inform the user about this event and wait for his reaction, or may simply proceed to writing a floating point number (this happens in different versions BASIC language).
Of course, in addition to whole numbers, people actively use fractions. And any real number can be written as a finite or infinite decimal fraction. However, such a representation is necessary, as a rule, only in theoretical constructions. But in practice...
In practice, in most cases one has to deal with approximate values of quantities. Approximate values arise during measurements, when calculating large quantities, and in many other cases. Therefore, a researcher or engineer, solving a particular problem, must initially estimate how many significant figures should be present in the course of his calculations and how many should be left in the result. But this is usually discussed in mathematics courses. Now we want to draw your attention to something else.
Let's say it's decided that three significant figures are enough. Then in numbers, say, 37,200,000; –372; 3.72; 0.000372 we only need to know these three digits and what decimal place they are written from. This is exactly the information that needs to be provided to the computer. To do this, let’s present the numbers in a uniform way: we write 0 (and preceded by a “–” sign if the number is negative), then a comma, immediately after the comma we write the significant digits and multiply the resulting decimal fraction by the appropriate power of 10. This is what we get for the four numbers above :
37,200,000 = 0.372 ·10 8;
–372 = –0.372 · 10 3 ;
3.72 = 0.372 · 10 1;
0.000372 = 0.372 10 –3.
It is clear that the absolute value of any number can be represented as the product of a number between 0.1 and 1 and a power of 10 with an integer exponent. The fractional part of the first factor in this representation is called mantissa numbers, and the exponent of the number 10 is in order numbers. The very representation of a number in the form of such a product is called normalized notation numbers. Another name for this representation of numbers is writing floating point numbers. The maximum number of digits allowed in a number's mantissa determines the precision with which the number can be represented.
In a computer, numbers are represented in the binary number system. For the binary system, the normalized form of a number is its representation in the form ± m·2 p, where 0.1 2 m < 1, а r- an integer. For example,
0.1 10 = 0.0(0011) 2 = 0.11(0011) 2 –3.
A floating point number can occupy a different number of bytes in computer memory. To write a number, as they say, with ordinary precision, 4 bytes are allocated, and double precision numbers occupy 8 bytes. However, depending on the design of the computer, there are other options, for example, when 10 bytes are allocated for recording a number.
In most practical cases, what is called ordinary precision in the representation of real numbers is quite sufficient. Therefore, we will further consider only this case. In it, the sign of the number and the order are assigned
1 byte, and these are the first 8 bits. The remaining 24 bits are allocated for the mantissa. This, for example, means that the mantissa of the computer representation of the number 0.1 10 will be as follows:
110011001100110011001101
The sign of a number is encoded in the usual way: “plus” is encoded with the symbol 0, “minus” with the symbol 1. As for the order of the number, the so-called machine order. It has seven bits and is equal to a non-negative integer number for which this code is a direct binary code. For example, the code 0101011 corresponds to machine order 43. Machine order is related to number order as follows:
number order = machine order – 2 6 .
Thus, the chain 0101011 is a code of order equal to –21. And the sequence 0000000 encodes the order –64. It is easy to see that the zeroth order is coded as 1000000. The highest positive order is coded 1111111 and is equal to 63.
Here's what the complete computer code for the number 0.1 10 looks like:
Let us note once again that the representation of floating point numbers in computer memory can be carried out very differently - depending on the programming language, architectural features
etc. For example, in some languages, only one byte is allocated for the mantissa and the sign of the number is written under the mantissa, and not placed in the leftmost digit. We have demonstrated here only the basic principles of representing such numbers.
Let's now look at adding floating point numbers. If the numbers in normalized form have the same orders, then it is enough to add the mantissas of these numbers, and then normalize the resulting result if this sum is greater than 1 or less than 0.1. For example,
Although the examples are given in the binary number system, it is clear that the stated rule applies to any positional system.
If the orders of the normalized numbers are different, then when adding floating point numbers, the first step is operation alignment of orders terms. Note that the value of the number does not change when the mantissa is shifted by one digit to the right with a simultaneous increase in order by 1. Therefore, in the term with a lower order, the mantissa is shifted to the right by the difference between the orders, after which the mantissas are added, and the result is again normalized. For example,
This means that we can formulate the following rule for adding floating point numbers.
It is much easier to multiply and divide numbers in normalized form.
For example,
0.101 · 2 –3 · 0.1011 · 2 4 = (0.101 · 0.1011) · 2 –3+4 = 0.0110111 · 2 1 = 0.110111 · 2 0 .
For example,
0.1011 · 2 –3: 0.101 · 2 4 = (0.1011: 0.101) · 2 –3–4 = 1.0001100110011... · 2 –7 = =0.10001100110011... · 2 –6.
The last example shows that in practice, even with ordinary calculations, we will be forced to be content with only an approximate value of the fraction. In a computer, the limited bit grid plays an even greater role. Let, for example, we add numbers a= 0.1 2 13 and b= 0.1 · 2 –12. After aligning the orders we get:
But only 24 digits fit into the bit grid for the mantissa, not 26. Therefore, the last two digits will be lost, and the result will coincide with the first addend. It turns out that in “computer arithmetic” there may well be a + b = a, Although b 0. And this is far from the only feature of computer arithmetic. Task 15 provides an example showing that the combination law for addition may not hold.
When multiplying and dividing normalized numbers, one possible effect is to overflow the bit grid for the order of the number. Here's an example:
0.1001 · 2 32 · 0.11 · 2 33 = 0.011011 · 2 65 = 0.11011 · 2 64.
But the highest possible order is 63. Therefore, this result is not representable in computer arithmetic. Typically, the operating system or programming language compiler in this case gives an “overflow” diagnosis. However, overflow for normalized numbers can also occur during addition; in task 17 you are asked to construct a corresponding example.
In addition to the cases discussed above, when a calculation on a computer produces an incorrect result or no result at all, one must keep in mind the effects associated with rounding numbers. These effects are also due to the limited nature of the discharge grid. One of them is loss of significant figures. Take, for example, the numbers 1/1000 and 1/1004. In the binary number system in normalized form, taking into account rounding, they are equal, respectively, to 0.100000110001001001101111 · 2 –9 and 0.100000101000110010110000 · 2 –9. After subtraction, we get 0.1000010110111111 · 2 –17. The exact difference is 4/1004000. When written in normalized form with a 24-bit mantissa, we obtain 0.100001011010111011101100 · 2 –17. As you can see, only the first 11 decimal places were accurate.
So, computer arithmetic can produce the following effects:
1) rounding errors that occur when writing numbers with rounding and can accumulate during operations;
2) overflowing the bit grid of the order of numbers leads to obtaining a number that cannot be reproduced in a computer;
3) loss of significant digits when subtracting close numbers or when the bit grid of the mantissa overflows;
4) ignoring the term with a large difference in orders.
As a practical recommendation, note that for real numbers that are represented in a computer in normalized form, you should not compare them for exact equality; instead, one must compare the absolute value of their difference with a suitable small positive number corresponding to the error of representation.
Questions and tasks1. What is the main reason for the different effects of computer arithmetic?
2. What is an additional code? What are the benefits of using additional code?
3. What is the range of integers that 4 cells are used to encode?
4. What is the effect of overflow?
5. Explain why the method given in the explanatory text of the paragraph really gives an additional code for a negative number.
6. a) The following integers are written in direct eight-bit code: 01101010; 10111011; 10001001; 01010111; 11111111. Find the negative numbers among them and write them in two's complement code.
b) The following numbers are written in direct sixteen-bit code:
Find the negative numbers among them and write them in two's complement code.
7. a) Perform the addition of the numbers 100 10 and 50 10 in one-byte fixed-point integer code. What number code (in the decimal system) will the result be? (Hint: Don't forget that negative numbers are represented in two's complement.)
b) Perform the addition of the numbers –80 10 and –64 10 in one-byte fixed-point integer code. What number code (in the decimal system) will the result be?
8. Why can the combinational law be violated during computer addition of integers?
(a + b) + c = a + (b + c)? Give a suitable example to support your answer.
9. What notation of a number is called normalized? What is the mantissa and the order of a number?
10. What will be the first character of the machine order code of a number if the order of the number represented in binary normalized form is non-negative?
11. The explanatory text of the paragraph contains a four-byte record of the number 0.1 10 in the computer memory.
a) What decimal number does this entry actually represent?
b) What are the absolute and relative errors in representing the number 0.1 10?
c) Explain why the last digit of the mantissa is 1.
12. Indicate which of the following real numbers can be represented in computer memory by the four-byte floating point code described in the explanatory text.
13. Perform addition of binary numbers presented in normalized form. Normalize the result.
14. Perform multiplication of binary numbers represented in normalized form. Normalize the result.
15. Using the rules of computer arithmetic, calculate the amounts
Make sure that the combination law is violated for these numbers.
16. Explain why the combination law may be violated when multiplying floating point numbers. Provide supporting examples.
17. Give an example of two normalized binary numbers that can overflow when added.
18. To solve a certain problem, Petya compiled the following algorithm:
alg Amount1 ( arg intact N, res things :S)
beginning intact : K
input N
nc For K from 1 to N
conclusion S
In turn, Kolya compiled the following algorithm to solve the same problem:
alg Sum2 ( arg intact N, res things :S)
beginning intact : K
input N
nc For K from N to 1 With step –1
kts
conclusion S
a) Is it true that both algorithms solve the same problem?
b) Is it true that when N= 1,000,000,000 will programs that implement these algorithms give the same result if the four-byte representation of normalized numbers described in the text of the paragraph is used?
1 Of course, it won’t work forever - either the computer’s memory will overflow while calculating more and more new numbers, or Chubais will turn off the lights...
2 This technique is quite well known to mathematicians, but is rarely used in programming.
3 By the way, the proof of this statement is that for other values K there are no solutions to problem 2 that do not coincide with the solution to problem 1 - the author of the article cannot obtain without a computer.
4 However, the history of mathematics is as replete with blank spots as any other history. Some researchers believe that the Pythagoreans were already interested in Mersenne prime numbers in connection with the so-called “perfect numbers”.
Test Mathematical foundations of computer science grade 9 contains 20 questions and is intended to test learning outcomes in computer science in grade 9 on a relevant topic.
1. The set of signs with which numbers are written is called:
a) number system
b) numbers of the number system
c) alphabet of the number system
d) the base of the number system
2. What is the result of adding two numbers written in Roman numerals: MSM + LXVIII?
a) 1168
b) 1968
c) 2168
d) 1153
3. The number 301011 can exist in number systems with bases:
a) 2 and 10
b) 4 and 3
c) 4 and 8
d) 2 and 4
4. The binary number 100110 in the decimal number system is written as:
a) 36
b) 38
c) 37
d) 46
5. In class 110010 there are 2% girls and 1010 2% boys. How many students are there in the class?
a) 10
b) 20
c) 30
d) 40
6. How many digits of 1 are there in the binary representation of the decimal number 15?
a) 1
b) 2
c) 3
d) 4
7. What is the result of adding the numbers 110 2 and 12 8?
a) 6 10
b) 10 10
c) 10000 2
d) 17 8
8. A computer memory cell consists of homogeneous elements called:
a) codes
b) discharges
c) numbers
d) coefficients
9. The number of bits occupied by a two-byte number is:
a) 8
b) 16
c) 32
d) 64
10. The following is entered into the sign digit of the cell for negative numbers:
a) +
b) —
c) 0
d) 1
11. Real numbers are represented on the computer in:
a) natural form
b) expanded form
c) normal form with normalized mantissa
d) in the form of an ordinary fraction
12. Which sentence is not a statement?
a) No reason excuses impoliteness.
b) Be sure to become an excellent student
c) Manuscripts do not burn
d) 10112 = 1 2 3 + 0 2 2 + 1 2 1 + 1 2 0
13. Which statement is false?
a) Familiar v stands for logical OR operation
b) Logical operation OR otherwise called logical addition
c) Disjunction is also called logical addition
d) Familiar v denotes the logical operation conjunction
14. For which of the indicated values of the number X is the statement true?
((X ?
a) 1
b) 2
c) 3
d) 4
15. For which symbolic expression is the following statement true:
“NOT (First letter is consonant) AND NOT (Second letter is vowel)”?
a)abcde
b) bcade
c) babas
d) cabab
16. A certain segment of the Internet consists of 1000 sites. The search server automatically compiled a table of keywords for sites in this segment. Here is its fragment:
scanner - 200
printer - 250
monitor - 450
How many sites will be found by request? printer | scanner | monitor,if on request printer | scanner 450 sites were found by request printer & monitor- 40, and on request scanner & monitor - 50?
a) 900
6) 540
c) 460
d) 810
17. Which logical expression corresponds to the following truth table?
A B F
0 0 1
0 1 1
1 0 1
1 1 0
18. When the computer broke down, its owner said: “The RAM could not fail.” The son of the computer owner suggested that the processor had burned out, but the hard drive was working. The service technician who came said that, most likely, everything was fine with the processor, but the RAM was faulty. As a result, it turned out that two of them said everything correctly, and the third said everything wrong. What's broken?
a) RAM
b) processor
c) hard drive
d) processor and RAM
19. A traffic accident occurred at the intersection, which involved a bus (A), a truck (D), a passenger car (L) and a minibus (M). Witnesses to the incident gave the following testimony. The first witness believed that the bus was the first to enter the intersection, and the minibus was the second. Another witness believed that the last car to enter the intersection was a truck, and the second was a truck. The third witness assured that the bus was the second to enter the intersection, followed by a passenger car. As a result, it turned out that each of the witnesses was correct in only one of their statements. In what order did the cars enter the intersection? The answer options list the first letters of the names of vehicles in a row without spaces in the order of their departure to the intersection.
a) AMLH
b) AGLM
c) GLMA
d) MLGA