지금까지 데이터의 저장, 조작법을 알아봤고 그걸 네트워크 상에서 통신하는 법을 배웠다.
그리고 코드로 목적을 달성하기 위한 알고리즘도 배워보겠다.
< 1 > 알고리즘
1. 알고리즘
2. 표현법
3. 발견법
4. 구조
5. 효율성과 정확성
알고리즘이란 문제를 해결하기 위한 실행가능한 단계(명령)들의 집합을 말한다
알고리즘은 4가지의 요구사항과 한가지의 특징이 있다
- 명확성
- 유일성
- 유효성
- 유한성
- 추상성
명확성이란 실행할 동작을 명확하게 결정할 수 있어야 한다는 것이다.
유일성이란 알고리즘의 각 단계들이 실행 순서와 관련하여 명확한 구조를 가져야 한다는 것이다.
유효성이란 알고리즘의 각 단계의 명령들이 실행 가능해야 한다는 것이다.
유한성이란 알고리즘이 반드시 유한한 단계를 가져서 결국 종료되야한다는 것이다.
추상성은 현상의 표현과 구별되며, 본질을 축약시켜 표현한다는 것이다.
< 1 > 알고리즘
1. 알고리즘
2. 표현법
3. 발견법
4. 구조
5. 효율성과 정확성
알고리즘을 표현하기위해 Primitive를 쓴다
Primitive란 알고리즘을 표현하기 위해 잘 정의된 요소이다.
Primitive는 구문과 의미로 구성된다.
구문이란 알고리즘의 표현을 위해 정의한 기호나 문자이다.
의미란 구문이 담고있는 의미로써 주로 동작을 표현한다.
그리고 Primitive의 목적처럼, 알고리즘을 Primitive로 표현하면 알고리즘의 정형적 표현이라고 한다.
그리고 Primitive를 인간이 이해하기 쉽게 하기 위해 의사코드 방식으로 작성할 수도 있다
의사코드란 자연어 문장을 프로그래밍 언어방식으로 배치한것을 의미한다
의사코드 Primitive 란, 의사코드 방식으로 만들어진 프리미티브를 의미한다
그 예로 두가지가 있다.
- 함수
- 식별자 표기법
함수는 프로그램 안에서 특정 동작을 수행하기 위한 코드다.
이것은 3가지 요소를 가진다.
매개변수, 실행코드, 반환값.
특징은 4가지를 가진다.
함수는 재사용으로 코드의 반복을 줄인다.
복수의 함수로 알고리즘을 단순화 한다.
식별자 표기법은 식별자에 대한 표기법이다.
식별자는 프로그래밍 언어에서 이름을 붙일때 쓰는 단어이다.
그러니까 식별자 표기법은 그냥 단순하게 변수 명명법이라고 보면 된다.
식별자 표기법은 4가지가 있다.
- 카멜
- 파스칼
- 스네이크
- 케밥
카멜 표기법이란, 변수, 함수 이름의 첫글자만 소문자로 하고 나머지 각 단어의 첫글자는 전부 대문자로 표기하는 방식이다. hiMan 같은 거다.
파스칼 표기법이란 클래스의 이름의 단어의 모든 첫글자를 대문자로 표기하는 방식이다
스네이크 표기법은 변수, 함수 이름의 각단어 사이에 _를 넣고 각단어는 전부다 소문자로 표기하는 방식이다.
케밥 표기법이란, 함수의 이름에서 각단어 사이에 -를 넣어서 표기하는 표기법이다
< 1 > 알고리즘
1. 알고리즘
2. 표현법
3. 발견법
4. 구조
5. 효율성과 정확성
알고리즘을 발견하기 위해서는 5가지 단계를 거친다.
(+0. 정보 수집)
1. 문제 이해
2. 해결절차에 대한 생각정리
3. 알고리즘 기술 및 정확성 검토
4. 프로그램 기술 및 정확성 검토
5. 타 문제 해결로의 활용성을 평가 및 일반화 검토
문제 이해를 위해선 세가지를 주로 한다.
목표 설정
배경, 제한 조건 파악
주요 기능, 요구사항 설정
방법론으론 8가지가 있다.
- 트리즈
- 스캠퍼
- 단계적 개선법
- 예증
- 패턴 매칭
- 단순화와 일반화
- 초기 사례
- 자료구조 브레인 스토밍
트리즈, TRIZ란 유사한 문제의 해결법을 찾고 적용하는 방법이다.
스캠퍼, SCAMPER란 기존의 해결법을 변형해서 적용하는 것이다.
예를들어 "대체, 결합, 적용, 변형, 확대, 축소, 용도변경, 제거, 재배치/거꾸로하기"가 있다.
단계적 개선법이란, 주어진 문제를 작은 쉬운 문제들로 분할하고 해결한 뒤 다시 취합하여 해결법을 찾는 것이다.
종류로 두단계가 있다.
- 하향식 방법
- 상향식 방법
하향식 방법이란, 주어진 문제를 기본 요소들로 세분화 하는 것이다.
상향식 방법이란, 기본 요소들을 조합하여 주어진 문제를 해결하는 것이다.
이 방법은 문제해결 단계에서 2~3번째 방법 (해결절차에 대한 생각정리, 알고리즘 기술)에서 쓴다.
- 트리즈
- 스캠퍼
- 단계적 개선법
- 예증
- 패턴 매칭
- 단순화와 일반화
- 초기 사례
- 자료구조 브레인 스토밍
예증 (exemplify)이란, 문제의 사례에서 일반적인 규칙을 찾아내는 것이다.
패턴매칭 (pattern matching)이란, 트리즈
단순화와 일반화란, 제약조건을 변경하여 단순화하고 알고리즘을 구하고 일반화하고 복잡한 형태로 다듬어 가는 방식이다.
초기사례로부터의 확장, base case로부터 build란, 초기사례의 답을 구했다고 가정하고 그 사례로부터 확장시켜나가면서
답을 구해나가다가 일반화 하여 모든 답을 구하는 방식이다.
자료구조 브레인 스토밍이란, 여러 자료구조들을 적용해보는 것이다.
< 1 > 알고리즘
1. 알고리즘
2. 표현법
3. 발견법
4. 구조
5. 효율성과 정확성
알고리즘 구조의 종류는 5가지가 있다.
- 반복
- 순차 검색
- 삽입 정렬
- 재귀
- 2진 검색
반복 구조란, 반복되는 활동을 묶은 뒤, 지정된 횟수만큼 반복하거나 일정 조건을 만족할때까지 반복하게 만든 체계를 말한다.
루프란, 어떤 조건에 만족할때까지 하나의 명령 또는 일련의 명령들을 반복적 사용하는 것이다.
루프는 행동이고
반복구조는 행동을 체계화 한것이다.
루프 제어의 구성 요소는 3가지다.
- 초기화
- 테스트
- 변경
초기화란, 종료 조건으로 이행 되어갈 초기 상태를 확립 하는 것이다.
테스트란, 현재 상태와 종료 조건을 비교하고 이들이 같으면 반복을 종료시키는 것이다.
변경이란, 종료 조건을 향해 이행되도록 상태를 변화시키는 것이다.
루프 구조는 두가지다
- 사전 테스트 루프
- 사후 테스트 루프
사전 테스트 루프란 포문이나 와일문 같은 것이다
- 반복
- 순차 검색
- 삽입 정렬
- 재귀
- 2진 검색
검색이란, 항목들의 선형 순서 집합인 리스트에서 특정 조건을 만족하는 항목을 찾는 작업이다.
순차 검색이란, 리스트를 처음부터 차례대로 읽으면서 검색모표 이름과 비교하는 것이다.
- 반복
- 순차 검색
- 삽입 정렬
- 재귀
- 2진 검색
정렬이란, 주어진 리스트에 저장되어 있는 항목들을 원하는 순서대로 나열하는 작업이다.
정렬 시에는 제약 조건이 있다.
정렬 시, 제약조건은 기억공간의 절약을 위해 리스트 안에서 항목의 이동으로 정렬하는 것이다.
이때, 임시 장소를 이용한다.
- 반복
- 순차 검색
- 삽입 정렬
- 재귀
- 2진 검색
재귀 구조란, 알고리즘이 끝나기 전에 자신을 호출하는 구조다.
재귀 구조 알고리즘은 분할 정복 접근법을 따른다.
분할이란, 전체문제를 유사하고 작은 부분 문제로 세분화하는 것이다.
정복이란, 재귀적으로 그 부분 문제들을 해결한다.
결합이란, 부분 문제들의 해를 결합해서 원래 문제의 해를 만드는 것이다.
.
- 반복
- 순차 검색
- 삽입 정렬
- 재귀
- 2진 검색
2진 검색법이란, 검색하고자 하는 값들을 반씩 쪼개가며 원하는 값을 찾는 방법이다.
< 1 > 알고리즘
1. 알고리즘
2. 표현법
3. 발견법
4. 구조
5. 효율성과 정확성
알고리즘의 평가에선 4가지 요소를 본다.
- 정확하게 작동하는가?
- 논리적 단위를 생성하기 위해 함수를 효과적으로 사용하는가?
- 주기억장치를 효율적으로 사용하는가?
- 실행 시간은 효율적인가?
그리고 효율성에선 3가지 경우를 본다.
- 최선
- 최악
- 평균
추가적으로 SW는 검증까지 거쳐야한다.
이때 SW검증이란, 정형논리를 이용해서 SW의 정확성을 증명하는 것이다.
이때 세가지 명제가 쓰인다.
- 사전 조건 명제
- 루프 불변 명제
- 사후 조건 명제
사전 조건 명제란, 실행하기전에 충족 되어야하는 명제다.
루프 불변 명제란, 루프 반복마나 참일 거라고 가정하는 명제다.
사후 조건 명제란, 실행 후에 만족되어야하는 명제다.
예를 들어 아래와 같다.
//Y의 값은 0이 아니다. – 사전 조건 명제
X = Y
//X의 값은 0이 아니다. – 사후 조건 명제
이걸 이용해서 SW를 검증하는 방법은
프로그램의 여러곳에 여러 명제들을 세워두고 프로그램 종료 시, 끝부분 명제가 사후조건 명제와 부합하면 이 SW은 정확하다고 결론을 내리는 것이다.
그 예는 아래와 같다.
'Computer Architecture' 카테고리의 다른 글
| 컴퓨터 시스템 개론 : 7장 : SW 공학 (0) | 2024.05.14 |
|---|---|
| 컴퓨터 시스템 개론 : 6장 : 프로그래밍 언어 (0) | 2024.05.14 |
| 컴퓨터 시스템 개론 : 4장 : 네트워크와 인터넷 (1) | 2024.04.27 |
| 컴퓨터 시스템 개론 : 3장 : 운영체제 (1) | 2024.04.26 |
| 컴퓨터 시스템 개론 : 2장 : 데이터의 조작 (0) | 2024.04.21 |
댓글