For the final week, I still can not get the concept of computability, I looked at some others slogs and it helps me alot.
http://ttesttrying.blogspot.ca/2014/11/csc-165-computability-review.html
http://www.reddit.com/r/journeythrough165/comments/2n1j08/week_11_computability_countability/
http://yuejiang165.blogspot.ca/2014/11/week-11.html
From the third slog, I had more clear concept of proving if a program is computable.
This week was review of computability, and studied some others slogs. And assignment 3 is due next monday!!!
And finally, I really enjoyed reading other slogs and I can learn a lot from reading slogs.
2014年12月2日星期二
week 11
Halting problems and Computability
The things we learned in this week is something new.
def H(f ,i)
"""
return True if f(i) = 42, else False
"""
In this case, if f is a well defined function, then we can say what f(i) is for every i in some domain, but we can not say how to compute f(i), in other words, it means f is not computable.
The things we learned in this week is something new.
def H(f ,i)
"""
return True if f(i) = 42, else False
"""
In this case, if f is a well defined function, then we can say what f(i) is for every i in some domain, but we can not say how to compute f(i), in other words, it means f is not computable.
week 9
We have been continuing doing some proves on concepts of big-oh and big-omega notations.
The definition of big-oh notation is f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
The definition of big-omega notation is f(n) = Ω(g(n)) means there are positive constants c and k, such that f(n) ≥ cg(n) ≥ 0 for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
But the difference between this week and last week is that, we are proving the relationship between two functions, rather than estimating the steps of a program would take.
For example, f(n) = O(g(n)), all we need to prove is f(n) will eventually dominated by g(n)
In this case, we need to prove from a point, (6n^5 - 4n^3 + 2n) ≥(5n^4 - 3n^2+1)
The definition of big-oh notation is f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
The definition of big-omega notation is f(n) = Ω(g(n)) means there are positive constants c and k, such that f(n) ≥ cg(n) ≥ 0 for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
But the difference between this week and last week is that, we are proving the relationship between two functions, rather than estimating the steps of a program would take.
For example, f(n) = O(g(n)), all we need to prove is f(n) will eventually dominated by g(n)
In this case, we need to prove from a point, (6n^5 - 4n^3 + 2n) ≥(5n^4 - 3n^2
week 8
After the tutorial, I had some idea of big-oh notation. We had same proofs in the lectures as last week, but for this time, I can understand the steps of professor took in the lectures. I started to know the steps taking in while loops and the constant steps.
In IS, the constant steps is step 1 and there are two while loops. Then we need to estimate the maximum steps would take for IS.
And the definition of big-oh notation is: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
In IS, the constant steps is step 1 and there are two while loops. Then we need to estimate the maximum steps would take for IS.
And the definition of big-oh notation is: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
week 7
For this week, I was lost in the lectures, big-oh is so new to me and I can not understand the concept of big-oh totally, in the lecture, we had a python program and we estimate the worse case for computer to process the steps, which means estimating the maximum steps that computer would take to process the program. for example:
And we need to prove that worst case of IS is in big-oh of n square.
week 6
We had a long-weekend, Thanksgiving holiday!!!
For this week, it was level-up from last week, questions are getting harder, and the statements are need to prove is more complex, but the whole technique is same, universal and existential.
The statements are now containing multiple quantifiers. which made me to think more and takes longer time to understand the statements, then I can decide to prove or disprove it.
For this week, it was level-up from last week, questions are getting harder, and the statements are need to prove is more complex, but the whole technique is same, universal and existential.
订阅：
博文 (Atom)