OpenMP代写：CS4000CountingSatisfyingAssignments

代写并行计算作业，采用OpenMP处理布尔表达式。

Introduction

Boolean formula (e.g. x ∧ y ∨ z) are used throughout computer science
(programming languages, AI, etc.). Sometimes, we want to know if something is
possible. In this case, we might want to know whether a boolean formula is
satisfiable, i.e., is there a setting of the variables in a way that makes the
entire formula true. Sometimes, we want to know how many ways something can be
done. This corresponds to counting the number of satisfying assignments to a
boolean formula. For this assignment, you will be counting the number of ways
that a given boolean formula can be evaluate to true.
For the purposes of this assignment, boolean formula will be described
recursively as follows.

1. A boolean formula might be just a single variable, e.g., ABC. Here, a variable is given a sequence of characters. The first character must be either a lowercase or uppercase letter (a-z or A-Z), with all subsequent characters being letters or numbers. So, for example x1 would be considered a variable name, whereas x.1 would not be a valid variable.
2. If A1 and A2 are boolean formula, then (A1 + A2) is a boolean formula (+ == AND), (A1|A2) is a boolean formula (| == OR), and A1 is a boolean formula (- == NOT).
   Hence, for example, (x + (y | -z)) is a valid boolean formula. This formula is
   true exactly 3 times.
   So, for this assignment, you will read in a boolean formula and you will
   compute the number of satisfying assignments to the boolean formula.

Part 1 Sequential Algorithm

For the first part, you will create a class SeqCounting with at least one
public member function int SatisfyingAssignments(string formula); that takes a
boolean formula as input (in string form) and returns the number of satisfying
assignments. Your code will do this by trying every possible setting of the
variables.

Part 2 Parallel Algorithm VI

For the second part, you will create a class ParCounting with at least one
public member function
int SatisfyingAssignments(string formula);
—|—
that takes a boolean formula as input (in string form) and returns the number
of satisfying assignments. Your code will do this by trying every possible
setting of the variables. However, your code will run in parallel using the
OpenMP constructs given in class. However,this code should NOT use the
reduction construct.
Your code should be at least 75% efficent when using 4 cores.

Part 3 Parallel Algorithm VII

For the second part, you will create a class Par2Counting with at least one
public member function
int SatisfyingAssignments(string formula);
—|—
that takes a boolean formula as input (in string form) and returns the number
of satisfying assignments. Your code will do this by trying every possible
setting of the variables. However, your code will run in parallel using the
OpenMP constructs given in class. In particular, your code should use the
reduction construct discussed in Lecture #5. Your code should be at least 75%
efficent when using 4 cores.

Submission

Each of the classes described above should be implemented in a single separate
C++ file. The instructor will provide an appropriate test harness. DO NOT
modify the class names or prototypes. Make sure that your code is adequately
documented.