Term

- Base case

기저 사례라고도 한다.

Recursive call에서 Terminal condition을 지정하는 경우를 말한다.

- Referential transparency/ Referential transparent function

참조적 투명성/ 참조적 투명 함수

Argument로 넘긴 입력에 대해 항상 같은 값만을 반환할 때 참조적 투명성이 있다고 한다. 함수가 이런 특징을 띄면 참조적 투명함수라고 한다.

- Mathematical exclusion(수학적 배제)

수학적 증명을 통한 탐색 공간을 배제하는 방법

- Branch & bound(가지치기, 경험적 배제라고도 함)

경험적으로 더 이상 해를 구할 수 없는 조건을 만났을 때, 탐색을 그만 두는 것.

탐색을 처음 시작할 때는 조건을 정할 수 없으나, 탐색을 진행하는 중에 조건이 설정/갱신된다.

더 탐색할 공간이 있음에도 불구하고 돌아오는 흐름을 바운딩(bounding) 또는 커팅(cutting)이라고 한다.

- 탐색기반설계

컴퓨터의 빠른 연산속도를 이용하여 짧은 시간에 가능한 해 집합을 탐색하면서 해를 구하는 기술적인 방법

- 관계기반설계

해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 효율적인 방법

1. 문제의 정의 및 상태를 함수로 정의

2. 함수들간의 관계를 점화식 혹은 이와 유사한 형태로 변환

- 수학적 귀납법

- 수학적 관점

자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립합을 증면하기 위한 수학의 증명법 중 하나

1. P(1)이 성립함을 보인다. - Basis

2. P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. - induction

- 컴퓨터 과학 관점

명제를 증명하는 방법이 아니라 문제의 입력 n에 대해 문제에서 구하는 해가 f(n)일 때, 귀납적 관계를 이용하여 f(n)을 구하는 문제해결의 방법

1. 입력값이 n인 문제의 해를 f(n)으로 정의한다. (명제 정하기)

2. f(1)을 직접 구하여 출력한다. - Basis

3. f(k)를 이미 구해두었다고 가정하고 f(k)를 통해 f(n)을 구하여 출력한다. - induction

- Scaffolding(스캐폴딩)

다양한 분야에서 다르게 해석된다.

감히 유추해보자면 "어떤 프로그램이나 알고리즘을 테스트하기 위한 작업 또는 프로그램"이라 할 수 있겠다.

- DSU

Disjoint set union

- Dynamic Table(동적표)

먼저 표의 일부를 어떤 값으로 채운 후, 나머지 칸들은 주변의 값들을 참조하여 동적으로 채워지는 표

- Graph

  1. 방향 그래프(Directed graph), 유향 그래프

각 간선이 방향이라는 속성을 갖는다. 정점 사이의 간선에 대해 방향성이 존재한다.

  2. 무향 그래프(Undirected graph)

각 간선에 방향 속성이 없는 그래프. 간선으로 연결된 인접한 두 정점에 대한 우선순위 혹은 순서가 없다.

  3.  가중치 그래프(Weighted graph)

각 간선이 가중치(weight) 속성을 갖는다. 간선 사이에 대한 가중치를 두어 경우에 따라 해석하도록 한다(도로 사이의 거리, 가격 등)

  4. 다중 그래프(Multigraph)

두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프.

  5. 단순 그래프(Simple graph)

두 정점 사이에 하나의 간선만 있는 그래프.

  6. 루트 없는 트리(Unrooted tree)

부모 자식 관계가 없을 뿐, 간선들의 연결 관계만 보면 트리와 같은 무향 그래프를 말함.

  7. 이분 그래프(Bipartite graph)

그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프.

  8. 사이클 없는 방향 그래프(DAG, Directed acyclic graph)

어떠한 정점에서 출발하더라도 자기 자신에게 돌아오는 경로(사이클)가 존재하지 않는 그래프.

  9. 의존성 그래프(Dependency graph)

각 작업을 정점으로 표현하고, 작업 간의 의존 관계를 간선으로 표현한 방향 그래프.

- Relevant to graph

  1. 단순 경로(Simple path)

한 정점을 최대 한 번만 지나는 경로. 대다수의 경우 경로라고 말하면 단순 경로로 보면 된다.

  2. 만족성 문제(Satisfiability problem, 2-SAT)

모든 정점에 대해 두 선택지 중 하나를 선택해야 하는 문제를 말한다.

  3. 희소 그래프(Sparse graph)

간선의 수가 |V|^2에 비해 훨씬 적은 그래프. |V|는 정점의 수를 말한다.

  4. 밀집 그래프(Dense graph)

간선의 수가 |V|^2에 거의 비례하는 그래프. |V|는 정점의 수를 말한다.

  5. 암시적 그래프(Implicit graph)

그래프 모델을 직접 메모리에 표현하지 않고, 간접적으로도 구현할 수 있는 그래프.

예를 들면, 2차원 배열에서 최단 경로 찾기 등이 있다.

- 오일러 회로(Eulerian circuit) : 모든 간선을 단 한 번만 방문하고, 시작점과 끝점이 같은 경로를 말한다.

- 오일러 경로(Eulerian circuit) : 모든 간선을 단 한 번만 방문하고, 시작점과 끝점이 다른 경로를 말한다.

- 해밀토니안 경로(Hamiltonian path) : 모든 정점을 정확히 한 번씩 지나는 경로를 말한다.

- 그래프 용어

1. 차수(Degree) : 한 정점에 인접한 간선의 수

2. 컴포넌트(Component)

   그래프 이론에서 Component는 일반적으로 Connected component를 말하며 두 개 이상의 정점에 대해 연결되어 있는 부분 그래프를 말한다.  때로는 최대 크기를 갖는 부분 그래프를 뜻하고 컴포넌트 개수라고 한다면 최대 크기를 갖는 부분 그래프의 개수를 말한다.

3. 진입 차수(indegree) : 특정 정점 하나에 대해 들어오는 간선을 말한다. 방향 그래프에서만 의미가 있다.

4. 진출 차수(outdegree) : 특정 정점 하나에 대해 나가는 간선을 말한다. 방향 그래프에서만 의미가 있다.

* DFS Spanning tree(DFS 스패닝 트리) : DFS를 이용하여 지나가는 간선만을 이어 만든 트리를 말한다.

* 트리 간선(tree edge) : 스패닝 트리에 포함된 간선

* 순방향 간선(forward edge) : 트리의 선조에서 자손으로 간선이 이어져 있으나 트리 간선이 아닌 것을 말한다.

* 역방향 간선(back edge) : 스패닝 트리에서 자손에서 선조로 연결되는 간선을 말한다.

* 교차 간선(cross edge) : 위의 세 가지에 어느 것도 해당되지 않는 간선을 말한다.

* 그래프의 지배 집합(Dominating set) : 각 정점이 자기 자신과 모든 인접한 정점들을 지배한다고 할 때, 그래프의 모든 정점을 지배하는 정점의 부분집합.

* 안전 간선(safe edge) : 최소 스패닝 트리를 구성할 때, 최소 스패닝 트리에 대한 루프 불변성을 유지하면서 최소 스패닝에 포함되는 간선.

* 역평행(antiparallel) 간선 : 

* 가상 출발점(supersource), 가상 도착점(supersink)

===========미정리 용어들===========

* Tournament graph

* 순환(Simple cycle)