7.1 Proof by cases
Proof by cases is one kind of intuitional way in life. We think every different possibility of one case and prove all these possibilities are true. In class, we face to the following problem:
∀n∈N,n^2+n is even
n2 + n = n (n+1)
To solve this case, we think all possibilities of n, which means n may be either even or odd.
If n is even, then n(n+1) is also even.
If n is odd, the n+1 must be even, n(n+1) is even.
The thinking above is just a rough one, we need to write the proof process academically:
Assume n ∈N
then (∃k∈N, n=2k+1) ∨ （∃k∈N, n=2k）
Case1: assume ∃k∈N, n=2k+1:
then n2 + n = n (n+1) = (2k+1)(2k+2)
=2 [(2k+1)(k+1)]
=2j let j be [(2k+1)(k+1)]
Case2: assume ∃k∈N, n=2k:
then n2 + n = n(n+1) =2k(2k+1)
=2[k(2k+1)]
=2k let k be [k(2k+1)]
Then n2+n is even
7.2 Review of proof patterns
This section aims to conclude all the ways of proof and find the pattern of them.
Generally there are two patterns of inference rules(from what we know to what we can infer):
Introduction rules start from a small statement and finally infer a bigger statement.
Elimination rules start from a big statement and finally infer a smaller statement.
7.3 Algorithm Analysis and Asymptotic Notation
This section seems very computer science related, but I do not think the professor explain the idea of algorithm very well as algorithm means. I think algorithm is a kind of sovereign goal that every computer scientist may pursue. In a lot of real life situations, there might be a lot of ways to solve a problem. Normal people may simply find one way and solve it. However, a computer scientist may find all possible ways and compare them, choose the best one in the end. The wordload is much higher than simply find one way while the final result is the same----The problem is solved. But this perfectionism makes the progress of the whole subject.
In the class we compare two sorting algorithms which are bubble sort and merge sort. These two can both achieve the goal of sorting certain codes, but the running time is totally different.
Running time does not mean the actual seconds of time the program run, because the actual time may vary depend on how powerful the hardware is. So even the program is not so efficient, one can still get the result faster than those who run a better program but on a poor hardware. Thus, if all programs are run on the same hardware, the number of steps is the real determinants.
By seeing the process of working, we find as the size of codes become larger, the more number of steps bubble would take rather than merge. In conclusion, the general pattern that bubble would take is 0.5n2 (though we do not study why is it.) and merge would take n log n.
Another important idea in algorithm is the significance of highest degree variables. That is to say x2 is no difference than 100000x2 because their variable's highest degree is the same.
Also, we may use the symbol O(f(n)) to presents the idea that a set of functions run no faster than f(n). (e.g.: 5x2 + 3x +1 is in O(3x2))
没有评论:
发表评论