정보과학의 이해: Data Structure, Algorithm

김 태영

한국교원대 컴퓨터교육과

• 정보산업 = H/W + S/W (+ Service)

- 전자공학(electronic engineering, EE): H/W

- 정보과학(computer science, CS)    : S/W

정보의 표현/저장: Data Structure, Database, Graphics, Multi-Media

정보의 처리(계산): Algorithm, AI

정보의 전달: Computer Networks, Data Communication

S/W 시스템: Language, Compiler, Authoring Tools, S/W Engineering

H/W 기기: Computer Architecture, OS, Distributed System

- Application S/Ws: 전자상거래(e-business), CRM, CAD/CAM, MIS, RFID/Sensor network, etc...

• 정보과학자(computer scientist)들은 무엇에 관심이 있는가?

1. 정보를 어떻게 표현할 것인가?: Data Structure

2. 정보를 어떻게 처리(계산)할 것인가?: Algorithm

3. 정보를 어떻게 전달할 것인가?: Protocol

⇒ 정보과학을 이해하는 3개의 키워드(keyword)들

Ⅱ. 정보의 표현: Data Structure

• 정보란?

"한 가족이 있다. 아버지는 adam이고, 어머니는 dotty이다. 자녀의 이름은 각각 edward와 fran이다.

옆집에는 betty가 사는데 자녀는 david이다.“

- 지식(knowledge)/정보(information) - invisible

⇒ 유기체/조직체가 환경에 적응하여 살아 남아 번영하기 위한 필수조건

ex)	곤충/인간 등: 감각기관, 뇌, 유전자(DNA)

기업/국가 등: 정보수집 및 저장, 전산조직

- data/media: 인간이 ‘정보’를 표현/전달하기 위한 수단 - visible

⇒ 음성, 그림, 문자, 숫자, 영상 등

• 정보의 표현(저장)

- 정보는 사람의 뇌에 어떤 구조로 저장되는가? We don't know yet... Why?

- 정보를 어떻게 컴퓨터에 표현할 것인가? data structure

• 정보의 처리(계산)

- 아래의 물음에 어떻게 답할 것인가? algorithm

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward 가족은 몇 명인가?

Q3: edward의 형제의 이름은?

- data structure와 algorithm은 밀접한 관련이 있다.

• History

- 9세기 전반 알콰리즈미(Alkhwarizmi;780-850, 아라비아)의 대수학저서 "al-gebr w'almuqubala"에 일차, 이차방정식의 풀이법이 나타나 있다. 여기서는 오늘날의 '이항'을 al-gebr, '동류항을 정리한다'를 almuqubala라고 불렀다.

- 그래서 대수학을 뜻하는 algebra는 al-gebr에서 유래하고, 계산법을 뜻하는 algorithm은 Alkhwarizmi에서 유래되었다고 보고 있다. <www.naver.com>

- "The Art of Computer Programming" by Donald Knuth

우리가 하고자 하는 작업(human)

컴퓨터가 할 수 있는 작업 (machine instructions)

Algorithm - 변환(transformation) 절차

(1973):	vol. 1. fundamental algorithms

vol. 2. seminumerical algorithms

vol. 3. sorting and searching

- discrete/finite algorithms

⇔ continuous/infinite mathematics

• Method #1

- one-dimensional (linear) 구조 - array, linked list, queue(FCFS), stack(LCFS)

- multi-dimensional 구조 - matrix

ex) programming languages: Fortran (John Backus at IBM, 1957),

C (Dennis Ritchie and Brian Kernighan at Bell Labs, 1972) etc.

family[0]: [0,0][adam] [0,1][dotty] [0,2][edward] [0,3][fran]

family[1]: [1,0][betty] [1,1][david] [1,2]   -      [1,3]  -

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward 가족은 몇 명인가?

Q3: edward의 형제의 이름은?

- 자료구조마다 표현의 한계(expresiveness)가 있다.

⇔ 사람의 언어(language)는?

• Method #2

- table 구조: 열(column)에 이름(의미)을 부여

⇒ ‘relation’

family

father	mother	child1	child2
adam -	dotty betty	edward david	fran -

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward 가족은 몇 명인가? betty 가족은 몇 명인가?

Q3: edward의 형제의 이름은?

- 같은 자료구조라도 여러가지 다른 표현방법이 있다.

parents

father	mother	child
adam adam -	dotty dotty betty	edward fran david

sibling

child1	child2
edward	fran

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward 가족은 몇 명인가?

Q3: edward의 형제의 이름은?

- table 형태의 자료 처리 algorithm: relational algebra

Edgar F. Codd, "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM, 1970. (IBM Rearch Lab., San Jose, Califonia)

- 기본 operation들.

1) 두 table의 union (R∪S) : R과 S에 있는 모든 tuple들의 집합이 생성.

2) 두 table의 difference (R-S) : R에는 있으나 S에는 없는 tuple들의 집합이 생성.

3) 두 table의 cartesian Product (R×S) : R과 S로부터 모든 가능한 두 쌍의 tuple들의 조합이 생성.

4) 한 table의 projection (πA R) : 특정 attribute값들이 추출. (이 경우 A)

5) 한 table의 selection (σA=‘a’ R) : 어떤 특정한 조건을 만족시키는  record들이 추출. (이 경우 A=’a')

Table R	A	B
	a b c	x y z

Table S	C	D
	a b	z y

- 다섯 가지 기본 operation들: (a)R∪S (b)R-S (c)R×S (d)πA R (e)σA=‘a’ R

						A	B	C	D		A		A	B
a	x		a	x		a	x	a	z		a		a	x
b	y		c	z		a	x	b	y		b
c	z					b	y	a	z		c
a	z					b	y	b	y
						c	z	a	z
						c	z	b	y
(a)			(b)			(c)					(d)		(e)

- RDBMS/SQL demo by using the Oracle server

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward의 형제의 이름은?

Q3: edward 가족은 몇 명인가?

Q4: dotty의 자식들은?

• Method #3

- tree 구조: node와 link를 사용, no cycles, root/leaves

⇒ ‘hierarchy’

- 가계도(family tree)

adam

dotty

edward

fran

parentOf

father

parentOf

family

mother

ex) 조직도, 지식체계(contents) etc.

- 표현: XML - nested form

<?xml version="1.0"?>

<families>

<family>

<father>

<name>	adam	</name>

<parentOf> edward	</parentOf>

<parentOf> fran	</parentOf>

</father>

<mother>	dotty	</mother>

</family>

<family>

<mother>

<name>	betty	</name>

<parentOf> david	</parentOf>

</mother>

</family>

</families>

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward의 형제의 이름은?

Q3: edward 가족은 몇 명인가?

Q4: dotty의 자식들은?

- 처리 algorithm: tree traversal - depth-first/breadth-first search

- Java: procedure-oriented vs. object-oriented (Alan C. Kay at Xerox PARC, 1972)

- DOM Demo

• Method #4

- graph 구조: node와 link를 사용, cycle을 허용,

⇒ 'network'

- 가계도(family network)

adam

dotty

edward

fran

parentOf

father

parentOf

siblingOf

spouseOf

family

mother

ex) The Web/the Semantic Web

Part Ⅱ: 정보의 처리(계산): Algorithm

• 대표적인 Algorithm들

- graph algorithms by Robert. E. Tarjan, Edsger W. Dijkstra 등

⇒ shortest-path, minimum spanning tree, bipartite graph, planar graph, etc...

- string match algorithms: Donald E. Knuth

• Techniques

- 순차(sequential)

- 순환(recursion): ex) the Tower of Hanoi(하노이의 탑)

- divide-and-conquer

- Turing machine: algorithm 수행 기계 by Alan Turing

- NP-completeness: Stephen Cook, Leonid Levin

- A. I.: heuristics, expert system, John McCarthy

- distributed algorithms: Leslie Lamport

- parallel algorithms

- genetic algorithms

Part Ⅳ: 한계에 관해

• 처리(계산)하기 어려운 문제들이 존재하는가? Complexity theory - NP-completeness

NP is the class of decision problems for which there is a polynomial-bounded nondeterministic algorithm. <S. Baase, Computer Algorithms, 1988>

⇒ The term "NP" refers to a class of problems which could be solved by a ‘nondeterministic’ computer(Turing machine) in an amount of time which varies as some polynomial in the size of the input (hence NP, for Nondeterministic Polynomial time).

⇒ deterministic polynomial time algorithm의 해를 가짐을 증명하지 못한 문제들.

P⊂NP, but P=NP?

⇒ 아마도 지수함수 시간(exponential time)을 요구하는 문제들.

⇒ 정보과학(algorithm)의 한계

⇒ heuristic 사용, sub-optimal solution

- Bin packing problem

Suppose we have an unlimited number of bins each of capacity 1, and n objects with sizes s1, …, sn, where 0 < si ≤1.

Optimization: Determine the smallest number of bins into which the objects can be packed.

⇔ Decision: Given, in addition the inputs described, an integer k, do the objects fit in k bins?

ex) n=8 objects: S={ 0.8, 0.5, 0.4, 0.4, 0.3, 0.2, 0.2, 0.2 }

- 과학에서 한계가 존재하는가?

“과학에서는 증명해줄 사실적인 증거(evidence)가 반드시 필요합니다. 그리고 그에 따른 정연한 논리가 필요합니다. 막연한 추측이 아닙니다.“ <사이언스타임즈, 2006>

- 하이젠베르크의 불확정성의 원리 (uncertainty principle)

고전역학에 의하면 전자의 위치와 운동량은 전자가 어떤 상태에 있든지 항상 동시 측정이 가능하다고 생각했다. 그 물리량의 측정값이 불확정하다는 것은 측정기술이 불충분하기 때문인 것으로 여겼다. 그러나 불확정성의 원리는 소립자 세계의 어떤 입자의 위치를 정확히 측정하면 운동량의 측정값에, 운동량을 정확히 측정하면 위치의 측정값에 불확정성이 생긴다는 것이다.  이 원리는 좀 더 풀어 나가면 거의 모든 측정치에 해당이 된다.  즉 한 측정치를 아주 정확하게 측정하면 할수록 다른 어떤 측정치의 측정값이 아주 불안해진다는 것이다.

예를 들어서 소립자세계에 어떤 입자가 있고, 이 입자는 어떤 일정한 운동량을 가지고 움직이고 있다고 하자.  만약 실험 등을 통해 이 입자가 A라는 지점에 아주 완벽하게 도달하는 것을 측정했다면, 그 A라는 지점에서 그 입자가 가진 운동량은 전혀 측정할 수 없게 된다는 것이다.  하지만 그 입자가 어느 때 B라는 운동량을 가졌다는 것을 정확하게 측정하게 되면, 대신 그 입자가 어디에 있는지는 전혀 알 수 없다라는 것이 된다. 따라서 양자역학의 입장에서는 입자의 위치 x와 운동량 p는 동시에 확정된 값을 가질 수 없고, 쌍방의 불확정성(오차) Δx와 Δp가 ΔxΔp≥h/2π(h는 플랑크상수)에 의해 서로 제약되어, 입자의 위치를 정하려고 하면 운동량이 확정되지 않고, 운동량을 정확히 측정하려 하면 위치가 불확정해진다. 즉, 둘 중 어느 하나라도 0, 즉 완벽한 측정이라면 다른 측정치의 오차는 h/2π를 0으로 나눈, 즉 무한대가 되게 된다. 그러므로 그 다른 측정치는 전혀 알 수 없다라는 결론이 나오게 된다.

불확정성의 원리는 여러 모로 이해하기 힘든 면이 많다.  이 중 가장 큰 문제는 바로 이 원리가 소립자세계 단위에서 일어나는 현상을 논하는 것이며, 또한, 이 현상은 인간의 능력한계로 인해 일어나는 것이 아니라 자연적 법칙중 하나라는 것이 다시 사람들의 머리를 아프게 한다. 결국, 인간이 얼마나 발전하든 자연에는 결코 알 수 없는 한계가 있다는 것을 절실히 깨닫게 하는 원리라 하겠다. <www.naver.com>

그 밖에도 우리가 사물을 관찰하는 것의 제한은 필자의 생각이 미치지 못하는 많은 영역이 있을 것이다. 그러한 인간이 관찰한 것을 바탕으로 우리는 이 세계를 이해하고 판단하고 있다. 그렇기 때문에 우리가 보는 세상이 우리에게 보이는 것뿐이라고 하는 것은 지나친 편견이 아닐 수 없다. (권재술, “우리가 보는 세상은 진실한가”, 2000, 교육과학사, p.286)

- 괴델의 불완전성정리 (Gödel's incompleteness theorem)

1931년 괴델이 발표한 논리학에 관한 정리. "자연수론을 포함하는 무모순인 모든 공리계 A에 대하여, A에는 결정 불가능한 명제들이 존재한다. 즉, A 안에는 G 또는 ~G를 A 안에서 증명할 수 없는 명제 G가 존재한다"는 괴델의 불완전성 정리는 참인 명제라고 꼭 증명이 가능한 것은 아니다라는 것이다.

이 정리가 발표되기 이전까지는 B. 러셀과 A.N. 화이트헤드를 포함한 대부분의 논리학자들은 주어진 수학적 명제의 참과 거짓을 판별할 수 있는 절대적인 지침이 있다고 믿었다. 즉, 참인 모든 명제는 증명이 가능하다고 생각하였다. 그러나 괴델은 참이지만 증명이 불가능한 식을 제시하여 그렇지 않음을 보였다. 이 정리는 튜링 기계(Turing machine)와 처치 설정(Church thesis), 괴델의 무모순성(consistency) 정리와 밀접한 관계가 있다. <www.naver.com>

- Alan Turing의 'halting problem' <http://en.wikipedia.org/wiki/Halting_Problem>

⇒ 'undecidable' problem

In computability theory the halting problem is a decision problem which can be informally stated as follows:

Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.

Alan Turing proved in 1936 that a ‘general’ algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines.

⇒ 거짓말장이의 paradox, '나는 거짓말쟁이이다‘

⇒ true→false, false→true

- 과학적 지식의 한계

과학적 법칙이나 이론은 자연에 존재하는 것이 아니라 자연 현상을 설명하기 위해서 인간이 고안해낸 불완전한 아이디어일 뿐이다. 일반적으로 알고 있는 것과 같이 지동설은 옳고 천동설은 틀린 것이 아니다. 지동설이 자연현상을 설명하는데 천동설보다 유용할 뿐이다. 따라서 자연과학은 진리를 찾는 것이 아니라 자연을 좀 더 잘 설명하는 방법을 찾는 것이다. (권재술, “우리가 보는 세상은 진실한가”, 2000, 교육과학사, p.268-269)

과학은 '사람에 의해서 만들어진 것'입니다. 이와 같은 사실을 사람들이 다시 한 번 새겨본다면 때때로 한탄하고 있는 정신과학-예술 분야와 기술-자연과학 분야라는 두 문화 사이에 가로놓여 있는 단절을 메울 수 있지 않을까 하고 생각해 봅니다. ...중략...

토론과 대화에서 원자물리학이 항상 주역을 연출한 것이 아닙니다. 오히려 인간적이고 철학적이며 정치적인 문제들이 빈번하게 등장하는데, 이는 자연과학이 이와 같은 일반적인 문제들과 분리되어서는 성립되기가 매우 어렵다는 사실을 분명히 밝히는데 큰 도움이 되리라고 생각하기 때문입니다. <하이젠베르크, “부분과 전체” 서문에서>

• 생명(life)의 자료구조

- Bioinformatics: DNA 정보체계 연구

- Where ‘programs and data’ for life come from? ex) 진화론

⇔ Where computer programs come from?	ex) CD-ROM

• 우리는 한계를 극복할 수 있는가?

• Socrates and Sophist

“그 당시 일부 아테네 사람들에게 소크라테스는 소피스트처럼 보이기도 했지만, 소크라테스는 모든 점에서 소피스트와 달랐다. 소피스트들은 그리스 전역을 돌아다니면서 연설했지만, 소크라테스는 아테네에 머물면서 아테네 사람들과 이야기를 하였다.

소피스트들은 수차례에 걸쳐 연속되는 설문을 철저하게 준비했지만, 소크라테스는 단지 질문을 했을 뿐이다. 소피스트들은 가르치는 값으로 많은 돈을 요구했지만, 소크라테스는 정기적인 급료를 거절하고 가난하게 살다가 가난하게 죽었다. 소피스트들은 영화배우들처럼 우아한 옷을 입고 요란하게 광고를 하였지만, 소크라테스는 노동자처럼 옷을 입고 맨발로 다녔다. 사실상, 소크라테스는 직업이 석공이었고 노동계층 출신이었다.

소피스트들은 특별하게 준비된 강당에서 강의를 하였지만, 소크라테스는 길옆이나 운동장 어디든지 사람들이 모여 있는 곳에서 이야기를 하였다. 마지막으로 소피스트들은 모든 것에 대해서 알고 있고 누구든지 배우겠다는 사람에게 그것을 설명해 주겠다고 말했지만, 소크라테스는 아는 것이 아무것도 없고 오직 찾아내고자 노력할 뿐이라고 말했다.” <김성권, 현대 수업 이론, 형설출판사, 1997>

현대의 과학자들도 자신이 정말로 솔직하다면 모든 사건의 궁극적인 원인을 알지 못한다는 것을 시인하지 않을 수 없다. 과학의 첨단에 있는 사람은 아마도 그렇지 않은 사람보다 더 자연의 신비함에 감탄을 할 것이다. 신을 먼 곳으로 쫓아버린 것이 인간의 지식 때문이 아니고 오히려 인간의 무지 때문이었다는 생각이 든다. 지금까지의 과학이 신을 인간으로부터 쫓아내는 역할을 했다면 앞으로의 과학은 잃어버린 신을 다시 찾는 역할을 하게 되지 않을까? (권재술, “우리가 보는 세상은 진실한가”, 2000, 교육과학사, p.262)

저자에 따르면 우주론의 수수께끼 중의 하나는 우주가 무척 친생명적이라는 것이다. 태초의 빅뱅 후 1초가 지났을 때 우주의 팽창속도가 실제보다 1/1010만큼만 더 빠르거나 느렸다면 생명탄생은 없었다. 몇 백만 년 내에 우주는 수축하거나 텅 비었을 것이기 때문이다. 생명이 출현할 수 있는 환경이 되도록 우주의 기본상수들은 적절한 값을 취하고 있다. 우연히 그렇게 될 통계적 확률은 1/10220이다. <제임스 가드너, 생명우주, 까치>