화요일 12시 ~ 1:15
목요일 12시 ~ 1:15

교재: 알고리즘의 능력과 한계, 커뮤니케이션북스, 2020년 8월
순서대로는 하지 않는다

중간고사 48점 / 기말고사 50점
출석 2점 (블랙보드 기록 이용)

강의자료 - 수업 후 1주일 지나면 삭제
화(목)요일 수업은 다음주 월(수)요일 밤 12시 삭제

중간고사기간: 4/20 화 ~ 4/26 월
기말고사기간: 6/15 화 ~ 6/21 월
** 김영란법 ** 성적 변경, 시험방식 변경 등 x

What hypertext is, N.Wardrip-Fruin et al, Hypertext 2004, page 126

Optimal Demand-Oriented Topology for Hypertext Systems, S. Aaronson, SIGIR 1997

i.e.
1. 웹사이트의 시작점은 알고 있다
2.
이 때 이 웹사이트가 잘 구성되어있느냐 아님 뒤죽박죽돼있느냐 ⇒ 항해가능성

항해가능성은 오른쪽의 이고 무언가의 합임을 볼 수 있다.
그 근거는 왼쪽의 가정 세가지.

왼쪽 line 4
이런게 잘 반영된 사이트는 좋은 사이트다. (절대적 기준은 아님)
(1) user demand : 사용자 요구
(2) relevance : 얼마나 페이지 간 적절한 관련성이 있는가 - 연관된 정보가 유기적으로 연결되어 있는가
(3) 길을 잃지 않고 서핑할 확률

왼쪽 문단 2: 어떻게 측정할것인가?
가정 ①, ②
페이지 에서 까지 갈 때,
attention-span factor : 주의집중정도
real link : (아래에서 설명. virtual link, mandatory link도 나옴)

strength of a path : 경로의 강도

왼쪽 문단 3: Clearly ~
경로가 여러 가지 있으면, 가장 짧은 것을 가지고 생각한다.

왼쪽 아랫부분 가정 ③: (link의 타입을 고려한.)
경로가 있다고 해도, 사용자가 따라갈 확률이 다 같지는 않다.
(길이 있는 것과 지나는 것은 다른 문제다.)
에서 까지 길을 따라갈 개연성(likelihood)
길이 얼마나 popular한지에 따라, 그 길을 지날 확률이 정해진다.

하이퍼링크에는 세 가지 타입이 있다.

• 가상의 링크 (virtual link)
  
• 꼭 있어야 하는 링크 (mandatory link)
  
• 실제 만들어지는 링크 (real link)
  
  

가상의 링크: 있으면 좋겠을 링크. 모든 가능성?

(꼭 있어야 하는 링크들) ⊆ (실제 만들어지는 링크들) ⊆ (가상의 링크들)
(mandatory links) ⊆ (real links) ⊆ (virtual links)

이제 내용 관련성도 가중치로 넣자는 얘기.

i.e.
x는 시작과 끝이 관련이 있고
y는 시작과 끝이 관련이 없다.

c→d는 없다.
c→b→d로 가야 한다.
즉 d는 c에서 두 단계 떨어져 있다.

a→d는 연결, d→a는 비연결.
해석: d는 a로부터 1단계 연관성이 있고, a는 d로부터 연관성이 없다.
연관성은 방향성이 있다. (directed graph)

a→c의 경로는
a→b→c도 있고
a→e→c도 있다.

https://kucom.korea.ac.kr/em/6040440946727 - 언제지워질까?

화살표가 하이퍼링크 역할을 함.

Which Semantic Web?, C.C. Marshall, F.M. Shipman, Hypertext 2003, page 57

①
② 2003년에서 30년 전이라면 70년대. 그 때부터, 인공지능이 hot했던 시기가 있었다.
③

왼쪽 line 6: 하나의 거대한 DB는 없을까? Semantic web으로 이걸 가능하게 해보자.
왼쪽 중간: Semantic web의 언어는 RDF이다.

line 6
We raise the question of
다음과 같은 질문을 해보자
how we can make sense of the statement
어떻게 문장의 의미를 파악할지
that we have found an extremely complicated structure
그 구조가 복잡하다는 것을 어떻게 이해를 할 수 있느냐

This is typical of the kind of question investigated in mathematical logic.
이것이 수리논리학 분야에서 전형적인 질문이다.
The guiding result of mathematical logic is the Incompleteness Theorem of Godel,
(가이드할수 있을만큼 중요한) 결과가 뭐냐면, 괴델의 불완전성정리이다.
which says that the logical structure of number theory is so complicated that it cannot be effectively axiomatized in its entirety.
여기서 number theory는 '정수론' 보다는 '명제들의 집합'.
=> 원소: 양의 정수들의 집합에 대해, 덧셈과 곱셈을 이용해 표현할 수 있는 명제들

In other words, the theory is non-recursive, i.e. there is no Turing machine that could tell whether a sentence of number theory is true or not.
여기서 Turing machine은 '알고리즘'으로 생각하면 됨.
명제들이 참인지 거짓인지 ... 는 법이 없음

계산문제: 입력과 출력이 명시된 문제
ex. 최대공약수를 찾는 문제: 입력: 정수 a,b 출력: gcd(a,b)
인스턴스: 입력이 될 수 있는 것 하나하나가 다 인스턴스임.

프로그램과 알고리즘의 차이:
(비전공자 입장에선 구분하기 힘들 수 있다는 얘기. ex. 유전자와 유전체)
프로그램은 무한루프를 돌 수 있지만 알고리즘은 정의에 의해 끝나야 하는 것임.

(있어야 하는 데) 가정에서 빠져 있는 것: a≥b

비결정적 알고리즘을 일컬을 땐 '비결정적'이란 말을 꼭 쓴다.
결정적 알고리즘을 일컬을 땐 '결정적'이란 말을 생략하는 경우가 많다.

57m 결정적 알고리즘과 비결정적 알고리즘
"문맥에서 확실하지 않은 경우 '비결정적'이란 말을"

결정적 algorithm: 유한단계 작동 후 정지. deterministic
비결정적 algorithm: 추측단계와 검증단계로 나누어짐.

// 03주 1강 12m page3
램지_정리,Ramsey
와 이 2보다 큰 양의 정수일 때, 다음 특성을 만족하는 가장 작은 양의 정수 이 반드시 존재한다.
만일 노드을의 개수가 이고 서로 다른 모든 두 노드들이 간선으로 연결된 무향그래프 G의 모든 간선들, 즉 개의 간선들을 파란색과 빨간색 두 개로 칠한다면, 어떻게 색칠하든지 상관없이 다음 둘 중 하나의 특징을 가지는 무향그래프 H=(V',E') 가 반드시 존재한다.

(a)
(b)
(k=3, n=3, m=6)

a, b, c, d, e, f 여섯 명의 사람

(임의로 f를 뽑아서) f 기준 (나머지 사람들과)
당연히 이렇게 둘로 나뉜다.

f-a,f-b,f-c
f-a,f-b --------------------this page(4) - tbw
//p5
유향그래프,directed_graph
노드,node
간선,edge

//p6
해밀토니언 경로 문제 Hamiltonian Path Problem
입력: 유향그래프,directed_graph G=(V, E), a, b
출력: 만일 a에서 시작해서 G 안의 모든 노드,node들을 단 한번씩만 방문하여 b에 도달하는 것이 가능하면 yes, 그렇지 않으면 no

ex.

　　Ａ→Ｂ
　　│　　　↘
　　│　　　　Ｄ
　　↓　　　↙
　　Ｃ←Ｅ

입력이 이 그래프와 A, D로 주어지면 no
입력이 이 그래프와 A, C로 주어지면 yes

//p7
Hamiltonian (G, a, b) algorithm서술

KU박성빈 하텍03주2강 58m

//// 결정문제,decision_problem, P-NP_문제

P={x|x는 결정문제이고, x를 해결하는 효율적인 알고리즘 존재}
NP={x|x는 결정문제이고, x를 해결하는 효율적인 비결정적 알고리즘 존재}

결정문제 - 계산문제의 한 종류. 출력이 둘 중의 하나, 예를 들어 yes 또는 no, 1 또는 0 등인 것.

P는 NP의 부분집합 - 모든 결정적 알고리즘, 즉 일반적으로 우리가 알고리즘이라고 부르는 것들은 모두 비결정적알고리즘의 특별한 케이스로 볼 수 있으므로

그렇다면????

NP도 P의 부분집합?
P가 NP의 진부분집합?
...

클레이연구재단의 새천년 7문제 중 하나 - P와 NP가 같은가?

1h:02m
계산가능한 함수와 계산불가능한 함수 - 2장
함수는 둘로 나뉜다는 것.

정의역,domain과 공역,codomain이 각각 양의정수들의 집합인 함수 - 무한히 많이 존재함

가 계산가능하다는 것의 의미
그렇지 않은 함수가 있는가? Y E S
1950년대 수학자 Rado가 정의한 바쁜비버함수,busy_beaver_function가 대표적인 예 (curr 바쁜비버,busy_beaver)
참고로 Rado는 Turing_machine으로 증명했지만, 여기선 직관적인 방법으로 설명하겠음.

1:03:07

계산불가능한 함수인 의 정의

바쁜 비버 함수 BB(n)의 정의를 위해 "특별한 컴퓨터 프로그램들을 먼저 고려함".
우리는 다음 네 특징을 동시에 만족시키는 프로그램들에만 관심이 있음.

1. 입력 없이 작동하는 프로그램
2. 길이(size)가 최대 n을 넘지 않는 프로그램 (n은 양의 정수)
3. 무한루프를 돌지 않고 유한 단계 작동한 후 정지하는 프로그램
4. 정지하기 바로 전에 양의 정수 한 개를 출력하는 프로그램

위 네 특징을 동시에 만족하는 (컴퓨터) 프로그램들은 무한히 많이 존재함. 그러나! n값이 정해지면 (ex. n=10, n=15 등으로 정해지면) 위의 네 특징들을 "모두" 만족하는 프로그램의 수는 유한 개!

BB(n)은 n값이 1, 2, 3, … 등일 때
위의 네 가지 특징들을 동시에 만족하는 프로그램들의 출력값들 중 최대값

ex. BB(100)은 길이가 100을 넘지 않으며 위의 1, 3, 4 특징 모두 만족하는 유한 개의 프로그램들이 출력하는 값들 중 최대값

1:09:38
BB(n)이 계산 불가능하다는것의 증명

BB(n)이 계산 불가능하다는 것의 의미
즉 함수값들은 존재하지만, 그 값들을 모두 정확하게 계산하는 알고리즘이 존재하지 않는다.

우리는 "BB(n)이 계산 불가능하다"는 명제,proposition를 직접 증명하지 않고 아래 명제 p가 참인 것을 증명함 - 그러면 명제 q도 참이 되고 BB(n)은 계산 불가능하다는 것이 증명됨
(왜 이 방식으로 증명? - 상대적으로 덜 복잡하기 때문)

명제 p:
명제 q:
그런데, p가 참이면 "왜" q가 참인가? 즉 "p이면 q"가 참인가? Y E S :)

//p12

p가 참이면 q도 참이다.

이유: 대우명제 p → q ≡ ~q → ~p
BB(n)이 계산가능하면 그 값 자체가 역할을 할 수 있음.

증명: 모순법(귀류법,proof_by_contradiction)
즉, p가 참인 것을 증명하고 싶은데 p가 거짓이라면 모순이 발생한다는 것을 이용해서 p가 참인것을 보이는 방법.
p가 거짓이라는 말은 모든 양의 정수 n에 대해서 이면서 계산가능한 함수 이 존재한다는 말.

그런데 만일 p가 거짓이라면
① 정지하는 것이 확실하고
② 입력 없이 작동하는 프로그램 x
가 주어질 경우 최대 x의 수행단계가 몇 단계를 넘지 않는지 그 최대 단계를 계산할 수 있음. How?

//p13 - 이건 다음시간에.

//p4
프로그램 x와 x의 수행 단계를 출력하는 프로그램 y

두 프로그램 x, y가 있다. 주어진 것은 x이다. (x라는 컴퓨터 프로그램.)
x : 입력없이 작동하면서 정지하는(유한 단계 안에 끝나는) 프로그램. (이것들은 알려져 있다. 그 외는 알려져 있지 않다.)

그럼 x가 수행하는 단계의 최대값? 상한? upper_bound? (2021-07-07: 왼쪽에 쓴거 용어혼란임. 상한,supremum, 상계,upper_bound 임.)

y는 그걸 계산한다. 어떻게 계산하느냐?

프로그램 y를 만드는데 그 과정은,
(1) x를 복사
(2) 추가로 변수 count 이용 (변수 하나를 정의)
(3) x의 명령(instruction) 하나 수행할때마다 count 증가하도록 설정
(4) y 수행 마치기 바로 직전에 count 값 출력

(x의 size) = a < (y의 size) = b
y의 사이즈가 당연히 크다...?

y가 출력하는 값
BB(b)는,

//p5
일단 S는 입력 없이 작동한다는 것 외엔 아무것도 모르는 프로그램이다.

따라서 (= 이전 슬라이드(p4)에서 설명한 과정에 의하면) 입력 없이 작동하는 임의의 프로그램 S가 주어지면, S의 size는 쉽게 알 수 있는데, 그 size가 c라 한다면
(1) 만일 S가 유한단계 작동 후 정지하는 프로그램이면, 1번 결과를 이용해 최대 수행단계가 얼마인지 계산 가능. 그 값을 d라 한다.

2. (fact -> 다음 슬라이드) 입력 없이 작동하는 임의의 프로그램 S를 줄 때 S가 무한루프를 도는지 아니면 유한단계 작동하고 정지하는지 계산 불가능하다. 즉 알고리즘이 존재하지 않는다.
이건 다음 슬라이드에서 얘기할것이다.

1번 결과를 이용해 이 fact에 모순이 됨을 보임. How?

//p6
S를 수행시키고 d까지 끝나지 않으면 무한루프를 도는 프로그램.
즉, 무한루프 도는지 아닌지 판별가능!
-> fact에 모순. 모순,contradiction

d는
만일 S가 정지하는 프로그램이라면 "1번 결과"에 의해 계산이 가능
물론 S는 정지하지 않고 무한루프 도는 프로그램일 수도 있지만, "중요한 것"은 S가 "정지하는 프로그램"인 경우는 100% 계산 가능하다는 것

따라서 명제 p는 참이고 BB(n)은 계산 불가능하다

명제 p: 모든 양의 정수 n에 대해서 BB(n)≤f(n)이면서 계산 가능한 f(n)은 존재하지 않는다
명제 q: BB(n)은 계산 불가능하다

//p7

P와 NP가 다르다는 것의 의미 1

P와 NP 각각은 결정문제,decision_problem들의 집합이지만
P의 원소이기 위한 조건과 NP의 원소이기 위한 조건이 다름

.... Our daily experience is that it is harder to solve a problem than it is to check the correctness of a solution (e.g., think of either a puzzle or a homework assignment). Is this experience merely a coincidence or does it represent a fundamental fact of life (i.e., a property of the world)? Could you imagine a world in which solving any problem is not significantly harder than checking a solution to it? Would the term "solving a problem" not lose its meaning in such a hypothetical and impossible in our opinion) world? The denial of the plausibility of such a hypothetical world (in which "solving" is not harder than "checking") is what “P different from NP" actually means, where P represents tasks that are efficiently solvable and NP represents tasks for which solutions can be efficiently checked.

일상적 경험으론 (문제를 푸는 것 "solving")이 (정답인지 체크하는 것 "checking")보다 어렵다. 이게 단순히 우연의 일치(coincidence)인가, 세상의 특징인가? .... 혹시 그런 (푸는 것과 확인하는 것의 난이도의) 차이가 없는 세상을 상상할 수 있는가?

학교에선 d/l가능 외부에선 모르겠음
Invitation to complexity theory O. Goldrecich, XRDS Crossroads - The ACM Magazine for students March, 2012

//p8

P와 NP가 다르다는 것의 의미 2

문제 A
명제 x가 주어질 때
- 증명하는 것 (즉, x가 정리,theorem임을 보이는 것

문제 B
명제 x와 그 명제가 정리임을 보여주는 증명,proof y가 주어질 때
- y가 x의 타당한 증명이라는 것을 보이는 것

The mathematically (or theoretically) inclined reader may also consider the task of proving theorems versus the task of verifying the validity of proofs. Indeed, finding proofs is a special type of the aforementioned task of "solving a problem" (and verifying the validity of proofs is a corresponding case of checking correctness). Again, "P different from NP" means that there are theorems that are harder to prove than to be convinced of their correctness when presented with a proof. This means that the notion of a "proof" is meaningful; that is, proofs do help when seeking to be convinced of the correctness of assertions. Here NP represents sets of assertions that can be efficiently verified with the help of adequate proofs, and P represents sets of assertions that can be efficiently verified from scratch (i.e., without proofs).

문제 A와 문제 B의 난이도?

//p9

계산문제는 언제 어려워지는가? (4장)
어떤 조건(들)이 만족할 때? (cf. 시간 - 언제 시작하는가? 에서의 의미와 다름)

3CNF satisfiability problem

불리언변수: ....true/false, 1/0 값들

리터럴(literal): 다음 두가지 모두 리터럴.
예)
모든 리터럴은 불리언변수인가? 그렇지 않을 가능성이 있다. - 앞에 부정이 붙은 것이 있으므로
모든 불리언변수는 리터럴인가? 그럴 수 있다.

절(clause) : 한 개 이상의 리터럴들이 or로 연결된 것.
예)
논리식(formula) : 한 개 이상의 절들이 and로 연결된 것.
예)
리터럴,literal
절,clause
논리식,formula (아마 적형식,wff과 동일? chk)

//p10
3CNF formula: 절들 안에 정확히 세 개의 리터럴들이 있는 formula(논리식).
예) (x₁ or ~x₂ or x₃) and (x₁ or x₂ or x₃)

3CNF satisfiability problem (충족가능성문제)
입력: 3CNF formula f
출력: 만일 f 안에 있는 불리언변수들에
진리값(truth value)
예) f₁ = (x₁ or ~x₂ or x₃) and (x₁ or x₂ or ~x₃)

//p11

3CNF 충족가능성 문제의 구조 특성 1

3CNF 충족가능성문제는 NP의 원소 - 그 이유는? (검증이 효율적/쉽게 되기 때문 - 그런데 그 말이 무슨 의미인지 명확하게 설명하면 다음과 같음)

이 문제의 인스턴스들 중 답이 yes인 것 하나, 즉 "yes 인스턴스"와
답을 yes가 되게 하는 것 (certificate이라고 부름)을 주면,
정말 답이 yes라는 것의 "검증"이 다항식 단계 안에 가능함 - 즉 "효율적으로 검증이 됨"

예를 들어, f = (x₁ or x₂ or ~x₃) and (~x₁ or ~x₃ or x₄) and (x₂ or x₃ or ~x₃)와
이 3CNF 논리식이 "true"가 되게 만드는 각 변수들의 값, 즉 certificate으로
f 안에 있는 변수들에 certificate으로 주어진 값들 대입하여 정말 f가 true가 되는지 그래서 yes 인스턴스가 정말 맞는지 검증하는 것은 "쉽게" 가능함!

3CNF 충족가능성 문제가 P의 원소인가? "아직 모름!" 두 가지 가능성
이것들은 증명되어 있음.

cf. co-NP는 답이 no인 것에 초점을 맞춘다

//p12

//p2
계산문제는 언제 어려워지는가? (4장)
어떤 조건(들)이 만족할 때? (cf. 시간 - 언제 시작하는가? 에서의 의미와 다름)

절(clause) : 한 개 이상의 리터럴들이 or로 연결된 것.
예)
논리식(formula) : 한 개 이상의 절들이 and로 연결된 것.
예)

//p3
// 이건 위의 상변이현상 그림

ratio of clauses to variables : 절(clause)과 불리언변수(variables)의 개수의 비율 (절의 개수 ÷ 변수의 개수)

오른쪽 그림: y축은 얼마나 계산에 시간이 많이 걸리는가.

//p4

order parameter?
order는 질서.

order parameter 값 = (절들의 수) / (변수들의 수)
이 값이 상대적으로 크다/작다에 따라
① satisfiable한 것이 대부분에서 값이 변화함에 따라
② 해결하는데 걸리는 시간 (=난이도 라고 보면)

//p5

(정량적인)분석의 예

분석
예) f₁ = ( ) and ( ) and ( ) … and ( )
반면, f₂ = ( ) and ( ) and … and ( )
(1)과 (2)를 비교하면 "상대적으로" (1)에서는 f₁을 satisfiable하도록 하기가 (2)에 f₂를 satisfiable하도록 하는 것에 비해서 어려움.

//p6

마찬가지로, (절들 수) / (변수들 수) 값이 상대적으로 아주 작거나 아주 크거나 하면, "쉽게" satisfiable, unsatisfiable 판별 가능.
그런데 이 값이 어떤 특정값(critical value)일 때 갑자기 어려워짐.

//p7

P대 NP문제 - 비유 (공통점들은?)

• 수학자 - 명제가 있으면 증명
  
• 과학자 - data를 일관되게 설명할 수 있는 이론을 찾는(만드는)
  
• 공학자 - 여러 가지 constraint를 주고서 그걸 만족시키는 설계를 찾는(설계하는)
  
  

검색(search) vs 검증("yes instance" 주면 정말 답이 yes라는 검증 쉽게 됨)

//p8

오러클 알고리즘 (1장)

오러클(oracle) - 계산문제가 주어지면 그 계산문제의 "정답"을 "단번에" 알려주는 것
(어떻게 정답을 아는지 알려져 있지 않고, 마치 블랙박스처럼 정답을 알려주는 것)
oracle algorithm - 작동하는 과정에서 oracle의 도움을 받아 작동하는 algorithm

//p9

//p10

//p11