Visualizzazione post con etichetta informatica. Mostra tutti i post
Visualizzazione post con etichetta informatica. Mostra tutti i post

Alcuni problemi di calcolo combinatorio (draft)

Consideriamo un insieme A finito di n elementi:

$\huge A = \{ a_1, a_2, ..., a_n \}$

Gli elementi dell'insieme A potrebbero ad es. essere le 52 carte di un mazzo da gioco (13 per ogni seme ad esclusione dei jolly) oppure ancora le 26 lettere dell'alfabeto.

Questi elementi possono essere combinati: ad esempio dall'insieme delle lettere possiamo formare parole oppure possiamo estrarre in vari modi 5 carte dal mazzo da gioco.

I modi per combinare gli elementi sono 2:

  • non ammettendo duplicati: ad es. $a_1, a_1, a_5$ non è ammesso perchè $a_1$ è presente 2 volte, mentre $a_3, a_5, a_9$ è ammessa perchè ogni elemento è preso 1 volta sola. Non ammettendo duplicati possiamo combinare fino a un massimo di n elementi (dove n è il numero di elementi dell'insieme)
  • ammettendo duplicati: possiamo avere ad. es $a_1, a_1, a_2$ (in cui $a_1$ è presente 2 volte). Ammettendo duplicati possiamo avere combinazioni con un numero qualsiasi di elementi (anche maggiore di n).

Le combinazioni possono essere di 2 tipi:

  • ordinate: e' importante l'ordine degli elementi. La combinazione $a_1, a_3, a_5$ è differente da $a_5, a_3, a_1$ anche se ha gli stessi elementi.
  • non ordinate: l'ordine non e' importante. La combinazione $a_1, a_3, a_5$ è uguale a $a_5, a_3, a_1$ perchè ha gli stessi elementi.

Le ordinate sono dette permutazioni, le non ordinate combinazioni .

Ora chiediamoci:

Non ammettendo duplicati quante combinazioni ordinate posso avere?

Estraiamo una carta dal mazzo senza rimetterla nel mazzo. La 1° estrazione avrà quindi 52 combinazioni possibili (52 - 1 + 1). La 2° avrà 51 estrazioni possibili (52 - 2 + 1). La terza 50, e così via fino all' r° estrazione che avrà 52 - r + 1 possibili estrazioni.

Il numero di combinazioni possibili per r estrazioni da un insieme di n elementi sarà quindi:

E = n * (n-1) * ... * (n-r+1)

Ricordando che il fattoriale di un numero n è:

n! = n * (n-1) * (n-2) * ... * 2 * 1

Possiamo riscrivere E in questo modo:

$\huge{E=\frac{n*(n-1)*...*(n-r+1)*(n-r)*(n-r-1)*...*2*1}{(n-r)*(n-r-1)*...*2*1}}$

che può essere riscritta come:

$\huge{E=\frac{n!}{(n-r)!}}$

Non ammettendo duplicati quante combinazioni non ordinate posso avere?

Nella sezione precedente abbiamo calcolato il numero di estrazioni ordinate e distinte. Queste estrazioni distinte possono essere raggruppate in estrazioni con gli stessi elementi. Ad esempio:

Con r=3 possiamo avere a_2, a_5, a_7 oppure a_5, a_2, a_7, oppure a_7, a_5, a_2 etc. che nel passo precedente sono conteggiate esattamente 6 volte.

Gli elementi a_2, a_5, a_7 possono essere considerati come un insieme di cui vogliamo calcolare il numero di combinazioni possibili. In questo caso n=3 e r=3.

Le combinazioni conteggiate nella sezione precedente possono quindi essere raggruppate per stessi elementi che andranno quindi conteggiati 1 sola volta.

In sostanza, in questo caso avremo:

$\huge{EN=\frac{E}{r!}=\frac{n!}{(n-r)!*r!}}$

Ammettendo duplicati quante combinazioni ordinate posso avere?

Estraiamo una carta dal mazzo, prendiamo nota e la rimettiamo nel mazzo. Poi passiamo all'estrazione successiva comportandoci allo stesso modo fino a r estrazioni.

Se r = 1 abbiamo 52 possibili combinazioni. Se r = 2 ogni singola carta del mazzo della prima estrazione può essere combinata con 52 possibili carte della seconda estrazione. Avremo quindi 52^2 combinazioni. Più in generale, considerando con n come il numero di elementi dell'insieme di partenza e con r il numero di estrazioni avremo:

E = n^r

Ammettendo duplicati quante combinazioni non ordinate posso avere?

Per dimostrare questo caso ci si riconduce a quello delle "combinazioni ordinate che non ammettono duplicati"

Supponiamo voler contare in quanti modi possiamo formare 3 sottoinsiemi a partire dagli elementi dell'insieme A= {a, b, c, d, e}. Ad es. {a, b}, {c, d}, {e} oppure {a}, {b,c}, {d, e}

Possiamo rappresentare gli elementi dell'insieme e i gruppi utilizzando | (barre). Ad es.:

a b | c d | e ({a,b}, {c,d}, {e}) oppure | | a b c d e (vuoto, vuoto, {a,b,c,d,e})

per creare i 3 gruppi ci servono 3 - 1 = 2 barre.

Considerando le barre come elementi distinti possiamo ricondurci alla situazione delle combinazioni ordinate che non ammettono duplicati. Supponiamo che l'insieme di partenza abbia n elementi, e il numero di gruppi sia r allora: ( (n+r-1)! | r! ) <- binomiale

Backus-Naur Form / BNF e EBNF

La notazione di Backus-Naur (conosciuta come BNF o Backus-Naur Form) è un metodo matematico formale usato per descrivere la sintassi di un linguaggio.

Il metodo prende il nome dal suo inventore, John Backus, che lo utilizzò per descrivere la sintassi del linguaggio di programmazione Algol 60.

In che modo si descrive il linguaggio?

Attraverso la BNF definiamo la grammatica del linguaggio (ciò che è permesso o non è permesso fare) in maniera formale (senza ambiguità e in maniera "esatta"). Più semplicemente possiamo considerarla come un gioco matematico che funziona in questo modo:

Si parte con un simbolo che chiamiamo S e vengono fornite le regole (dette regole di produzione) per rimpiazzare questo simbolo con altri simboli o stringhe (le stringhe sono dette valori terminali).

Le regole di produzione hanno la forma seguente:

simbolo := alternativa1 | alternativa2 | ... | alternativaN

e indicano i modi in cui può essere rimpiazzato il simbolo ( indicato a sinistra del := ).

Con := si indica: "ciò che è alla mia sinistra si trasforma in una delle alternative che ho indicato alla mia destra".

Le alternative (separate da | ) possono essere altri simboli o valori terminali:

I simboli (non terminali) hanno sempre regole di produzione (devono essere sostituiti con altro)

I valori teminali non hanno regole di produzione ( non possono essere sostituiti con altro e quindi non si troveranno mai a sinistra del := ) e pertanto terminano il processo di produzione.

Esempio

Vediamo di chiarire meglio la BNF con un esempio. Utilizziamo la BFN per descrivere la grammatica della scrittura di un numero: ad esempio 34.6 oppure -4 oppure -45.35 .

S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

I simboli sono abbreviazioni per: S è il simbolo iniziale (dal quale si partirà con le produzioni), FN (Fractional Number) è il numero frazionario, DL (Digit List) è un elenco di numeri (da 0 a 9, es. 12345), D (Digit) è un numero da 0 a 9.

Vediamo come produrre il numero 3.14 con la grammatica descritta nell'esempio:

  1. S - partiamo sempre dal simbolo iniziale. Abbiamo 2 scelte: una per rappresentare numeri negativi e l'altra positivi. 3.14 è positivo quindi:
  2. FN - per FN abbiamo 2 scelte: una per numeri interi e l'altra per numeri frazionari. 3.14 è un numero frazionario, quindi:
  3. DL '.' DL - prendiamo il primo DL. DL può essere o un numero (singolo) o un numero seguito da un elenco numeri. 3 di 3.14 che è prima del . è un singolo numero. Quindi:
  4. D '.' DL - D è un valore terminale che va quindi sostituito con il 3 di 3.14 . Quindi:
  5. 3 '.' DL - riprendiamo il secondo DL che avevamo lasciato in sospeso. Dobbiamo rappresentare il 14 di 3.14 . DL può quindi essere o un singolo numero (D ma non è questo il caso) oppure un singolo numero seguito da un elenco di numeri (D DL). Quest'ultima trasformazione è ciò che interessa. Quindi:
  6. 3 '.' D DL - l'ultimo DL rimasto deve essere trasformato in 1 singolo numero
  7. 3 '.' D D - procedendo alla sostituzione degli ultimi 2 D rimasti:
  8. 3 '.' 1 D
  9. 3 '.' 1 4

Da notare come le regole di produzione rendano impossibile una rappresentazione impropria dei numeri frazionari: ad esempio è impossibile produrre un 3..14 o un 3.1.4 .

L'esempio dimostra come in alcuni casi la BNF possa diventare complessa o di difficile lettura: ad esempio si è usata la ricorsione per rappresentare un elenco di numeri decimali (DL che produce altri DL).

Per tale motivo la BNF è stata estesa con la EBNF descritta nella sezione seguente.

EBNF: BNF estesa

L'EBNF estende la BFN descritta sopra con l'aggiunta di 3 operatori:

  • ?: indica che il simbolo che sta alla sua sinistra è opzionale (può non essere presente oppure essere presente 1 volta)
  • *: il simbolo alla sua sinistra può essere presente 0 o più volte (a differenza di ? dove il simbolo può essere presente 1 sola volta, in questo caso piò essere presente anche più di una volta)
  • +: il simbolo alla sua sinistra può essere presente o 1 sola volta o più volte. A differenza dei precedenti dove il simbolo è opzionale, in questo caso il simbolo è obbligatorio.

Con simbolo in questo caso è possibile intendere anche un gruppo di simboli raggruppati in un "unico simbolo" attraverso l'uso di parantesi.

La grammatica dell'esempio precedente può quindi essere scritta nella forma seguente (molto più abbreviata e leggibile):

S := '-'? D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Nota: l'EBNF non è più espressiva della BNF. Le regole che è possibile scrivere con la EBNF possono essere convertite nella BNF. L'EBNF è solo da intendersi come estensione utilizzata per rendere la BNF più leggibile e semplice.

Riferimenti

Sistemi di numerazione

Il modo con cui indichiamo quantità numeriche è detto sistema di numerazione decimale.
Ciò viene fatto rappresentando la quantità numerica per mezzo di 10 simboli (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) che assumono significato in base alla posizione in cui si trovano (sistema di numerazione posizionale).
Ad esempio se pensiamo al numero 123 ciò che visualizziamo mentalmente in realtà è:
$1*10^2 + 2*10^1 + 3*10^0 = 1 * 100 + 2 * 10 + 3 * 1 = 100 + 20 + 3 = 123$
che sono 1 centinaio, 2 decine e 3 unità
Nel sistema di numerazione posizionale la posizione dei simboli assume il significato descritto di seguito:
  • se ci spostiamo a sinistra, i numeri hanno un'elevazione a potenza di 10 crescente
  • se ci spostiamo a destra si ha una potenza di 10 decrescente.
In altri termini: non avendo a disposizione infiniti simboli per rappresentare infinite quantità differenti si tende a raggruppare per potenze del numero di simboli disponibili.
Con 10 simboli possiamo indicare assenza di unità, 1 unità, 2 unità ..., 9 unità. Ma non si ha un simbolo per rappresentarne 10.
La soluzione è quindi raggruppare i 10 non rappresentabili in 1 gruppo ed indicarlo sempre con i simboli disponibili ma spostato di una posizione più a sinistra.
10 è quindi da intendersi come: 1 gruppo di 10 + 0 elementi.

Esempi

33 elementi: raggruppiamo le unità in 3 gruppi da 10 + 3 elementi
99 elementi: 9 gruppi da 10 + 9.
111 elementi: 11 gruppi da 10 + 1 elemento non è possibile perchè non abbiamo alcun simbolo per rappresentare l' 11. Soluzione: stesso trucco, raggruppiamo gli 11 in 1 gruppo di 10 gruppi di 10 elementi, al quale aggiungiamo 1 gruppi di 10 elementi, al quale aggiungiamo 1 elemento. Quindi il gruppo di 10 gruppi di 10 elementi sarà indicato di una posizione ancora più a sinistra dando quindi: 111 dove:
  • il primo 1 indica 1 gruppo di 10 gruppi di 10 elementi
  • il secondo 1 indica 1 gruppo di 10 elementi
  • il terzo 1 indica 1 elemento

Rappresentazione di numeri decimali

Estendendo il discorso con il numero decimale 123,45 in realtà si intende:
1*10^2 + 2*10^1 + 3*10^0 + 4 * 10^-1 + 5 * 10^-2 = 1 * 100 + 2 * 10 + 3 * 1 + 4 * 0,1 + 5 * 0,01 = 100 + 20 + 3 + 0,4 + 0,05 = 123,45

Altri sistemi di numerazione e sistema di numerazione binario

Il sistema di numerazione decimale non è l'unico possibile. Siamo liberi di rappresentare quantità con il numero di simboli che vogliamo. Questo numero sarà quindi la nuova base del nostro elevamento a potenza (che usiamo per indicare i raggruppamenti, raggruppamenti di raggruppamenti, ... e così via).
Ad esempio possiamo inventarci un sistema che abbia solo 2 simboli: 0 e 1. In tal caso il numero 101 è da interpretarsi in questo modo:
1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 1 * 4 +0 * 2 + 1 * 1 = 4 + 0 + 1 = 5
Il sistema a soli 2 simboli è detto sistema di numerazione binario ed è utilizzato praticamente da tutti gli elaboratori esistenti: rappresenta 2 livelli di tensione es. 0V e 5V .
Un altro sistema in uso e' il sistema di numerazione esadecimale. Questo sistema utilizza 16 simboli che sono 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f .
Dove ad es. 5 rappresenta 5 unità, a rappresenta 10 unità, f rappresenta 15 unità.
Per rappresentare 16 unità si scriverà 10 : 1 gruppo di 16 elementi (i simboli sono 16 incluso lo 0 quindi non abbiamo simbolo per rappresentare il 16) + 0 elementi .
Ultimo esempio:
1FA = 1 * 16^2 + 15 * 16 ^ 1 + 10 * 16^0 = 256 + 240 + 10 = 506

Come convertire una rappresentazione da sistema decimale ad altro sistema numerico

Partiamo dall'ultimo esempio per il quale abbiamo visto che 1FA in rappresentazione esadecimale è 506 in rappresentazione decimale e vediamo di fare il procedimento inverso: partiamo da 506 e dobbiamo arrivare a 1FA.

Abbiamo detto che il sistema esadecimale utilizza 16 simboli e dove abbiamo una quantità che non è rappresentabile con un simbolo si raggruppa.

506 non ha un simbolo che lo rappresenti. Proviamo a vedere quanti gruppi di 16 abbiamo: 506/16 = 31 gruppi da 16 + 10 unità . 31 non è rappresentabile quindi procediamo ricorsivamente a raggruppare gruppi di 16: 31/16 = 1 gruppo di 16 gruppi di 16 unità + 15 gruppi da 16 unità + 10 unità.

Abbiamo quindi:

  • 1 gruppi di 16 gruppi di 16 unità rappresentabile in esadecimale con il simbolo 1
  • 15 gruppo di 16 unità rappresentabile in esadecimale con il simbolo F
  • 10 unità rappresentabili in esadecimale con il simbolo A

Partendo quindi dal raggruppamento più grande abbiamo 1FA.

Lettori fissi

 
DISCLAIMER: Questo blog non costituisce una testata giornalistica. Non ha carattere periodico ed è aggiornato secondo la disponibilità e la reperibilità dei materiali. Pertanto non può essere considerato in alcun modo un prodotto editoriale ai sensi della Legge. n. 62 del 2001.
COPYRIGHT: Tutti i diritti sui testi/contenuti presenti su questo blog sono di proprietà dell'autore. Per utilizzare il materiale contattarmi all'indirizzo: nevit76@gmail.com