복습노트 복습노트

Ford-Fullkerson 알고리즘을 통해 maximum bipartite matching을 찾는데 시간 복잡도는 O(VE)가 걸렸다. 우리는 Hopcroft-Karp 알고리즘을 통해 O(√V * E)의 시간복잡도를 알아볼것이다. 2~5 번째 줄은 O(√V) 만큼 반복 3번째 줄은 O(E) 만큼 반복 먼저 maximal set of vertex-disjoint shortest M-augmenting path를 찾는 방법을 볼것이다. phase 1 : undirected 그래프인 G를 directed 버전인 GM을 형성한다. phase 2 : bfs을 통해 GM에서 directed 비순환 그래프 H를 생성한다. phase 3 : H의 전치 HT에서 dfs를 실행함으로써 maximal set of vert..

What is File System? 우리가 평소 사용하는 application은 process address space에 data를 저장할 수 있습니다. 이것이 과연 충분할까??? data의 크기는 virtual address space에 제한받고, data는 application이 사라질 때 잃게 되고, 다수의 process들은 똑같은 data에 access하기를 원할지도 모릅니다. 이를 위해 영구적인 정보들을 위한 몇가지 기준이 생겼습니다. 먼저 매우 큰 정보들을 저장할 수 있어야 합니다. 두번째로 정보는 process가 사용하는 동안 무조건 살아있어야 합니다. 세번째로 여러 process에 동시에 access할 수 있어야 합니다. 이를 해결할 수 있는 것이 File입니다. File은 논리적인 저장..

확률 분포 통계를 통해 modeling을 하고 simultaion을 거친뒤 output를 낸다. Steps in Simulation Study Definition of System Discrete and Continues System Discrete-Event Simulation 시스템 state가 시간의 event의 걸쳐 진화하는 simulation 모델 시스템의 state는 오직 event가 발생했을 때만 변한다. event들 사이에서는 시스템 state가 변하지 않는다. Continuous Simulation 시간에 지남에 따라 시스템의 state가 변화된다. 시스템은 미분 방정식의 집합에 따라 연속적으로 변화하는 변수의 도움을 받아 모델링 된다. 미분 방정식의 집합은 추상적인 수준에서 시스템을 나..

Graph G = (V, E)라고 표현 V = 정점, E = 간선 |V| = V집합의 갯수 |E| = E집합의 갯수 예를 들어 V = {1, 2, 3, 4, 5}일 때 |V| = 5 이다. n개의 정점이 있는 그래프에서 최대 간선은 n(n-1) / 2 개이다. 만약 그래프가 n개의 정점이있고 간선은 n(n-1)/2 개 있으면 완전 그래프라고 부른다. 그래프의 표현은 2가지가 있다. 1. Adjacency List 2. Adjacency Matrix Adjacency List 공간 복잡도는 O(V + E) 이다. Adjacency Matrix |V| * |V| 크기의 배열을 생성 공간 복잡도는 O(V^2) Depth First Search (DFS) 한 정점을 계속 깊이 탐색하는 알고리즘 이다. 모든 정점..

An Activity-Selection Problem activity들의 시작 시간은 s이고 끝나는 시간은 f이다. 여기서 최대 몇개의 activity들을 할 수 있을지 구하는 것이다. 예를 들어 3번째 activity는 0분에 시작해 6분에 끝난다. {3, 9, 11}을 선택하면 {0~6}, {8~11}, {12~16}의 시간들을 즐길 수 있다. 즉, 시간이 겹치지 않으면서 최대로 많은 activity를 하는 것이 목표이다. 그리디 알고리즘을 활용해 최적의 결과만을 선택하면 결국 최적의 결과를 얻을 수 있다. 최적의 경우는 구할 수 있지만, 모든 최적의 경우는 다 구할 수 없다. 그렇다면 그리디 선택을 어떻게 할것인가? 현재 시간을 기준으로 할 수 있는 끝나는 시간이 가장 빠른 활동만을 계속하는 것이다..

Motivation of Virtual Memory 프로그램을 실행하려면 메모리에 있어야 하지만, 프로그램 전체가 사용되지는 않습니다. 프로그램의 일부분만 메모리에 있어 실행되면 많은 이점을 가져올 수 있습니다. 가상 메모리란 물리 메모리로 부터 사용자 logical(가상) 메모리 분리 입니다. 즉, process 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법입니다. (= 프로그램이 실행되는데 최소한 얼만큼의 메모리가 필요한지에 집중) 나머지는 보조기억 장치, 즉 디스크에 저장되있습니다. 주요 장점 중 하나는 사용자 프로그램이 물리 메모리 보다 커져도 된다는 것입니다. 따라서 개발자들은 더이상 물리 메모리 크기에 국한받지 않고 개발할 수 있습니다. Virtual Memory > Physi..

네트워크 트래픽의 좋은(예측적) 모델은 확률적 process이다. 우리는 일반적으로 단위 시간당 byte 수(또는 패킷 또는 flow)에 대해 말한다. stochastic process(확률적 과정)은 랜덤 변수의 집합이다. Distribution Function 랜덤 변수 X가 주어지면 확률 분포 함수(PDF)로 나타낼 수 있다. f(x) = P(x) Histogram and CDFs CDF F(x) = P[X_i x] 큰 값은 통계와 성능을 지배한다. tail의 모양은 매우 중요하다. Light Tails, Heavy Tails Light tails - Exponential or faster decline = f1 (x) Heavy tails - Slower than any exponential = ..

Background Program Execution 프로그램을 실행하려면 메모리를 가져와야 합니다. user program은 실행되기 전에 몇 가지 단계를 진행됩니다. 1. Instruction fetch from memory (메모리로 부터 명령어 가져오기) 2. Instruction decode (명령어 해석) 3. Operand fetch (피연산자 가져오기) 4. Instruction execute (프로그램 실행) 5. Results may be stored back in memory (결과물 메모리에 저장) Memory Access Speed processor에 내장된 main memory와 register는 CPU가 직접 access할 수 있는 유일한 저장소 입니다. 따라서 실행되는 명령들과..