Please enable JavaScript.
Coggle requires JavaScript to display documents.
Random Numbers, Limits to Computation - Coggle Diagram
Random Numbers
Definitions of randomness
One cannot predict the next item. The series is unpredictable
The series cannot be described more briefly than simply listing it out. This is
the equidistribution property
A sequence is pseudorandom if no future term can be predicted in
polynomial time, given all past terms.
Most computer systems use a deterministic algorithm to select pseudorandom
numbers
The most commonly is the Linear
Congruential Method (LCM).
Example 16.4 Given a t value of 13, we can get very different resultsdepending on the b value that we pick, in ways that are hard to predict.
r(i) = 6r(i − 1) mod 13 =
..., 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, ...
r(i) = 7r(i − 1) mod 13 =
..., 1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, ...
r(i) = 5r(i − 1) mod 13 =
..., 1, 5, 12, 8, 1, ...
..., 2, 10, 11, 3, 2, ...
..., 4, 7, 9, 6, 4, ...
..., 0, 0, ...
Clearly, a b value of 5 is far inferior to b values of 6 or 7 in this example
Discrete Fourier Transform (DFT).
Fourier Transform(double *Polynomial, int n) {
// Compute the Fourier transform of Polynomial
// with degree n. Polynomial is a list of
// coefficients indexed from 0 to n-1. n is
// assumed to be a power of 2.
double Even[n/2], Odd[n/2], List1[n/2], List2[n/2];
if (n==1) return Polynomial[0];
for (j=0; j<=n/2-1; j++) {
Even[j] = Polynomial[2j];
Odd[j] = Polynomial[2j+1];
}
List1 = Fourier Transform(Even, n/2);
List2 = Fourier Transform(Odd, n/2);
for (j=0; j<=n-1, J++) {
Imaginary z = pow(E, 2
i
PI*j/n);
k = j % (n/2);
Polynomial[j] = List1[k] + z*List2[k];
}
return Polynomial;
Limits to Computation
The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be performed with a given amount of mass, volume, or energy.
Reductions
Reduction allows us to solve one problem in terms of another. Equally importantly, when we wish to understand the difficulty of a problem, reduction allows us to make relative statements about upper and lower
Hard Problems
There are several ways that a problem could be considered hard. For example, we might have trouble understanding the definition of the problem itself. At the beginning of a large data collection and analysis project, developers and their clients might have only a hazy notion of what their goals actually are, and need to work that out over time.