[08] 이산수학(수열과 행렬)
주제 : 수열과 행렬
수열이란 정수 집합의 부분집합으로부터 집합 s로의 함수이다. (ex. 등차수열, 등비수열)
점화 관계란 앞서 나온 항들 간의 재귀적 규칙성을 이용하여 다음에 올 항들을 나타내는 것이다.
특히, 점화 관계가 효력을 나타내기 시작하는 항에 앞서서 나타나는 항을 초기 조건(initial conditions)라고 한다.
피보나치수열
점화 관계의 해 : 초기 조건이 수반된 점화 관계를 푸는 것, 또는 "해를 구하시오."라는 의미
점화 관계로부터 수열의 닫힌 공식(closed formula)라고 부르는 수열의 일반항을 구하는 것
점화 관계의 방법들:
- 반복법 : 점화 관계를 반복적으로 사용하여 해를 찾는 방법
특수한 정수 수열 : 패턴 찾기
- 같은 값이 계속 나타나는가? 즉, 같은 값이 연속해서 여러 번 나타나는가?
- 앞의 항에 일정한 값을 더하거나 수열 내에서 위치에 관련되는 어떤 값을 더하면 다음 항을 얻을 수 있는가
- 앞의 항에 일정한 값을 곱하면 다음 항을 얻을 수 있는가?
- 앞의 항들을 어떠한 일정한 방식으로 조합하면 다음 항을 얻을 수 있는가?
- 항들이 일정한 규칙성을 갖고 순환되는가?
수열의 합을 나타내기 위해 시그마(Σ)를 사용함.
행렬: 중간고사에 나온다.
행렬은 수를 사각형으로 배열한 것이다. m개의 행(row)과 n개의 열(column)을 갖는 행렬을 mxn 행렬이라 부른다.
같은 수의 행과 열을 갖는 행렬을 정방 행렬(square matrix)이라 한다.
두 행렬이 같은 쉬의 행을 갖고 같은 수의 열을 가지면서 각 원소의 위치가 같을 때, 두 행렬이 같다(equal)고 표현한다.
행렬의 이름을 쓸 때, 굵은 대문자로 쓴다.
행렬의 번호를 매길 때 행 번호가 앞에 오고 렬 번호가 뒤에 온다. (행이 가로줄, 렬이 세로줄)
행렬의 덧셈:
같은 크기의 두 행렬의 합은 해당 위치의 원소를 합해서 구할 수 있다.
두 행렬의 합은 두 행렬이 같은 수의 행과 같은 수의 열을 가질 때만 가능하다.
뻴셈도 위와 같은 방식으로 진행한다.
행렬의 곱셈:
행렬의 곱셈은 덧셈과는 다르게 행렬 A의열과 행렬 B의 행의 각 원소를 곱해서 더하는 것이다. 따라서 행렬 A가 mxn라면, 행렬 B는 nxk이어야 곱셈을 할 수 있다.
따라서 다음과 같은 경우 AB는 가능하지만 BA는 불가능하다.
항등행렬:
항등행렬은 항상 정사각형이다. 어떤 행렬에 적절한 크기의 항등행렬을 곱하면 그 행렬은 바뀌지 않는다.
전치(Transpose)행렬과 대칭(Symmetrix)행렬:
0-1행렬(Zero-one matrix):
모든 원소가 0과 1로 이루어진 행렬
0-1행렬의 부울 곱(Boolean product):
부울 곱은 일반적인 행렬의 곱셈과 유사하지만 덧셈은 ∨곱셈은 ∨로 대치된다.