PowerPoint 프레젠테이션

Transcription

1 강의소개 1. 교재 C로쓴자료구조론, Horowitz, Sahi, Aderso-Freed 보조 : itroductio to algorithms, corme 외 3명, MIT press 2. 강의자료 E 강의실게시판 3. 교수컴퓨터공학부지상문연구실 : 8관 606호전화 : smchiks@ks.ac.kr 4. 성적퀴즈 20%, 중간 40%, 기말 40%

2 시스템생명주기 (1) 요구사항 (requiremets) 프로젝트들의목적을정의한명세 (specificatio) 들의집합 입력과출력정보의기술 (2) 분석 (aalysis) 문제들을실제다룰수있을정도의작은단위들로나눔 상향식 (bottom-up) / 하향식 (top-dow) (3) 설계 (desig) 자료객체들과수행될연산들의관점 - 추상자료형 (abstract data type) - 알고리즘의명세와설계기법고려

3 시스템생명주기 (4) 정제와코딩 (refiemet & codig) 자료객체에대한표현선택수행될연산에대한알고리즘작성 (5) 검증 (Verificatio) 정확성증명 (correctess proofs) - 수학적기법들을사용하여프로그램의정확성증명테스트 (testig) : 테스트데이타와수행가능한코드 - 프로그램의정확한수행검증 - 프로그램의성능검사오류 (error) 제거 - 독립적단위테스트 - 통합테스트

4 1.2 알고리즘명세 알고리즘 (Algorithm) 특정한일을수행하기위한명령어의유한집합다음조건 (criteria) 만족하여야함 ⅰ. 입력 : 외부에서제공되는데이터가 0개이상 ⅱ. 출력 : 적어도한가지의결과 ⅲ. 명확성 (defiiteess) : 모호하지않은명확한명령 ⅳ. 유한성 (fiiteess) : 한정된수의단계뒤에는종료 ⅴ. 유효성 (effectiveess) : 기본적, 실행가능명령 iodef - 프로그램은유한성을만족하지않아도됨 - 알고리즘을자연어로기술할경우에는명확성에유의

5 예제 1.1 >= 1 개의서로다른정수정렬프로그램 알고리즘이아닌예 : " 정렬되지않은정수들중에서가장작은값을찾아서정렬된리스트다음자리에놓는다 알고리즘기술을위한첫번째예 : 정수들이배열 (array), list 에저장 : i 번째정수는 list[i] 에저장 for (i = 0; i < ; i++) { list[i] 에서부터 list[-1] 까지의정수값을검사한결과 list[mi] 이가장작은정수값이라하자 ; list[i] 와 list[mi] 을서로교환 ; 최소정수를찾는작업 1 최소정수가 list[i] 라가정 2 list[i] 와 list[i+1] ~ list[-1] 비교 - 더작은정수를만나면새로운최소정수로선택최소정수값을 list[i] 값과교환하는작업

6 최소정수값을 list[i] 값과교환하는작업 함수사용 : swap(&a, &b) //a, b 는정수형변수 void swap(it *x, it *y) /* 매개변수 x, y 는정수형을갖는포인터변수이다 */ { it temp = *x; /* temp 변수를 it 로선언하고 x 가가리키는주소의내용을지정한다 */ *x = *y; /* y 가가리키는주소의내용을 x 가가리키는주소에저장한다 */ *y = temp; /* temp 의내용을 y 가가리키는주소에저장한다 */ 매크로정의 #defie SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

7 프로그램 1.3 선택정렬 #iclude <stdio.h> #iclude <math.h> #defie MAX_SIZE 101 #defie SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) void sort(it [ ], it); /* selectio sort */ void mai(void) { it i, ; it list[max_size]; pritf("eter the umber of umbers to geerate: "); scaf("%d", &); if (<1 >MAX_SIZE) { fpritf(stderr, "Improper value of "); exit(1); for (i=0; i<; i++) { /* radomly geerate umbers*/ list[i] = rad() % 1000; pritf(%d ", list[i]);

8 sort(list, ); pritf("sorted array:"); for (i=0; i<; i++) { /* prit out sorted umbers */ pritf("%d ", list[i]); pritf(""); void sort(it list[], it ) { it i, j, mi, temp; for (i=0; i<-1; i++) { mi = i; for ( j=i+1; j<; j++) if (list[ j]<list[mi]) mi = j; SWAP(list[i], list[mi], temp);

9 정확성증명 정리 1.1 증명 함수 SORT(list, ) 는 >= 1 개의정수를정확하게정렬한다. 그결과는 list[0],..., list[-1] 로되고여기서 list[0] <= list[1] <=... <= list[-1] 이다. i=q 에대해, 외부 for 문이완료되면 list[q] <= list[r], q < r < 이다. 다음반복에서는 i>q 이고 list[0] 에서 list[q] 까지는변하지않는다. 따라서 for 문을마지막으로수행하면 ( 즉, i=-2), list[0] <= list[1] <=... <= list[-1] 가된다.

10 예제 [ 이진탐색 ] : 정수 searchum 이배열 list 에있는지검사 list[0] <= list[1] <=... <= list[-1] 로이미정렬된상태임 있다면 list[i] = searchum 인인덱스 i 를반환 없다면 -1 반환 기본아이디어초기값 : left = 0, right = -1 list 의중간위치 : middle = (left + right) / 2 list[middle] 과 searchum 을비교한후 1) searchum < list[middle] : list[0] <= searchum <= list[ middle - 1] right = middle-1 2) searchum = list[middle] : middle 을반환 3) searchum > list[middle] : list[middle+1] <= searchum <= list[-1] left = middle+1

11 탐색전략기술 while (there are more itegers to check) { middle = (left + right) / 2; if (searchum < list[middle]) right = middle - 1; else if (searchum == list[middle]) retur middle; else left = middle + 1; 비교연산 : 함수, 매크로 #defie COMPARE(x,y) ((x) < (y))? -1 : ((x) == (y))? 0 : 1)

12 프로그램 1.6 순서리스트탐색 it bisearch(it list[], it searchum, it left, it right) { it middle; while (left<=right) { middle = (left + right)/2; switch (COMPARE(list[middle], searchum)) { case -1: left = middle + 1; break; case 0: retur middle; case 1: right = middle - 1; retur -1;

13 순환알고리즘수행이완료되기전에자기자신을다시호출 - 직접순환 : direct recursio - 간접순환 : idirect recursio factorial, 거듭제곱, 이항계수 이후의장에서필요 : 리스트, 트리등 1 1 1, )!!(! * 1 * 1) ( *! m m m m m m

14 Factorial 계산 반복 (iterative) 계산 it fac_iter (it ) { it fact=1, k ; for (k=; k>0; --k) fact *= k ; retur fact ; 순환 (recursive) 계산 it fac_rec (it ) { if ( <= 1) retur 1 ; // 순환을멈추는부분 else retur * fac_rec (-1);// 작은부분으로분할

15 거듭제곱계산 반복 (iterative) 계산 double pow_iter (double x, it ) { double pow = 1; for (it k=0; k<; ++k) pow *= x ; retur pow ; 순환 (recursive) 계산 : 이경우는더빠름 double pow_rec (double x, it ) { if ( == 0) retur 1 ; // 순환을멈추는부분 else if (%2==0) { // 짝수 retur pow_rec(x*x, /2) ; else { // 홀수 retur x*pow_rec(x*x, (-1)/2) ;

16 예제 [ 이진탐색에대한순환구현 ] it bisearch(it list[], it searchum, it left, it right) { /* search list[0] <= list[1] <=... <= list[-1] for searchum*/ it middle; if (left <= right) { // 순환호출이종결될수있도록경계조건설정 middle = (left + right) / 2; switch (COMPARE(list[middle], searchum)) { case -1: retur bisearch(list, searchum, middle+1, right); case 0: retur middle; case 1: retur bisearch(list, searchum, left, middle-1); retur -1;

17 예제 [ 순열 ] : >= 1 개의원소를가진집합에서모든가능한순열을출력하는함수 - a, b, c : (a,b,c),(a,c,b),(b,a,c), (b,c,a),(c,a,b),(c,b,a) - 원소 :! 개의상이한순열 - a, b, c, d 1) a로시작하는 b, c, d의모든순열 2) b로시작하는 a, c, d의모든순열 3) c로시작하는 a, b, d의모든순열 4) d로시작하는 a, b, c의모든순열 초기함수호출 : perm(list, 0, -1);

18 void perm(char *list, it i, it ) /* geerate all the permutatios of list[i] to list[]*/ { it j, temp; if (i == ) { // 경계조건 for (j = 0; j <= ; j++) pritf("%c", list[j]); pritf(" "); else { /* list[i] to list[] has more tha oe permutatio, geerate these recursively */ for ( j = i; j <= ; j++) { SWAP(list[i], list[j], temp); perm(list, i+1, ); SWAP(list[i], list[j], temp);

19 하노이탑 (P15 연습문제 11) #iclude <stdio.h> void haoi (it, char from, char tmp, char to) { if (==1) { pritf ("disc 1 from %c to %c\", from, to) ; else { haoi (-1, from, to, tmp) ; pritf ("disc %d from %c to %c\",, from, to) ; haoi (-1, tmp, from, to) ; // tower A, B, C ad discs from A to C it mai () { haoi (64, 'A', 'B', 'C') ;

20 하노이탑실행결과 1. haoi (1, 'A', 'B', 'C') ; disc 1 from A to C 2. haoi (2, 'A', 'B', 'C') ; disc 1 from A to B disc 2 from A to C disc 1 from B to C 3. haoi (3, 'A', 'B', 'C') ; disc 1 from A to C disc 2 from A to B disc 1 from C to B disc 3 from A to C disc 1 from B to A disc 2 from B to C disc 1 from A to C 4. haoi (4, 'A', 'B', 'C') ; disc 1 from A to B disc 2 from A to C disc 1 from B to C disc 3 from A to B disc 1 from C to A disc 2 from C to B disc 1 from A to B disc 4 from A to C disc 1 from B to C disc 2 from B to A disc 1 from C to A disc 3 from B to C disc 1 from A to B disc 2 from A to C disc 1 from B to C

21 1. 3 데이타추상화 C 언어의기본데이타타입 : char, it, float, double - 키워드 short, log, usiged 에의해변경 자료의그룹화 : 배열 (array), 구조체 (structure) - it list[5] : 정수형배열, - 구조체 struct studet { char last_ame; it studet_id; char grade; 포인터데이타타입 : 정수형, 실수형, 문자형, float 형포인터 it i, *pi; 만들어진새로운데이타타입 : 사용자정의데이타타입

22 정의 : 데이타타입 (data type) 은객체 (object) 와그객체위에작동하는연산 (operatio) 들의집합 데이터타입 it 의예 객체 : 0, +1, -1, +2, -2,..., INT_MAX, INT_MIN 연산 : +, -, *, /, %, 테스트연산자, 치환문... atoi 와같은전위 (prefix) 연산자, + 와같은중위 (ifix) 연산자 이름, 매개변수, 결과가명세되어야함 데이터타입의객체표현 char 형 : 1 바이트비트열 it 형 : 2 또는 4바이트 구체적인내용을사용자가모르도록하는것이좋은방법객체구현내용에대한사용자프로그램의독립성

23 정의 : 추상자료형 (ADT : abstract data type) 객체의명세와그연산의명세가그객체의표현과연산의구현으로부터분리된자료형 연산의구현이나객체의표현에독립적으로객체의필수요소들을이해 명세와구현을명시적으로구분 Ada - package, C++ - Class ADT 연산의명세 - 함수이름, 매개변수형, 결과형, 함수가수행하는기능에대한기술 - 내부적표현이나구현에대한자세한설명은필요없음 ADT가구현에독립 ADT 의정의가완전히설명되어지면, 그후구현과표현방법에대해논의

24 예 [ 추상자료형 Natural_Number] Structure Natural_Number 객체 (objects): 0 에서시작해서컴퓨터상의최대정수값 (INT_MAX) 까지 순서화된정수의부분범위이다. 함수 (fuctios): for all x, y Nat_Number, TRUE, FALSE Boolea에대 해, 여기서 +, -, <, 그리고 == 는일반적인정수연산자이다. Nat_No Zero() ::= 0 Boolea Is_Zero(x) ::= if (x) the FALSE else retur TRUE Nat_No Add(x, y) ::= if ((x+y)<=int_max) retur x+y else retur INT_MAX Boolea Equal(x,y) ::= if (x==y) retur TRUE else retur FALSE Nat_No Successor (x) ::= if (x==int_max) retur x else retur x+1 Nat_No Subtract(x,y) ::= if (x<y) retur 0 else retur x-y ed Natural_Number

25 성능분석및측정 1.4장성능분석 (performace aalysis) 시간과공간의추산, 복잡도이론 (complexity theory) a priori estimates 1.5장성능측정 (performace measuremet) 컴퓨터의존적실행시간 a posteriori testig 성능분석의두개의복잡도정의 공간복잡도 (space complexity) : 프로그램을실행시켜완료하는데필요한공간의양 시간복잡도 (time complexity) : 프로그램을실행시켜완료하는데필요한컴퓨터시간의양

26 공간복잡도 프로그램에필요한공간 1) 고정공간요구 c : 프로그램입출력의횟수나크기와관계없는공간요구, 명령어공간, 단순변수, 고정크기의구조체변수, 상수 2) 가변공간요구 Sp(I) : 특정인스턴스 I 에의존하는크기를가진가변공간, 스택공간예 ) 입력이 개의요소를갖는배열이라면 은인스턴스특성, 이유일한인스턴스특성이면 Sp(I) 표현을위해 Sp() 사용 총공간요구량 : S(P) = c + Sp(I) 예제 : 고정공간요구만을가지는함수이므로 Sabc(I) = 0 float abc(float a, float b, float c) { retur a+b+b*c + (a+b-c) / (a+b) ;

27 예제 1.7 : 가변공간요구, 배열 ( 크기 ) - 함수에대한배열의전달방식 - Pascal : 값호출 (call by value).ssum(i)=ssum()= : 배열전체가임시기억장소에복사 - C : 배열의첫번째요소의주소전달. Ssum() = 0 float sum(float list[], it ) { float tempsum = 0; it i; for (i = 0; i < ; i++) tempsum += list[i]; retur tempsum; // 프로그램 1.10

28 예제 1.8 rsum : 컴파일러가매개변수, 지역변수, 매순환호출시에복귀주소를저장 float rsum(float list[], it ) { if () retur rsum(list, -1) + list[-1]; retur 0; // 프로그램 1.11 하나의순환호출을위해요구되는공간 (80386 예 ) 두개의매개변수, 복귀주소를위한바이트수 = = 6 배열이 = MAX_SIZE 만큼의기억장소를가진다면, 가변공간은 Srsum(MAX_SIZE) = 6 * MAX_SIZE 으로순환함수는반복함수보다훨씬큰오버헤드를가짐

29 1.4.2 시간복잡도 프로그램 P 에의해소요되는시간 : T(P) 컴파일시간 + T_P ( 실행시간 ) T_P()=Ca ADD() + Cs SUB() + Cl LDA()+ Cst STA() Ca, Cs, Cl, Cst : 각연산을수행하기위해필요한상수시간 ADD, SUB, LDA, STA() : 특성 에대한연산실행횟수 실제컴퓨터의존적인실행시간을구할때는시스템클럭을이용한성능측정이용

30 프로그램단계 (program step) 컴퓨터에독립적인견적은연산의횟수를계산 정의 : 프로그램단계 (program step) 실행시간이인스턴스특성에상관없이구문적으로또는의미적으로독립성을갖는프로그램의단위 1 step 예 a = 2 a = 2*b+3*c/d-e+f/g/a/b/c 한단계실행에필요한시간이인스턴스특성에독립적이어야함. 프로그램단계의계산방법 1 전역변수 cout 의사용

31 예제 [ 수치값리스트의합산을위한반복호출 ] float sum(float list[], it ) { float tempsum = 0; cout++; /* 배정문을위한선언 */ it i; for (i = 0; i < ; i++) { cout++; /* for 루프를위한연산 */ tempsum += list[i]; cout++; /* 배정문을위한연산 */ cout++; /* for 문의마지막실행 */ cout++; /* 반환을위한문장 */ retur tempsum; // float sum(float list[], it ) /* 단순화된프로그램 */ { float tempsum = 0; it i; for (i = 0; i < ; i++) cout += 2; cout += 3; retur 0; 프로그램단계수 steps

32 예제 [ 수치값리스트의합산을위한순환호출 ] float rsum(float list[], it ) { cout++; /* if 문을위한문장 */ if () { cout++; /* 반환과 rsum 의호출을위한문장 */ retur rsum(list, -1) + list[-1]; cout++; retur list[0]; = 0 -> 2 (if, 마지막 retur) > 0 -> 2 (if, 처음 retur) : 회호출 steps (iterative) > (recursive) Titerative > Trecursive?? 단계수가많지만, 각단계가실행에걸리는시간은순환적인것이더느리다.

33 단계의계산 ( 방법 2) 테이블방식 (tabular method) : 단계수테이블 1 문장에대한단계수 : steps/executio, s/e 2 문장이수행되는횟수 : 빈도수 (frequecy) - 비실행문장의빈도수 = 0 3 총단계수 = 빈도수 x s/e [ 수치값리스트의합산을위한반복호출 ] s/e 빈도수총단계수 float sum(float list[], it ) { float tempsum = 0; it i; for (i = 0; i < ; i++) tempsum += list[i]; 1 retur tempsum; 합계 2+3

34 예제 [ 수치값리스트의합산을위한순환호출 ] s/e 빈도수총단계수 float rsum(float list[], it ) { if () retur rsum(list, -1) + list[-1]; 1 retur list[0]; 합계 2+2 프로그램 1.6 의함수 bisearch 를고려 순서화된리스트를탐색, 매개변수는원소수 탄색시간은 searchum 의위치에따라다르다. 단계수를유일하게결정하지않고, 최상, 최악, 평균을정의한다. 최상단계수 : 주어진매개변수에대해실행될수있는단계수가최소 최악단계수 : 주어진매개변수에대해실행될수있는단계수가최대 평균단계수 : 주어진매개변수를갖는인스턴스에대해실행되는평균단계수

35 1.4.3 점근표기법 단계수 (step cout) 두프로그램의시간복잡도비교에사용 인스턴스의특성에따른실행시간의증가예측에사용 그러나, 한 step 이정확한실행시간을가지지않으므로두프로그램을비교하려는목적에는유용하지않다. x=y, x=y+z+(x/y)+(x*y*z-x/z) 를한단계로계산 step cout 대신에점근적복잡도를주로사용 대략적인단계수를의미 , 등을대략 의복잡도로표현 1000 과 ^2 + 2 을비교하면 <= 998 에서는 1000 이크지만더큰 에대해서는 ^2 + 2 이더크다. 의복잡도보다는 ^2 의복잡도가 이커짐에따라복잡도증가

36 점근표기법 Big "oh" : (f of 은 big-oh of g of ) f() = O(g()) iff positive costats c ad 0 s.t. f() cg() for all, 0 ex : =O() for all 2 즉, c=4, 0 =2, g()= 의경우이다.

37 예제 , , , = Ο() = Ο() 5, 10^ ^2 4, 6*2^ + ^2 7*2^ 2, ^ = Ο() 10^ = Ο(^2) 6*2^ + ^2 = Ο(2^) = Ο(^2) 2, 10^ ^4 10^ = Ο(^4) 0 인모든 과임의의상수 c 에대해 <= c 가 false 인경우가존재하면 3+2 Ο(1) 10^ Ο()

38 order of magitude ( 오름차순 ) O(1) : 상수 (costat) O(log ) : logarithmic O() : 선형 (liear) O(log ) :log liear O( 2 ) : 평방형 (quadratic) O( 3 ) : 입방형 (cubic) O(2 ) : 지수형 (expoetial) O(!) : factorial f() = Ο(g()) 0 인모든 에대해 g() 값은 f() 의상한값 g() 은조건을만족하는가장작은함수여야함

39 Therem 1.2: f() 은지수가제일큰 Proof: 주의 라고는않함 마찬가지로라고는않함 중가장차수가낮은것을사용 0 1 ) ( a a a f m m ) ( m O m i i m m i m i i m m i i i a a a f ) ( ) ( O ) ( 3 O ) ( O )) ( ( g O

40 정의 [Omega] [f() = Ω(g()) ( 하한값 ) f() = Ω(g()) iff c,_0 > 0 존재, s.t f() >= cg() 모든, >= 0 예제 1, = Ω() 1, = Ω() 1, = Ω() 1, 10^ ^2 100^ = Ω(^2) 1, 6*2 + ^2 2^ 6*2^ + ^2 = Ω(2^) g() : f() 의하한값 ( 가능한큰함수 )

41 정의 [Theta] [f() = Θ(g()) f() = Θ(g()) iff C1, C2, 0 > 0 존재, s.t C1g() f() C2g(), 모든, >= 0 예제 2, 3 <= <= = Θ() - c1 = 3, c2 = 4, 0 = = Θ() 10^ = Θ(^2) 6*2^ + ^2 = Θ(2^) 10*log + 4 = Θ(log ) g() 이 f() 에대해상한값과하한값을모두가지는경우 g() 의계수는모두 1!! 예제 Tsum = Tsum() = Θ() Trsum() = = Θ() Tadd(rows,cols) = 2rows cols + 2rows + 1 = Θ(rows cols)

42 점근적복잡도 (asymptotic complexity:ο,ω,θ) 는정확한단계수의계산없이쉽게구함 예제 [ 행렬덧셈의복잡도 ] 문장 점근적복잡도 void add(it a[][max_size] ) 0 { 0 it i, j; 0 for (i=0; i < rows; i++) Θ(rows) for (j=0; j < cols; j++) Θ(rows cols) c[i][j] = a[i][j] + b[i][j]; Θ(rows cols) 0 합계 Θ(rows cols) 예제 [ 이진탐색 ] 프로그램 1.6, while loop는log 2 ( 1) 이므로, 최악 Θ(log )

43 1.4.4 실용적인복잡도 두프로그램의성능비교를위해서는, 복잡도와 고려 P 는 10^6, Q 는 ^2 일때, <= 10^6 일경우는 Q 가더빠르므로 Q 를사용 현실적으로볼때, 작은복잡도 (, log, ^2, ^3) 이유용하고, ^10, 2^ 등은 =100 경우에오랜시간걸림

44 log f 그림 1.3 함수값의그래프 log

45 1.5 Performace Measuremet 성능측정 프로그램의수행에요구되는실제적인메모리와시간을얻는방법, 함수 clock 또는 time 사용, 43 페이지 최악의경우, 탐색하는시간측정 it seqsearch(it list[], it searchum, it ) { it I; list [] = searchum ; for (I=0; list[i]!= searchum; I++) ; retur ((I<)? I: -1) ;

46 #iclude <stdio.h> #iclude <time.h> #defie MAX_SIZE 1001 #defie ITERATIONS 16 it search (it [], it, it) void mai (void) { it I, j, positio; it list[max_size]; it sizelist[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 400, 600, 800, 1000 ; it umtimes[] = {30000, 12000, 6000, 5000, 4000, 4000, 4000, 3000, 3000, 2000, 2000, 1000, 500, 500, 500, 200; clock_t start, stop; double duratio, total; for (I=0; I < MAX_SIZE; I++) list[i] = I ; for (I=0; I < ITERATIONS; I++) { start = clock() ; for (j=0; j < umtimes[i]; j++) positio = seqsearch(list, -1, sizelist[i]) ; stop = clock() ; totoal = ((double)(stop - start)) / CLK_TCK; duratio = total / umtimes[i] ; pritf( %5d %d %d %f %f\, sizelist[i], umtimes[i], (it)(stop start), total, duratio) ; list[sizelist[i]] = sizelist[i]; /* 값의재설정 *