-
When we refer to the computability of a problem on a computer, what question are we trying to answer?
We want to know what the limitations of the problem-solving capabilities of computers.
-
When we refer to the complexity of solving a problem with a computer, what are we referring to?
We want to know what kinds of problems can be solved on a computer in a reasonable time, using a reasonable amount of memory.
-
What are the three main components of a Turing machine?
A Turing machine consists of a tape (that extends infinitely in both directions), a read/write head that moves at the direction of the control unit, and a control unit that keeps track of what "state" the machine is in, directs the tape to move (and in which direction), and whether and what the head should write.
-
How does the control unit decide what the machine should do?
- The control unit keeps track of the state of the machine (what it is currently doing), then evaluates the current symbol under the read/write head to make 3 determinations:
- 1) determine which symbol to place in the current cell
- 2) determine whether to move the read/write head one cell to the left or right, and
- 3) determine the next state of the machine
-
A Turing machine can be defined by a ____________________________.
state transition diagram
-
Review state transition diagram class activity.
-
What is the Church-Turing Thesis?
The Church-Turing Thesis states that the set of functions that can be calculated on a computer is exactly the same as the set of functions for which a Turing machine can be devised.
-
Give an example of a problem that has been proven to be non-computable.
The Halting Problem has been proven to be non-computable. It asks: given a program with a set of input values, does the program halt on that input, or does it get stuck in an infinite loop?
-
What does time complexity refer to?
It is a measure of how many steps are executed when the associated program is run. (Big O notation)
-
What does "Big O" notation provide information about?
- It provides information regarding the program's "order of complexity".
- O(1) -> execution time doesn't relate to the size of the number n.
- O(n) -> execution time increases linearly as n increases
- O(n*squared) -> execution time increases quadratically as n increases
-
Name three types of complexity an algorithm can have other than linear and quadratic (also not O(1)).
- *logarithmic - number of steps in its execution is bounded by a logarithmic function (k ln(n))
- *polynomial - number of steps in its execution is bounded by a polynomial function (ix^2+jx+k)
- *exponential - number of steps in its execution is bounded by an exponential function (k*2 to the n)
-
Why do we care about the complexity of an algorithm?
When you perform a small number of calculations, you can use an algorithm that is costly in time and not be penalized too much. But if you apply the same algorithm to a large number of calculations, the problem may take so long on your machine that it is effectively incalculable.
-
What is The Knapsack Problem?
You have a knapsack that can hold up to W weight; no more than that. Given a set of jewels, each of which has a weight w and a price p, pack the maximum worth of gems into the knapsack without exceeding its capacity.
|
|
