Artificial Intelligence: Entailment and Algorithms PDF
Document Details
Uploaded by ComplimentarySecant2841
Università di Pavia
2024
Marco Piastra
Tags
Related
- Artificial Intelligence: Chapter 3.3 Search Algorithms PDF
- Lecture 2 Artificial Intelligence PDF
- Introduction to Artificial Intelligence with Python PDF
- CIT 478 Artificial Intelligence Course Guide PDF
- AI310 & CS361 Intro to Artificial Intelligence Lectures (Fall 2024) PDF
- Artificial Intelligence: A Modern Approach (4th Edition) - PDF
Summary
These lecture slides from Università di Pavia cover the foundations of artificial intelligence, focusing on entailment, algorithms, and computational complexity, including Turing machines and the Halting Problem. The material is intended for an undergraduate audience and provides a basis for understanding these core AI concepts.
Full Transcript
Artificial Intelligence A Course About Foundations Artificial Intelligence 2024-2025 Entailment and Algorithms Entailment as Satisfiability Artificial Intelligence 2024-2025 Entailment and Algorithms...
Artificial Intelligence A Course About Foundations Artificial Intelligence 2024-2025 Entailment and Algorithms Entailment as Satisfiability Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W w() Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W w() w({}) Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W w() w({}) w({}) Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W w() w({}) w({}) w( {}) = w() w({}) w( {}) = = Artificial Intelligence 2024-2025 Entailment and Algorithms Transforming problems: entailment as satisfiability ▪ {} w() W ▪ {} wff {} ( {}) wff wff {} {} Artificial Intelligence 2024-2025 Entailment and Algorithms “Algorithm” (Computational Complexity Theory in a Quick Ride) Artificial Intelligence 2024-2025 Entailment and Algorithms Turing Machine (A. Turing, 1937) ▪ Artificial Intelligence 2024-2025 Entailment and Algorithms Turing Machine (A. Turing, 1937) ▪ 0 Artificial Intelligence 2024-2025 Entailment and Algorithms Decisions and decidability (automation) ▪ ▪ K S ▪ S {0, 1} K I wff wff I Artificial Intelligence 2024-2025 Entailment and Algorithms Decisions and decidability (automation) ▪ K Artificial Intelligence 2024-2025 Entailment and Algorithms An aside: The Halting Problem ▪ H M D “halt” “loop” M D Machine M H “halt” / “loop” Input D Artificial Intelligence 2024-2025 Entailment and Algorithms An aside: The Halting Problem ▪ H M D “halt” “loop” M D Machine M H “halt” / “loop” H M Artificial Intelligence 2024-2025 Entailment and Algorithms An aside: The Halting Problem ▪ H M D “halt” “loop” M D Machine M H “halt” / “loop” H R H “halt” “halt” H “loop” “loop”? R Machine M YES H “halt” NO do loop! Artificial Intelligence 2024-2025 Entailment and Algorithms An aside: The Halting Problem ▪ H M D “halt” “loop” M D Machine M H “halt” / “loop” H R H “halt” “halt” H “loop” “loop”? R Machine R YES H “halt” NO do loop! R R R R Artificial Intelligence 2024-2025 Entailment and Algorithms Computational complexity ▪ wff ▪ ▪ Artificial Intelligence 2024-2025 Entailment and Algorithms Classes P, NP and NP-complete - The SAT problem ▪ P O(P(n)) P( ) n ▪ NP P P P NP Artificial Intelligence 2024-2025 Entailment and Algorithms Classes P, NP and NP-complete - The SAT problem ▪ NP-complete NP NP-complete NP K NP-complete NP K ▪ NP-complete K M(K) J K M(J) M(K) M(J) M(K) M(J) ▪ NP-complete P = NP P NP Artificial Intelligence 2024-2025 Entailment and Algorithms Exhaustive (Tree) Search Artificial Intelligence 2024-2025 Entailment and Algorithms Satisfiability and decidability (in LP) ▪ wff Artificial Intelligence 2024-2025 Entailment and Algorithms Satisfiability and decidability (in LP) : (B D (A C)) B 1 0 D D 1 0 1 0 A A A A 1 0 1 0 1 0 1 0 C C C C C C C C 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 Artificial Intelligence 2024-2025 Entailment and Algorithms Satisfiability and decidability (in LP) : (B D (A C)) B 1 0 D D 1 0 1 0 A A A A 1 0 1 0 1 0 1 0 C C C C C C C C 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 (B D A C) Artificial Intelligence 2024-2025 Entailment and Algorithms Satisfiability and decidability (in LP) : (B D (A C)) B 1 0 D D 1 0 1 0 A A A A 1 0 1 0 1 0 1 0 C C C C C C C C 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 (B D A C) O(2n) n Artificial Intelligence 2024-2025 Entailment and Algorithms
