chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.2 Set Operations Union 합집합 표기: A ∪ B Example: What is {1,2,3} ∪ {3, 4, 5}? Solution: {1,2,3,4,5} Intersection 교집합 표기: A ∪ B 만약 교집합이 존재하지 않는다면, A와 B는 disjoint되었다고 말한다. Example: What is {1,2,3} ∩ {3,4,5} ? Solution: {3} Example: What is {1,2,3} ∩ {4,5,6} ? Solution: ∅ Complement 여집합 U - A (전체집합에서 A를 제외한 나머지) Ā(or Ac) = {..

chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1 Sets 집합 Sets 집합은 순서가 없는(unordered) object들의 모임이다. ex. 반의 학생들 / 방의 의자들 집합의 object들을 elements(원소), 또는 집합의 members(멤버)라 칭한다. 집합은 이러한 element들을 포함(contain)하고 있다. a ∈ A : a는 집합 A의 element이다. a ∉ A : a는 집합 A의 element가 아니다. Describing a Set: 원소나열법 S = {a,b,c,d} 순서는 중요하지 않다. ☞ S = {a,b,c,d} = {b,c,a,d} 중복 멤버는 허용하지 않는다. ☞ S =..

chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Equivalences in Predicate Logic predicates(술어)와 quantifiers(한정자)가 포함된 문장은 동일한 진리 값을 갖는 경우에만 논리적으로 동일하다. - 이 statements(진술)로 대체되는 모든 predicate에 대하여 - 표현식의 변수에 사용되는 담론의 모든 domain에 대해 표기법 S ≡ T: S와 T가 논리적으로 동일하다. Example: ∀x¬¬S(x) ≡ ∀xS(x) Thinking about Quantifiers as Conjunctions and Disjunctions Conjunctions: ∧ Disjuncti..

chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Quantifiers quantifiers(한정자): all과 some를 포함한 영어 단어의 의미를 표현하기 위해 필요하다. - “All men are Mortal.” - “Some cats do not have fur.” 가장 중요한 두 가지 한정자는 다음과 같다. - 전체 한정자(Universal Quantifier), “For all,” symbol: ∀ - 존재 한정자(Existential Quantifier), “There exists,” symbol: ∃ ∀xP(x) (☞모든 x에 대해 P(x)) 와 ∃xP(x) (☞P(x)인 x가 존재) 와 같이 사용한다. ..

chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Propositional Logic Not Enough "모든 사람은 죽는다." "소크라테스는 남자다." ☞ "소크라테스는 죽는다" 명제 논리(Propositional Logic)로는 이러한 추론을 나타낼 수 없다. 따라서 사물, 그 속성, 그리고 그 관계에 대해 말하는 언어가 따로 필요하다. Introducing Predicate Logic 술어논리 도입 술어 논리는 다음과 같은 새로운 기능을 사용한다. 변수(Variables): x, y, z 술어(Predicates): P(x), M(x) ☞술어논리에서는 변수가 들어간 형태를 허용. 명제 논리의 논리식은 변수를 포함..

TCP: Transmission Control Protocol 3. A TCP Connection Connection establishment using three-way handshake data 전송 전 연결 setup 과정. 해당 과정이 끝나야 버퍼가 생성되고 data 전송이 가능하다. 서버는 클라이언트보다 먼저 실행해서 클라이언트의 연결 요청을 대기하고 있어야 한다. 순서 1. 클라이언트는 Control field의 SYN에 1을 셋팅해 연결요청 패킷임을 명시한 뒤 해당 패킷을 서버에게 보내 연결을 요청한다. (seq: 8000- 랜덤 번호. SYN 패킷이 잘 도착했는지 확인하는 역할) 2. 서버는 ACK을 클라이언트에게 전송해 연결요청을 허가(SYN에 대한 응답)한다. 동시에 SYN을 클라이언트..

TCP: Transmission Control Protocol 3. Segment TCP segment format TCP의 헤더 크기는 기본 20byte ~ 60byte이다. 헤더의 크기가 유동적이기 때문에 헤더 안에 어디까지가 헤더이고 어디부터 data인지 표시를 해주어야 한다. 즉, 헤더의 길이를 나타내 주어야 한다. HLEN 4bits 헤더의 길이를 나타낸다. 4bits로는 1111(2) 즉, 10진수로 15까지 표현할 수 있는데, 헤더의 길이는 최대 60byte까지 나타날 수 있기 때문에 이진수로 60을 나타내려면 111100(2) 총 6bits가 필요하다. 따라서 4bits로 60을 나타내기 위해 해당 수에 ÷4를 한다. ex1. HLEN = 60(10) = 111100(2), 111100(2..

1. Analyzing Algorithms and Problems: Principles and Examples 1-3. Classifying Functions by Their Asymptotic Growth Rates 점근적 증가율에 따른 함수 분류 Clasifying Functions asymptotic growth rate점근적 증가율, asymptotic order점근적 순서 또는 order of functions함수 순서 asymptotic: input size n이 충분히 커짐을 뜻함 n이 충분히 커졌을 때 함수의 증가율 상수 인자와 small input을 무시하는 함수 비교 및 분류. The Sets big oh O(g), big thetaθ(g), big omega Ω(g) f와 g가 음이 ..

chapter 1. The Foundations: Logic and Proofs 1.3 Propositional Equivalences 명제 동치(section 1.3) Tautologies, Contradictions, and Contingencies tautology : 언제나 true 값을 갖는 명제(항진 명제) ex. p ∨¬p contradiction : 언제나 false 값을 갖는 명제(모순 명제) ex. p ∧¬p contingency : p와 같이 true가 되기도 하고 false가 되기도 하는 명제 Logically Equivalent 만약 *p ↔ q가 항진명제라면, 두 개의 결합 명제 p와 q는 논리적으로 동치이다. 이를 p ⇔ q 또는 p ≡ q 로 나타낸다. 진리표에서 각 열의 값..