대학수업/이산수학

[17] 이산수학 ( 계수 기초_#02)

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

[16] 이산수학 ( 계수 기초 )

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

[14] 이산수학 ( 그래프의 표현)

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

[13] 이산수학 (그래프의 용어)

그래프의 용어 # 인접하다 비방향성 그래프 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) 라 고 한다. 𝐴가 𝑉의 부분집합이라면 𝑁(𝐴)는 𝐴안의 각각의 꼭지점들에 인접한 모든 꼭지점들의 ..

[12] 이산수학(관계)

관계(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)가 되면..

[11] 이산수학(합동 풀기)

소인수 분해의 유일성 : (별 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를 밑으로 하는 의사소수라..