Basic Concepts in Computer Science

A short introduction to some basic concepts in computer science.

Boolean Logic and Logic Gates

Representing transistors of two states - the binary representation \(\Rightarrow\) true/false & \(0/1\) - representing raw electrical signals.

In terms of mathematics - the field of Boolean Algebra (named after George Boole). Fundamental operators in Boolean Algebra: and, or, not \(\to\) the values are only true/false.

Transistor may be thought of as an electrically controlled switch.

NOT operator Gate (\(\neg\))

              / --- 1st electrode
--- control_wire 
              \ --- 2nd electrode

In order to reach an output from a transistor, there needs to be some input. A NOT indicates the negation.

AND operator Gate (\(\land\))

We assume that the transistor only yields true, such that both of the inputs are true.

--- control_wire --- o --- o ---- output
                     |     | 
                     A     B

OR operator Gate (\(\lor\))

We assume that the transistor yields true \(\iff\) either of inputs is true or both are true.

                / --- A --- \
--- control_wire              --- output
                \ --- B --- /

Exclusive OR (`XOR`) operator Gate (\(\oplus\))

We assume that the transistor yields true \(\iff\) either of inputs is true only. A XOR Gate is created from a combination of other gate operators.

Representing Numbers and Letters with Binary

In a binary representation, we rely on the 2 possible digits: \([0, 1]\), i.e. a base-two notation.

Expressed mathematically (conversion bin -> dec):

\[(A)_{2} = (B)_{10} \equiv \sum_{i = 0}^{n = \bar{A}} A_{i}^{n - i}\]

where \(\bar{A}\) denotes the number of digits of \(A\), and \(A_{i}\) is the \(i\)-th digit of \(A\).

Conversion dec -> bin:

We rely on the modulo (\(\%\)) operator. Example given (no. 47):

remainder	mod (\(n \% 2\))
47	-
23	1
11	1
5	1
2	1
1	0
0	1

We then concatenate the digits to a binary notation from bottom to the top \(\Rightarrow (47)_{10} = (101111)_2\).

Each 0,1 represents a single bit (b), hence a number made from \(n\) bits belongs to the interval from \(0\) to \((2^{n} - 1) \subset \mathbb{N}\), making \(2^{n}\) total possible numbers.

*First bit - sign of the number; positive - 0, negative - 1.

8 bits (b) = 1 Byte (B)

Floating point numbers (float): sign + exponent + significant.

Representing textual data

ASCII: 7-bit - 128 characters.
Extended ASCII: 8-bits - 256 characters.
Unicode: single universal encoding scheme - 16-bits.

Compilers and Interpreters

TL;DR

Interpreter: direct translation, one-by-one, to execute each line from instructions (much slower process; each translation is processed manually).
Compiler: all instructions processed at once; there’s no space to fix a problem on the go, though performs much faster.