INTRODUZIONE 1

1. RETI BOOLEANE 3
    1.1. INTRODUZIONE 3
    1.2. DEFINIZIONE 8
    1.3. DINAMICA 10
    1.4. RETI BOOLEANE STOCASTICHE 12
    1.5. APPLICAZIONI 15
        1.5.1. Applicazioni in ambito biologico 15
        1.5.2. Applicazioni relative all’apprendimento automatico 17
        1.5.3. Osservazioni e considerazioni sulle capacità computazionali delle reti booleane 26
        1.5.4. Un approccio alternativo 27
    1.6. RETI BOOLEANE E RETI NEURALI ARTIFICIALI 29
        1.6.1. Reti neurali artificiali: richiami 29
        1.6.2. Reti booleane e reti neurali artificiali: analogie e differenze 33

2. IL PROBLEMA DI SODDISFACIBILITA’ 37
    2.1. DEFINIZIONE 37
    2.2. ALGORITMI COMPLETI 40
        2.2.1. Algoritmo di Davis-Putnam 40
        2.2.2. Algoritmo di Davis-Logemann-Loveland 42
        2.2.3. Algoritmi di soluzione per problemi di soddisfacimento di vincoli 44
    2.3. ALGORITMI INCOMPLETI 51
        2.3.1. Ricerca locale 51
        2.3.2. Algoritmi di ricerca nello spazio degli stati 56
        2.3.3. Algoritmo GSAT 64
        2.3.4. Algoritmo SASAT 66
        2.3.5. Algoritmo WalkSAT 67
    2.4. SAT E PROBLEMI DI SODDISFACIMENTO DI VINCOLI 68
        2.4.1. Trasformazione di un GCP in un SAT 69
    2.5. ANALISI DELLA COMPLESSITA’ DEL SAT 71
        2.5.1. Complessità media del k-SAT 72

3. APPLICAZIONE DELLE RETI BOOLEANE AL SAT 76
    3.1. INTRODUZIONE 76
    3.2. DESCRIZIONE DELL’APPLICAZIONE 78
        3.2.1. Determinazione del mapping 78
        3.2.2. Simulazione della dinamica della rete 83
        3.2.3. Esempi 85
    3.3. RISULTATI 92
        3.3.1. Caratteristiche della dinamica delle reti generate da m 1 93
        3.3.2. Risultati dell’algoritmo SAT-RB con mapping m 1 96
    3.4. CONSIDERAZIONI SUL MAPPING m 1 102
    3.5. CONSIDERAZIONI CONCLUSIVE 108

4. RETI BOOLEANE PROBABILISTICHE 111
    4.1. DEFINIZIONE 111
    4.2. UNA RETE BOOLEANA PROBABILISTICA PER IL SAT:RBP1 116
        4.2.1. Definizione 116
        4.2.2. Caratteristiche della rete RBP1 121
        4.2.3. Esempio 122
        4.2.4. Analisi probabilistica delle transizioni della rete RBP1 125
    4.3. APPLICAZIONE DELLA RETE RBP1 AL SAT 128
        4.3.1. Algoritmo 128
        4.3.2. Simulazioni e risultati 133
        4.3.3. Osservazioni 146
    4.4. CONSIDERAZIONI CONCLUSIVE 156

5. RETI BOOLEANE ASINCRONE 157
    5.1. DEFINIZIONE 157
        5.1.1. Dinamica 158
    5.2. UNA RETE BOOLEANA ASINCRONA PER IL SAT:RBA1 162
        5.2.1. Definizione 162
        5.2.2. Caratteristiche della rete RBA1 165
    5.3. APPLICAZIONE DELLA RETE RBA1 AL SAT 167
        5.3.1. Algoritmo 167
        5.3.2. Simulazioni e risultati 170
        5.3.3. Osservazioni 176
    5.4. CONSIDERAZIONI CONCLUSIVE 178

6. CONFRONTO DEI RISULTATI 179
    6.1. ORGANIZZAZIONE DELLE SIMULAZIONI 179
        6.1.1. Algoritmo GSAT 180
        6.1.2. Generazione di istanze test 182
    6.2. RISULTATI RELATIVI AL 3-SAT 183
        6.2.1. 3-SAT con n = 10 183
        6.2.2. 3-SAT con n = 20 186
        6.2.3. 3-SAT con n = 30 190
        6.2.4. 3-SAT con n = 40 194
        6.2.5. 3-SAT con n = 50 198
        6.2.6. 3-SAT con n = 80 202
        6.2.7. 3-SAT con n = 100 206
        6.2.8. Risultati sul 3-SAT nel punto critico 210
6.3. OSSERVAZIONI CONCLUSIVE 211

7. CONCLUSIONI 212

BIBLIOGRAFIA 218