We started off this lecture with a big-omega proof. It is similar to a big-oh proof, only in that we underestimate the function and over-estimate the inside of the bracket.
Takeaway:
-magic breakpoint B=1
-simplify the function without changing the highest degree
Next, we learned the proof of general statements for big-Oh: using a definition of function sets, we can group functions together. For example, all the functions we work with take in a natural number, and return a non-negative real number. For these problems, the main point is to find a relationship between the c values, B values and that of the others. A relationship (comparative) can be manipulated to prove a statement or definition.
Computability:
The next part of our lecture was on Computability. Computers cannot solve everything, as there are some functions that are impossible to define. These will cause infinite loops or/and causing the program to crash.
However, if we can reduce a function to another one, then we just need to find the computability of the reduced function.
computable implies computable, and non-computable implies non-computable.
No comments:
Post a Comment