[암호구현및실습] 01. Algorithm and Computation

1. Computational Problem(계산문제)

1) 컴퓨터를 사용해 해결할 수 있는 작업 또는 도전 과제. 이는 일련의 단계나 명령으로 나누어져 컴퓨터가 실행할 수 있도록 구성할 수 있는 것을 의미한다.

ex) 소인수분해문제 factorisation problems

Given a positive integer n, find a nontrivial prime facotr of n.

2) A computational problem consists of multiple cases (instances) with on one or more possible solutions

3) 해답이 존재하지 않는 계산 문제의 예로는 정지 문제(Halting Problem)이 있다.

4) 해당 과목의 목표는 계산 문제를 해결하는 방법을 배우고, 그 해결책이 정확하고 효율적임을 전달하는 것이다. 

-계산 문제 해결 

-정확성 증명

-효율성 논증

-의사소통

5) 계산 문제 정의: 계산 문제는 입력들의 집합(인스턴스들)과 각 입력에 대한 유효한 출력(해결책)의 집합으로 구성된다. 목표는 주어진 입력에 대해 올바른 출력을 결정하는 것이다.

6) 이항 관계(Binary Relations)와의 연결

계산 문제는 이항 관계 R ⊆X ×Y로 표현될 수 있다. 

여기서 X는 가능한 입력들의 집합, Y는 가능한 출력들의 집합

(x,y) ∈R는 y가 입력 x에 대한 유효한 해결책임을 의미한다.

7) 계산 문제의 예시

-Decision Problems: 주어진 입력 x에 대해 "Yes" 또는 "NO"를 반환, 이는 X에서 {0,1}로 가는 이항 관계로 볼 수 있음.

=>쉽다고도 어렵다고도 할 수 없는 문제

-Function Problems: 각 입력 x는 정확히 하나의 올바른 출력 y를 가진다. 이는 각 x가 유일한 y로 매핑되는 이항관계의 특수한 경우로 볼 수 있다.

-Search Problems: 하나의 입력 x가 여러 개의 유효한 출력들 y1, y2, ...를 가질 수 있다. 이는 하나의 x에 대해 여러 쌍 (x,y)가 존재할 수 있는 보다 일반적인 이항 관계에 해당한다. 

8) Not General(small input instance): In this room, is there a pair of students with same birthday?

General(arbitrarily large inputs): Given any set of n students, is there a pair of students with same birthday?

 

2. Algorithm

1) A fixed sized algorithm to solve a general problem (arbitrarily large input)

2) 각 입력을 하나의 출력으로 매핑하는 절차(deterministic)

3) 알고리즘은 모든 문제 입력에 대해 올바른 출력을 반환한다면, 그 문제를 해결한다고 말할 수 있다. 

4) Algorithm vs. Function

 알고리즘은 절차,

 Function은 코드 or instructions의 집합, program language와 dependency가 있다. 

 

📚 요약/정리

알고리즘이란? => 문제를 해결하기 위한 논리적 절차

 -문제를 해결하기 위한 단계별 절차 또는 규칙들의 집합

 -입력을 받아 원하는 출력을 생성함

 -프로그래밍 언어에 독립적인 개념적 저으이를 가짐

 -예시: 최대공약수(GCD)를 구하는 유클리드 알고리즘

함수란? =>알고리즘을 코드를 구현한 것

 -특정 작업을 수행하는 프로그래밍 언어 내 코드 블록

 -입력(매개변수)를 받아 출력(결과)를 반환함

 -Python, C, Java 등의 특정 언어로 구현되어야 함

 -예시: 유클리드 알고리즘을 구현한 함수

 

5) example: an algorithm to solve birthday matching

① Maintain a record of of names and birthdays (initially empty)

② Intervjiew each student in some order

③ If birthday exists in record, return found pair!

④ Else add name and birthdya to record

⑤ Return None if last student interviewed without success

 

3. Correctness

1) 입력이 작을 경우, 우리는 사례 분석을 사용할 수 있다. 

2) 입력이 임의로 클 경우, 알고리즘은 재귀 혹은 반복 구조를 가져야 한다.  =>수학적 귀납법 사용

3) 수학적 귀납법

 수학적 귀납법은 명제 P(n)이 모든 자연수 n에 대해 참임을 증명하는 방법. 즉, 무한히 많은 경우들 P(0), P(1), P(2), P(3),...이 모두 참이라는 것을 증명하는 방식

귀납법에 의한 증명은 Base case와 Induction step 두 단계로 이루어진다. 

4) 생일 일치 알고리즘의 정확성 증명

귀납 대상 k: 기록에 있는 학생 수를 기준으로 귀납을 진행

가정(귀납 가설): 처음 k명의 학생 중 생일이 같은 쌍이 있다면, 알고리즘은 학생 k+1을 인터뷰하기 전에 해당 쌍을 반환함.

기초 사례: k=0, 기록이 비어 있으므로 일치하는 쌍이 없음

귀납 단계: k=k'일 때 귀납 가설이 성립한다고 가정하고, k=k'+1인 경우를 생각함. 만약 처음 k'명의 학생 중에서 생일이 일치한다면 귀납 가설에 따라 이미 쌍이 반환됨. 

그렇지 않다면(처음 k'명은 모두 생일이 다름) 학생 k'+1이 생일이 겹치는 경우라면, 그 쌍은 k'+1을 포함함. 

알고리즘은 학생 k'+1의 생일이 처음 k'명 안에 존재하는지 직접 확인 따라서 일치하는 생일이 있다면 반드시 탐지됨.

 

4. Efficiency

1) 알고리즘이 정확한 출력을 얼마나 빠르게 생성하는가? 걸린 시간?

2) 💡 알고리즘이 정답을 반환하기까지 수행하는 고정 시간 연산의 수를 세어보자.

실행 시간은 입력 크기에 따라 달라질 것으로 예상됨-> 입력이 클수록 시간이 오래 걸릴 수 있음

입력 크기는 보통 n이라고 부르지만 항상 그런 것은 X

입력 크기에 대한 다항 시간 내에 결과를 반환하면 효율적이 알고리즘

하지만 어떤 문제는 효율적인 알고리즘이 존재하지 않기도 함.

3) Efficiency or Performance of Algorithm

실제 시간을 측정하지 않고, 대신 연산 횟수를 센다. 성능은 입력의 크기(보통 n)에 따라 달라진다.

4) 예시: 어떤 입력 크기 n에 대해, 한 알고리즘의 효율성은

점근 표기법(Asymptotic Notation)

상수 항이나 낮은 차수의 항은 무시한다. 

 

• Big-O (O): 상한 (최악의 경우 얼마나 오래 걸릴까?)
• Omega (Ω): 하한 (최소 얼마나 걸릴까?)
• Theta (Θ): 정확한 경계 (상하한 모두 해당될 때)

 

 

5. Asymptotic Notation (시험 빈출)

1) Big O

For a given complexity function f(n), O(f(n)) is the set of complextiy functions g(n) for which there exits some positive real constant c and some nonnegative integer N such that for all n ≥ N, 

If g(n) ∈O(f(n)), we say that g(n) is big O of f(n).

2) Omega Ω
• For a given complexity function 𝑓(𝑛),Ω(𝑓(𝑛)) is the set of complexity functions 𝑔(𝑛) for which there exists some positive real constant c and some nonnegative integer N such that, for all 𝑛 ≥ 𝑁 ,
𝑔 (𝑛) ≥ 𝑐 × 𝑓(𝑛)
• If 𝑔 (𝑛) ∈ Ω (𝑓 (𝑛)) , we say that 𝑔(𝑛) is omega of 𝑓(𝑛)

 

3) Theta Θ
• For a given complexity function 𝑓(𝑛),
Θ (𝑓(𝑛)) = 𝑂 (𝑓 (𝑛)) ⋂Ω(f(n))
This means that Θ (𝑓(𝑛)) is the set of complexity functions 𝑔(𝑛) for which there exists some positive real constants 𝑐 and d and some nonnegative integer 𝑁 such that, for all 
𝑛 ≥ 𝑁,
𝑐 × 𝑓 (𝑛 ) ≤ 𝑔 (𝑛) ≤ 𝑑 × 𝑓(𝑛)
• If 𝑔( 𝑛)∈ Θ (𝑓(𝑛)) , we say that 𝑔(𝑛) is order of 𝑓(𝑛).

 

📒Exercise

 

 

6. Model of Computation

 

• 계산 모델이란, 기계에서 어떤 연산을 수행할 수 있으며 그 연산이 O(1)시간에 수행된다고 가정하는 명세(specification)를 의미한다.
• 이 수업에서 사용하는 모델은 Word-RAM이다.
  • 이론 컴퓨터 과학에서, Word-RAM(word random-access machine)은 무작위 접근(random-access) 기계가 w 비트 길이의 워드(word)에 대해 산술 및 비트 연산을 수행하는 계산 모델이다.
  • 머신 워드 (Machine word): w 비트로 구성된 블록 (여기서 w는 Word-RAM의 워드 크기)
  • 메모리 (Memory): 머신 워드들의 주소 지정 가능한 시퀀스
  • 프로세서 (Processor)는 O(1)개의 워드(정수)에 대해 다음과 같은 상수 시간 연산들을 지원합니다:
    • 정수 산술 연산: +,−,∗,//,%
    • 논리 연산자: &&,∣∣,!,==,<,>,<=,>=
    • 비트 연산: &,∣,<<,>>,...
    • 주소 a가 주어지면, 주소 a에 있는 워드를 읽고 쓸 수 있다.

*Python은 더 복잡한 계산 모델이며, Word-RAM 위에 구현되어 있다.

 

7. Data Structure

1) A data strucure is a way to store non-constant data, that supports a set of operatons

2) 연산들의 모음은 interface라고 불린다. 

 -Sequence: 항목들에 외재적 순서가 있음(첫번쨰, 마지막, n번째)

 -Set: 항목들에 내재적 순서가 있음(항목 키를 기반으로 질의)

3) 자료구조는 같은 인터페이스를 구현할 수 있지만, 성능은 다를 수 있다. 

4) 예시: 정적 배열(Static Array)

• fixed width slots, fixed length, static sequence interface
• StaticArray(𝑛): allocate static array of size 𝑛 initialized to 0 in Θ(𝑛) time
• StaticArray.get at(𝑖): return word stored at array index 𝑖 in Θ(1) time
• StaticArray.set at(𝑖, 𝑥): write word 𝑥 to array index 𝑖 in Θ(1) time