건빵의 블로그

오늘은 저녁에 놀아야 되니까, 좀 일찍 정리해보자 ㅋ Trees 트리는 Graph부분에서도 나왔지만 자료구조에서도 매우 중요하게 다뤄지는 중요한 개념이라 그런지 따로 언급된다. Graph부분에서는 트리는 acyclic connected graph라고 하였다. 또 다른 정의로써, tree는 모든 vertices의 쌍 사이에 유일한 path가 존재하는 ugraph이다. 또한 rooted tree는 지정된 root vertex를 가지고 모든 edge가 root로부터 directed away(?) 되는 트리이다. directed away는 정확한 해석은 모르겠지만 루트로의 길의 일부분이 된다? 정도로 받아들이면 될 것 같다. 이 부분에서 헷갈려야 하지 말아야 하는 것이 rooted tree와 tree이다. 우리..

어제 졸려서 못다한 정리 이어서 하기~ 이산수학에서 중점적으로 다뤄야 할 건 우리가 흔히 아는 그래프, 트리같은 것의 수학적 정의를 숙지하는 것이다. Graph undirected graph, 즉 ugraph는 edge가 2개 element의 쌍을 가지는 vertex의 subset인 경우를 말한다. 음. 즉 엣지가 set의 성질을 따르기 때문에 순서는 상관없다는 것을 의미한다. directed graph, 즉 digraph는 일반적으로 정의하는 그래프 같은 것으로써 엣지는 버텍스 간의 카티션 곱의 서브셋이다. 즉 버텍스간의 릴레이션이다. 수학적으로 표현하면, E⊆V×V 이다. 그리고 어떠한 Graph가 다이그래프일때, path는 vertices의 sequence로 정의되며 각각의 인접한 버텍스들 간에는 ..

오늘도 이산수학 공부하고 정리하기~ 중요한 것 위주로 정리하자. Relation 릴레이션은 Set 나오는 부분에서도 나왔지만 중요해서 그런지 따로 챕터가 있다. 어제 공부한 걸 정리할겸 되돌아보면 Relation은 두가지로 정의(표현)된다. 첫째는 R⊆A×B로써 표현되며 집합임을 나타내며, 둘째는 aRb 형태로 표현되며 infix binary boolean operator를 나타낸다. True or False 값을 가진다. Function 또한 앞에서 정의하였지만 Relation의 관점에서 다룬다. 함수는 (a,b)∈f일때 a에 대해 b가 하나만 존재하는 특수한 릴레이션이다. 따라서 위에서 언급했던 릴레이션의 두가지 표현방식으로 볼 때, a f b와 같이 표현하는것도 가능하다. 이 또한 T/F값을 가질 ..

2장은 기본적인 구조에 대해서 나온다. Sets 집합은 정렬되지 않은 object의 collection이다. 집합 내의 object는 element, member로 불린다. 어떠한 집합 A의 모든 멤버가 다른 집합 B의 멤버일 경우 A는 B의 부분집합이다. subset에서 equal을 제외한 것을 proper subset이라고 한다. 아.. 기호가 많은데 글로만 쓸려니 힘들다 'ㅁ' 어떠한 집합 S에 대해 |S|를 S의 cardinality 라고 하며 집합 S의 멤버의 갯수를 의미한다. 어떤 집합의 카디날리티가 유한하면, 유한집합이라고 하고.. 카디날리티가 무한하면, 무한집합이라고 한다. Power Set P(S)는 집합 S의 모든 부분집합을 원소로 가지는 특이한 집합이다. Cartesian produc..

방학들어 대학원 스터디의 본격적인 시작! 시간 날때마다 정리해 보자. Propositional Logic Proposition(명제)는 True 혹은 False 값을 가지는 문장이다. Proposition은 Proposition과 논리연산자들을 이용해서 재귀적으로도 정의된다.(negation, and, or, xor, implication 등등) 여기서 기억해둬야 할것은 p->q가 (not p) and q와 동일하다는것! 어떤 proposition이 항상 참인 것을 tautology라고 하며, 항상 거짓인 것을 contradiction, 그냥 일반적인 나머지 proposition을 contingency라 한다. 명제 p와 q에 대해서 pq 가 tautology면, p랑 q는 논리적으로 동등(logical..