works/bPmatch1D20.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.
teoria e dimostrazioni
L'[idea intuitiva] dell'algoritmo
[Definizioni e dimostrazioni] formali del funzionamento
[Complessità in spazio ed in tempo]
esempi e statistiche
Esempio di [generazione di un grafo]
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
PHPMySQLTheGIMPsourceForge
©2002-2004 by Claudio Felicioli as pangon - mail -