대학수업/이산수학

# 이항 정리 # 파스칼 방정식 # 파스칼 삼각형 # 반복을 허용하는 순열 반복이 허용되는 경우, n개를 r개 뽑는 것 # 반복을 허용하는 조합 원소를 구분하기 위한 칸막이 수 = n-1, # 구별할 수없는 객체의 순열 따로따로 C를 구해서 곱한다. 들어갈 수 있는 칸은 앞의 경우의 수를 고려하면 점점 줄어든다. # 객체를 상자에 분배하기 많은 계수 문제들은 객체들을 상자에 넣는 방법의 수를 세는 것으로 풀 수 있다. # 순열 만들기 사전순 정렬 : 앞에서부터 작은 숫자나 먼저 오는 알파벳이 앞에 온다. # 조합 만들기 규칙이 있다. 뒤에 것이 앞에 것보다 무조건 커야한다는 규칙을 만족시키려면 순열과는 다르게 구해야 한다.

계수의 개념 계수란 특정 성질을 갖는 사물의 수를 세는 것을 말한다. 순열 조합을 하기 위해 사용한다. # 곱셈 법칙 하나의 과정이 여러 개의 독립적인 작업들로 구성되어 있을 때 적용할 수 있다. # 덧셈 법칙 겹치지 않고, 여러 가지의 방법 중 하나의 방법으로 수행할 수 있을 때 # 뺄셈 법칙 겹치는 것 빼는 것. # 나누셈 법칙 공통된 개수가 있을 때 나눌 수 있다. # 트리 도표 # 비둘기집 원리 비둘기집이 19개인데 20마리의 비둘기가 오면 적어도 한 집에는 적어도 1집에는 2마리가 들어간다. # 순열 순서 있게 나열한다. 따라서 순서가 중요하다 # 조합 순서와 무관하게 원소들을 선택하는 방법

# 단순 그래프 한 쌍의 정점 사이에 많아도 하나의 연결선으로 이루어진, 우리가 통상 다루는 그래프로서 루프가 없는 그래프를 말한다. # 멀티 그래프 단순 그래프의 확장으로서 한 쌍의 꼭지점 사이에 연결선 개수의 제한이 없는 일반적인 그래프를 말한다 # 인접 리스트 (adjacency list) 다중 모서리를 갖지 않는 그래프를 표현하는 여러가지 방법 중 하나이다. 인접리스트는 각 꼭지점에 인접한 꼭지점들을 모두 나열하는 것을 말한다. # 동형 그래프(isomorphism of graphs) 위상이 다르더라도 대응되는 점이 있으면 동형이라 할 수 있다. # 오일러 순환 그래프 𝐺의 오일러 순환(Euler circuit)은 𝐺의 모든 모서리를 포함하는 단순 순환이다. # 해밀턴 경로 해밀턴 경로란 그래프에..

그래프의 용어 # 인접하다 비방향성 그래프 G에서 두 ㄲㄱ지점 u와 v가 G의 모서리의 끝점이라면 u와 v는 인접한다(adjacent) 또는 이웃한다(neighbor)고 한다. # 붙어있다 e가 {u,v{와 관련되면, 모서리 e는 꼭지점 u와 v에 붙어있다(incident)라고 한다. 모서리 e는 u와 v를 연결한다(connect)라고 한다. 꼭지점 u와 v는 {u,v}와 연관된 모서리의 끝점(end point)들이라고 부른다. # 이웃관계(neighborhood) 그래프 𝐺 = (𝑉, 𝐸)의 꼭지점 𝑣의 모든 이웃 (neighbor)들의 집합을 𝑁(𝑣)로 표기하고 𝑣의 이웃관계 (neighborhood) 라 고 한다. 𝐴가 𝑉의 부분집합이라면 𝑁(𝐴)는 𝐴안의 각각의 꼭지점들에 인접한 모든 꼭지점들의 ..

관계(Relation) A와 B를 집합이라고 하자. A에서 B로의 이항관계(binary relation from A to B)는 두 집합의 곱집합 A x B의 부분집합이다. # 관계와 함수 집합 A에서 집합 B로의 함수 f는 A의 각 원소가 B의 원소 하나에 연결된다. A에서 B로의 관계 R은 두 집합 원소 사이의 일대다 관계로 표현할 수 있다. # 역관계 집합 A에 B로의 관계 R이 있을 때, B에서 A로의 관계를 R에 대한 역관계라고 한다. # 관계 행렬(Relation Matrix) 부울 행렬을 이용하는 방법으로서, 관계 행렬은 집합 A에서 집합 B으로 가는 관계 R에 대한 n x m 행렬로 정의할 수 있다. # 반사관계 집합 A에 대한 관계 R이 A에 속한 a들에 대해 R에 속한 (a,a)가 되면..

소인수 분해의 유일성 : (별 3개)m이 양의 정수이고, a,b,c를 정수라 하자. 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚)이고 gcd 𝑐, 𝑚 = 1이면 𝑎 ≡ 𝑏 mod 𝑚 . 베주의 정리 : 시험 중국인의 나머지 정리 : 만약 선형합동 시스템이 주어져 있고, 나누는 수가 쌍으로 서로소라면, 이 수들의 곱으로 나눈 나머지 시스템은 유일한 해를 가진다. 시험문제에 나온다.(예제 4번) 페르마의 작은 정리 : 𝑝가 소수이고 𝑎가 𝑝로 나눌 수 없는 정수이면 𝑎^(𝑝−1) ≡ 1 mod 𝑝 이다. 또, 모든 정수 𝑎에 대하여 𝑎 ^𝑝 ≡ 𝑎 mod 𝑝 이다. 시험 의사소수(pseudoprime) : b가 양의 정수라 하자. 만약 n이 양의 합성수이고 b^(n-1) 1(mod n)이면, n을 b를 밑으로 하는 의사소수라..

정수의 표현 : 우리는 일상생활에서 10진법을 이용하여 정수를 표현한다. 하지만 컴퓨터는 연산할 때 2진법을 사용하고, 문자나 숫자 등을 표현할 때 8진법 또는 16진법을 사용한다. 정수 n을 위의 그림처럼 표현한 것을 n의 밑 b 전개(base b expansion of n)라 한다. 2진수 곱셈 : 10진수가 10의 자리마다 들여쓰기를 하는 것처럼, 2진수는 2의 자리마다 들여쓰기한다. 소수 : 1보다 큰 모든 정수는 최소한 두 정수(1과 자기 자신)로 나누어 떨어진다. 정확히 두 개의 서로 다른 양의 정수가 약수인 양의 정수를 소수(prime)라고 한다. 대수학의 기본 정리 : 1보다 큰 모든 정수는 소수이거나, 둘 이상의 소수의 곱으로 표현할 수 있다. 소수 판별법 : 만약 n이 합성수라면, n의..

주대각선 : 파란색으로 표시된 부분의 성분은 행렬 A의 주대각선 상에 있다. 대각합 : 주대각선 위 모든 성분들을 대각항이라 하고, 대각항들의 합을 대각합이라고 한다. 정방행렬 A의 대각합은 tr(A) 또는 trace(A)로 표기한다. 행렬의 대각합은 행과 열 번호가 같은 성분들의 합과 같다. 영행렬(Zero matrix) : 성분이 모두 0인 행렬 모든 i,j에 대하여 a(ij) = 0인 행렬을 말하며, 간단히 볼드체의 O이라고 표기한다. 교대 행렬(Skewed-symmetric matrix) : 전치행렬에 (-)를 붙인 n x n 행렬을 교대행렬이라고 한다. 삼각 행렬(Triangular matrix) : 상부삼각행렬(upper triangular matrix) : 주대각선 아래에 있는 모든 항들이 ..