SSC : Strongly Connected ComponentSCC : Maximul Subset of Nodes s.t., all Nodes are Reachable from Each OtherHow do you find them?Strongly Connected라는건, 양쪽 방향으로 가는 길이 있다는 것이다.어디서 잡든 다른 노드로 가는 길이 있고, 다시 돌아오는 길이 있다. SSC의 간단한 예시는 cycle 한 노드가 여려 곳에 속하지는 않음만약, 두개의 SCC가 한 노드를 공유한다고 생각하자. -> 그러면 결국 이 두개는 한개의 SCC이다. 따라서 두 컴포넌트가 그냥 합쳐지기 때문에 한 노드를 공유하는 순간 하나의 SCC가 된다.  Let's DFSDFS를 해서 Tree 가 여러개 나왔다고 가정하..

랜덤에 대한 간단한 이야기항공 모함에 비행기가 착륙할 때, 줄에 걸려서 착륙하게 되어있다. 이 줄에 잘 걸리는 비행기와 잘 걸리지 않는 비행기가 존재하기 때문에 이 줄의 간격을 다양하게 한다. Randomized QuickSortQuicksort? pivot을 잡은 후, pivot보다 작은 값과 pivot보다 큰 값으로 나눠 생각하는 것 For any deterministic QuickSort Alogrithm there exist Classes of Inputs which the Algorithm takes O(N\(^2\)) TimeThe Average was taken over all possible inputsAll my inputs could be in the classcan you make t..

주파수 대역폭\(R = W log_2(1+SNR)\)R : data rateW : 주파수 대역폭  T = 0.1초 라는 것은 1초에 10symbol = 20bits 가 전송된다는 것이다 (QPSK 기준)T= 0.01초라는 것은 1초에 100symbol = 200bits가 전송되느다는 것이다.1/T가 주파수 대역이 된다.  의미S1과 S2의 대역폭이 100Hz라는 것을 의미한다. 국가에서 기업에서 돈을 받고 주파수 대역폭을 할당해준다. 이와 같이 되어있다면, SKT에서는 10^5의 단말기가 사용할 수 있는 것이다위에는 주파수 s1, 아래는 주파수 s2를 사용한다고 하자 ( 대역폭이 100hz)위에 사람이 받은 수신된 신호는 (s2가 없다면) r = S1 + N이다. r = s1+s2 + N인데, s2가 필..

통신 시스템Bit Source모든 신호는 bit stream으로 표현한다.4 x 4로 표현된 이미지가 있다고 생각해보자16 pixels x 8 = 128 bits가 된다 Symbol mapppingbitsteam을 symbol로 매핑한다.j는 복소수이고s1 = 1+j (00)s2 = 1-j (01)s3 = -1-j (10)s4 = 1-j(11)과 같이, 위상 변화를 90씩 주어 4개 종류의 디지털 심볼로 전송하는 4진 PSK 방식이다그에 따라 128bit는 64 symbol이 된다 noise채널에서 신호 전송 중 외부 요인에 의해 신호에 추가되는 불필요한 전기신호송신단에서 수신단으로 전달할 때신호 감세fadingnoise효과가 발생함 전자 회로에서 random motion(noise)가 발생한다. (-2..

Media Access Control (MAC)two types of link - point to point- broad cast (shared wired or wireless link) - 대부분 MAC protocolschannel partitioning : TDMA(time), FDMA(frequency)Random Access : Allow collisionsOFDMA (LTE/5G)다른 시간대, 다른 주파수를 사용하기 때문에 서로 소통에 지장이 가지 않는다 TDMA는 시간만, FDMA는 주파수만 분할한 것이다결국 핵심은 user들이 충돌이 되지 않도록 서로 다른 주파수 자원을 할당하는 것이다 OFDMA에서는 현재 분할된 곳에서 single user가 해당 부분을 사용할 수 있다.random ac..

Reliable data Transferflow control : dst에서 데이터를 처리하는 속도보다 src가 더 빨리 보내지 않도록 하는 것error control error detection : retransmission 요구(ARQ) -> 패킷에서 한 비트만 에러가 발생하더라도 다 버리게 되어있음error correction : 문제가 있는 비트를 맞게 바꿔줌 (Forward Error Correction)feed back feed forwardfeed back 시스템은 다시 보낸 시도가 어떠한 시스템에 영향을 미치는데feed forward는 정방향으로만 흐름이 흐른다. 즉, 다시 되돌아가서 영향을 미치지 않음 ex)12개의 비트로 이루어진 패킷이 있다고 가정해보자101101011011에러가 발..

Routing AlgorithmRouting Algorithm : 루트를 결정하는 알고리즘 (Host-to-Host) & algorithm that finds that least cost path Graph G = (N, E)N = set of Nodes (ROUTER)E = set of Links Cost = 여러 상황을 고려하여 링크에 부여되는 값으로, 한 라우터에 많은 부담이 생기면 바뀔 수 있음cost는 물리적인 거리만 고려한 것은 아니다 라우터를 거치지 않는 것이 더 적은 cost가 드는 것은 아니다.파란색은 cost가 5, 빨간색은 cost가 4이기 때문에 결국 빨간 경로가 cost가 더 작다. c(x,y) or \(C_{xy}\) : 둘 다 x,y의 cost를 나타낸다.If (x,y) \(\..

어떤 문제가 있다4쌍의 부부가 와서 서로 악수를 하는데, 부부끼리는 악수를 하지 않는다.최소 0번 최대 6번의 악수를 할 수 있게 된다그런데, 사람들에게 악수한 횟수를 물어보니 숫자가 7개 다 나왔다.그러면 사람이 8명인데 숫자가 7명이기 때문에 무조건 겹치는 숫자가 하나 나오게 된다이때 겹치는 숫자는 무엇인가? 어딘가는 6이 있어야한다. 즉, 자신의 부부 빼고 모두 악수를 했기 때문에 6과 0은 부부이다0,6을 제외하고 3쌍의 부부만 남는다고 생각하자그럼 3쌍의 부부에게는 최소 0번 최대 4번의 악수를 할 수 있다. 이때 0,4를 또 하나의 부부로 생가각하여 없앨 수 있다.이 과정을 반복하면 1,5 2,4 3,3 이렇게 부부가 되어3이 두번 겹치는 것을 알 수 있다 이것과 Topological Sort..

BCCBiconnected Component : Connected component + Maximal = 연결된 노드에서 노드 집합을 늘릴 수 없을 때까지 늘린것Parts of Graph separated by Cut Vertices Two Nodes in a BCC has two completely different Paths connecting them : edge도 node도 겹치지 않음Meaning of "Separated" can be confusingCut vertex와 반대의 개념이라고 생각할 수 있음connected component들은 노드들은 파티션으로 나눔biconected component는 cut vertex로 나뉘며, 이 cut vertex는 중복되어 들어갈 수 있음 여전히 Cu..

Def Cut VertexRemoving a node s makes Graph DisconnectedExists x and y s.t., all paths from x to y goes through s : 노드 x, y가 있어서 x, y를 연결하는 모든 path가 s를 지나감연결된 그래프에서만 생각한다연결된 그래프에서 특정 노드를 지우면 끊어진 그래프가 될 때 그 노드를 cut vertex라고 한다G = (V,E)|V| = n, |E| = mundirected graph (=>) 노드 S를 제거하면 Connected component가 여러개 생김서로 다른 connected component 에서 x, y라는 노드를 각각 고름이러면 x, y 로 통하는 path 가 없다. 따라서 현재 s를 제거하면서 이..