• MATHEMATICAL PRELIMINARIES AND NOTATION
  • 수학적 개요 및 표기법

집합(Sets)

원소(elements)들의 모임.

  • x가 집합 S의 원소
  • 정수 0, 1, 2 를 포함하는 집합
  • 의미가 명확하면 생략 기호 를 쓸 수 있다.
  • 다음과 같이 표현할 수도 있다.
    • “S는 0보다 크고 짝수인 모든 i의 집합, i는 정수.”
  • 합집합(union, )
  • 교집합(intersection, )
  • 차집합(difference, )
  • 여집합(complementation)
    • 전체 집합 U 가 정의된 상태에서,
  • 공집합(empty set, null set)
  • 집합의 정의로부터 알 수 있는 것들

DeMorgan의 법칙

부분집합

  • 부분집합(subset)
  • 진부분집합(proper subset)
    • 이면서 에 없는 원소를 포함하는 경우.
  • 서로소(disjoint)
    • 두 집합 사이에 공통으로 속하는 원소가 없는 경우.
    • 즉, 인 경우.
  • 무한 집합(infinite set) : 원소의 개수가 무한한 경우.
  • 유한 집합(finite set) : 원소의 개수가 유한한 경우.
  • 유한 집합의 크기
    • 집합의 원소의 개수

멱집합

  • 멱집합(powerset)
    • 한 집합 S의 모든 부분 집합들의 집합.
    • 집합을 원소로 삼는 집합이라는 점에 주목.

예를 들어 집합 의 멱집합은 다음과 같다.

곱집합

In many of our examples, the elements of a set are ordered sequences of elements from other sets. Such sets are said to be the Cartesian product of other sets.

  • 곱집합(Cartesian product, 데카르트 곱, 카티지언 프로덕트)
    • 한 집합의 원소들이 다른 여러 집합 원소들의 순서열(ordered sequence)인 경우.
    • 두 집합의 카티션 곱은 순서쌍(ordered pair)들의 집합이 된다.

예를 들어 두 집합 이 다음과 같을 때,

카티션 곱은 다음과 같다.

  • 주의: 순서쌍 내 원소의 순서는 중요하다.
  • (4, 2)는 있지만 (2, 4)는 없다는 점에 주목.

둘 이상의 집합에 대한 카티션 곱.

분할

집합은 여러 부분집합으로 분할할 수 있다.

의 부분집합이고 다음의 조건들을 만족한다면…

  • 부분집합 은 서로소(mutually disjoint)이다;
  • ;
  • 중 어느 집합도 공집합이 아니다.

이러한 경우 의 분할(partition)이라 한다.

함수와 관계(Functions and Relations)

A function is a rule that assigns to elements of one set a unique element of another set. If f denotes a function, then the first set is called the domain of f, and the second set is its range.

  • 함수(function) : 집합의 원소들 각각에 대해 다른 집합의 단일 원소로 배정하는 규칙.
  • 가 함수라면, 첫 번째 집합을 함수 의 정의역(domain)이라 하고, 두 번째 집합을 치역(range)이라 한다.
  • 함수 는 다음과 같이 표기한다.
  • 위와 같이 표기한다면 다음을 의미한다.
    • 함수 의 정의역은 의 부분집합이다.
    • 함수 의 치역은 의 부분집합이다.

전체 함수, 부분 함수

  • 전체 함수(total function): 함수 의 정의역이 과 같다면 를 전체 함수라 한다.
  • 부분 함수(partial function): 가 전체 함수가 아닌 경우.

크기 순위 표기법(order-of-magnitude notation)

  • 이 정의역이 양의 정수들의 부분집합인 함수라 하자.

충분히 큰 모든 n에 대하여, 다음의 부등식을 만족하는 양의 상수 c가 존재한다면,

의 순위가 의 순위보다 높지 않다고 한다(we say that has order at most ).

그리고 다음과 같이 표기한다.

충분히 큰 모든 n에 대하여, 다음의 부등식을 만족하는 양의 상수 c가 존재한다면,

의 순위가 의 순위보다 낮지 않다고 한다(then has order at least ).

그리고 다음과 같이 표기한다.

충분히 큰 모든 n에 대하여, 다음의 부등식을 만족하는 상수 가 존재한다면,

와 같은 크기 순위를 갖는다고 한다( and have the same order of magnitude).

그리고 다음과 같이 표기한다.

예제

다음과 같은 함수가 있다.

크기 순위 표기법은 다음과 같다.

즉, 다음과 같이 생각할 수 있다.

TAOCP도 찾아보자

좀 더 이해를 돕기 위해 TAOCP 1권의 1.2.11.1 O 표기법 챕터를 찾아보자.

Let’s look at some more examples. We know that

그럼 예들을 좀 더 보자. 다음은 우리가 알고 있는 것이다.

so it follows that

이로부터 다음을 얻는다.

Equation (2) is rather crude, but not incorrect; Eq. (3) is a stronger statement; and Eq. (4) is stronger yet.

식 (2)가 상당히 대략적이긴 하지만, 그렇다고 부정확한 것은 아니다. 식 (3)은 좀 더 엄정한 서술이다. 그리고 식 (4)는 더욱 엄정하다.

(중략)

The O-notation is a big help in approximation work, since it describes briefly a concept that occurs often and it suppresses detailed information that is usually irrelevant. Furthermore, it can be manipulated algebraically in familiar ways, although certain important differences need to be kept in mind. The most important consideration is the idea of one-way equalities: We write , but we never write . (Or else, since , we might come up with the absurd relation .) We always use the convention that the right-hand side of an equation does not give more information than the left-hand side; the right-hand side is a “crudification” of the left.

O 표기법은 자주 나타나는 개념을 간략히 서술하고 대체로 별 상관이 없는 세부 정보를 숨긴다는 점에서 근사를 다룰 때 큰 도움이 된다. 더 나아가서, 이 O들을 익숙한 대수적 방법으로 조작하는 것이 가능하다. 단, 몇 가지 중요한 차이들은 염두에 두어야 하는데, 가장 중요한 것이 단방향 상등(one-way equality)이라는 개념이다. 즉, 이라고 쓸 수는 있지만 이라고는 절대 쓸 수 없다. (만일 그런 표기가 허용된다면, 이므로 이라는 터무니없는 결과가 나온다.) 이 표기법이 관련된 등식에서는 항상 등식의 우변이 좌변보다 더 자세한 정보를 제공하지 않는다는 관례를 사용한다. 즉, 우변은 항상 좌변보다 조악한 버전인 것이다.

관계

함수를 순서쌍의 집합으로 표현할 수 있다.

where is an element in the domain of the function, and is the corresponding value in its range. For such a set to define a function, each can occur at most once as the first element of a pair. If this is not satisfied, the set is called a relation.

  • 관계
    • 순서쌍의 집합으로 함수를 표현하려면 각 가 이 집합 내에서 순서쌍의 첫 번째 위치에 한 번만 나타나야 한다.
    • 이 조건이 만족되지 않는 경우에는 이 집합을 함수라 할 수 없다.

동치 관계

동치 관계(equivalence relation)는 세 가지 성질을 만족하는 경우를 말한다.

  • 반사성(reflexivity rule)
  • 대칭성(symmetry rule)
  • 전이성(transitivity rule)

예제

다음과 같은 음이 아닌 정수 집합에서의 관계를 정의하자.

이는 대략 다음과 같은 의미이다.

  • 이면 라고 정의하자.

이 관계에서는 등이 성립한다.

If S is a set on which we have a defined equivalence relation, then we can use this equivalence to partition the set into equivalence classes. Each equivalence class contains all and only equivalent elements.

  • 만약 집합 S에 동치관계가 정의되어 있다면, 이러한 동치성을 사용하여 집합 S를 동치부류(equivalence classes)로 분할할 수 있다.
  • 각각의 동치부류는 서로 동치인 원소들만을 포함한다.

그래프와 트리(Graphs and Trees)

  • 그래프 : 두개의 유한 집합으로 이루어지는 구조.
    • 정점(vertex)들의 집합.
    • 간선(edge)들의 집합.

예: 정점 를 잇는 간선

  • 기준으로 는 진출 간선(outgoing edge).
  • 기준으로 는 진입 간선(incoming edge).

유향 그래프(digraph)

Such a construct is actually a directed graph (digraph), since we associate a direction (from to ) with each edge.

위의 예와 같이 각 간선에 방향을 지정하는 그래프를 유향 그래프(directed graph, digraph)라 부른다.

라벨 그래프(labeled graph)

  • 정점이나 간선에 라벨(label)을 지정한 그래프.
    • 라벨로 특별한 이름이나 정보를 부여한다.

그래프 도식화

  • 정점은 원으로 표현한다.
  • 간선은 두 정점을 잇는 화살표로 표현한다.

다음은 이고, 인 그래프이다.

image

A sequence of edges is said to be a walk from to .

  • 보행(walk): 와 같이 표현되는 간선들의 순서열을 로부터 으로의 보행(walk)라 한다.

The length of a walk is the total number of edges traversed in going from the initial vertex to the final one.

  • 보행의 길이(length of a walk): 보행의 시작 정점부터 마지막 정점까지 지나게 되는 간선들의 수.

A walk in which no edge is repeated is said to be a path;

  • 경로(path): 어느 간선도 중복되지 않는 보행을 경로라 한다.

a path is simple if no vertex is repeated.

  • 단순 경로(simple path): 어느 정점도 중복하여 지나지 않는 경로.
    • 예:

A walk from to itself with no repeated edges is called a cycle with base .

  • 를 base로 삼는 사이클(cycle): 정점 로부터 어느 간선도 중복하여 지나지 않고 자신에게 돌아오는 보행.
    • 예:

If no vertices other than the base are repeated in a cycle, then it is said to be simple.

  • 단순 사이클(simple cycle): 한 사이클에서 base 정점 외의 어느 정점도 중복하여 지나지 않는 것.

Finally, an edge from a vertex to itself is called a loop.

  • 루프(loop): 한 정점에서 자기 자신으로의 간선.
    • 예:

트리(Tree)

image

Trees are a particular type of graph. A tree is a directed graph that has no cycles and that has one distinct vertex, called the root, such that there is exactly one path from the root to every other vertex. This definition implies that the root has no incoming edges and that there are some vertices without outgoing edges. These are called the leaves of the tree. If there is an edge from to , then is said to be the parent of , and the child of . The level associated with each vertex is the number of edges in the path from the root to the vertex. The height of the tree is the largest level number of any vertex.

  • 트리는 그래프의 일종이다.
  • 트리는 사이클이 없으며, root라 불리는 하나의 구별되는 정점을 갖는 유향 그래프(directed graph)이다.
  • 루트에서 다른 모든 정점으로는 하나의 경로만이 존재한다.
  • 루트는 진입 간선(incoming edge)가 없다.
  • 트리는 진출 간선(outgoing edge)을 갖지 않는 정점들이 존재한다.
    • 이런 정점들을 leaves라 부른다.
  • 부모(parent): 정점 에서 로의 간선이 존재할 때, 를 부모라 한다.
  • 자식(child): 정점 에서 로의 간선이 존재할 때, 를 자식이라 한다.
  • 레벨(level): 루트에서 해당 노드까지의 간선의 개수.
  • 높이(height): 트리의 정점들 중 가장 큰 레벨을 갖는 정점의 레벨.
  • 각 레벨에 있는 노드에 순서를 부여하는 트리를 순서 트리(ordered tree)라 부른다.

증명 기법(Proof Techniques)

Induction is a technique by which the truth of a number of statements can be inferred from the truth of a few specific instances.

  • 귀납법(proof by induction): 몇 개의 특정 사례(instance)가 true라는 사실들로부터 여러 문장들이 true임을 추론해 내는 기법.

Proof by contradiction is another powerful technique that often works when everything else fails. Suppose we want to prove that some statement P is true. We then assume, for the moment, that P is false and see where that assumption leads us. If we arrive at a conclusion that we know is incorrect, we can lay the blame on the starting assumption and conclude that P must be true.

  • 귀류법(proof by contradiction): 생략.

Links