0 장 서론 0-1

용어  알고리즘 : 작업을 수행하는 방법을 정의하는 단 계들의 집합  프로그램 : 알고리즘의 한 표현  프로그래밍 : 프로그램을 개발하는 과정  소프트웨어 : 프로그램과 알고리즘  하드웨어 : 장비 0-2

컴퓨터의 발전 과정  고대의 초기 계산기 – 기원전 2600 년경  중국에서 물건을 사고팔거나 혹은 농사를 지으면서 계산이 필요할 경우 현재의 주판과 같은 기구를 만들어 사용 –17 세기  초기 계산기 형태 등장  스코틀랜드의 수학자인 존 네이피어 (John Napier) 에 의해 1617 년 네이피어의 계산봉 (Napier's Bones) 개발

그림 0.3 주판 0-4

5/ 25 컴퓨터의 발전 과정  컴퓨터의 태동 – 파스칼린 (pascalin)  계산기 형태를 갖춘 가장 최초의 계산기  파스칼 (Blaise Pascal, 1623~1662) 에 의해 개발  톱니바퀴를 이용  덧셈과 뺄셈 연산만 가능  파스칼린을 응용한 이후의 계산기에서 중요한 원칙 – 자리올림은 자동적으로 수행 가능 – 뺄셈은 다이얼을 역으로 회전시킴으로써 수행 가능 – 곱셈은 덧셈의 반복적인 수행으로 가능

컴퓨터의 발전 과정  컴퓨터의 태동 – 라이프니츠 계산기  1673 년 독일의 라이프니츠 (Gottfried Wilhelm Leibnitz, 1646~1716) 에 의해 개발  파스칼린과 같은 톱니바퀴 형태  이동식 부품을 더하고 옆에 톱니바퀴를 돌리는 손잡이를 추가 – 추가된 이동식 부품은 곱셈과 나눗셈을 반복 계산하는 시간을 줄여줌

컴퓨터의 발전 과정  컴퓨터의 태동 – 미분기 (Difference Engine)  1786 년 독일의 뮬러 (J. H. Muller, 1746~1830) 가 발명  뮬러 자신은 이 기계를 직접 제작하여 생산하지는 않았음 – 해석기관 (Analytical Engine)  미분기의 발명 이후 유사한 기계들이 30 년 동안에 걸쳐 찰스 배비지 (Charles Babbage, 1791~1871) 에 의해 설계  배비지는 숫자를 20 자리까지 정확하기 표현하과 인쇄된 결과를 만들 수 있 는 초대형 미분기를 개발하려고 시도  배비지가 죽은 이후 그의 아들인 헨리 배비지가 그의 아버지의 설계도에 의 한 해석기관을 제작 – 배비지의 아이디어  현대의 범용 디지털 컴퓨터를 구성하는 기본적 인 부분들, 즉 제어, 산술연 산, 기억장치, 입출력 장치 등을 포함

컴퓨터의 발전 과정  컴퓨터의 태동 –Tabulating Machine  미국의 홀러리스 (Herman Hollerith, 1860~1929) 에 의해 탄생  미국의 인구 조사를 위해 처음으로 사용  소규모의 저장소로 달러 계산서와 같은 크기의 구멍을 뚫은 표의 일 련번호를 사용  구멍 – 기계의 감지기에서 자동적으로 인식 – 각 구멍의 의미를 신속하게 파악

초창기 데이터 저장 방법  천공카드 – 직조 패턴 저장에 Jacquard Loom(1801) 이 사용한 것이 효시임 – 배비지의 해석엔진에서 프로그램 저장에 사용 –1970 년대 말까지 널리 사용  톱니바퀴 위치 0-9

초창기 컴퓨터  기계 릴레이 방식 –1940: 벨연구소에서 Stibitz 의 계산기 –1944: Mark I: 하버드에서 Howard Aiken 과 IBM  진공관 방식 – : 아이오아대에서 Atanasoff-Berry –1940 년대 : Colossus: 독일 암호 분석을 위한 영국 의 비밀 장비 –1940 년대 : ENIAC: 펜실베이니아대의 Mauchly 와 Eckert 0-10

그림 0.4 Mark I 컴퓨터 0-11

컴퓨터의 발전 과정  전자회로를 사용한 컴퓨터의 등장 – 에니악 (ENIAC, Electronic Numerical Integrator And Computer)  1943 년에서 1946 년에 걸쳐 펜실베이니아 대학의 모클리 (John William Mauchly, 1907~1980) 와 에커트 (John Preper Eckert Jr. 1919~1995) 가 제작한 세계 최초의 전자 컴퓨터

개인용 컴퓨터 - PC – 컴퓨터 취미생활자들이 먼저 사용 –IBM 이 1981 년 PC 를 소개  기업에서도 채택함  대부분의 데스크톱 컴퓨터를 위한 표준 하드웨어 설계로 정착됨  대부분의 PC 는 Microsoft 의 소프트웨어를 사용함 0-13

컴퓨터의 발전 과정  전자회로를 사용한 컴퓨터의 등장 – 제 1 세대 컴퓨터 (1951~1958) – 제 2 세대 컴퓨터 (1959~1964) 구분내용 주요 소자진공관 (tube) 연산 속도 ms(10 -3 sec) 사용 언어기계어, 어셈블리어 특징하드웨어 개발에 치중하였으며 주로 과학계산용으로 사용되었다. 부피와 전력 소모는 크지만 계산 능력 및 신뢰도는 떨어진다. 주로 통계용이나 미사일 탄도 계산에 사용되었다. 구분내용 주요 소자트랜지스터 (transistor) 연산 속도㎲ (10 -6 sec) 사용 언어 COBOL, FORTRAN, ALGOL 등 특징하드웨어 중심에서 소프트웨어 중심으로 전환되었으며 COBOL 과 같은 고 급언어가 개발 되었다. 운영체제가 등장하였고 멀티프로그래밍이 도입 되었다. 부피는 작아진 반면 신뢰도는 크게 향상되었으며 온라인 실시간 처리 시스 템 이 실용화 되었다.

컴퓨터의 발전 과정  전자회로를 사용한 컴퓨터의 등장 – 제 3 세대 컴퓨터 (1965~1974) – 제 4 세대 컴퓨터 (1974~1985) 구분내용 주요 소자집적회로 (IC) 연산 속도 ns(10 -9 sec) 사용 언어 BASIC, PASCAL, LISP, PL/1 등 특징시분할 처리 시스템 (Time Sharing System) 기법이 개발되었다. OMR, OCR, MICR 과 같은 입력 장치가 사용되었다. 경영 정보 시스템 (MIS) 이 도입되었다. 구분내용 주요 소자고밀도 집적회로 (LSI) 연산 속도 ps( sec) 사용 언어사용 언어 C, Ada 등 특징마이크로프로세서 (Micro Processor) 의 출현으로 컴퓨터의 소형화가 이 루어졌다. 최초의 개인용 컴퓨터와 슈퍼 컴퓨터가 등장하였다. 네트워크 (Network) 가 크게 발달되어 원격지의 자료도 공유가 가능해졌다. 공장자동화 (FA), 사무자동화 (OA) 등 각종 분야에 컴퓨터를 이용한 자동 화가 이루어졌다. 가상 기억 장치 기법 (Virtual Memory) 이 도입되었다.

컴퓨터의 발전 과정  전자회로를 사용한 컴퓨터의 등장 – 제 5 세대 컴퓨터 (1986~ 현재 ) 구분내용 주요 소자초고밀도 집적회로 (VLSI) 연산 속도 fs( sec) 사용 언어 Visual C, Visual Basic, Java, Delphi 등 특징인공 지능 (AI), 전문가 시스템 (Expert System), 패턴 인식 시스템, 의 사 결정 시스템 (DSS), 퍼지 이론 (Fussy Theory) 등 컴퓨터를 이용하여 보다 복잡한 계산을 수행하고 고도의 시스템 분야에 활용하고 있다.

컴퓨터 산업의 빠른 발전 v=mQmsLXyrAXw

알고리즘의 역사  알고리즘에 관한 연구는 수학의 한 분야로 시작 되었다.  알고리즘 예 : – 나눗셈법 – 유클리드의 호제법 알고리즘  Gödel 의 불완전성 정리 (Incompleteness Theorem): 알고리즘으로 해결할 수 없는 문 제들이 존재한다. 0-18

그림 0.2 유클리드의 호제법 알고리즘 0-19 설명 : 이 알고리즘은 두 개의 자연수가 입력되는 것을 가정하고 그 두 값의 최대공약수를 계산한다. 절차 : 단계 1. 두 입력 값 중 큰 값은 M, 작은 값은 N 에 지정한다. 단계 2. M 을 N 으로 나누고 그 나머지를 R 이라고 부른다. 단계 3. R 이 0 이 아닐 경우, N 이 가진 값을 M 에 지정하고 R 의 값은 N 에 지정한 다음 단계 2 로 돌아간다. R 이 0 일 경우, 현재 N 에 지정된 값이 최대공약수이다.

Hilbert’s 10 th Problem  임의의 주어진 디오판토스 방정식이 정수해를 갖는지를 판별하는 알고리즘을 제시하라. – 디오판토스 방정식의 예 –Matiyasevich’s Theorem  Every recursively enumerable set is Diophantine.  의미 : 찾을 수 없음. 또는 결정할 수 없음. – 괴델의 불완전성 원리  해답이 없으면서 동시에 그 방정식에 해답이 없다 는 것을 증명할 수 없는 디오판토스 방정식이 존재 한다.

컴퓨터 과학  알고리즘에 관한 학문  다른 분야의 학문적 성과들을 응용 – 수학 – 공학 – 심리학 – 경영학 – 언어학 0-21

컴퓨터과학의 핵심적 질문들  알고리즘적 처리과정에 의해 해결될 수 있는 것은 어떤 문제들인가 ?  어떻게 하면 알고리즘을 보다 쉽게 찾을 수 있을 것인가 ?  어떻게 알고리즘의 표현 및 전달 기법을 개선할 수 있을까 ?  알고리즘과 기술에 관한 지식을 보다 우수한 컴퓨 터를 만드는데 어떻게 적용할 것인가 ?  서로 다른 알고리즘들의 특성들을 어떻게 분석하 고 비교할 수 있을까 ? 0-22

그림 0.5 컴퓨터과학에서 알고리즘의 핵심적 역할 0-23

추상화 (abstraction)  추상화 : 개체의 외적 속성과 내적 구성의 세부사 항을 구별하는 것  추상적 도구 : 그 내적 구성을 모르고서도 사용할 수 있도록 만들어진 컴포넌트  추상화의 예 – 운영체제 – 프로그래밍 언어 –VMWARE 0-24

정보화 사회와 직업  직업 형태 변화 과정 – 일자리의 변화 – 정보화 시대의 직업을 바라보는 견해 ( 빌게이츠 ) 구분 18~19 세기 90 년대 이전 2000 년 이후 시대산업사회탈 산업사회정보화 사회 생산방식수공업적 주문생산대량생산다품종 유연생산 구분빌게이츠 - “ 새로운 노동 질서 ” 현상정보일꾼 역할 증대 새로운 비즈니스 기회 창출 전 산업으로의 비즈니스 확대 시각미래 사회에 대한 긍정적 시각을 가지고 있음 대안정보처리, 실시간 업무처리

정보화 사회와 직업  컴퓨터 기술의 발달로 인한 직업 형태의 변화 – 미래 근로공간  실제 공간과 가상공간이 융합되는 하이브리드 형태로 변화  미래의 근무 형태를 위하여 해결해야 할 과제 – 미래의 근무 환경을 위하여 사회 문화적인 환경 조성이 중요 – 미래의 근무 형태가 삶과 일 사이의 효율적인 조화라는 인식 강화 – 장애인, 노령자 등 거동이 불편한 계층을 대상으로 컴퓨터 기반 미래의 근무 환경을 최우선적으로 적용 – 일반적인 정보 취약지역을 우선적으로 적용 – 미래 근무 형태의 확산을 위해 기존 제도와 보안규칙의 재정비