mojo's Blog

We have shown previously that independent set, vertex cover, and clique are all equivalent. We now show they are all NP-complete by showing independent set is. independent set이 NP-complete 임을 보임으로써 나머지 vertex cover, clique 또한 동일하게 NP-complete 임을 확인해보도록 하자. Up to now, all reductions transformed one form of constraint into another. However, independent set is not a constraint satisfaction problem ..

Data Structures for Disjoint Sets • Partition – A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets. – Example: X = {1, 2, 3, 4, 5, 6} → { {1, 3, 5}, {2}, {4, 6} } • Disjoint-set data structure (union-find data structure) – Used to effectively manage a collection of subsets that partition a given set of elements. • Basic ope..

Parameter Passing Parameter: actual parameter, formal parameter ● 실 매개변수와 형식 매개변수는 서로 값을 주고받는다 (parameter passing) ● 여러 가지 parameter passing 방법이 있음 ○ 참조 호출(Call by reference): 포트란77 ○ 값 호출 (Call by value): C 예시) a[i] = a[j] ● 산술식 a[j]는 값을 나타내는 r-값(right value) ● a[i]는 a[j]의 값이 있는 메모리의 위치인 l-value(left value, location value)을 나타낸다. ○ l-value: 산술식이 나타내는 기억 위치 ○ r-value: 메모리에 저장될 값 Call by Value 값 ..

Concepts File : - byte 들의 단순한 선형적인 array로 정의된다. - inode number 로서 low-level 이름을 각 파일마다 가지고 있다. Directory : - 디렉토리도 파일이다. - A list of pairs. Interface : Creating a file O_CREAT flag을 사용하여 open system을 사용한다. int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR); O_CREAT : 파일을 생성 O_WRONLY : 파일이 열릴 때, 오직 write 만을 허용 O_TRUNC : 파일 사이즈를 0으로 만듬 (그러나 기존에 있던 내용물이 제거됨) Interface : Reading a..

Structural data type 기본 자료형(elementary data type) ● 하나의 이름이 하나의 자료 객체(data object)를 가진 것 ● 정수, 실수, 문자형 등 구조적 자료형(structured data type) ● 하나의 이름에 여러 개의 자료 객체가 있는 것 ● 레코드, 배열, 문자열, 집합, 트리 등 ○ 레코드, 구조체: 이질(heterogeneous)의 자료 개체들을 하나로 묶고 이름을 부여하여 하나의 자료형을 선언 ○ PL/I, 코볼, 파스칼, C, 알골 등과 같은 언어는 레코드를 사용할 수 있는데 구체적 표현은 언어마다 조금씩 다르다. Record 레코드 ADDRESS ● PERSON, STREET, CITY와 같은 그룹 항목 ● 각 항목들은 다시 하나 이상의 기본..

circuit sat Input: A Boolean circuit C Question: Is C satisfiable? Note that a Boolean circuit is a powerful enough model of computation to express any algorithm. We will show witness existence ≤ circuit sat implying circuit sat is NP-complete. We will convert an instance of (Π, x, t) of witness existence to a Boolean circuit C of polynomial size s.t. C is satisfiable if and only if there is a wit..