Processing math: 100%

본문 바로가기

전체 글

(64)

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 :..

Function 1. Function 1-1. Definition Definition 1 A와 B를 set라고 할 때,

$\forall x \in A$ 에 대해 unique한

$y \in B$ 가 있는 경우 A relation f from A to B를 function이라고 부른다.

$f \subseteq A \times B$ 이다. 모든 x에 대한 함숫값이 있어야 하고, 그 함숫값은 하나만 존재해야 한다. 1-2. Terminology f :

$A \rightarrow B$ 그리고 f(a) = b일 때, A = the domain of f B = the codomain of f b = image of a under f a = pre-image of b under f The range R = $\{b|(a, b) \in f..

Case Studies in Combinational Logic Design 1. General Design Procedure (1) Understand the problem => input과 output은 무엇인가? (2) Forbulate the problem using a suitable design representation => truth table과 waveform을 이용해서 I/O를 가시화' (3) Choose implementation target => ROM, PAL, PLA 등 어떤 게이트를 사용해서 디자인 할 것인가? (4) Follow implementation procedure => K-maps, design tool을 이용해서 implement ex) BCD to 7-Segment Display Decoder PLA를 디자인하려는 경우 Product te..

List, Stacks, and Queues 1. List 1-1. 정의 유한하고, 순서가 정해져있는 자료구조 List의 element는 위치가 정해져있다. 1-2. Implementation concept current position의 컨셉을 가지고 있다. Operation은 curr_pos에 근거해서 일어나게 된다. 1-3. Array-based List : array를 이용하여 만든 list 장점 : 설치하기/이해하기 쉽다. 빠르게 특정 위치의 element에 접근하기 쉽다. access만 하고 insert나 remove가 안되는 application의 경우 Linked list에 비해 빠르다. linked list에 비해 메모리를 적게 쓸 수도 있다.(pointer를 저장할 필요가 없기 때문에) 약점: insert와 remove에 Θ(n)..

목록 더보기

티스토리툴바