中庸 中庸

시스템 프로그래밍 수업의 3번째 Lab인 Shell Lab을 수행하기 위한 기초 지식을 정리하기 위해 작성한 글입니다. 먼저, 이 장에서 사용될 용어들에 대한 정의부터 알아봅시다. 제어흐름 (flow of control) 제어흐름이란, CPU는 한 번에 한 가지 명령(Instruction)을 처리하는데, 이 Instruction의 순차적 처리를 flow of control이라고 합니다. BombLab을 수행하신 분들은 아시겠지만, 컴퓨터는 Assembly 수준에서 순차적으로 명령어들을 처리하다가 function을 call해야 한다거나, Branch 하는 등의 명령을 만나면 current Instruction 수행 후 잠시 다른 주소로 넘어가 subroutine 명령을 수행하고 다시 돌아와 next ins..

Undirected Graph에서는 Connected Component를 구하려면 아무 Vertex나 잡고 DFS를 수행한 결과 생성되는 DFS Tree 가 Connected Component 였다. (Definition of Connected Component of Graph G : G의 maximal 한 connected subgraph) Directed Graph에서는 Connected를 Strongly Connected로 정의하는 것이 일반적이다. 그럼 Strongly Connected란 무엇일까? Definition of Strongly Connected in Directed Graph Directed Graph G에서 G에 속한 서로 다른 두 vertex v, u에 대하여 path v to u..

Articulation Point (단절점)을 이용하여 Biconnected Component (이중 연결 요소) 을 어떻게 찾을 수 있을까? 먼저, Biconnected Component의 정의를 살펴보자 Definition of Biconnected Component G' of G : Graph G의 maximal Biconnected Subgraph 1) Maximal 해야하고 2) Biconnected여야 한다. Key Property : G의 Biconnected Component 는 G의 Edge들을 Partitioning할 수 있으며 각각의 Biconnected는 오직 한 의 Articulation Point 만을 공유한다. proof Contradiction. 만약 Graph G의 서로 다..

DFS Tree의 성질을 이용하여 Articulation Point를 찾기 DFS Tree의 성질과 Articulation Point(단절점)의 정의를 활용하여 Graph에서 Articulation Point(단절점)를 찾아보자. Definition of Articulation Point 단절점의 정의 : 어떤 Graph G에 속하는 vertex v에 대하여 vertex v와 vertex v와 incident한(edge의 구성요소로 v를 가지고 있는) edge를 G에서 제거했을 때, G가 disconnected 된다면 vertex v는 G의 Articulation Point가 된다, *Definition of Connected G : G에 속하는 임의의 vertex v, w에 대하여 v에서 w가 reac..