※ 이 글은 chatGPT를 기반으로 작성한 글입니다.
결정 문제와 비결정 문제
① 결정 문제(Decision Problem)는 주어진 문제에 대해 '예' 또는 '아니오'로 답할 수 있는 문제를 의미한다.
② 결정 문제에 대한 예시는 다음과 같다.
㉠ 소수 결정 문제(Prime Decision Problem)
ⓐ 질문: n=7은 소수인가?
ⓑ 답: yes
㉡ 그래프 연결성 결정 문제(Graph Connectivity Decision Problem)
ⓐ 질문: 주어진 그래프가 연결되어 있는가?
ⓑ 답: yes or no
㉢ 해밀턴 경로 문제(Hamiltonian Path Problem)
ⓐ 질문: 주어진 그래프 내에서 모든 정점을 정확히 한 번씩 방문하는 경로가 존재하는가?
ⓑ 답: yes or no
㉣ SAT(Boolean Satisfiability Problem)
ⓐ 질문: 논리식 \((x \vee y) \wedge (\neg x \vee z) \) 를 만족시키는 \(x, y, z\)의 값이 존재하는가?
ⓑ 답: yes
㉤ 배낭 문제(Knapsack Problem)
ⓐ 질문: 무게 15kg 내에서 물건들을 골라 총 가치가 100 이상이 되게 할 수 있는가?
ⓑ 답: yes or no
③ 비결정 문제(non-decision problem)는 단순히 '예' 또는 아니오'로 답할 수 있는 결정 문제와 대비되는 개념이다.
④ 비결정 문제의 예시는 다음과 같다.
㉠ 정렬 문제(Sorting Problem)는 주어진 배열을 특정 순서(오름차순, 내림차순)으로 정렬하는 문제다.
㉡ 최적화 문제(Optimization Problem)는 주어진 조건을 만족하면서 최대 또는 최소 값을 찾는 문제다.
㉢ 머신 러닝 알고리즘(Machine Learning Algorithm)은 데이터로부터 학습하여 새로운 데이터에 대한 예측, 분류, 군집화 등을 수행하는 문제다.
결정적 알고리즘과 비결정적 알고리즘
⑤ 결정적 알고리즘(Deterministic Algorithm)은 동일한 입력에 대해 항상 일관된 결과를 제공하는 예측 가능하고 비확률적인 알고리즘이다.
⑥ 결정적 알고리즘의 예시는 다음과 같다.
㉠ 이진 검색 알고리즘(Binary Search)은 정렬된 배열을 가지고 중간 값을 기준으로 반으로 나누어 탐색하는 과정을 반복한다. 이 과정은 무작위성이나 확률적 요소가 없으며, 동일한 입력에 대해서는 항상 동일한 방식으로 탐색하고, 동일한 위치를 결과로 제공한다.
㉡ 버블 정렬(Bubble Sort)은 배열의 인접한 요소들을 반복적으로 비교하고 필요에 따라 교환한다. 이과정은 배열의 첫 요소부터 시작하여 끝 요소까지 진행되며, 정렬 과정은 완전히 예측 가능하다. 동일한 배열에 대해서는 항상 같은 순서로 비교하고 교환을 수행한다.
㉢ 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 각 단계에서 최소 비용의 노드를 선택하고, 그래프의 모든 노드와 간선을 검토한다. 이 과정에서 무작위성이 없으며, 동일한 그래프에 대해서 항상 동일한 최단 경로를 계산한다.
⑦ 비결정적 알고리즘(Non-deterministic Algorithm)은 주어진 입력에 대해 여러 가능한 경로를 가질 수 있으며, 동일한 입력에 대해서도 다른 결과를 생성할 수 있는 알고리즘을 의미한다.
⑧ 비결정적 알고리즘의 예시는 다음과 같다.
㉠ 유전 알고리즘(Genetic Algorithm)은 생물학적 진화의 과정을 최적화 문제를 해결하는 알고리즘이다. 유전자의 세대를 거듭하며 변이, 교차, 선택 등의 과정을 통해 다양한 해결책을 탐색하기 때문에 비결정적 알고리즘이다.
㉡ 몬테 카를로 방법(Monte Carlo Method)는 확률적 샘플링을 이용하여 수학적 모델링, 물리학, 금융학 등에서 복잡한 문제를 해결하는 방법이다. 이 방법은 난수를 기반으로 하여 동일 입력에 대해 다양한 결과를 생성할 수 있기 때문에 비결정적 알고리즘이다.
비결정적 알고리즘은 전역 최적화 문제에서 효과적이다.
최적화 문제
⑨ 최적화 문제(Optimization Problem)은 주어진 조건과 제약 하에 어떤 목표 함수의 값을 최대화하거나 최소화하는 해결책을 찾는 문제다.
⑩ 최적화 문제의 예시는 다음과 같다.
㉠ 경로 최적화는 주어진 지점들을 방문하는 데 필요한 총 거리나 시간을 최소화하는 경로를 찾는 문제이다.
㉡ 자원 할당 문제는 제한된 자원을 효율적으로 배분하여 최대 이익을 얻는 문제이다.
⑪ 지역 최적해(Local Optimum)은 최적해가 그 주변에서는 최적이지만, 전체 탐색 공간에서는 최적이 아닐 수 있는 해를 말한다.
㉠ 힐 클라이밍(Hill Climbing) 알고리즘과 같은 탐색 기법은 지역 최적해에 도달할 수 있지만, 전역 최적해를 보장하지는 않는다.
⑫ 전역 최적해(Global Optimum)은 전체 탐색 공간에서 주어진 목표 함수를 최소화하거나 최대화하는 해를 말한다.
㉠ 유전 알고리즘이나 머신 러닝 등은 전역 최적해를 찾는 데 효과적일 수 있다.