Hyun's Wonderwall

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 # 오른쪽 부분리스트 원소의 개수 ..

1단원알고리즘 과목에서 공부할 내용- 알고리즘 표현: 문제를 정확하고 추상적으로 정의하는 것, 알고리즘을 수도코드로 나타내는 것- 알고리즘 유효성: 알고리즘이 옳다는 것을 증명- 알고리즘 분석: 시, 공간 복잡도.- 알고리즘 설계: 고전적인 알고리즘. 메타 알고리즘. 어떤 상황에 사용? 알고리즘이란?- 절차의 순서. 주어진 문제에 대해, 조건 만족 위해. 입력. 출력. 자료구조와 연관. 알고리즘 분석- 성능과 리소스 사용량 중요. 그외에 정확성. 간결성. 신뢰성 등.. 왜 알고리즘과 성능을 공부?- 확장성 이해 도와줌. 실행 가능/불가능 알수있. 성능이 가치판단의 기준이 됨. 등2단원Pseudocode: 알고리즘 표현을 위해 설계되었음. 컴파일되지는 않음. 삽입정렬 In..

application 계층에서는: message transport 계층에서는: segment network 계층에서는: datagram, packet link 계층에서는: frame Internet Protocol Stack 중 Data Link 레이어 (data transfer) Network Access/Data Link: 프로토콜은 Ethernet, WiFi, ATM, frame relay Data Link Protocols Frame이 관심대상. Physical Layer의 헤더를 뗀 (Data layer의 헤더까지만) Data Links Services - Framing(프레임 잘 나눴고 빠진거 뭔지 확인) - Error control - Flow control (window 정해놓고~) - M..

Types of Errors 에러: TX와 RX 사이에 bit이 바뀐 것 - Single bit errors: 1개 bit가 바뀌고 주변에 영향x(isolated). white notse로 인해 발생할 수 있음. - Burst errors: B 비트의 연속 시퀀스(첫 비트와 마지막 비트 및 그 중간 임의의 비트가 오류). 임펄스 노이즈 또는 모바일 무선 환경의 fading으로 발생 가능. 데이터 전송 속도가 높을수록 burst error의 영향이 커진다. (특정 시간동안 에러가 발생했을 때 깨지는 bit 수가 많음) (예시 그림을 보면 burst error of length B=10) Error Control • 디지털 전송 시스템에서 에러가 발생한다. BER: 에러 발생 확률. - 구리선의 BER=10..

예제: Maximum Data Rate Telephone line: 주파수 범위 300~3300Hz. 대역폭: 3000Hz. - Signal-to-noise ratio: 3162 - 이때 이론적으로 highedst data rate = C를 구하면 된다. Encoding vs Modulation Physical Layer의 핵심 두 요소: Encoding & Modulation (데이터: 아날로그/디지털 상관x) - Encoding(인코딩): 데이터를 디지털 신호로 변환 (통신 channel을 통해 전송할 수 있는 포맷) - Modulation(변조): 데이터를 아날로그 신호로 변환 - 인코딩된 데이터를 운반하기 위해 carrier signal을 사용 (아날로그 신호에 싣기 위해. 주파수 fc로 carr..

~ week 4-2 ~ Summary Guided transmission media Wireless transmission Wireless propagation Line-of-sight transmission Data Rate와 Distance를 결정하는 요인들 Bandwidth Pr가 Pt *1/(d^2*f^2)에 비례 (Pr = 받은, Pt = 보낸) Transmission impairments impairments, attenuation, Interference - 다른 주파수들이 noise가 되는 등 Number of receivers - 받는 사람 많으면 감쇄됨 Electromagnetic Spectrum of Telecommunications wavelength = vt = v/f 다양하다 P..

~ week 3-2 후반, week 4-1 ~ Internet Protocol Stack Physical layer: bits on the wire. Transmission of bit stream. Specifies medium. signal encoding technique. data rate. bandwidth. physical connector. 사례: Twisted pair, optical fiber, satellite, terrestrial microwave Encapsulation analog 신호로 전송됨. source. direct link. 아날로그 디지털 변환 Physical Layer: Data Transmission Transmitter: medium에 전송하기 최적화된 form인..

~ week 3-1, 3-2 중반까지 ~ Web and HTTP 웹 페이지는 objects로 이루어져있다. 객체는 HTML 파일, 이미지 등이 될 수 있다. 웹 페이지는 several referenced objects??, each addressable by a URL를 포함하는 base HTML-file로 구성되어있다. host name(호스트 이름. 주소) / path name(계층적 구조) HTTP overview HTTP: Hypertext Transfer Protocol. 웹의 5계층 프로토콜. client-server model client: 브라우저. HTTP 요청 보내며, 받고 웹 객체를 보여줌. server: 웹 서버. HTTP 프로토콜을 사용해 객체를 응답으로 보냄. HTTP의 특징 1..

~ Week 2-1의 Protocol부터 Week 2-2 끝까지 ~ Protocol Layers & Reference Models Networks는 많은 조각들로 이루어져서 복잡하다. -> 어떻게 조직? 비행기 여행의 예시 비행기 탑승 과정과 내리는 과정이 서로 대칭적임. 여러 서비스들 존재 -> layers. 각 레이어는 service를 제공한다. (독자적인 계층의 action을 통해. 하위 계층에서 제공되는 서비스에 의존.) 왜 Layering? 복잡한 시스템 다루기: 명시적인 구조를 통해 복잡한 시스템 조각들을 식별하고 관계를 맺을 수 있다. (layered reference model) 모듈화로 시스템의 유지보수, 업데이트 용이 (계층의 서비스 구현 변경 -> 나머지 부분에 영향 x) Intern..