Qualcuno potrebbe indicarmi la definizione di MATRICE CICLICA?
Sarei interessato anche alle proprieta’ fondamentali ed ai riferimenti
bibliografici.
Il mio interesse nasce nell’ambito della teoria dei grafi, e piu’ in
particolare per la necessita’ di affrontare alcuni aspetti relativi alla
applicazione nell’ambito della MINIMIZZAZIONE DELLE FUNZIONI BOOLEANE.
Ancora piu’ specificamente sono interessato ai problemi di copertura di
funzioni booleane che presentano ciclicita’, nel senso che la "matrice di
copertura" non presenta righe/e colonne dominanti (vedi Figura).
_ _ _ _
|1|1|1| |
|1| |1| | Mappa di Karnaugh
|1|1|1| |
|_|_|_|_|
________
A|11 |
B| 11 |
C| 11 |
D| 11 |
E| 11 | e relativa Matrice di Copertura
F| 11 |
G| 11|
H|1______1|
Si noti l’assenza di righe/colonne dominanti.
Definizione:
Riga Dominante=Riga uguale ad un’altra ma con qualche 1 in piu’ (ovvero che
copre qualche colonna in piu’ della prima).
Analogamente per le colonne.
Grazie.
n…@iol.it
In article <6asv9m$…@everest.vol.it>,
- Hide quoted text — Show quoted text -
Domenico D’Ambrosio <n…@iol.it> wrote:
>Qualcuno potrebbe indicarmi la definizione di MATRICE CICLICA?
>Sarei interessato anche alle proprieta’ fondamentali ed ai riferimenti
>bibliografici.
>Il mio interesse nasce nell’ambito della teoria dei grafi, e piu’ in
>particolare per la necessita’ di affrontare alcuni aspetti relativi alla
>applicazione nell’ambito della MINIMIZZAZIONE DELLE FUNZIONI BOOLEANE.
>Ancora piu’ specificamente sono interessato ai problemi di copertura di
>funzioni booleane che presentano ciclicita’, nel senso che la "matrice di
>copertura" non presenta righe/e colonne dominanti (vedi Figura).
>_ _ _ _
>|1|1|1| |
>|1| |1| | Mappa di Karnaugh
>|1|1|1| |
>|_|_|_|_|
> ________
>A|11 |
>B| 11 |
>C| 11 |
>D| 11 |
>E| 11 | e relativa Matrice di Copertura
>F| 11 |
>G| 11|
>H|1______1|
>Si noti l’assenza di righe/colonne dominanti.
>Definizione:
>Riga Dominante=Riga uguale ad un’altra ma con qualche 1 in piu’ (ovvero che
>copre qualche colonna in piu’ della prima).
>Analogamente per le colonne.
>Grazie.
>n…@iol.it
Non so se si tratti di un problema di teoria oppure di prattica.
Nel secondo caso, programmi per la minimizzazione Booleana esistono, e
nella maggior parte i loro risultati sono buoni e ottenuti piuttosto
rapidamente. Ma se lei sta cercando un algoritmo _perfetto_, ed _efficace_
(in P, cioe: per qualche k, il tempo massimo per ogni formula di lunghezza n
essendo <= n^k), la teoria non ci lascia grande speranza; un tale algoritmo
sarebbe prova che P = NP.
La ciclicita potrebbe essere d’ aiuto… ma io almeno ne sarei
sorpreso. Si sa che copertura della mappa Karnaugh non da sempre il vero
minimo — fatto generale. E assenza di dominanti, direi, non ci porta piu
vicino. (Chissa pero, forse mi sbaglio! … non ho una dimonstrazione
che questo sia cosi).
Ilias