| works/bPmatch | 1D20.net |
La funzione dell'algoritmo è di calcolare, date le
sequenze S e T, la copertura massima di T utilizzando
solo sottosequenze e sottosequenze inverse e complementate di S, con lunghezza
minima l, eventualmente sovrapposte tra di loro, ed in tale copertura
massima minimizzare il numero di sequenze utilizzate. Il problema è stato risolto eseguendo una preelaborazione di S (indipendente dalla sequenza sulla quale si andrà poi a cercare la copertura massima e quindi utilizzabile per ogni possibile T) generando un grafo che permette di riconoscere rapidamente le sottosequenze di S. Si generano quindi il grafo G usando S ed il grafo G' usando S invertito e complementato, utilizzando poi G, G' e T si esegue un calcolo rapido della copertura massima. | |
[Definizioni e dimostrazioni] formali del funzionamento [Complessità in spazio ed in tempo] | |
Esempio di [calcolo di copertura] utilizzando i grafi dell'esempio precedente Statistiche dei [cursori attivi] durante la creazione dei grafi Statistiche degli [archi laterali] presenti nei grafi Statistiche dell'[influenza della lunghezza minima l] nel calcolo della copertura | |
| ©2002-2004 by Claudio Felicioli as pangon - mail - | ||||