Automated Reasoning: satisfiability

  • 4.8
Approx. 25 hours to complete

Course Summary

This course teaches the foundations of automated reasoning, with a focus on the Boolean Satisfiability (SAT) problem. Students will learn how to solve problems using SAT solvers and how to encode problems as Boolean formulas. The course also covers applications of automated reasoning in various fields.

Key Learning Points

  • Learn the fundamental concepts and techniques of automated reasoning
  • Understand how to encode problems as Boolean formulas
  • Develop problem-solving skills using SAT solvers

Related Topics for further study


Learning Outcomes

  • Ability to solve problems using SAT solvers
  • Understanding of problem encoding as Boolean formulas
  • Developed problem-solving skills using automated reasoning

Prerequisites or good to have knowledge before taking this course

  • Basic knowledge of propositional logic
  • Familiarity with programming concepts

Course Difficulty Level

Intermediate

Course Format

  • Online
  • Self-paced

Similar Courses

  • Logic and Proofs
  • Discrete Optimization

Notable People in This Field

  • Georg Gottlob
  • Moshe Vardi

Related Books

Description

In this course you will learn how to apply satisfiability (SAT/SMT) tools to solve a wide range of problems.

Outline

  • SAT/SMT basics, SAT examples
  • General introduction, and an application to poster printing
  • Introduction to SAT
  • SMT syntax and tools
  • Eight queens problem
  • Binary Arithmetic: addition
  • Binary Arithmetic: multiplication
  • Examples from the lecture
  • Eight queens formula in SMT syntax
  • Truth table
  • Carries in binary addition
  • Binary multiplication
  • SMT applications
  • Rectangle fitting
  • Solving Sudoku
  • Scheduling
  • Bounded model checking
  • Sudoku formula in SMT 2 format
  • Introduction
  • Rectangle fitting
  • Scheduling
  • Bounded Model Checking
  • Filling trucks for a magic factory
  • A sudoku variant
  • Job scheduling
  • Program correctness
  • Theory and algorithms for CNF-based SAT
  • Resolution
  • Example of resolution
  • DPLL
  • Transforming DPLL to resolution
  • CDCL basics
  • CDCL optimizations
  • Resolution
  • apply resolution
  • DPLL
  • DPLL to resolution
  • Theory and algorithms for SAT/SMT
  • Transforming a propositional formula to CNF
  • The Tseitin transfomation
  • Introduction to the Simplex method
  • Optimizing by the Simplex method
  • Checking feasibility by the Simplex method
  • The Simplex method and SMT

Summary of User Reviews

Discover the power of Automated Reasoning SAT with this online course from Coursera. Students rave about the engaging lectures, practical exercises, and useful resources that help them understand the subject better. One key aspect that many users appreciated is the clear explanations of complex concepts.

Pros from User Reviews

  • Engaging lectures
  • Practical exercises
  • Useful resources
  • Clear explanations of complex concepts
  • Great for beginners

Cons from User Reviews

  • Some technical difficulties with the course platform
  • Lack of interaction with instructors and peers
  • No certificate of completion included in the free version
  • Not enough real-world examples
  • Some assignments are too challenging
English
Available now
Approx. 25 hours to complete
Hans Zantema
EIT Digital
Coursera

Instructor

Hans Zantema

  • 4.8 Raiting
Share
Saved Course list
Cancel
Get Course Update
Computer Courses