Computer Science (31) 썸네일형 리스트형 Graphs 1. Definition and terms Graph (V, E)는 set of vertices V와 set of edges E로 이루어져 있다. vertex는 하나의 node 점을 의미하고, edge는 vertex끼리 이어진 선을 의미한다. # of Vertices는 |V| # of Edges는 |E| 이다. Path : Vertices의 sequence와 n-1개의 edge로 이뤄진 집합을 의미한다. simple path : Path를 이루는 모든 vertices가 distinct한 것을 뜻한다. Cycle : $v_1$에서 시작하여 자기 자신으로 돌아오는 길이가 3 이상인 path를 뜻한다. Simple Cycle : 처음과 끝을 제외하고 모든 vertices가 distinct한 것을 뜻한다. Co.. Searching 1. Searching Ordered Arrays 만약 element가 정렬되어 있지 않다면, linear search($\Theta(n)$)가 가장 최선의 선택지이다. 정렬이 되어 있다면 Binary Search($\Theta(log n)$)이 linear search보다 낫다. 하지만 우리가 사전에 데이터의 분포와 사용 패턴을 알고 있다면 Binary Search보다도 더 좋은 Search Algorithm을 찾을 수 있다. 1-1. Jump Search k의 범위를 두고, L[0], L[k-1], L[2k-1]...을 순차적으로 방문하며 해당 값이 찾고자 하는 값 K보다 큰지 작은지를 검사한다. 해당 값이 K보다 크다면 계속해서 jump search를 진행하고 아니라면 이전의 값으로 돌아가 Line.. Internal Sorting 각각의 sorting algorithm을 비교하기 위해 # of comparison, # of swap을 기준으로 삼는다. 1. $\Theta(n^2)$ Sorting Algorithms 1-1. Insertion Sort (1) 초기에 output은 비어있다. (2) 각각의 item을 알맞은 장소에 삽입한다. static Non-Binary Tree(General Tree) 1. General Tree 1-1. Definition & Terms 노드가 child를 0 또는 1개 이상으로 가질 수 있는 tree를 뜻한다. 기본적인 term(root, parent, subtree..)들은 binary tree와 동일하다. 1-2 Preorder Traversal general tree에서도 똑같이 동작한다. Root - 1st left subtree - 2nd subtree - ... - nth subtree로 방문 static void preorder(GTNode rt){ PrintNode(rt); if(!rt.isLeaf()){ GTNode temp = rt.leftmostChild(); while(temp != null){ preorder(temp); temp = temp.. Sequential Logic Design 1. Sequential Circuits 1-1. Circuits with feedback Sequential circuit의 output은 input, 전의 input, 전의 output으로 결정된다. Logic circuit 내부에서 memory를 설치하는 것으로 이루어진다. Door combination lock은 sequential circuit의 하나의 예시이다. 1) state가 하나의 메모리이고, 2) state는 combination circuit의 아웃풋이자 다음의 인풋이 된다. 3) combination에서의 output은 저장된다. 어떻게 아웃풋과 인풋을 연결할 것인가? -> 아웃풋과 인풋을 바로 연결하면 끊임없이 값이 순환하게 된다. 1-2. Simplest Circuits with.. Lattice 1. Lattices as Partially Ordered Sets Definition 1 A partially ordered set (or poset) $\langle L, \preceq \rangle$이 만약 모든 L pair에 대해 lub와 glb를 가지면 lattice라고 부른다. lub는 보통 a+b, glb는 보통 a*b로 표시된다. ex1) L = {a, b, a+b, a*b} ex2) $x \preceq y \iff x \text{ divides } y$ ex3) $x \preceq y \iff x \subseteq y$ 모두 lattice에 해당! Theorem 1 $\langle L, \preceq \rangle$이 lattice라고 하고, x*y가 glb, x+y가 lub를 나타낼 때.. Algebra 1. Definition Definition 1 algebra는 다음의 3가지 component로 구성된다. 1) carrier라고 불리는 집합 A 2) carrier로 정의되어지는 Operators 3) carrier의 구별되는 elements, constants(추후 다루겠지마느 identity나 zero 같은 것들을 의미한다.) 2. Closed with respect to operations Definition 2 $\circ$, $\triangleright$ 를 set T의 binary, unary operation이라고 정의하자 T'를 T의 subset이라고 한다면 T'는 closed with respect to $\circ$ $\Leftarrow a,b \in T' \land a \circ .. Counting, Recurrence Relation, Infinite Sets 1. Infinite Sets 1-1. Finite Sets Definition 1 집합 A가 finite하려면 A가 empty하거나 특정 자연수 n에 대해 {1, 2, ..., n} 집합과 집합 A이 bijection 관계에 있어야 한다. n은 A의 cardinality이다. cardinality A는 |A|로 표시된다. 1-2. Pigeonhole Principle Theorem 1(Pigeonhole Principle) 만약 A와 B가 finite set이고, |A| = m, |B| = n이고, m > n이면, 함수 $f : A \rightarrow B$는 injection이 아니다. 즉 B의 image 중 둘 이상의 pre-image를 가지는 것이 무조건 있다. Example 1 Theorem :.. 이전 1 2 3 4 다음
