This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
fuss:computer_science [2019/03/08 23:56] – created office | fuss:computer_science [2024/09/19 08:07] (current) – [The Empty String, List, Queue, Etc...] office | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== | + | ====== |
+ | |||
+ | Von-Neumann debiasing can be used to remove entropy bias from a sequence of random or pseudo-random binary digits using a simple algorithm. | ||
+ | |||
+ | Given the set of binary digits: | ||
+ | |||
+ | \begin{eqnarray*} | ||
+ | B &=& \{ k | k \in \{ 0, 1 \} \} \\ | ||
+ | \end{eqnarray*} | ||
+ | |||
+ | and $S$ a sequence of arbitrary binary digits: | ||
+ | |||
+ | \begin{eqnarray*} | ||
+ | S &=& {\huge\bullet_{i=1}^{n}} k_{i},k_{i} \in B,n \ge 2 | ||
+ | \end{eqnarray*} | ||
+ | |||
+ | Let $r_{i}$ be a debiased random binary number such that: | ||
+ | \begin{equation} | ||
+ | r_{i} = | ||
+ | \begin{cases} | ||
+ | 0 & k_{i-1} = 0,k_{i} = 1 \\ | ||
+ | 1 & k_{i-1} = 1,k_{i} = 0 | ||
+ | \end{cases} | ||
+ | \end{equation} | ||
+ | |||
+ | The following table shows the possible outcomes for the random binary digit $r_{i}$: | ||
+ | ^ $k_{i-1}$ ^ $k_{i}$ ^ $r_{i}$ ^ | ||
+ | | 0 | 0 | discard | | ||
+ | | 0 | 1 | 0 | | ||
+ | | 1 | 0 | 1 | | ||
+ | | 1 | 1 | discard | | ||
+ | |||
+ | ====== Exercises ====== | ||
+ | |||
+ | You can find [[/ | ||
+ | |||
+ | ====== Definition of a Line of Text ====== | ||
+ | |||
+ | A line of text [[https:// | ||
+ | <WRAP info> | ||
+ | 3.206 Line | ||
+ | A sequence of zero or more non-< | ||
+ | </ | ||
+ | |||
+ | Regular Expression: | ||
+ | < | ||
+ | / | ||
+ | </ | ||
+ | where the following regular expression engine modifiers have to be set: | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Due to the definition many programs and environments (for example, [[/ | ||
+ | |||
+ | ====== The Empty String, List, Queue, Etc... ====== | ||
+ | |||
+ | One confusing concept to non-computer science majors is the concept behind the expression "the empty string", | ||
+ | |||
+ | All variables are considered from a memory model perspective containers and that types are qualifiers for those containers. In that sense, "the empty O" where " | ||
+ | |||
+ | The following definitions can then be constructed: | ||
+ | * an empty string is a string container that contains zero characters and is referred to by a given variable | ||
+ | * on a technical layer zero characters could be represented by a single end-of-string character '' | ||
+ | * an empty list is a list container that contains zero element | ||
+ | * on a technical layer, usually a list contains a counter of its internal size (ie: for linked lists), which in the case that the list is empty, should be zero | ||
+ | * bear in mind that if lists are to be considered sets, then a set $l$ such that $l = \varnothing$ is still a valid set containing nothing | ||
+ | |||
+ | Object-oriented programming makes theoretical computer science more perceivable at the level of code, where objects are synonymous with types, such that a " | ||
- | {{indexmenu> |
For the contact, copyright, license, warranty and privacy terms for the usage of this website please see the contact, license, privacy, copyright.