TIL - 2021.09.15

Wanna be __·2021년 9월 22일
0

TIL

목록 보기
34/45
post-thumbnail

Today, I Learned

1. CE2

X

2. DB

  • 6개의 Basic operator를 바탕으로 생성하는 additional Operations.

Set-Intersection - same arity를 가지는 두 table에 대하여 교집합만 추출.

Natural-Join Operation - 두 개의 relation을 Cartesian product한 후에 같은 이름의 attribute들의 값이 같은 record들을 select실행.

Theta-Join Operation - natural join하면서 추가적인option을 명시함.

Assignment Operation - Complex query를 간단하게 할당하기 위함.

Outer-Join Operation - Natural Join을 하게 되면, 같은 값을 가진 결과만 추출되기 때문에, 그렇지 못한 tuple들은 loss됨. 따라서, Left, Right, Full 여부에 따라서 information을 모두 적으면서 표현.

  • Null value? Null과 산술연산한 모든 결과는 Null.
    값이 아직 정해지지 않은 상태.

Division Operation - 같은 Column에 대해서, 나눠주는 table의 value가 모두 포함된 것을 뽑음.
ex) student who have taken all courses in the Biology department.

Generalized Projection Operation - 일반적인 arithmatic function + 산술연산한 결과를 나타낼 때 사용.

Grouping Operation - aggregate하는 것과 같음. 필드의 속성별로 group을 지어서, 각 group별 어떤 값의 sum, min, max, averate, count등을 할 때 사용.

  • Query에서의 Deletion
    r <- r - E
    DB에서 하나의 값만 지우는 것은 불가능하기 때문에, 한 tuple을 뺀것을 저장하는 것과 같음.
  • Query에서의 Insertion
    r <- r U E
    위와 마찬가지.

3. AI

  • 여태껏 간단 요약.

Blind Search

DFS는 Fringe는 비교적 적게 발생하는데, Optimal하지 않고, Finite한 depth에서는 Complete하기는 함.
BFS는 Fringe는 비교적 많은데, Cost가 일정한 경우에 Optimal, Finite한 경우 Complete함.
UCS는 Fringe도 줄이면서, Cost가 다르더라도, Start에서 해당 node까지 비용을 최소화 하는 방향으로 진행하기 때문에, Complete하고 Optimal한 결과를 낼 수 있음.

Informed Search

위 3가지 단순한 Search는 node에서 goal state까지의 거리 혹은 비용에 대한 정보가 없는 상태에서 진행한 search들임. 그렇기 때문에, Goal까지의 방향성이 없는 결정을 하기 때문에, 살펴볼 필요가 없는 방향까지 뻗어나가는 단점이 있음.

이를 보완하는 Search가 Heuristic을 이용한 Search들임.

Greedy

g(n)을 최소화 하는 선택을 한다. Optimal하지도, Complete하지도 않음. 그저 빠른 선택을 할 뿐임.

A*

f(n) = g(n) + h(n)을 최소화 하는 선택을 한다. h(n)이 heuristic function이고, Tree 혹은 Graph의 Search에 따라서, 각 search가 complete하기 위한 h(n)의 조건이 필요함.

Admissibility - h(n)이 Optimistic 해야함.
즉 0 <= h(n) <= h*(n).

Consistent - h(a)-h(c) <= Cost(a to c). 즉, 각 path의 cost 보다 실제 node의 heuristic 값은 더 큰 차이를 보여야 함. 다시말해서, 모든 노드에 대해서 일관적으로 optimistic한 heuristic을 적용해야함. 또 다시 말하자면, f(n) 값이 path를 따라감에 따라 증가해야함. 왜냐하면, 다른길로 갔을 때 전체 경로가 줄어드는 일이 발생한다면, Graph에서의 Optimal path는 찾을 수 없기 때문.

Tree search - Admissibility가 있으면 Optimal
Graph search - Consistent가 있으면 Optimal

profile
성장하는 개발자

0개의 댓글