본문 바로가기

전공 공부

 (20)
[인공지능] CSPs- 4 𝐾-Consistency 𝐾-Consistency 일관성 정도의 증가(Increasing degrees of consistency) : 일관성의 정도는 𝐾의 값에 따라 증가한다. 1-Consistency (Node Consistency) 각 단일 노드의 도메인에는 해당 노드의 단항 제약 조건(unary constraint)을 충족하는 값이 있다. 2-Consistency (Arc Consistency): 노드 쌍마다(each pair of node) 하나에 일관된 할당이 다른 하나로 확장될 수 있다. K-Consistency: k개의 노드마다 k-1에 대한 일관된 할당이 k번째 노드로 확장될 수 있다. 더 높은 k 값을 계산하려면 더 비싸지게 된다. (k=2의 경우 :Arc Consistency) Str..
[인공지능] CSPs- 3 Backtracking Search Backtracking Search 기본 개념 Backtracking search는 CSPs (Constraint Satisfaction Problems)를 해결하기 위한 기본적인 비정보화된 알고리즘(basic uninformed algorithm)이다. Idea 1: 한 번에 하나의 변수(One variable at a time) 변수 할당은 교환 가능(commutative)하므로 순서를 고정(fix ordering)한다. 즉, [WA = red then NT = green]은 [NT = green then WA = red]와 동일하다. 각 단계에서 단일 변수에 대한 할당만 고려할 필요가 있다. Idea 2: 진행 중에 제약 조건 확인(Check constraints..
[인공지능] CSPs -2 Constraint Graphs 제약 그래프는 Constraint Satisfaction Problem (CSP)의 구조와 관계를 시각적으로 표현하는 데 사용되며, 이를 통해 문제의 복잡성과 구조를 더 잘 이해하고 해결할 수 있다. Binary CSP 각 제약 조건은 최대(at most) 두 변수와 관련된다. 이는 제약 조건이 두 변수 사이의 관계만을 정의한다는 것을 의미한다. Binary Constraint Graph 노드(node)는 변수(variable)를 나타내며, 호(arc)는 제약 조건을 나타낸다. 이 그래프는 변수 간의 제약 조건을 시각적으로 표현하는 도구로 사용됩니다. General-Purpose CSP Algorithms 일반 목적의 CSP 알고리즘은 그래프 구조(Graph structu..
[인공지능] Constraint Satisfaction Problems - 1 Outline Constraint Satisfaction Problems (CSPs): CSPs는 여러 변수와 이러한 변수에 대한 제약 조건들 사이의 관계를 표현하는 문제이다. DFS and Backtracking Search: 깊이 우선 탐색(DFS) 및 백트래킹 탐색은 CSPs를 해결하는 데 사용되는 알고리즘이다. 백트래킹 탐색은 특히 제약 조건을 만족하지 않는 솔루션을 빠르게 배제하여 탐색 공간을 줄인다. Speed-ups: Ordering: 변수의 값을 시도하는 순서를 최적화하여 탐색 속도를 향상시킬 수 있다. Filtering: 불가능한 솔루션을 조기에 감지하여 탐색 공간을 줄일 수 있다. Structure: 문제의 구조를 활용하여 탐색 속도를 향상시킬 수 있다. Iterative Algorit..
[인공지능] Propositional Logic - 5 SAT Solvers in Practice SAT 솔버가 실제로 어떻게 다양한 분야에서 사용되는지를 설명합니다. 1. Circuit Verification 주어진 VLSI(매우 대규모 집적 회로) 회로가 올바른 답을 계산하는지 확인한다. 회로 설계의 정확성과 신뢰성을 검증하기 위해 SAT 솔버를 사용한다. does this VLSI circuit compute the right answer? 2. Software Verification 특정 프로그램이 올바른 결과를 계산하는지 확인한다. 코드의 논리적 오류를 찾고, 프로그램이 예상대로 작동하는지 검증한다. does this program compute the right answer? 3. Software Synthesis(합성) 올바른 답을 계산하는 프로..
[인공지능] propositional logic - 4 Satisfiability and Entailment Satisfiable 정의: 문장이 만족 가능(satisfiable)하다는 것은 그 문장이 적어도 하나의 세계에서 참이라는 것을 의미한다. Entailment Testing with SAT Solver: 만약 우리가 매우 효율적인 SAT(Satisfiability) solver를 가지고 있다면, 이를 사용하여 함의(entailment)를 테스트하는 방법은 다음과 같다 주어진 α가 β를 함의한다고 표현되면 α⊨β. 이는 α⇒β가 모든 세계에서 참이라는 것과 동일하다. 이는 ¬(α⇒β)가 모든 세계에서 거짓이라는 것과 동일하다. 이는 α∧¬β가 모든 세계에서 거짓이라는 것과 동일하며, 즉, 만족 불가능(unsatisfiable)하다는 것을 의미한다. Pr..
[인공지능] Propositional Logic - 3 EXAMPLE 2 문제 : 문장 α=(A∧B)∨(C∧¬D) 라고 하자 α가 true인 모델은 몇개가 있는가? (In how many models is a true?) 진리값 평가 과정: 각 기호 A,B,C,D는 독립적으로 참 또는 거짓이 될 수 있으므로, 총 2^4=16개의 가능한 모델이 있다. 이 16개의 모델 중에서 문장 α가 참인 모델의 수를 센다. (A∧B)가 참인 모델: A와 B가 모두 참인 경우 A=true,B=true,C=true,D=true A=true,B=true,C=true,D=false A=true,B=true,C=false,D=true A=true,B=true,C=false,D=false (C∧¬D)가 참인 모델: C가 참이고 D가 거짓인 경우 A=true,B=true,C=true,..
[인공지능] Propositional Logic - 2 Inference: Entailment Entailment(함의)이라는 개념은 한 논리적 표현이 다른 표현이 참이라는 것을 필연적으로 의미하는지를 설명한다. 기호로는 α⊨β 로 표현되며, 이는 “α entails β” 또는 “β follows from α”라고 읽을 수 있다. 정의: α⊨β : α 가 참인 모든 가능한 세계에서 β 도 참이다. 다르게 표현하면, α-worlds는 β-worlds의 부분집합이다. [models(a) ⊆ models(b)] 예제 설명: α_2​⊨α_1 이라고 가정. 여기서 α_2​는 ¬Q∧R∧S∧W이고, α_1​은 ¬Q이다. α_2​가 참인 모든 세계에서 α_1​도 참이어야 한다. α_2​가 참이면, ¬Q는 반드시 참이므로, α_2​는 α_1​을 함축(entail)한다. In..

티스토리툴바