Team:MoWestern Davidson/project mathmodel

From 2009.igem.org

(Difference between revisions)
(Rough and Fine distribution)
(Rough and Fine distribution)
Line 8: Line 8:
To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many inputs  satisfied a certain number of clauses in a problem. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.  
To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many inputs  satisfied a certain number of clauses in a problem. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.  
-
 
[[Image:Table2.png|none|750px|]]
[[Image:Table2.png|none|750px|]]
-
 
-
 
Fine distributions look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied '''singly''' or '''doubly''' respectively. The fine distribution for the red problem from the table above is '''0011212100'''. This distribution means that 0 inputs satisfied 0 clauses, 0 inputs satisfied 1 clause singly, 1 input satisfied 1 clause doubly, 1 input satisfied 2 clauses with 2 singles, 2 inputs satisfied 2 clauses with 1 single and 1 double, 1 input satisfied 2 clauses with 2 doubles, 2 inputs satisfied 3 clauses with 3 singles, 1 input satisfied 3 clauses with 2 singles and 1 double, 0 inputs satisfied 3 clauses with 1 single and 2 doubles, and 0 inputs satisfied 3 clauses with 3 doubles.
Fine distributions look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied '''singly''' or '''doubly''' respectively. The fine distribution for the red problem from the table above is '''0011212100'''. This distribution means that 0 inputs satisfied 0 clauses, 0 inputs satisfied 1 clause singly, 1 input satisfied 1 clause doubly, 1 input satisfied 2 clauses with 2 singles, 2 inputs satisfied 2 clauses with 1 single and 1 double, 1 input satisfied 2 clauses with 2 doubles, 2 inputs satisfied 3 clauses with 3 singles, 1 input satisfied 3 clauses with 2 singles and 1 double, 0 inputs satisfied 3 clauses with 1 single and 2 doubles, and 0 inputs satisfied 3 clauses with 3 doubles.

Revision as of 19:51, 27 July 2009

Lego Models

B2 Bomber

Rough and Fine distribution

To classify SAT problems, we began looking at the Rough distribution of each problem, meaning how many inputs satisfied a certain number of clauses in a problem. The table below gives the number of clauses satisfied for a few select 2-SAT problems for each input.

Table2.png

Fine distributions look more deeply at how each clause was satisfied. If an input satisfies one or two literals in a clause, that clause is satisfied singly or doubly respectively. The fine distribution for the red problem from the table above is 0011212100. This distribution means that 0 inputs satisfied 0 clauses, 0 inputs satisfied 1 clause singly, 1 input satisfied 1 clause doubly, 1 input satisfied 2 clauses with 2 singles, 2 inputs satisfied 2 clauses with 1 single and 1 double, 1 input satisfied 2 clauses with 2 doubles, 2 inputs satisfied 3 clauses with 3 singles, 1 input satisfied 3 clauses with 2 singles and 1 double, 0 inputs satisfied 3 clauses with 1 single and 2 doubles, and 0 inputs satisfied 3 clauses with 3 doubles.