Basic Concepts in Computer Science

August 27, 2022

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

1. ASCII: 7-bit - 128 characters.
2. Extended ASCII: 8-bits - 256 characters.
3. 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.