2-SATisfiabilty casi problemi di test

Question

Ho scritto un risolutore di SAT per il problema 2-soddisfacibilità, qualcuno si prega di fornire me un banco di prova con il dire 10000 letterali che ha una sola assegnazione soddisfacibili cioè una sola soluzione

The format can be:(for 3 literals)
2            // No of clauses and then each clause
2 3
1 -2
corresponding to
(b+c).(a+!b)

Answer 1

Test di copertura di solito è difficile, il più delle volte, è solo dimenticare un fattore o un altro.

Io di solito procede in due passi:

1. Assicurarsi che risolve un problema banale (o alcuni)
Casi
2. bordo di prova / Condizioni al contorno: 0 clausola per esempio
3. casi di test di errore: ingresso mal formattato, problemi con nessuna soluzione
4. Performance Test / Messa a iniezione (vedere se il programma non va in crash sotto carico, non perde, ...)

2) e 3) sono praticamente intercambiabili, 4) dovrebbe venire solo se si dispone di metodi per indagare questo tipo di informazioni (benchmarking, rilevamento di perdite di memoria ...).

Un punto importante è che non si deve decodificare il codice per scrivere i test, perché si finirebbe per testare il tuo codice, ma non prova che obbedisce alle specifiche.

Se si tratta di un progetto di casa, le caratteristiche tecniche sono di solito informale, ma esistono ancora (in testa) e questo è dopo di loro che si dovrebbe produrre i casi di test.

Answer 2

Fa questo lavoro approccio?

 (a + b ).(a + !b) 

Questo può essere soddisfatta per mezzo solo se a è vero.

 (a + !b).(!a + !b)

Può essere soddisfatta solo se B è falso. Quindi

  (a + b ).(a + !b).(a + !b).(!a + !b)

Completamente specifica i valori per a e b. Ora possiamo estendere questo per qualsiasi numero di letterali.

Per verificare l'applicazione si potrebbe anche specificare requriements contraddittorie, quindi qualcosa con nessuna soluzione.