Hyun's Wonderwall

전. 단일 셀 WLAN엑세스포인트가 Ethernet switch에 연결되어있고, 이더넷 스위치는 다른 이더넷 스위치에 합쳐지거나 bridge/router/switch로 연결될 수 있음.CM: 제어 모드, UM: 사용자 모드 다중 셀 WLAN같은 주파수대역 쓰면 interference. 주파수를 잘 정해서 써야함.- 여러 CM들이 Ethernet Switch에 연결됨.  Ad Hoc WLAN: central AP가 없음.  Wireless LAN에서 중요한 것들: throughput, 하나의 ap에 몇개의 노드 연결할 수 있는지, 백본 LAN에 연결, 얼마만큼 커버? 배터리? 전송? 보안?  옆에 있는 타 네트워크와의 operation은 어떤지. 라이센스 FREE이다. handoff/roaming 필요. ..

9. Wide Area Networks (WAN)10-11. Cellular Wireless Networks12-13. Local Area Networks (LAN)13-14. Ethernet14. Wireless LANS (Wifi 등) 이중 Ethernet부터 타이핑으로 정리한다.Ethernet Links by SpeedEthernet은 유선 연결이다.다양한 capacity - High Throughput 내는 것들이 많이 사용된다. Traditional Ethernet* 가장 이른 방식은 ALOHA - station은 아무떄나 프레임을 보낼 수 있었다. 동시에 보내면 충돌 발생. 재전송 전에 랜덤한 시간만큼 기다린다.* slotted ALOHA: time slot이 있는 ALOHA. 유용성 증가 C..

Accessing SQL from a Programming Language* DB 프로그래머가 general-purpose programming language를 써야 하는 이유1. SQL은 범용 프로그래밍 언어가 아니라 모든 쿼리를 표현할 수 없다.2. Non-declarative actions 은 sql로 수행될 수 없다.* two approaches to accessing SQL from a general-purpose programming language(1) A general-purpose program - can connect to and communicate with a database server using a collection of functions (ex. JDBC)(2) Embedd..

Joined Relations* Join operations는 두 개의 관계를 취하고 결과적으로 다른 관계를 반환.* join 연산은 두 관계의 튜플을 (어떤 조건하에서) 매치하는 카티젼곱이다. 또한 조인 결과 존재하는 속성들을 나타낸다.* join 연산은 from 절 안에 subquery expressions로 쓰인다. // FROM (... join ...)[3가지 조인 종류] (1) Natural join, (2) Inner join, (3) Outer join 1. Natural Join in SQL* natural join은 조인하는 테이블들의 모든 속성에 대해 동일한 속성(컬럼)이 존재하면 결과값에 하나만 남긴다.* 두 테이블 간 동일 이름, 동일 데이터 타입인 컬럼을 찾아서 조인 조건으로 설..

기말고사 범위 정리 Where Clause Predicates* SQL은 "between" 비교 연산자를 포함한다  ex. select * from i where salary between 90000 and 100000* 튜플 간 비교 -  select * from instructor i, teaches t where (i.ID, dept_name) = (teaches.ID, 'Biology'); Set Operations* A or B 찾기: 합집합. (select c_id from section where sem='Fall' and year=2017) union (select c_id from section  where sem='Spring' and year=2018)* A and B 찾기: 교집합...

힙 정렬- 최악: O(nlgn)- 제자리 정렬.- Heap 자료구조 특징- Heapify(), BuildingHeap(), HeapSort()- 우선순위 큐 Heap 자료구조- 힙은 완전이진트리 (맨 마지막 level 제외 꽉 차있는 이진 트리)  - 트리는 무조건 부모/자식 단일 연결. 상향: 부모, 하향: 자식.- 배열로 구현된다. (노드에 1번부터 번호 붙어있. 삽입 순서=배열 인덱스. A[0] 안쓰는 경우로 설명함.)- root 노드 A[1]- i번째 노드 A[i]: 부모 노드 A[i/2], 왼쪽 자식 노드 A[2i], 오른쪽 자식 노드 A[2i+1] Heap 용어- 노드의 height: 리프부터 노드까지의 간선 개수- 트리의 height: 루트노드의 높이- 노드의 ..

재귀적인 탐색. Binary Search: (1) 분할 (2) 정복 (3) 결합 - 피보나치 수열 Binary Search Tree: 문제는 하나, 부분 문제들로 잘려진다. - 매 단계마다 찾는 key값과 중간값이 같은지 본다. (상수번 반복이라 Θ(1)) - (1) 같 = stop (2) 작 = 왼 sub arr, (3) 큼 = 오 sub arr - 시간복잡도 Θ(lgn) BST의 점화식 T(n) = T(n/2) + Θ(1) - 부분 문제의 개수 1개므로 a=1. - 부분 문제의 크기 n/2이므로 b=2 - 결합의 시간복잡도 Θ(1) 마스터정리 case 2. Θ(lgn) # 수도 코드 BinarySearch(A[1..N], value) { if (N == 0) return -1; // not found..

4-1. Recurrence 점화식 분할정복기법1. 분할, 2. 정복, 3. 결합 T(n) = { 1  // n = 1 (base case)             T(n-1) + 1 // n > 1 (recursion case)점화식의 해: T(n) = n T(n) = { 1 // n =1              2T(n/2) + n // n > 1점화식의 해: T(n) = nlgn + n 팩토리얼 예시 점화식의 관심사는 계산비용이다.T(n) = aT(n/b) + D(n) + C(n)* a개의 부분문제 (크기 n/b)* D(n): 분할하는 비용* C(n): 부분문제들의 답을 다시 결합하는 비용재귀적 알고리즘들은 점화식으로 표현될 수 있다. 점화식을 푸는 3가지 방법..

Asymptotic Analysis 점근적 분석- Order of growth가 관심사.- 이론적으로 수행 시간을 분석: n에 대한 함수로 알아낸다. 최고차항이 결정.- 시간복잡도 비교: 1  Asymptotic Notations 점근적 표기- Big-Oh, Big-Omega, Theta, small-oh, small-omega Big O: f(n) = O(g(n))이면 g(n)은 f(n)의 상한. upper bound.small o: f(n) = o(g(n))이면 f(n)은 g(n)보다 느리다Big Ω: f(n) = Ω(g(n))이면 g(n)은 f(n)의 하한. lower bound.small ω: f(n) = ω(g(n)) 이면 f(n)은 g(n)보다 빠르다.Theta Θ: f(..

재귀적 알고리즘분할 정복의 핵심 아이디어- 큰 문제를 작은 문제들로 분할한다. (상수 비율로) 상수나 변수로 - 각 작은 문제들을 재귀적으로/명시적으로 푼다- 작은 문제들을 결합하여 처음 문제를 푼다. Merge Sort 합병정렬MERGE-SORT A[1..n]    1. If n=1, done    2 .Recursively sort A[1.. ⌈n/2⌉] and A[⌈n/2⌉+1..n]    3. Merge the 2 sorted listsKey Subroutine: MERGE (결합 단계) Merge 합병정렬 수도 코드MERGE(A,p,q,r) n1 = q - p + 1 # 왼쪽 부분리스트 원소의 개수 n2 = r - q # 오른쪽 부분리스트 원소의 개수 ..