포스트를 읽으실 때 참고하실 점
- 프로그래밍에 대한 깊은 이해를 쌓고자, 개인적으로 필요한 수학적 지식들을 간략하게만 기록하기 위한 포스팅입니다. 단순한 수준의 프로그래밍을 하기 위해서는 필요하지 않은 내용이 다수 포함될 수 있습니다.
- 만약 포스팅에 잘못된 내용이 있다면 댓글이나 이메일을 통해 알려주시면 수정하겠습니다. 감사합니다.
Strict weak ordering
집합 $S$에 대하여 다음의 4 가지 조건을 만족하는 동차 관계(homogeneous relation) $<$를 strict weak ordering이라고 한다.
- 비반사성(irreflexibility): 집합 $S$에 속하는 모든 원소에 대해 $a < a$는 거짓이다.
- 추이성(transitivity): 집합 $S$에 속하는 원소 $x, y, z$에 대해, $x < y, y < z$가 참이면 $x < z$은 참이다.
- 비대칭성(asymmetry): 집합 $S$에 속하는 원소 $x, y$에 대해, $x < y$가 참이면 $y < x$는 거짓이다.
- 비교 불가능의 추이성(transitivity of incomparability): 집합 $S$에 속하는 원소 $x, y, z$에 대해, $x$와 $y$가 비교 불가능(incomparable)하고 $y$와 $z$가 비교 불가능하면, $x$와 $z$도 비교 불가능하다.
여기서의 '<' 는 부등호가 아니고 두 원소 사이의 관계(relation)를 나타내는 수학적 기호인데, 우리가 알고 있는 부등호 '<' 도 관계 연산의 하나이기 때문에 이해가 어려우면 그냥 부등호로 대입해서 생각해봐도 될 것 같다(수학이 원래 좀 깊게 들어가면 뭐가 뭔 소린지...).
* 참고) 위의 4 가지 조건 중 비반사성, 추이성, 비대칭성을 만족하는 관계 연산을 엄격한 부분 순서(strict partial order)라고 한다.
해당 개념이 필요한 이유 / 사용되는 곳
이러한 개념은 주로 정렬 알고리즘에 대해 수학적으로 깊게 분석할 때 등장하는 이론적인 개념인데, 어떠한 집합이 주어졌을 때 해당 집합의 모든 원소들을 유일한 방법으로만 순서를 매길 수 있는 비교 연산이 되기 위한 필요 조건이다. 사용자가 정의한 비교 연산(예: 이항 조건(predicate) - bool 형의 리턴형을 가지는 펑터)을 사용해 정렬할 때, 비교 연산이 strict weak ordering을 만족하지 않는다면 정렬 알고리즘을 적용하더라도 오류가 발생할 수 있다.
댓글