Random Number Generator

Automata: Regular Expression

Usually we prove that a language is not regular by using the Pumping Lemma (PL). But that's not very pleasant. Instead of looking at regular expressions, let's look at finite automata. A finite automaton has a finite number of states, and states is all you have in order to keep track of what you've done so far and, therefore, of what need to be done.

Here are some of the problems that our instructor Prof. Larmie Feliscuzo Santos give us that makes me bleed and I even consult it to science forums and here is what the reply....

1. regular expression for w contains even number of a's and b's
This is a regular expression because we never need more than 2 bits to remember where we are:
00 = we are OK
01 = we need another 'b'
10 = we need another 'a'
11 = we need another 'a' and another 'b'

Thus, we need 4 states:
OK ----a----> NEEDA
OK ----b----> NEEDB
NEEDA----a---->OK
NEEDA----b---->NEEDA&B
NEEDB----a---->NEEDA&B
NEEDB----b---->OK
NEEDA&B----a--->NEEDB
NEEDA&B----b--->NEEDA

This is tough:
( aa | bb | (ab|ba)(aa+bb)*(ab+ba) )*

2. every a is followed by b
This is simple: we just need one bit:
0 = we don't need a 'b'
1 = we need a 'b' right now

We have 2 states:
OK ----a---->NEEDB_NOW_
OK ----b---->OK
NEEDB_NOW_----b---->OK

(ab|b)*

3. palindrome: w = reverse of w
Impossible. If a string is palindrome and of length n, we need to remember n/2 characters to check that it is really palindrome. That n is unbounded, because if we fix a number of states, then we can enter a string that would need even more states. Remember that states =~ MEMORY.

I guess this is right. Thanks to the scienceforum especially to gandalf23.

ann_sarte2007

ann_sarte2007

Shared via AddThis

Random Number Generation (RNG)

It is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. Hardware-based systems for random number generation are widely used, but often fall short of this goal, though they may meet some of the statistical tests for randomness intended to ensure that they do not have any easily discernible patterns.

Practical Applications:

RNG have applications in gambling, statistical sampling, computer simulation, cryptography, completely randomized design, and other areas where a random number is useful in producing an unpredictable result.

Random number generators are very useful in developing Monte Carlo method simulations as debugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same random seed. They are also used in cryptography so long as the seed is secret. Sender and receiver can generate the same set of numbers automatically to use as keys.

The generation of pseudo-random numbers is an important and common task in computer programming. While cryptography and certain numerical algorithms require a very high degree of apparent randomness, many other operations only need a modest amount of unpredictability. Some simple examples might be presenting a user with a "Random Quote of the Day", or determining which way a computer-controlled adversary might move in a computer game. Weaker forms of randomness are also closely associated with hash algorithms and in creating amortized searching and sorting algorithms.

Two principal methods to generate random numbers:
1. Physical Methods. If there are such things as "true" random numbers, they are most likely to be found by looking at physical processes which are, as far as is known, unpredictable. The earliest methods for generating random numbers — dice, coin flipping, roulette wheels — are still used today, mainly in games and gambling as they tend to be too slow for applications in statistics and cryptography. Generating true random numbers outside the computer environment is based on the theory of entropy. A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose unpredictability can be traced to the laws of quantum mechanics. Sources of entropy include radioactive decay, thermal noise, shot noise, clock drift, and atmospheric conditions.

Various imaginative ways of collecting this entropic information have been devised. Atari 8-bit computers used electronic noise from an analog circuit to generate true random numbers. One common technique is to run a hash function against a frame of a video stream from an unpredictable source. Lavarand used this technique with images of a number of lava lamps. Lithium Technologies uses a camera pointed at the sky on a windy and cloudy day. HotBits measures radioactive decay with GM tubes, while Random.org uses variations in the amplitude of atmospheric noise recorded with a normal radio.

Some physical phenomena, such as thermal noise in Zener diodes appear to be truly random and can be used as the basis for hardware random number generators. However, many mechanical phenomena feature asymmetries and systematic biases that make their outcomes not truly random. The many successful attempts to exploit such phenomena by gamblers, especially in roulette and blackjack are testimony to these effects. Another common entropy source is the behavior of human users of the system, if such users exist. While humans are not considered good randomness generators upon request, they generate random behavior quite well in the context of playing mixed strategy games. Some security-related computer software requires the user to input a lengthy string of mouse movements or keyboard input to add a certain degree of randomness to computational pseudo-random number generation.

2.Computational Methods.Pseudo-random number generators (PRNGs) are algorithms that can automatically create long runs with good random properties but eventually the sequence repeats (or the memory usage grows without bound). One of the most common PRNG is the linear congruential generator, which uses the recurrence to generate numbers.

X_n+1 = (aX_n + b) mod m
or
X_n = (aX_n-1 + b) mod m

The maximum number of numbers the formula can produce is the modulus, m. To avoid certain non-random properties of a single linear congruential generator, several such random number generators with slightly different values of the multiplier coefficient a are typically used in parallel, with a "master" random number generator that selects from among the several different generators. A simple pen-and-paper method for generating random numbers is the so-called middle square method suggested by John Von Neumann. While simple to implement, its output is of poor quality.

Most computer programming languages include functions or library routines that purport to be random number generators. They are often designed to provide a random byte or word, or a floating point number uniformly distributed between 0 and 1.

Travelling Salesman Problem

The Travelling Salesman problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. It's origin is unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment.

The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as genome sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.

In the theory of computational complexity, the decision version of TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSP problems. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly.

Euclidean Algorithm

In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). The algorithm is also called Euclid's algorithm, after the Greek mathematician Euclid, who described it in Books VII and X of his Elements.

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12; 105 = 21 × 5); since 252 − 105 = 147, the GCD of 147 and 105 is also 21. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number. By reversing the steps in the Euclidean algorithm, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. This important property is known as Bézout's identity.

The earliest surviving description of the Euclidean algorithm is in Euclid's Elements (c. 300 BC), making it one of the oldest numerical algorithms still in common use. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains. The Euclidean algorithm has been generalized further to other mathematical structures, such as knots and multivariate polynomials.

The Euclidean algorithm has many theoretical and practical applications. It is a key element of the RSA algorithm, a public-key encryption method widely used in electronic commerce. It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. The Euclidean algorithm can also be used in constructing continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modern number theory, such as Lagrange's four-square theorem and the fundamental theorem of arithmetic (unique factorization).

Euclid's algorithm computes the GCD of large numbers efficiently, because it never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Methods for improving the algorithm's efficiency were developed in the 20th century.

Brazilian Soccer Schools, Leeds, England

Brazilian Soccer Schools, Leeds, England

Shared via AddThis

GoBoardz - Computers - Programming Languages

GoBoardz - Computers - Programming Languages

Shared via AddThis

Computer science (or computing science) is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.It is frequently described as the systematic study of algorithmic processes that describe and transform information; the fundamental question underlying computer science is, "What can be (efficiently) automated?" Computer science has many sub-fields; some, such as computer graphics, emphasize the computation of specific results, while others, such as computational complexity theory, study the properties of computational problems. Still others focus on the challenges in implementing computations. For example, programming language theory studies approaches to describing computations, while computer programming applies specific programming languages to solve specific computational problems, and human-computer interaction focuses on the challenges in making computers and computations useful, usable, and universally accessible to people.

The general public sometimes confuses computer science with vocational areas that deal with computers (such as information technology), or think that it relates to their own experience of computers, which typically involves activities such as gaming, web-browsing, and word-processing. However, the focus of computer science is more on understanding the properties of the programs used to implement software such as games and web-browsers, and using that understanding to create new programs or improve existing ones.