[logica] stringa di 20 lettere...

[mamo139]

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]

Posta in uno dei thread in rilievo: aiuti in informatica (no programmazione) oppure aiuti in matematica.

[mamo139]

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

[checo]

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

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]

Fico. Esercizio tipico da olimpiadi

Allora, tutte le possibili stringhe sono 21! (inteso come 21 fattoriale ovviamente )

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

Qualche espertone corregga magari

[mamo139]

@ checo: non ho capito cosa intendi per x e poi x/2 x/3 ecc...

@ Alessandro::Xalexalex: la stringa da 20 lettere ammette ripetizioni
quindi non è vero che tutte le combinazioni sono 21!
tutte le combinazioni sono 20^21

[Xalexalex]

Originariamente inviato da mamo139

@ checo: non ho capito cosa intendi per x e poi x/2 x/3 ecc...

@ Alessandro::Xalexalex: la stringa da 20 lettere ammette ripetizioni
quindi non è vero che tutte le combinazioni sono 21!
tutte le combinazioni sono 20^21

Uh è vero
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!

[mamo139]

Originariamente inviato da Alessandro::Xalexalex

Uh è vero
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]

Giusto! Allora aggiungerei un fattore 19*18*17 al denominatore , right?

[mamo139]

che risultato ti esce che ho fatto un po di confusione sui tuoi calcoli?

[Wilcomir]

Originariamente inviato da mamo139

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!

[checo]

Originariamente inviato da Wilcomir

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

[checo]

Originariamente inviato da Alessandro::Xalexalex

Fico. Esercizio tipico da olimpiadi

Allora, tutte le possibili stringhe sono 21! (inteso come 21 fattoriale ovviamente )

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

Qualche espertone corregga magari

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)
vabbè diciamo che hai scritto male io a prima botto non moltiplicherei per 17/21 ma dividerei però non so se giusto

[Wilcomir]

Originariamente inviato da checo

è 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!

[Banus]

Originariamente inviato da checo

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.

Originariamente inviato da checo

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 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

[checo]

Originariamente inviato da Banus

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'

[checo]

Originariamente inviato da Wilcomir

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]

Diciamo che se fossi stato alle olimpiadi avrei ottenuto un risultato magrerrimo

[Wilcomir]

Originariamente inviato da checo

beh è correto sia bassa ad occhio così calcolata dovresti avere 4 cosonanti e il resto vocali

direi che hai ragione

ora però sono troppo fuso, domani ho anche il compito... su calcolo combinatorio e probabilità

se mi ricordo lo chiedo alla prof

notte a tuttiiiiii

ciaoooo!

[mamo139]

Originariamente inviato da Wilcomir

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

Originariamente inviato da Banus

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 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

si sono messo come te... ho capito la logica con cui procedere... ma le combinazioni mi vengono troppe e mi perdo nei calcoli...

Originariamente inviato da Wilcomir

direi che hai ragione

ora però sono troppo fuso, domani ho anche il compito... su calcolo combinatorio e probabilità

se mi ricordo lo chiedo alla prof

notte a tuttiiiiii

ciaoooo!

si dai chiedi che è meglio