csp unit 6

Simulations are computer representations of real things or situations that vary over time. A simulation is an abstraction designed for a particular purpose.

An infinite loop is a sequence of computer instructions that repeats forever.

An unsolvable problem is one for which no algorithm can ever be written to find the solution.

An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value. Undecidable problems are a subcategory of unsolvable problems that include only problems that should have a yes/no answer (such as: does my code have a bug?).

Lossless data compression algorithms (such as PNG) are reversible (there is no loss in quality); you can reconstruct the original data.

Lossy data compression algorithms are not fully reversible; you can reconstruct only an approximation of the original data.

A binary sequence (also called a bitstream) is a string of ones and zeros.

Analog data have values that change smoothly, unlike digital data which change in discrete intervals.

Sampling means measuring values, called samples, of an analog signal at regular intervals.

The sampling rate is the number of samples measured per second.

A bit is a single unit of data that can only have one of two values. We usually represent the two values as 0 (off) and 1 (on).

A byte is eight bits.

A word is a sequence of however many bits the CPU processes at a time. As of 2017, words are 32 or 64 bits.

Metadata are data about data. For example, the piece of data may be an image, while the metadata may include the date of creation or the file size of the image.

A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated. Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.

The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.

An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten.

A linear search (or sequential search) algorithm checks each element of a list in order, a process which takes linear time.

A problem is a general description of a task that may (or may not) be solved algorithmically.

An instance of a problem is one case of a problem, with specific inputs.

A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?").

An optimization problem is one with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?").

A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.

An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

Digital and analog are opposites. Digital means information that is represented as ones and zeros. Analog means information that is represented by signals that vary continuously (that is, including in-between values).