기본
induktion 구조
- induktionsbasis : 만족하는 가장 작은 수 찾기 | 여러개 가능
- induktionsschritt : n beliebig fixiert
-- induktionsannahme : n 에 대해 만족한다
-- induktionsbehauptung : n+1에 대해 만족하냐? | 여러개라면 그 다음수
-- beweis der induktionsbehauptung : 증명하기
- 부등호라면 A > x > B 이렇게 가운데 들어갈 수 하나를 정하고 비교
(예를 들면 A식을 통해서 X를 세우고 x가 B보다 크다는거 보여주면됨.)
Mengen & Function
알파벳 집합으로 표현하기
relation
representationsystem
동치관계 예시 모음.
automorpisim
바꿧을 때 이웃이 같도록. 갯수 뿐 아니라 진짜 이웃이.
그래프
*중요!!! grad sequence 가 그래프? 실현가능?
- Grad 합이 짝수인가? (홀수면 불가)
- 최대 디그리는 ‘노드수-1’ 을 넘을 수 없음
- 하벨 하키미로 쳐내서 00이 나오나
연결그래프?
- degree가 젤 큰 노드랑 젤 작은 노드가 이웃 있으면 항상 주잠맨항
e >= v-1- jeder einfache Graph mit mindestens
zusammenhangend sein muss.
평면그래프
- K3,3 (3,3,3,3,3,3) 이나 K5(4444) 가 부분그래프면 X
f-e+v = 2- 연결래프일때. orf-e+v = 1+ "쭈잠맨항 컴포넨트 수 k(k는 최소 1_연결일때. 아니면 2부터)"e <= 3(v-2)- +) 평면그래프는 4개로 색칠가능!
- 니콜라스 하우스는 평면 아님.
BAUM
- blaetter 최소 2개
- e = v-1 (아니면 크라이스 생김)
- 퍼펙바움은 2^n 개 블래터.
오일러
- 연결그래프인지
- 모든 d(v)가 짝수 (kreis) 이거나 홀수 두개 (경로)
해밀턴
- 그래프 실현여부부터 판단 (하키미 소거법으로!)
- ! 주의 ! 필요충분조건은 아님.
- 모든
d(v) >= |v|/2- bipartit 그래프면 O
로직
논리 연산자
- A
->B :A가 0orB가 1일때 true =-A + Bxor: 서로 다를 때 참 =(A+B)*(-A + -B)=f<->: 서로 같을 때 참
레졸루션 예시
erfuellbarkeitsaequivalente formal
신텍스 바움에서 구역 나눠서 (변수를 먼저 준다.)
A ↔ (B ∨ C) ≡ 위에 참고.
(A ↔ (B → C)) ≡ (A ∨ B) ∧ (A ∨ ¬C) ∧ (¬A ∨ ¬B ∨ C)
(A ↔ (B ↔ C)) ≡ (A ∨ B ∨ C) ∧ (¬A ∨ B ∨ ¬C) ∧ (¬A ∨ ¬B ∨ C) ∧ (A ∨ ¬B ∨ ¬C)
DPPL
- OLR : {r} 이렇게 한 변수짜리 클라우젤
- PLR : 전체 통틀어 T/F 중 하나만 있는 변수
- case
==>> {{}} : unerfuellbar {}: erfullbar 한 경우
kombinatorik
이항정리
순열조합분할분배표
zurucklegen / reihenfolge | k ziehung aus N
- mit mit : (중복순열) m^k
- ohne mit : (순열) n^k- = n! / (n-k)!
- mit ohne : (중'조) (n+k-1 | k ) -> 몇개를 뽑나 주의해랏
- ohne ohne : (조합) (n | k)
-
injective는 순열. 정의역이 더 적음. 겹치지 않음
-
surjective는 중복조합. 정의여이 많아서 치역이 겹침
-
bijeckt는? 아마도 n!
-
다항계수 tu10.2 참고
분할 분배 표
https://j1w2k3.tistory.com/881
+) 요상한 감마 파티션 갯수 -> s(n,k) 구하는 식
조합 구할 때 크기가 같은 그룹은 더블로 세지 않게 나눠줘야 함..
각각 케이스 별로 감마i = m 이렇게 식을 쓰고 구하기 시작해야해.
-> 퍼뮤테이션은 라운듵테이블
비둘기집 원리 schubfachprinzip
x개의 사물을 y개의 용기에 나누어 담으려면 적어도 1개의 용기에는
[x/y] 크거나 같은 정수(올림)개가 담긴다. ex) 13명의 사람들 1-12월 생일 -> 적어도 한사람은 다른사람과 생일 겹친다...
알게브라
그룹 판별
1.abgeschlossen(군에 속하는 두 원소를 가지고 연산 후에도 속하냐)
2.neutrales 3.inverses
그룹 별 크기와 엑스포넨트
- 엑스포넨트 : 1. kgv(가능한 오드눙) = 모든
a^k=항등원을 만족하는 k
<Z_n, +n, 0>
- 크기 : n | 엑스포넨트 : n
<Z_n
*, *n, 1>
- 크기 : 파이(n) =
n * (1-1/p)- 엑스 : n = 1 -> 1 | n = 2 -> 1, 2, 2^k-1 | n>=3 -> 파이(n) = |G|
<S_n, 0, Id>
- 크기 : n! | 엑스 : kgv(1,2,...,n)
erzeuger / Generator
<a>이 제너레이터?? 테스트 (곱나머지군)
- 집합 크기를 구한다. 그 크기의 하세디아그램을 그린다
- a가 생성자라면 ord(a)가 크기랑 같아야 한다 -> 하세의 바로 아래 층을 확인해서 전부 1이 아니면 생성자 맞음!! 1이 나오면 ord(a)는 그 아래(1이 나온 수 이하)이다. 생성자 아님!!
ex) 3^44 mod 89 = 1?
제너레이터와 ord의 관계
어떤 g가 G의 제너레이터면 그 오드눙
ord(g) = |G| = n
=>ord(g^N/d)= dg의 집합크기/d 승의 오드눙은 d임...
ex) Z_89* 의 제너=3, ord(x) = 22 인 x를 구해라 : 3^88/22 = 3^4. ord(81)=22
제너레이터 수 구하기
덧셈베이스 군Z_n의 제너레이터 수 = 파이(n)
- 곱셉균 Z_p* 는 Z_n-1과 isomo -> 파이(n-1) 생성원
- Z_n* 은 Z_n 과 isomo -> 파이(n)개 생성원
erweiterten euklidischen Algorithmus
mod 연산
113 ^ 90 mod 47 ?
- 113은 47 모드를 구함.
- 90은 파이(47)=46 모드 구함.
=> 19^44 === 19^-2- 인버스 활용하기. (5^-1 = 19면 19의 인버스는 5)
=> 19^-2 == 5^2 == 25
