View Full Version : [logica] stringa di 20 lettere...
prendiamo l'alfabeto italiano: 21 lettere di cui 5 vocali e 16 consonanti...
abbiamo una stringa di 20 lettere casuali
qual'è la probabilità che ci siano 4 consonanti vicine?
in altri termini la domanda puo essere posta così: quante combinazioni che vanno da aaa...aaa a zzz...zzz presentano almeno 4 consonanti vicine?
una risoluzione con un progamma informatico (trascurando il tempo di esecuzione ) sarebbe piuttosto facile... ma a livello logico/matematico come possiamo risolvere il problema??:)
Ziosilvio
08-05-2008, 12:44
Posta in uno dei thread in rilievo: aiuti in informatica (no programmazione) oppure aiuti in matematica.
mhh ma non è che in realtà abbia bisogno di risolvere questo esercizio...
mi è venuto in mente così per caso e mi sembrava carino come esercizio, quindi l'ho proposto a chi vuole risolverlo degli utenti ;)
beh adesso non mi ricordo bene ma a statistica ste cose si facevan sempre
quindi per gradi, parti dal presupposto di aver la stringa di 4 lettere e quindi la probabilità è
16/20*16/20*16/20*16/20 se è prevista la ripetizione altrimenti
16/20*15/20*14/20*13/20 se le consonanti debbono essere diverse
adesso vado a spanne :D
su una stringa di 4 lettere ho 1 possibile stringa di 4 lettere con probabilità x che siano consonanti
su una stringa di 5 lettere ho 2 possibili stringhe di 4 lettere con probabilità x/2 che siano consonanti
su una stringa di 6 lettere ho 3 possibili stringhe di 4 lettere con probabilità x/3 che siano consonanti
su una stringa di 7 lettere ho 4 possibili stringhe di 4 lettere con probabilità x/4 che siano consonanti
.....
su una stringa di 20 lettere ho 17 possibili stringhe di 4 lettere con probabilità x/17 che siano consonanti
....
su una stringa di n lettere ho n-3 possibili stringhe di 4 lettere con probabilità x/n-3 che siano consonanti
non so se ho detto boiate non mi ricordo un caiser di statistica sono andato a logica
Xalexalex
08-05-2008, 20:47
Fico. Esercizio tipico da olimpiadi :D
Allora, tutte le possibili stringhe sono 21! (inteso come 21 fattoriale ovviamente :D )
Le consonanti sono 16, ne vogliamo 4 vicine.
Posizione A : 16 possibilità
Posizione B : 16 possibilità
Posizione C : 16 possibilità
Posizione D : 16 possibilità
Possibili quartetti di posizione: 17
Risultato:
16*16*16*16*17/21!
Se le cosonanti devonon essere tutte uguali basta sostiture nelle posizioni B,C,D con 1/16.
Mi pare di avere considerato tutti il considerabile :D
Qualche espertone corregga magari :D
@ checo: non ho capito cosa intendi per x e poi x/2 x/3 ecc...:(
@ Alessandro::Xalexalex: la stringa da 20 lettere ammette ripetizioni :p
quindi non è vero che tutte le combinazioni sono 21!
tutte le combinazioni sono 20^21
Xalexalex
09-05-2008, 07:36
@ checo: non ho capito cosa intendi per x e poi x/2 x/3 ecc...:(
@ Alessandro::Xalexalex: la stringa da 20 lettere ammette ripetizioni :p
quindi non è vero che tutte le combinazioni sono 21!
tutte le combinazioni sono 20^21
Uh è vero :D
Ma allora casomai, 21^20 (21 possibilità nella prima posizione, 21 nella seconda, etc.. fino alla 20esima).
Per il resto mi pare cmq giusto...
Ciaoz!
Uh è vero :D
Ma allora casomai, 21^20 (21 possibilità nella prima posizione, 21 nella seconda, etc.. fino alla 20esima).
Per il resto mi pare cmq giusto...
Ciaoz!
e mi sa di no... non consideri che devono essere vicine ma possono essere ovunque..
Xalexalex
09-05-2008, 12:56
Giusto! Allora aggiungerei un fattore 19*18*17 al denominatore :), right?
che risultato ti esce che ho fatto un po di confusione sui tuoi calcoli?:p
Wilcomir
09-05-2008, 16:28
prendiamo l'alfabeto italiano: 21 lettere di cui 5 vocali e 16 consonanti...
abbiamo una stringa di 20 lettere casuali
qual'è la probabilità che ci siano 4 consonanti vicine?
in altri termini la domanda puo essere posta così: quante combinazioni che vanno da aaa...aaa a zzz...zzz presentano almeno 4 consonanti vicine?
una risoluzione con un progamma informatico (trascurando il tempo di esecuzione ) sarebbe piuttosto facile... ma a livello logico/matematico come possiamo risolvere il problema??:)
allora:
i casi possibili sono Cp = 21^20
(21*21*21*21*21*...*21*21)
i casi favorevoli, fissate le quattro consonanti, sono Cf = 21^16
la probabilità pertanto è p = Cf/Cp = 21^16 / 21^20 = 5,142 * 10^-6 = 0,000005142 che è lo 0,0005142%
le stringhe totali infatti sono 278.218.429.446.951.548.637.196.401
quelle "buone" sono 1.430.568.690.241.985.328.321
ciaoooo!
allora:
i casi possibili sono Cp = 21^20
(21*21*21*21*21*...*21*21)
i casi favorevoli, fissate le quattro consonanti, sono Cf = 21^16
la probabilità pertanto è p = Cf/Cp = 21^16 / 21^20 = 5,142 * 10^-6 = 0,000005142 che è lo 0,0005142%
le stringhe totali infatti sono 278.218.429.446.951.548.637.196.401
quelle "buone" sono 1.430.568.690.241.985.328.321
ciaoooo!
è in questo calcolo dove tieni conto che deve essere una stringa di 4 consonanti?
anche perchè non credoci siano così tante stringhe di 4 consonante in 20 caratteri tu più che altro hai tenuto conto delle stringhe di 20 caratteri possibili che altro non è 21^20
a me quella sembra la probabilità che siano tutte consonanti più che altro
Fico. Esercizio tipico da olimpiadi :D
Allora, tutte le possibili stringhe sono 21! (inteso come 21 fattoriale ovviamente :D )
Le consonanti sono 16, ne vogliamo 4 vicine.
Posizione A : 16 possibilità
Posizione B : 16 possibilità
Posizione C : 16 possibilità
Posizione D : 16 possibilità
Possibili quartetti di posizione: 17
Risultato:
16*16*16*16*17/21!
Se le cosonanti devonon essere tutte uguali basta sostiture nelle posizioni B,C,D con 1/16.
Mi pare di avere considerato tutti il considerabile :D
Qualche espertone corregga magari :D
il ragionamento è simile al mio solo che
se usi la tua "formula" vien fuori un risultato >1 il che non è possibile
se fai un ripasso veloce delle frazioni scoprirai che scrivere
16*16*16*16*17/21 non è la stessa cosa di scrivere (16/21)*(16/21)*(16/21)*(16/21)*(17/21)
:D vabbè diciamo che hai scritto male io a prima botto non moltiplicherei per 17/21 ma dividerei però non so se giusto
Wilcomir
09-05-2008, 19:14
è in questo calcolo dove tieni conto che deve essere una stringa di 4 consonanti?
anche perchè non credoci siano così tante stringhe di 4 consonante in 20 caratteri tu più che altro hai tenuto conto delle stringhe di 20 caratteri possibili che altro non è 21^20
a me quella sembra la probabilità che siano tutte consonanti più che altro
allora, segui il mio ragionamento. in effetti un errore l'ho fatto, ora mi correggo e mi spiego meglio.
definendo la probabilità come casi favorevoli fratto casi possibili, per trovare la probabilità di un dato evento è sufficiente calcolare quanti sono i casi in cui si verifica e quanti sono i casi totali.
sul fatto dei casi totali direi che siamo tutti daccordo, al primo posto 21 possibilità, per ognuna di queste altre 21 al secondo posto e così via, fino al 20esimo posto. si deduce che:
Cp = 21^20 = 278.218.429.446.951.548.637.196.401
detto questo, mettiamo da parte i casi possibili. passiamo ad analizzare i casi favorevoli, ovvero i casi in cui abbiamo almeno quattro consonanti messe in fila in qualsiasi punto della stringa. ponendo questa condizione noi non facciamo altro che fissare in qualche modo 4 caratteri consecutivi della nostra stringa, in una posizione che varia dalla 1 alla 17 (17 posizioni). se pensiamo ad una semplice stringa di 4 caratteri forse è più chiaro: le consonanti sono 16, quindi noi abbiamo 16^4 possibili quartetti. ognuno di questi può essere posto in una qualsiasi delle 17 posizioni, quindi noi avremo 17 * 16^4 stringhe valide, la disposizione del resto delle lettere infatti non ci interessa: da cui
Cf = 17 * 16^4 = 1.114.112
spero di aver chiarito la faccenda... anche se a dirti la verità le stringhe favorevoli mi sembrano tremendamente poche... magari se qualcuno ha voglia di scrivere due righe di codice...
ciao!
a me quella sembra la probabilità che siano tutte consonanti più che altro
No, è la probabilità di avere 4 consonanti scelte in 4 posizioni definite, ad esempio BBBB all'inizio della stringa. Infatti si ottiene una probabilità di 5 su un milione, che è un valore molto basso.
se usi la tua "formula" vien fuori un risultato >1 il che non è possibile
Perché la formula funziona solo se gli eventi sono disgiunti, e non è questo il caso. Ad esempio avere 4 consonanti all'inizio della stringa - probabilità (16/21)^4 - non esclude la possibilità di averne altre 4 a partire dalla decima lettera.
Si può usare il principio di inclusione/esclusione (http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html) delle probabilità per cancellare sistematicamente i duplicati, ma il lavoro è complicato dalle sovrapposizioni fra diverse ripetizioni di consonanti. Ad esempio la probabilità di avere 4 consonanti in posizione 0 e in posizione 1 non è (16/21)^8 ma (16/21)^5. A parte il caso di coppie di sovrapposizioni, le combinazioni sono abbastanza complesse e non sono riuscito a trovare una formula compatta per esprimerle :stordita:
No, è la probabilità di avere 4 consonanti scelte in 4 posizioni definite, ad esempio BBBB all'inizio della stringa. Infatti si ottiene una probabilità di 5 su un milione, che è un valore molto basso.
e intendevo che 21^20 sono tutte le stringhe di 20 caratteri su un alfabeto di 21 lettere con ripetizione delle lettere e su questo non ci piove
ad ogni modo le ripetizioni le escluderei per semplicità, un numero salta fuori o no'
allora, segui il mio ragionamento. in effetti un errore l'ho fatto, ora mi correggo e mi spiego meglio.
definendo la probabilità come casi favorevoli fratto casi possibili, per trovare la probabilità di un dato evento è sufficiente calcolare quanti sono i casi in cui si verifica e quanti sono i casi totali.
sul fatto dei casi totali direi che siamo tutti daccordo, al primo posto 21 possibilità, per ognuna di queste altre 21 al secondo posto e così via, fino al 20esimo posto. si deduce che:
Cp = 21^20 = 278.218.429.446.951.548.637.196.401
detto questo, mettiamo da parte i casi possibili. passiamo ad analizzare i casi favorevoli, ovvero i casi in cui abbiamo almeno quattro consonanti messe in fila in qualsiasi punto della stringa. ponendo questa condizione noi non facciamo altro che fissare in qualche modo 4 caratteri consecutivi della nostra stringa, in una posizione che varia dalla 1 alla 17 (17 posizioni). se pensiamo ad una semplice stringa di 4 caratteri forse è più chiaro: le consonanti sono 16, quindi noi abbiamo 16^4 possibili quartetti. ognuno di questi può essere posto in una qualsiasi delle 17 posizioni, quindi noi avremo 17 * 16^4 stringhe valide, la disposizione del resto delle lettere infatti non ci interessa: da cui
Cf = 17 * 16^4 = 1.114.112
spero di aver chiarito la faccenda... anche se a dirti la verità le stringhe favorevoli mi sembrano tremendamente poche... magari se qualcuno ha voglia di scrivere due righe di codice...
ciao!
beh è correto sia bassa ad occhio così calcolata dovresti avere 4 cosonanti e il resto vocali
Xalexalex
09-05-2008, 22:05
Diciamo che se fossi stato alle olimpiadi avrei ottenuto un risultato magrerrimo :asd:
Wilcomir
09-05-2008, 22:17
beh è correto sia bassa ad occhio così calcolata dovresti avere 4 cosonanti e il resto vocali
direi che hai ragione :D
ora però sono troppo fuso, domani ho anche il compito... su calcolo combinatorio e probabilità :D:D
se mi ricordo lo chiedo alla prof :)
notte a tuttiiiiii
ciaoooo!
Cf = 17 * 16^4 = 1.114.112
spero di aver chiarito la faccenda... anche se a dirti la verità le stringhe favorevoli mi sembrano tremendamente poche... magari se qualcuno ha voglia di scrivere due righe di codice...
ciao!
mi dispiace ma è sbagliato...
infatti viene un numero davvero troppo basso come tu stesso hai notato :)
No, è la probabilità di avere 4 consonanti scelte in 4 posizioni definite, ad esempio BBBB all'inizio della stringa. Infatti si ottiene una probabilità di 5 su un milione, che è un valore molto basso.
Perché la formula funziona solo se gli eventi sono disgiunti, e non è questo il caso. Ad esempio avere 4 consonanti all'inizio della stringa - probabilità (16/21)^4 - non esclude la possibilità di averne altre 4 a partire dalla decima lettera.
Si può usare il principio di inclusione/esclusione (http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html) delle probabilità per cancellare sistematicamente i duplicati, ma il lavoro è complicato dalle sovrapposizioni fra diverse ripetizioni di consonanti. Ad esempio la probabilità di avere 4 consonanti in posizione 0 e in posizione 1 non è (16/21)^8 ma (16/21)^5. A parte il caso di coppie di sovrapposizioni, le combinazioni sono abbastanza complesse e non sono riuscito a trovare una formula compatta per esprimerle :stordita:
si sono messo come te... ho capito la logica con cui procedere... ma le combinazioni mi vengono troppe e mi perdo nei calcoli...:p
direi che hai ragione :D
ora però sono troppo fuso, domani ho anche il compito... su calcolo combinatorio e probabilità :D:D
se mi ricordo lo chiedo alla prof :)
notte a tuttiiiiii
ciaoooo!
si dai chiedi che è meglio :doh:
Non verrebbe più comodo calcolare quante stringhe possono essere composte con 4 vocali e 16 consonanti senza tenere conto dell'ordine e poi considerare lo spostamento delle vocali?
(5^4*16^16)*16
si sono messo come te... ho capito la logica con cui procedere... ma le combinazioni mi vengono troppe e mi perdo nei calcoli...:p
Facendo un po' di prove per allenare l'intuizione ho trovato questa formula per stringhe di lunghezza 9 :p
http://operaez.net/mimetex/6p^4 - 5p^5 + p^8 - p^9
dove p=16/21, e si ottiene 0.765181188. Le stringhe che hanno 4 consonanti consecutive nelle prime nove lettere sono un sottoinsieme delle soluzioni del problema, e quindi questo valore si può considerare un minorante della probabilità reale. A partire da 10 lettere ci possono essere combinazioni di tre o più gruppi con "buchi" (esempio: 4 consonanti, vocale, 5 consonanti) che rendono più difficile classificare i casi.
Ragionando sul problema tra l'altro ho ottenuto questa inaspettata uguaglianza (notando cancellazioni "magiche"):
http://operaez.net/mimetex/np^l-%5Csum_{j=0}^{n-1} %5Csum_{k=j+1}^{n-1}(-1)^j (n-k){k-1 %5Cchoose j} p^{l+k} = np^l-(n-1)p^{l+1}
Probabilmente spezzando ulteriormente le combinazioni al primo membro dovrei riuscire a trovare la formula corretta (quella riportata sopra è evidentemente sbagliata, visto che per N = n + l -1 = 20 e l = 4 supera 1 :D). Se avrò voglia proverò ad attaccare ancora il problema :p
Non verrebbe più comodo calcolare quante stringhe possono essere composte con 4 vocali e 16 consonanti senza tenere conto dell'ordine e poi considerare lo spostamento delle vocali?
(5^4*16^16)*16
la probabilita va da 0 a 1 estremi compresi ti ricordo
la probabilita va da 0 a 1 estremi compresi ti ricordo
basta dividere per il numero totale di stringhe allora:-)
basta dividere per il numero totale di stringhe allora:-)
no non viene il risultato giusto...
la difficoltà del problema sta nel fatto che la stringa deve avere ALMENO 4 consonanti consecutive, ma ne puo avere anche di piu... ad esempio 5,6... 20... e il tutto va considerato per qualsiasi posizione!
in piu bisogna poi considerare che se come molti di voi hanno provato a fare si addotta il metodo di analizzare 4 blocchi alla volta ( ovvero:
primo blocco: (16/21)^4*(21/21)^16
secondo blocco: (21/21)*(16/21)^4*(21/21)^15
ecc.ecc...
..... che alla fine dà come risultato finale 17*(16/21)^4 )
si trascura il fatto che non si considerano molti casi, ovvero tutti quelli in cui la stringa è piu lunga di 4...
se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica (quindi neanche io l'ho capito perche si basa su teoremi e metodi gia definiti)... è per questo che sono alla ricerca di un metodo piu intuitivo :sofico:
basta dividere per il numero totale di stringhe allora:-)
capisco andare a tentativi ragionando, ma sparar a caso mi sa che non ci si imbrocca
no non viene il risultato giusto...
la difficoltà del problema sta nel fatto che la stringa deve avere ALMENO 4 consonanti consecutive, ma ne puo avere anche di piu... ad esempio 5,6... 20... e il tutto va considerato per qualsiasi posizione!
in piu bisogna poi considerare che se come molti di voi hanno provato a fare si addotta il metodo di analizzare 4 blocchi alla volta ( ovvero:
primo blocco: (16/21)^4*(21/21)^16
secondo blocco: (21/21)*(16/21)^4*(21/21)^15
ecc.ecc...
..... che alla fine dà come risultato finale 17*(16/21)^4 )
si trascura il fatto che non si considerano molti casi, ovvero tutti quelli in cui la stringa è piu lunga di 4...
se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica (quindi neanche io l'ho capito perche si basa su teoremi e metodi gia definiti)... è per questo che sono alla ricerca di un metodo piu intuitivo :sofico:
io ho studiato statistica 3 anni all'itis + un esame a ing ma de ste cose proprio non ci ho mai capito un kaiser
se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica
Catene di Markov magari? Grazie per l'indizio, mi ha indirizzato verso la soluzione.
La strada dell'inclusione/esclusione è troppo complicata, sia dal punto di vista concettuale, sia dal punto di vista matematico. E' più semplice impostare il problema con questa procedura:
scorro la stringa e tutte le volte che incontro una consonante inizio a contare le consonanti adiacenti; se trovo una vocale azzero, se trovo 4 consonanti consecutive segno "successo".
Questa procedura può essere espressa come una catena di Markov. Se con "0" indichiamo "vocale" e "1" consonante gli stati possibili sono 0, 1, 11, 111, 1111. La matrice di transizione (http://en.wikipedia.org/wiki/Transition_matrix) è questa (click sul link per vedere l'immagine):
http://operaez.net/mimetex/P=%5Cleft%28%5Cbegin%7Bmatrix%7D1-p&p&0&0&0%5C%5C1-p&0&p&0&0%5C%5C 1-p&0&0&p&0%5C%5C1-p&0&0&0&p%5C%5C0&0&0&0&1%5Cend%7Bmatrix%7D%5Cright%29
L'elemento in posizione i,j indica la probabilità di passare dallo stato i allo stato j, ad esempio a(1,2) è la probabilità di trovare una consonante dopo una vocale (=p). Le probabilità della matrice esprimono essenzialmente questo: la probabilità di trovare una vocale è 1-p, e se e hai meno di quattro consonanti azzeri il contatore; se trovi una consonante (con probabilità p) incrementa, e se hai quattro consonanti resta fermo (con probabilità 1).
Una catena di Markov ha bisogno di uno stato iniziale. Per semplicità prendiamo 0 (una vocale) perché non altera il numero di consonanti consecutive e perchè in questo modo il problema ha una formulazione più semplice: dopo una iterazione abbiamo il primo carattere della stringa, dopo due il secondo e così via. La probabilità di avere 4 consonanti consecutive in una stringa di 20 caratteri è quindi la probabilità di trovarsi nello stato 5 (1111) dopo 20 iterazioni.
Una proprietà molto comoda delle catene di Markov è che la matrice di transizione dalla posizione 0 alla posizione k è dato da P^k. Se la distribuzione degli stati iniziali è il vettore p, la probabilità degli stati finali è pP^k. La distribuzione iniziale in questo caso è (1,0,0,0,0) (vocale con probabilità 1) e ci interessa la probabilità finale di 1111. Quindi in pratica ci interessa l'elemento (1,5) di P^20. P^20 può essere calcolata facilmente (ad esempio usando questo sito (http://wims.unice.fr/wims/wims.cgi?module=tool%2Flinear%2Fmatrix.en)) e si ottiene il risultato finale p=0,960325735.
Con questo metodo ho scoperto un errore (segno invertito) nella formula per le stringhe di lunghezza 9 che ho riportato sopra. La formula corretta è questa:
http://operaez.net/mimetex/6p%5E4%20-%205p%5E5%20-%20p%5E8%20+%20p%5E9
Catene di Markov magari?
esattamente, complimenti per la soluzione :D
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.