시스템 생명 주기(System Life Cycle)(1/2) 요구사항(requirements) 프로젝트들의 목적을 정의한 명세들의 집합 입력과 출력에 관한 정보를 기술 분석(analysis) 문제들을 다룰 수 있는 작은 단위들로 나눔 상향식(bottom-up)/하향식(top-down) 접근 방법 설계(design) 추상 데이타 타입(abstract data type) 생성 알고리즘 명세와 설계 기법 고려

시스템 생명 주기(2/2) 정제와 코딩(refinement and coding) 검증(verification) 데이타 객체에 대한 표현 선택 수행되는 연산에 대한 알고리즘 작성 검증(verification) 정확성 증명(correctness proof) 수학적 기법들을 이용해서 증명 테스트(testing) 프로그램의 정확한 수행 검증 프로그램의 성능 검사 오류 제거(error removal) 독립적 단위로 테스트 후 전체 시스템으로 통합

포인터와 메모리 할당(1/3) 포인터 C언어에서는 어떤 타입 T에 대해 T의 포인터 타입이 존재 포인터 타입의 실제값은 메모리 주소가 됨 포인터 타입에 사용되는 연산자 & : 주소 연산자 * : 역참조(간접 지시) 연산자 Ex) i(정수 변수), pi(정수에 대한 포인터) int i, *pi pi = &i; i에 10을 저장하기 위해서는 다음과 같이 할 수 있다. i = 10; 또는 *pi = 10; 널포인터 정수 0값으로 표현 널포인터에 대한 검사 int (pi ==Null) 또는 if(!pi)

포인터와 메모리 할당(2/3) 동적 메모리 할당 프로그램을 작성할 당시 얼마나 많은 공간이 필요한지 알수 없을때 사용 히프(heap) 기법 새로운 메모리 공간이 필요할 때마다 함수 malloc을 호출해서 필요한 양의공간을 요구 int i, *pi; float f, *pf; pi = (int *) malloc(sizeof(int)); pf = (float *) malloc(sizeof(float)); *pi = 1024; *pf = 3.14; printf(“an integer = %d, a float = %f\n”, *pi, *pf); free(pi); free(pf); 메모리 할당과 반환

포인터와 메모리 할당(3/3) 포인터의 위험성 포인터가 대상을 가리키고 있지 않을때는 값을 전부 null로 정하는 것이 바람직 이는 프로그램 범위 밖이나 합당하지 않은 메모리 영역을 참조할 가능성이 적어짐 명시적인 타임 변환(type cast) pi = malloc(sizeof(int)); /* pi에 정수에 대한 포인터를 저장 */ pf = (float *) pi; /* 정수에 대한 포인터를 부동소수에 대한 포인터로 변환 */

알고리즘 명세 알고리즘(Algorithm) 특정한 일을 수행하기 위한 명령의 유한 집합 조건 입력 : (외부) 원인 ≥ 0 출력 : 결과 ≥ 1 명백성(definiteness) : 모호하지 않은 명확한 명령 유한성(finiteness) : 종료 유효성(effectiveness) : 기본적, 실행가능 명령 Ex) program ≡ algorithm 흐름도(flowchart) ≡ algorithm (명백성과 모호성에 결여)

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

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

알고리즘 명세 #include <stdio.h> #include <math.h> #define MAX_SIZE 101 #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) void sort(int [], int); /* selection sort */ void main(void) { int i, n; int list[MAX_SIZE]; printf(“Enter the number of numbers to generate: ”); scanf(“%d”, &n); if(n<1 || n> MAX_SIZE) { fprintf(stderr, “Improper value of n\n”); exit(EXIT_FAILURE); } for (i=0; i<n; i++) { /* randomly generate numbers*/ list[i] = rand()%1000; printf(“%d”, list[i]);

알고리즘 명세 sort(list, n); printf(“\n Sorted array:\n”); for(i=0; i<n; i++) /*print out sorted numbers */ printf(“%d”, list[i]); printf(“\n”); } void sort(int list[], int n) { int i, j, min, temp; for(i=0; i<n-1; i++) { min = i; for (j = i+1; j<n; j++) if(list[j] <list[min]) min =j; SWAP(list[i], list[min], temp);

알고리즘 명세 예제[이진탐색]: 정수 searchnum이 배열 list에 있는지 검사 List[0] ≤ list[1] ≤... ≤ list[n-1] 주어진 정수 searchnum에 대해 list[i]=searchnum인 인덱스 i를 반환 없는 경우는 -1 반환 초기값 : left=0, right=n-1 List의 중간 위치 : middle=(left+right)/2 List[middle]와 searchnum을 비교 1) searchnum < list[middle] : list[0] ≤ searchnum ≤ list[middle-1] right = middle-1 2) searchnum = list[middle] : middle을 반환 3) searchnum > list[middle] : list[middle+1] ≤ searchnum ≤ list[n-1] left = middle+1

알고리즘 명세 while (there are more integers to check) { middle = (left + right) / 2; if(searchnum < list[middle]) right = middle-1; else if (searchnum = = list[middle]) return middle; else left = middle +1; } < 정렬된 리스트 탐색 > int compare(int x, int y) { /* compare x and y, return -1 for less than, 0 for equal, 1 for greater */ if (x<y) return -1; else if (x = = y) return 0; else return 1; } < 두 정수의 비교 >

알고리즘 명세 비교 연산 : 함수, 메크로 첫번째 수치 값이 두번째 수치의 값보다 작을때 음수 반환 두 수치 값이 같은 경우 0을 반환 첫번째 수치 값이 두번째 수치 값보다 큰 경우 양수 반환 #define COMPARE(x, y) ((x)<(y) ? -1 : (x) = =(y)) ? 0 : 1) int binsearch(int list[], int searchnum, int left, int right) { */ search list [0] <= list[1] <= … <= list[n-1] for searchnum. Return its position if found. Otherwise return -1 */ int middle; while (left <=right) { middle = (left + right) / 2; switch (COMPARE(list[middle], searchnum)) { case -1: left = middle + 1 break; case 0 : return middle; case 1 : right = middle -1;} } return -1;

순환 알고리즘 예제 [이진 탐색] int binsearch(int list[], int searchnum, int left, int right) { */ search list [0] <= list[1] <= … <= list[n-1] for searchnum. Return its position if found. Otherwise return -1 */ int middle; if (left <=right) { middle = (left + right) / 2; switch (COMPARE(list[middle], searchnum)) { case -1: return binsearch(list, searchnum, middle+1, right); case 0 : return middle; case 1 : return binsearch(list, searchnum, left, middle-1); } return -1; < 이원탐색에 대한 순환 구현 >

데이터 추상화(1/4) C언어의 기본 자료형 : char, int, float, double 키워드 : short, long, unsigned 자료의 그룹화 : 배열(array), 구조(stucture) Int list[5] : 정수형 배열 구조 포인터 자료형 : 정수형, 실수형, 문자형, float형 포인터 int i, *pi; 사용자 정의(user-defined) 자료형 struct student { char lastName; int studentId; char grade; }

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

데이터 추상화(3/4) 정의 : 추상 자료형(ADT: abstract data type) 객체의 명세와 그 연산의 명세가 그 객체의 표현과 연산의 구현으로부터 분리된 자료형 명세와 구현을 명시적으로 구분 Ada – package, C++ – Class ADT 연산의 명세 함수 이름, 매개 변수형, 결과형, 함수가 수행하는 기능에 대한 기술 내부적 표현이나 구현에 대한 자세한 설명은 필요 없음  ADT가 구현에 독립 자료형의 함수 생성자(creater)/구성자(constructor) : 새 인스턴스 생성 변환자(transformer) : 한 개 이상의 서로 다른 인스턴스를 이용하여 지정된 형의 인스턴스를 만듬 관찰자(observers)/보고자(reporter) : 자료형의 인스턴스에 대한 정보를 제공

데이터 추상화(4/4) 예제[추상 데이터 타입 NaturalNumber] 객체(objects) : 0에서 시작해서 컴퓨터상의 최대 정수값 (INT_MAX)까지 순서화된 정수의 부분 범위이다. 함수(functions) : for all x, y ∈ Nat_Number, TRUE, FALSE ∈ Boolean에 대해, 여기서 +, -, <, 그리고 ==는 일반적인 정수 연산자이다. NaturalNumber Zero() ::= 0 Boolean IsZero(x) ::= if(x) return FALSE else return TRUE Boolean Equal(x, y) ::= if(x= =y) return TRUE else return FALSE NaturalNumber Successor ::= if(x = = INT_MAX) return x else return x+1 NaturalNumber Add(x,y) ::= if((x+y)<= INT_MAX) return x+y else return INT_MAX NaturalNumber Subtract(x,y) ::= if(x<y) return 0 else return x-y End NaturalNumber

성능 분석 성능 평가(performance evaluation) 정의 성능분석(performance analysis) 시간과 공간의 추산 복잡도 이론(complexity theory) 성능측정(performance measurement) 컴퓨터 의존적 실행 시간 정의 공간 복잡도(space complexity) 프로그램을 실행시켜 완료하는데 필요한 공간의 양 시간 복잡도(time complexity) 프로그램을 실행시커 완료하는데 필요한 컴퓨터 시간의 양

시간 복잡도 단계의 계산(방법 2) [예제] 리스트에 있는 수를 합산하는 반복함수 테이블 방식(tabular method) : 단계수 테이블 문장에 대한 단계수 : steps/execution, s/e 문장이 수행되는 횟수 : 빈도수(frequency) 비실행 문장의 빈도수 = 0 총 단계수 : 빈도수  s/e [예제] 리스트에 있는 수를 합산하는 반복함수 문 장 s/e 빈도수 총단계수 float sum(float list[], int n) { float tempsum = 0; int i; for (i=0; i<n; i++) tempsum += list[i]; return tempsum; } 0 0 0 1 1 1 1 n+1 n+1 1 n n 합 계 2n+3

시간 복잡도 [예제] 리스트에 있는 수를 합산하는 순환 함수 [예제] 행렬의 덧셈 문 장 s/e 빈도수 총단계수 합 계 문 장 s/e 빈도수 총단계수 float rsum(float list[], int n) { if (n) return rsum(list, n-1) + list[n-1] return list[0]; } 0 0 0 1 n+1 n+1 1 n n 1 1 1 합 계 2n+2 문 장 s/e 빈도수 총단계수 void add(int a[][MAX_SIZE] ··· ) { int i, j; for (i=0, i<rows; i++) for(j=0, j<cols; j++) c[i][j] = a[i][j] + b[i][j] } 0 0 0 1 rows+1 rows+1 1 rows(cols+1) rows·cols+row 1 rows·cols rows·cols 합 계 2rows·cols+2rows+1