컴퓨터 과학 총론, 휴먼싸이언스, 이광수 외 3명 공역 Chapter 05 알고리즘

5.1 알고리즘의 개념

알고리즘: 작업이 어떻게 수행되는지를 규정하는 일련의 단계

모호하지 않고 실행 가능한 단계들의 집합이며, 단계들에는 순서가 정해져 있고 종료되는 프로세스를 정의한다.

이 정의는 알고리즘의 단계들에 순서를 정하도록 요구한다 ( 이는 알고리즘 안의 단계들이 실행 순서와 관련하여 명확한 구조를 가져야 함을 의미한다. 그러나 이 말이 단계들이 나타나는 순서에 따라 차례대로 실행되어야 한다는 것을 의미하는 것은 아니다.)

5.2 알고리즘의 표현

프리미티브: 알고리즘의 표현에 사용될 언어가 정확히 정의되지않거나 정보가 충분히 자세하게 기술되지 않을 경우 의사소통 문제가 발생한다.

컴퓨터과학에서는 알고리즘 표현에 사용할 잘 정의된 기초 요소의 집합을 구축함으로써 이와 같은 문제를 해결한다. 이러한 기초요소를 프리미티브라고 부른다.

프리미티브의 특징

1) 모호성 문제가 해결

2) 세부사항 서술 정도의 일관성을 확립

3) 각 프리미티브는 자체의 구문과 의미를 갖는다

구문이란 프리미티브의 기호 표현을 가리키며, 의미는 프리미티브가 나타내는 개념을 가리킨다.

프로그래밍 언어: 프리미티브의 집합과 더 복잡한 개념을 표현하기 위한 프리미티브 조합 규칙의 집합

의사코드: 알고리즘 개발과정에서 생각들을 보다 자유로운 형식으로 표현할 수 있는 표기 체계이다.

의사코드를 만드는 한 가지 방법은 정형적인 프로그래밍 언어의 구문과 의미구조를 차용하되 그 언어의 규칙들을 다소 완화하고 비정형적인 구문들을 섞어 사용하는 것이다.

순서도는 도형과 화살표로 알고리즘을 표현, 설계보다는 설명에 사용할 경우 여전히 유용한 도구이다.

비슷하지만 같지는 않은 단어들

부프로그램 = 서브루틴 = 프로시저 = 메소드 = 함수

* 참고

파스칼 케이싱 ArrivalTime 

케멀케이싱 arrivalTime

5.3 알고리즘의 발견

5.4 반복 구조

5.5 재귀구조

5.6 효율성과 정확성