3. The Fundamentals: Algorithms, the Integers and Matrices

3.1. Algorithms

Algorithm은 9세기 수학자 al-Khowarizmi에서 유래되었다.
al-Khowarizmi는 힌두 숫자, 현대 10진법의 기초를 다진 수학자이다.
Decimal notation을 Algorithm이라고 하였으나 현재에는 Solving problem의 Procedure로 사용한다.
즉, Algorithm은 계산을 수행하거나 문제를 해결하기 위한 정밀한 지침의 Finite set이다.

Computer language를 통해서 Algorithm을 설명 가능하나 해당 Language의 Instruction만 사용 가능하다.
대신에 Pseudocode를 통해 Algorithm을 설명한다면 Programming language와 Natural language로 설명하는 것의 중간 단계가 되어 유용하게 활용할 수 있다.

팁

Example of Pesudocode

Algorithm : Finding the Maximum Elemet in a Finite Sequence

procedure $max$($a_1,a_2,\cdots,a_n$: integers)
$max$ := $a_1$
for $i$ := 2 to $n$
if $max$ < $a_i$ then $max$ := $a_i$
($max$ is the largest element)

Algorithm은 여러 Property가 존재한다.

• Input: Algorithm은 특정 Set에서 Input value를 받는다.
• Output: 각 Input value set에서 지정된 Output value를 생성한다.
• Definiteness: Algorithm의 Step은 정확하게 정의되어야 한다.
• Correctness: Algorithm은 주어진 Set의 모든 Input에 대해 Finite step 후 원하는 Output을 생성해야 한다.
• Effectiveness: Algorithm의 각 Step을 정확히 수행 가능해야 하며 Finite time 내에 이루어져야 한다.
• Generality: Procedure는 특정 Input value set에 국한되지 않고 원하는 모든 form의 Problem에 적용 가능해야 한다.

Searching Algorithms

Ordered list에서 Element를 찾는 Problem을 Searching problem이라고 한다.
일반적으로 서로 다른 Element로 이루어진 List에서 Element $x$를 찾거나 List에 없음을 확인한다.
즉 Output은 List 내에 존재할 경우 Position value를, 그렇지 않다면 Minimum position value - 1을 반환한다.

Linear Search

Linear search(=Sequential search)의 경우 $x$와 각 List의 Element $a_i$를 비교한다.
$x=a_i$일 경우 Solution은 $i$, 그렇지 않을 경우 다음 Element를 반복하여 확인한다.
끝까지 $x$를 찾지 못했을 경우 Solution은 Minimum position이 이 환경에서 1로 정의되었기에 0이다.

정보

Pseudocode

Algorithm: The Linear Search Algorith

procedure $linear\ search$($x$: integer, $a_1,a_2,\cdots,a_n$: Distinct integers)
$i$ := 1
while($i\leq n$ and $x\not=a_i$)
$i$ := $i+1$
if $i\leq n$ then $location$ := $i$
else $location$ := 0
{$location$ is the subscript of the term that equals $x$, or is 0 if $x$ is not found}

Binary Search

Binary search의 경우 Ordered list에서 찾고자 하는 Element $x$를 List의 Middle term과 비교하여 같다면 $x$의 Position을, 그렇지 않다면 적절한 범위의 분리된 Sublist에서 해당 동작을 반복한다.

정보

Pseudocode

Algorithm: The Binary Search Algorithm

procedure $binary\ search$($x$: integer, $a_1,a_2,\cdots,a_n$: increasing integers)
$i$ := 1 {$i$ is left endpoint of search interval}
$j$ := $n$ {$j$ is right endpoint of search interval}
while $i$ < $j$
begin
$m$ := ($i+j$)/2
if $x>a_m$ then $i$ := $m+1$
else $j$ := $m$
end
if $x=a_i$ then $location$ := $i$
else $location$ := 0
{$location$ is the subscript of the term equal to x, or 0 if is not found}

Sorting Algorithms

어떤 Set의 Element list를 Sorting하는 것은 Element들을 오름차순으로 나열하는 것이다.

Bubble Sort

Bubble sort는 가장 간단하나 효율적이지 않은 Sortirng algorithm이다.
인접한 Element들을 차례로 비교해 조건에 맞게 교환하며 Sorting한다.

정보

Pseudocode

Algorithm: The Bubble Sort

procedure $bubble\ sort$($a_1,a_2,\cdots,a_n$: real numbers with $n\geq 2$)
for $i$ := 1 to $n-1$
for $j$ := 1 to $n-i$
if $a_j>a_{j+1}$ then interchange $a_j$ and $a_{j+1}$
{$a_1, \cdots, a_n$ is in increasing order}

Insertion Sort

Insertion sort는 간단한 Sorting algorithm이나 효율적이지 않다.
$n$개의 Element로 이루어진 List를 정렬하기 위해 Linear search를 반복한다.

정보

Pseudocode

Algorithm: The Insertion Sort

procedure $insertion\ sort$($a_1,\cdots,a_n$: real numbers with $n\geq 2$)
for $i$ := 2 to $n$
begin
$j$ := $i$
while $a_j>a_i$
$j$ := $j+1$
for $k$ := 0 to $j-i-1$
$a_{j-k}$ := $a_{j-k-1}$
$a_i$ := $m$
end
{$a_1,\cdots,a_n$ are sorted}

Greedy Algorithm

Greedy algorithm은 최적화하는 데 사용하여 각 Step의 최선의 선택을 수행한다.

정보

Pseudocode

Algorithm: Greedy Change-Making Algorithm

procedure $change$($c_1,\cdots,c_r$: values of denominations of coins, where $c_1>\cdots >c_r$; $n$, a positive integer)
for $i$ := 1 to $r$
while $n\geq c_i$
begin
add a coin with value $c_i$ to the change
$n$ := $n-c_i$
end

The Halting Problem

Computer program과 Program에 대한 Input을 받고 주어진 Input으로 실행할 때 Program이 멈출 지(Not infinite loop)에 대한 여부를 판별하는 것이 Halting problem이다.

Alan Turing이 위 Halting problem의 Procedure가 존재하지 않음을 증명하였다.
Program이 종료되지 않았을 때 이후 해결될 것인지, 결코 정지하지 않을 지 알 수 없다.
Procedure가 무엇인 지 명시적으로 정의하지 않았기 때문이다.

Procedure $H(P,I)$는 Program $P$가 $I$라는 Input을 받고 실행이 끝나면 True, 그렇지 않을 경우 False를 반환한다고 가정할 때 Subroutine $T$를 아래와 같이 가정한다.
function $T$($P$: Halting problem을 판단할 Code)
if $H(P,P)$ = false
return true
else
loop forever

위와 같이 가정하였을 때 $T(P)$가 True를 반환한다면 $H(P,P)$가 False이나 $T(P)$는 Infinite loop를, $T(P)$가 Infinite loop에 빠진다면 $H(P,P)$가 True를 반환하는 Contradiction 발생으로 Halting problem을 해결할 수 있는 Algorithm은 존재하지 않음을 증명할 수 있다.

3.2. The Growth of Functions

Big-O Notation

Function $f, g$에 대해 Integer나 Real number에서 Real number로 가는 Function일 때 $f(x)$가 $O(g(x))$라고 할 때 Constant $C, k$가 존재하여 $x>k$일 때 $|f(x)|\leq C|g(x)|$가 성립함을 의미한다.
위 Constant $C, k$를 Big-$O$ notation의 정의에서 $f(x)$가 $O(g(x))$의 Relationship의 Witness라고 불리며 $O(g(x))$임을 증명하기 위해 한 Pair의 Witnesses가 필요하다.

Witnesses pair를 찾기 위해 먼저 $x>k$일 때 $|f(x)|$의 크기를 쉽게 추정할 수 있는 $k$ 값을 선택한 후 $|f(x)|<C|g(x)|$를 성립하는 $C$ 값을 찾는다.
$f(x)$가 $O(g(x))$를 $f(x)=O(g(x))$로 표현하나 Equaility를 표현하는 뜻은 아니다.
명확하게 표현하기 위해 $f(x)\in O(g(x))$이며 $O(g(x))$는 여러 $O(g(x))$인 Function들의 Set이기 때문이다.

Big-$O$ notation은 Computer science에서 Algorithm 분석에 사용되며 Asymptotic notation(점근 표기법)의 하나로 Lamdau symbol이라고도 한다.

Function $f(x)$가 $O(g(x))$이고, $h(x)$가 충분히 큰 $x$ Value에 대해 $g(x)$보다 절대값이 더 큰 Function을 의미한다면 $f(x)$는 $O(h(x)), g(x)$는 절대값이 더 큰 Function으로 대체 가능하다.

$x>k$일 때 $|f(x)|\leq C|g(x)|$이고, 모든 $x>k$일 때 $|h(x)|>|g(x)|$라면, $x>k$일 때 $|f(x)|\leq C|h(x)|$, 즉, $f(x)\in O(h(x))$이다.

Some Important Big-O Results

Polynomial은 Function의 Growth estimate를 위해 사용할 수 있다.

정보

Theorem

Degree가 $n$ 이하인 Polynomial의 Dominate가 Growth의 지배적 Element이며 Degree가 $n$ 이하인 Polynomial은 $O(x^n)$이다.

• Proof
  $a_0,a_1,\cdots,a_{n-1},a_n$이 Real number일 때 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$이면 $f(x)$는 $O(x^n)$이다.
  만약 $x>1$인 경우 $|f(x)| = |a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0|\\ \leq |a_n|x^n+|a_{n-1}|x^{n-1}+\cdots+|a_1|x+|a_0|\\ =x^n(|a_n|+|a_{n-1}|/x+\cdots+|a_1|/x^{n-1}+|a_0|/x^n)\\ \leq x^n(|a_n|+|a_{n-1}|+\cdots+|a_1|+|a_0|)$
  따라서 $|f(x)|\leq Cx^n$이다.
  Witness $C=|a_n|+|a_{n-1}|+\cdots+|a_1|+|a_0|, k=1$이므로 $f(x)\in O(x^n)$이다.

The Growth of Combinations of Functions

Algorithm은 두 개 이상의 서로 다른 Subprocedure로 구성할 수 있다.
어떤 Algorithm에 대한 Big-O estimate를 구하기 위해 Subprocedure의 Big-O estimate를 찾아 결합할 수 있다.
Function의 Combination에 대한 Big-O estimate는 서로 다른 Big-O estimate를 Combine할 때 주로 두 Function의 Sum이나 Product를 Estimate하는 것이 필요하다.
$f_1(x)\in O(g_1(x)), f_2(x)\in O(g_2(x))$일 때 Big-O notation의 정의에 따라 Constant $C_1, C_2, k_1,k_2$가 아래의 식을 만족한다.
$x>k_1$일 때 $|f_1(x)|\leq C_1|g_1(x)|$, $x>k_2$일 때 $|f_2(x)|\leq C_2|g_2(x)|$라면 $k_1<x \land k_2<x$일 때 Sum은 $|(f_1+f_2)(x)|=|f_1(x)+f_2(x)|\leq |f_1(x)|+|f_2(x)|$이다.
$C=C_1+C_2$이고 $g(x)=\max(g_1(x),g_2(x))$일 때 $|f_1(x)|+|f_2(x)|\leq C_1|g_1(x)|+C_2|g_2(x)|\leq C_1|g(x)|+C_2|g(x)|=C|g(x)|$이다.
$x>k_1\land x>k_2$이고 $C=C_1C_2$일 때 Product는 $|(f_1f_2)(x)|=|f_1(x)||f_2(x)|\leq C_1|g_1(x)|C_2|g_2(x)|\leq C|(g_1g_2)(x)|$이다.

요약하여 $f_1(x)\in O(g_1(x)), f_2(x)\in O(g_2(x))$라면 $(f_1+f_2)(x)\in O(\max(|g_1(x)|,|g_2(x)|), (f_1f_2)(x)\in O(g_1(x)g_2(x))$이다.

Big-Omega and Big-Theta Notation

Big-O notation은 Function의 Growth를 설명하는 데 사용되나 상한선만을 제공한다는 한계가 존재한다.
Big-$\Omega$ notation은 Function $f(x)$의 점근적 하한선을 표현한다.
상한선과 하한선 모두 제공하기 위해 Reference function $g(x)$에 대해 Big-$\Theta$ notation을 사용한다.

Function $f, g$가 Integer set이나 Real number set에서 Real number set으로의 Function일 때 Positive constant $C, k$가 존재하여 $f(x)$가 $g(x)$의 $\Omega(g(x))$라고 할 때는 $x>k$일 때 $|f(x)|\geq C|g(x)|$를 의미한다.

Function $f, g$가 Integer set이나 Real number set에서 Real number set으로의 Function일 때 Positive constant $C,k$가 존재하여 $f(x)\in O(g(x)), f(x)\in \Theta(g(x))$일 때 $f(x)\in \Theta (g(x))$라고 하며 이 때 $f(x)$는 $g(x)$의 Degree이다.

3.3. Complexity of Algorithms

Time Complexity

Algorithm의 Time complexity는 Input 크기 대비 Algorithm의 사용 Operation 수로 표현한다.

Worst-case analysis는 Algorithm이 Solution을 보장하기 위해 필요한 최대 Operation 수를 기준으로 한다.

Average-case analysis는 Algorithm이 모든 Input에 대해 Solution을 보장하기 위한 평균 Operation 수를 기준으로 한다.

Understanding the Complexity of Algorithm

Complexity	Terminology
$\Theta(1)$	Constant complexity
$\Theta(\log n)$	Logarithmic complexity
$\Theta(n)$	Linear complexity
$\Theta(n \log n)$	$n\log n$ complexity
$\Theta(n^b)$	Polynomial complexity
$\Theta(b^n),\text{ where }b>1$	Exponential complexity
$\Theta(n!)$	Factorial complexity

많은 Tractable인 Problem들 중 Polynomial worst-case time 안에 검증할 수 있는 Algorithm을 Class P, 그렇지 않은 Problem들을 Class NP라고 한다.
NP-complete(NP-C, NPC) Problem들 중 하나라도 Polynomial worst-case time안에 검증 가능하다면 다른 모든 Problem들도 Class P가 된다.

Solution을 도출하는 데 Computer가 얼마나 걸리는 지 아는 것은 Problem Solving에 Computer time이나 돈을 투자하는 것이 가치있는 지 판단하는 근거가 된다.

추가적으로 Parallel processing을 통해 Operation들을 동시에 수행하여 Process time을 줄일 수 있다.

3.4. The Integers and Division

Division

Integer $a, b$에 대해 $a\not= 0$일 때 $b$가 $a$로 나누어 떨어지는 조건은 $b=ac$를 성립하는 Integer $c$가 존재하는 것이다.
$b$가 $a$로 나누어 떨어지면 $a$는 $b$의 Factor이고 $b$는 $a$의 Multiple이다.
Notation으로 $a\mid b$로 $b$가 $a$로 나누어 떨어짐을, $a\nmid b$를 통해 $b$가 $a$로 나누어 떨어지지 않음을 나타낸다.
Quantifier를 사용해 $a\mid b$를 표현할 때 $\forall_c(ac=b)$로 나타낼 수 있다.

정보

Theorem

Integer $a,b,c$에 대해

1. $\text{if }a\mid b \land a\mid c \text{ then } a\mid(b+c)$
2. $\text{if } a\mid b \text{ then } \forall_c(a\mid bc)$
3. $\text{if }a\mid b \land b\mid c \text{ then } a\mid c$

The Division Algorithm

실제 Algorithm은 아니나 전통적인 이름이 Division algorithm이다.

정보

Theorem

The Division Algorithm

Positive integer $a, d$에 대해 $0\leq r\leq d$일 때 $a=dq+r$을 만족하는 유일한 Integer가 존재한다.

이 때 $d$를 Divisor, $a$를 Dividend, $q$를 Quotient, $r$을 Remainder라고 부른다.

Quotient와 Remainder를 Notation으로 아래와 같이 표현한다.
$q=a\div d\\ r=a\mod d$

Modular Arithmetic

Integer $a, b$, Positive integer $m$에 대해 $a$는 $m$으로 $b$와 Equivalent라고 할 때 $m$이 $a-b$를 나눈다는 뜻이다.

$a$ is congruent to $b$ modulo $m$임을 나타내기 위해 $a\equiv b(\mod m)$라는 Notation을 사용하고 $a$와 $b$가 Equivalent가 아니라면 $a\not \equiv b(\mod m)$이라고 표기한다.

정보

Theorem

Integer $a, b$, Positive integer $m$에 대해 $a\equiv b(\mod m)$은 $a \mod m = b \mod m$이다.

정보

Theorem

Positive integer $m$이 Integer $a,b$가 $a$ is congruent to $b$ modulo $m$일 때 $a=b+km$을 만족하는 Integer $k$가 존재하는 경우에만 성립한다.

Modulo $m$에 대해 Integer $a$와 Equivalent인 모든 Integer set을 $a$ modulo $m$의 Congruence class라고 한다.

정보

Theorem

Positive integer $m$에 대해 $a\equiv b(\mod m) \land c\equiv d(\mod m)$일 때 $a+c\equiv b+d(\mod m)$이고 $ac\equiv bd(\mod m)$이다.

정보

Corollary

Positive integer $m$에 대해 Integer $a, b$가 존재할 때 $(a+b)\mod m=((a\mod m)+(b\mod m))\mod m$, 그리고 $ab\mod m=((a\mod m)(b\mod m))\mod m$이다.

Applications of Congruences

Hashing function은 One-to-one이 아니기에 하나의 Memory location에 여러 File이 할당될 수 있는데 이를 Collision occur이라고 표현한다.

체계적인 방법으로 생성된 숫자는 실제로 임의적이지 않기에 Random number라고 하지 않고 Pseudorandom number라고 한다.
Pseudorandom number를 생성하는 데 가장 일반적으로 사용되는 Procedure는 Linear comgruential method이다.
$2\leq a<m,0\leq c<m,0\leq c<m,0\leq x_0<m$일 때 총 네개의 Integer인 Modulus $m$, Multiplier $a$, Increment $c$, Seed $x_0$를 선택하여 $x_{n+1}=(ax_n+c)\mod n$의 Congruence를 통해 $0\leq x_n<m$인 Pseudorandom number의 Sequence $\{x_n\}$을 생성할 수 있다(즉 생성된 Random number는 $x_n/m$).

Cryptology

Congruences의 가장 중요한 응용 중 하나는 Cryptology이며 Cryptology의 기초는 Julius Caesar의 Caesar's cipher이다.

Caesar's cipher는 각 Alphabet에서 Position에 따라 0~25의 Integer로 변환하고 Cryptographic function $f(x)$의 Domain은 $\{0,1,\cdots,25\}$, $f(x)=(x+3)\mod 26$의 형식으로 Alphabet을 변환하는 것이다.

3.5. Primes and Greatest Common Divisors

Primes

1보다 큰 Positive integer는 최소 두 개의 Positive integer로 나누어 떨어진다(1, 자기 자신).
정확히 두 개의 Positive integer로만 나누어 떨어지는 Integer를 Prime이라고 한다.
Prime이 아닌 수를 Composite라고 한다.
즉 Composite $n$은 $1<a<n$이며 $a\mid n$인 $a$가 존재하여야 한다.

Prime은 무수히 많다.

정보

Theorem

Prime은 무한히 존재한다.

• Proof
  Proof by contradiction을 이용하여 $p_1,p_2,\cdots,p_n$만큼만 Prime이 존재한다고 가정했을 때 $Q=(p_1p_2\cdots p_n)+1$로 가정하여 $Q$가 Prime이 아니라면 두 개 이상의 Prime의 Product로 나타낼 수 있어야 하나 $p_1$부터 $p_n$ 사이의 모든 Prime의 Product로 나타낼 수 없기에 Contradiction이 발생한다.
  즉 $Q$ 자체가 Prime이거나 $Q$의 Prime factor일 수 있다.

발견된 가장 큰 Prime의 형태는 $p$가 Prime일 때 $2^{p}-1$의 형태이며 이를 Mersenne prime이라고 한다.
$2^p-1$가 Prime인 지 여부를 경정하는 Lucas-Lehmer test가 존재하여 빠르게 검증 가능하다.
현재 찾은 가장 큰 Mersenne prime은(2024년 10월에 찾은) 2^136279841-1이며 약 4102만 자릿수를 가진다.

정보

Theorem

$x$ 이하의 Prime의 수와 $x/ \ln x$의 비율은 $x$가 무한히 커짐에 따라 1에 가까워진다.

Conjectures and Open Problems About Primes

Number theory는 Conjecture를 쉽게 세울 수 있는 Subject이며 그 중 일부는 해결되지 않은 문제로 남아있다.

Goldbach는 모든 Odd integer $n$($n>5$)는 세 Prime의 Sum이라는 Conjecture를 제기하였는데 Euler는 이 Conjecture는 모든 Even integer $n$($n>2$)는 두 Prime의 Sum이라는 Conjecture와 동등하다고 답변하였다.
모든 Even integer $n$($n>2$)는 두 Prime의 Sum이라는 Conjecture를 Goldbach's conjecture라 한다.

Twin prime은 2 만큼 차이나는 Prime이다.
Twin prime conjecture는 Twin prime이 무한히 많다고 주장하는 것이다.

Greatest Common Divisors and Least Common Multiples

0이 아닌 Integer $a, b$에 대해 $a, b$를 동시에 나눌 수 있는 가장 큰 Integer를 Greatest common divisor라 하며 $\gcd(a,b)$로 표현한다.
Integer $a,b$에 대해 $\gcd(a,b)=1$일 경우 Relatively prime이라고 한다.

Positive integer $a,b$에 대해 $a,b$ 모두 나누어 떨어지는 가장 작은 Positive integer를 Least common multiple이라고 하며 $\operatorname{lcm}(a,b)$로 표현한다.

정보

Theorem

Positive integer $a,b$에 대해 $ab=\gcd(a,b)\operatorname{lcm}(a,b)$이다.

3.6. Integers and Algorithms

43