집합(Set)
집합의 개념
- 집합에 속하는 각 객체는 많아야 한 번 그 집합에 나타난다.
- S1이 S2와 완전히 같음을 증명하기 위해서는 S1이 S2에 포함되며, S2가 S1에 포함됨을, 즉 두가지를 증명하면 된다.
카테시안 곱(Cartesian product)
카테시안 곱은 a∈A와 b∈B의 모든 쌍 (a,b)으로 이루어진 집합이다.
예로 A = {1,2,3} , B = {4,5,6}에 대한 카테시안 곱은 다음과 같다.
{(1,4), (1,5), (1,6), (2,4) .... (3,5), (3,6)}
유한집합인 A와 B의 카테시안 곱 크기는 12이며 |A x B|로 표현될 수 있다.
함수
함수는 가능한 입력 집합 D의 각 원소에 대해 가능한 출력을 할당하는 규칙이다.
출력은 함수에 의한 입력의 상(image)이고, 입력은 출력의 원상(pre-image)이다. 가능한 입력 집합 D는 함수의 정의역(domain)이다.
함수 f에 대해 , f에 의한 q의 상(함수값)을 f(q)로 나타낸다. 만약 r = f(q)이면 q는 f에 의해 r로 매핑된다고 한다. (문장에 익숙해질 것)
정의역 : 가능한 입력 집합, image, 숫자들의 쌍이 될 수 있음
공역 : 함수값이 선택되는 집합
치역 : 모든 정의역 원소들에 대한 함수값들의 집합, 공역의 원소들 중 실제로 함수값이 되는 공역 원소들의 집합
- 코사인 함수의 경우 공역은 실수전체가 될 수 있지만, 치역은 실수의 -1~1 범위가 된다.
함수, 프로시저, 계산 문제
- 프로시저는 계산 절차에 대한 정확한 기술이다.(표현이 이해안가) 이것은 입력을 받아들여 출력을 생성한다.
프로시저와 함수의 다른점
- 프로시저와 달리 함수와 계산 문제는 입력을 사용하여 출력을 어떻게 계산하는지에 대한 정보를 주지 않는다.
- 때로는 동일한 프로시저가 다른 함수를 위해 사용될 수 있다.
- 함수와 달리 계산문제는 모든 입력에 대해 하나의 유일한 출력을 명시할 필요가 없다.
- 계산 문제(computational problem)은 프로시저가 필요할 수도 있는 입력-출력에 대한 사양이다.
함수(계산문제)는 입력과 결과의 모든 경우의 수가 나타나있는 집합이다. 입력에 대해 출력이 발생하는 원리에 대해서는 나타나있지 않다. 그 원리는 여러가지 일 수 있으며, 그 각각의 원리를 프로시저라고 한다.
a personal blog