Problemi di combinatoria[help]
Premessa: sto affrontando un problema riguardante le sequenze di DNA. Abbiamo sequenze di k simboli sceglibili da un alfabeto di n simboli. Quante di queste sequenze si possono prendere insieme, al massimo, mantenendo la proprieta' che ciascuna di esse differisca per 1 simbolo da esattamente una sola delle altre sequenze considerate? Io penso che il nunmero sia n*k, ma non l'ho dimostrato. Sareste cosi' gentili da darmi una mano?
Risposte
Vediamo se questo stuzzica un poco la fantasia...Il problema si ricollega alla teoria dei grafi: dato un insieme di stringhe lunghe k fatte con un alfabeto di n simboli costruiamo un grafo che ha come vertici le stringhe. Ora poniamo un arco tra due vertici quando essi differiscono per esattamente un simbolo. Quanti vertici ha il cammino semplice piu' lungo possibile?
Ringrazio chiunque si stia interessando...sono proprio felice!
L'ordine non conta. k*(n-1) è il numero di sequenze che differiscono per un simbolo da una data sequenza scelta.
Quello che dico io è diverso, esempio: n=4, k=4.
ABCD - ABCA - ABDA - ACDA - BCDA - BDDA - BDAA - BDAB - CDAB - CAAB - CABB - CABC - DABC - DBBC - DBCC. Se se ne aggiunge un'altra, ovvero DBCD, si chiude il cerchio e si rompe la proprietà.
Credo quindi che il numero sia n*k - 1.
Trovatemi un controesempio, e io vi credero'!
L'ordine non conta. k*(n-1) è il numero di sequenze che differiscono per un simbolo da una data sequenza scelta.
Quello che dico io è diverso, esempio: n=4, k=4.
ABCD - ABCA - ABDA - ACDA - BCDA - BDDA - BDAA - BDAB - CDAB - CAAB - CABB - CABC - DABC - DBBC - DBCC. Se se ne aggiunge un'altra, ovvero DBCD, si chiude il cerchio e si rompe la proprietà.
Credo quindi che il numero sia n*k - 1.
Trovatemi un controesempio, e io vi credero'!
guarda bemipefe...non ho capito niente di quello che hai detto, però mi sento di essere d'accordo con te! [;)]
e cmq io scherzavo...chiaramente!
e cmq io scherzavo...chiaramente!
quote:
Originally posted by infinito
Non ho capito alcune cose, fra cui:
- l'ordine dei simboli è significativo?
- in una sequenza i vari simboli devono essere tutti diversi o possono anche essere uguali?
io ho assunto che l' ordine sia significativo e che i simboli possano essere ripetuti anche K volte, facendosi riferimento al dna che mi sembra utilizzi un codice binario l' ordine deve avere significato.
K*(n-1)? se il testo è scritto esattamente come lo riporti
[/quote]
scusa ho dimenticato un +1 che è la sequenza iniziale
[k*(n-1)]+1
[/quote]
scusa ho dimenticato un +1 che è la sequenza iniziale
[k*(n-1)]+1
quote:
Originally posted by lupin
Premessa: sto affrontando un problema riguardante le sequenze di DNA. Abbiamo sequenze di k simboli sceglibili da un alfabeto di n simboli. Quante di queste sequenze si possono prendere insieme, al massimo, mantenendo la proprieta' che ciascuna di esse differisca per 1 simbolo da esattamente una sola delle altre sequenze considerate? Io penso che il nunmero sia n*k, ma non l'ho dimostrato. Sareste cosi' gentili da darmi una mano?
K*(n-1)? se il testo è scritto esattamente come lo riporti
.....la prossiam volta ci starò più attento comunque grazie "[vecchio]"!
Bemipefe
Bemipefe
per "[vecchio]"
Io penso che un matematico abbia bisogno anche della visione macroscopica del mondo e non solo di quella microscopica......e poi che sarebbe per un matematico laurearsi in lettere......sarebbe come fare una partita a scacchi....per una mente abituata alle Alpi , come quella di un matematico è , scalare la Collina del sapere di "filosofico-umano" , cioè quel saggio sapere uamno che si tramanda negli scritti , non sarebbe poi tanto impegnativo....basterebbe capire........cosa che in matematica non basta.....
Bemipefe
Io penso che un matematico abbia bisogno anche della visione macroscopica del mondo e non solo di quella microscopica......e poi che sarebbe per un matematico laurearsi in lettere......sarebbe come fare una partita a scacchi....per una mente abituata alle Alpi , come quella di un matematico è , scalare la Collina del sapere di "filosofico-umano" , cioè quel saggio sapere uamno che si tramanda negli scritti , non sarebbe poi tanto impegnativo....basterebbe capire........cosa che in matematica non basta.....
Bemipefe
...e perchè nò anche da informatici , economisti.....
..di sicuro non mi mettero a fare siti web o fare il gestore di una rete....questo semmai lo lascio al tempo libero o per quando andrò in pensione...
...la strada più facile non è mai quella più buona....tu capisci perchè punto il più alto possibile no!?
Potere è Dovere .....e quì Potere = Sapere .....beato chi ce l'ha di questi tempi.
Adesso mi fermo senno se inizio a parlare non mi arresto più
CIAO!
Bemipefe
..di sicuro non mi mettero a fare siti web o fare il gestore di una rete....questo semmai lo lascio al tempo libero o per quando andrò in pensione...
...la strada più facile non è mai quella più buona....tu capisci perchè punto il più alto possibile no!?
Potere è Dovere .....e quì Potere = Sapere .....beato chi ce l'ha di questi tempi.
Adesso mi fermo senno se inizio a parlare non mi arresto più
CIAO!
Bemipefe
Ebbene anche io studio Scienze Informatiche , ma aveveo capito che facevi biologia visto che mi parlavi di DNA.....è per questo che ti ho detto che farò combiantoria il prossimo hanno cioè quest'anno poichè sono ancora al primo.
.....ma di preciso che cos'è "Combinatoria" ? Quanto è difficile il secondo hanno rispetto al primo?
E poi tutto sommato non è che ce ne sia poca di matematica in qusto tipo di ramo.......Nel mio corso ci Sono Logica, Calcolo Differenziale e Integrale (molto voluminosi) , Algebra , Fisica .....e poi anche programmare infondo è fare matematica no!? e così projettare un architettura.......comunque anch'io pensavo di usare questa laurea(se mai la prendero) per fare "matematica"....cioè mi piacerebbe ad esempio creare modelli virtuali della variazione di fenomini come avviene in chimica per il calcolo delle sostanze risultanti, in biologia per vedere gli effeti di una sustanza su una cellula , e poi ci sono i modelli fatti per vedere l'evoluzione nel tempo del "tempo" atmosferico........insomma ci sono molti campi ....per i quali però credo che serva fare un master o qualcosa del genere, perchè non si possono creare modelli su qualcosa che non si conosce.....infatti chimica è omessa nel mio sorso così coem biologia (nella specialistica ci dovrebbe essere) che sarebbero invece ben accolte se fatte in maniera ovviamente non rigorosa....
Se poi ti piace la matematica non applicata beh per questo penso servano bsi molto buone di matematica....e poi comunque la matematica penso che non sia mai fine a se stessa, molte scoperte sono state fatte per necessità reali di applicarle alla fisica o in altri campi applicativi
da appunto fisici, chimici etc...
Bemipefe
.....ma di preciso che cos'è "Combinatoria" ? Quanto è difficile il secondo hanno rispetto al primo?
E poi tutto sommato non è che ce ne sia poca di matematica in qusto tipo di ramo.......Nel mio corso ci Sono Logica, Calcolo Differenziale e Integrale (molto voluminosi) , Algebra , Fisica .....e poi anche programmare infondo è fare matematica no!? e così projettare un architettura.......comunque anch'io pensavo di usare questa laurea(se mai la prendero) per fare "matematica"....cioè mi piacerebbe ad esempio creare modelli virtuali della variazione di fenomini come avviene in chimica per il calcolo delle sostanze risultanti, in biologia per vedere gli effeti di una sustanza su una cellula , e poi ci sono i modelli fatti per vedere l'evoluzione nel tempo del "tempo" atmosferico........insomma ci sono molti campi ....per i quali però credo che serva fare un master o qualcosa del genere, perchè non si possono creare modelli su qualcosa che non si conosce.....infatti chimica è omessa nel mio sorso così coem biologia (nella specialistica ci dovrebbe essere) che sarebbero invece ben accolte se fatte in maniera ovviamente non rigorosa....
Se poi ti piace la matematica non applicata beh per questo penso servano bsi molto buone di matematica....e poi comunque la matematica penso che non sia mai fine a se stessa, molte scoperte sono state fatte per necessità reali di applicarle alla fisica o in altri campi applicativi
da appunto fisici, chimici etc...
Bemipefe
Non ho capito alcune cose, fra cui:
- l'ordine dei simboli è significativo?
- in una sequenza i vari simboli devono essere tutti diversi o possono anche essere uguali?
- l'ordine dei simboli è significativo?
- in una sequenza i vari simboli devono essere tutti diversi o possono anche essere uguali?
di sicuro non siamo forti in italiano eh??
???[;)]
quote:
...pultroppo...
???[;)]
Grazie per l'interessamento...intanto ho chiesto anche a Luca Lussardi, che ha detto che ci pensera' su. Ma tu studi matematica all'universita'? Se si: wow! Mi sarebbe piaciuto intraprendere quella strada, ma ci ho pensato un po' tardi: mi laureo ad ottobre in Informatica...comunque e' tra i miei desideri un giorno di studiare meglio questo ramo, che e' appena accennato nell'informatica. Tanti Saluti!
caro "lupin" se avessi "il sapere" ti offrirei la mia esperienza ma pultroppo "combinatoria" la farò solo il prossimo anno e biologia la studio solo per passione....tuttavia non sono ancora arrivato alle sequenze di DNA.
Comunque qualcuno troverai prima o poi....anche se adesso sono quasi tutti in "vacanza"...
...mi spiace
CIAO!
Bemipefe
Comunque qualcuno troverai prima o poi....anche se adesso sono quasi tutti in "vacanza"...
...mi spiace
CIAO!
Bemipefe
Consideriamo un alfabeto avente n simboli. Creiamo sequenze di k simboli ciascuna.
1) Quante di queste sequenze si possono prendere insieme, al massimo, in modo che ciascuna
differisca per un simbolo (distanza di hamming 1) da esattamente due altre sequenze?
2) Quante di queste sequenze si possono prendere insieme, al massimo, in modo che ciascuna
abbia distanza di hamming > 1 dalle altre?
3) Data una sequenza quante sono quelle che (tra tutte le sequenze lunghe k formabili)
hanno distanza di hamming 2 da essa? Io penso ((n-1)^2)*(combinazioni di 2 in classe k):
e' giusto?
1) Quante di queste sequenze si possono prendere insieme, al massimo, in modo che ciascuna
differisca per un simbolo (distanza di hamming 1) da esattamente due altre sequenze?
2) Quante di queste sequenze si possono prendere insieme, al massimo, in modo che ciascuna
abbia distanza di hamming > 1 dalle altre?
3) Data una sequenza quante sono quelle che (tra tutte le sequenze lunghe k formabili)
hanno distanza di hamming 2 da essa? Io penso ((n-1)^2)*(combinazioni di 2 in classe k):
e' giusto?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo