[2021/08/29][짤막한 이야기 - 동형]

[2021/08/29][짤막한 이야기 - 동형]
“동형(Isomorphic)”이란 서로 구조가 동일한 두 대상을 의미한다.
즉 간단히 말하면 모양이 동일하다는 의미이다.
자료구조에서는 두 자료구조가 동형인지 판별하는 것도 중요한데,
예를 들어 임의의 두 그래프(Graph)가 동형인지 판별하는 것도 매우 중요하다.
프로그래밍을 접해본 바 있다면, "제어흐름 그래프(Control-Flow Graph)"를 알고 있을 것이다.
임의의 두 프로그램의 제어흐름 그래프가 동일한지 판단하는 것 또한 보안측면에서 중요하기 때문에 많이 연구되고 있다.
그러나 임의의 두 그래프의 동형 여부 판단 문제는 다항시간 내에 풀릴 수 있는지 증명된 것이 아니기 때문에, 무작정 동형 검사를 수행하는 것에는 주의하여야 한다.
그림에서의 두 그래프가 서로 동형인 그래프의 예이다.
외면을 보는 것만으로는 동형 여부 판단이 어렵기 때문에 특별한 방법을 적용해야 한다.
그것이 바로 여러분들도 잘 알고있는 순회(Traverse) 혹은 탐색(Search)이다.
[관련된 짤막한 이야기 - 시간 복잡도[2021/08/04]]
#이야기 #루니프 #알고리즘 #자료구조 #동형 #그래프 #제어흐름그래프 #다항시간

[2021/08/29][Short Story - Isomorphic]
“Isomorphic” means two objects that are identical in structure to each other.
In other words, it simply means that the shape is the same.
In data structures, it is also important to determine whether two data structures are isomorphic.
For example, it is also very important to determine whether any two graphs are isomorphic.
If you've been into programming, you're probably familiar with the "Control-Flow Graph".
Determining whether the control-flow graph of any two programs is the same is also important in terms of security, so it is being studied a lot.
However, since it has not been proven that the problem of determining whether any two graphs are isomorphic can be solved within polynomial time, caution should be exercised in performing the isomorphism test indiscriminately.
The two graphs in the figure are examples of graphs that are isomorphic to each other.
Since it is difficult to determine whether structures are isomorphic just by looking at the outside, a special method must be applied.
That's "Traverse", or "Search", you're all familiar with.
[Related Short Story - Time Complexity[2021/08/04]]
#Story #LootNiP #Algorithm #DataStructure #Isomorphism #Graph #ControlFlowGraph #PolynomialTime