ㅈ씀
Sequence
sequence는 '열'을 말한다.
고등학교 때 배웠던 수열 뿐만 아니라 문자열도 모두 포함하는 것이다.
어떤 순서에 의해 무언가를 늘어놓은 것을 Sequence라고 부른다.
finite sequence / infinite sequence
sequence는 finite sequence와 infinite sequence로 나뉜다.
finite sequence는 '유한수열', infinite sequence는 '무한수열'이다.
sequence를 나타내는 두가지 formula
sequence는 두가지 formula로 나타낼 수 있는데, 그게 바로 Recursive와 Explicit이다.
Recursive는 수열의 첫값을 주고 n을 n-1에 관한 식으로 나타내는 방법이다.
이전 값으로부터 다음 값을 계산하는 것이 바로 Recursive이다.
Explicit은 n에 관한 식을 직접 주는 것이다. 식에 n값을 넣으면 바로 구할 수 있다.
String, Set corresponding to a sequence
String은 문자열을 뜻하고 'abababab......'와 같은 열이 그 예이다.
'xyzxyzxyzzzyyxzxz...'라는 string에 쓰인 문자를 찾아서 집합을 만들어보면 {x, y, z}가 되는데,
이 때 {x, y, z}는 Set corresponding to a sequence라고 부른다.
즉 sequence에 쓰인 원소들의 집합을 Set corresponding to a sequence라고 한다.
Sequence vs Linear array (or List)
Linear array 또는 List는 Sequence와 유사한 개념이지만 차이가 있다.
Sequence에서는 하나의 값이 바뀌면 sequence 자체가 다른 sequence로 바뀐다고 보지만,
array에서는 하나의 값이 바뀌어도 그대로의 array로 본다.
즉 array는 일정한 칸을 만들어놓고 그 칸에 숫자를 채우는 식으로 보면 된다.
Characteristic functions
characteristic function은 집합 A에 원소 x가 속하면 그 값을 '1'로,
속하지 않으면 '0'으로 결정하는 함수로, f로 표기한다.
이 함수를 이용해서 컴퓨터로 집합 연산을 빠르게 할 수 있다고 한다.
전체집합 U가 {a, b, c, d, e, f, ......}이라면 {a b c d e f ........ }와 같이 sequence로 나열하고,
부분집합 A에 어떤 원소가 속한다면 그 값을 1로, 속하지 않는다면 0으로 표기해 열을 만든다.
가령 A={b,d,e}라면 a 자리에 0, b 자리에 1을 넣는 식으로 아래와 같이 만들면 된다.
{0, 1, 0, 1, 1, 0 ......}
이런 식으로 0과 1로만 표현되는 Binary sequence를 만들면 컴퓨터에서 알아보기 쉽게 된다.
예를 들어,
부분집합 A : 1 1 0 0 0 0
부분집합 B : 0 1 0 1 0 1 로 표시될 때, 두 집합을 쉽게 비교해 and, or 연산을 할 수 있다.
and 연산을 하면 A∩B, or 연산을 하면 A∪B이 된다.
이런 식으로 characteristic function을 이용하면 일일히 비교하지 않아도 되고
2진수를 이용하는 컴퓨터에서도 빠르게 처리할 수 있다.
감사합니다.
답글삭제