Riepilogo di Metodi Matematici per Informatica

∩B

b. L'unione di due insiemi è data dagli elementi sia di A che di B presi insieme e si

∪

scrive A B c. La differenza A-B è data da tutti gli elementi di A non in comune con B

Esempio: nei numeri naturali IN

A=numeri dispari e B=numeri pari

A∩B=0, cioè insieme vuoto

∪

A B= IN, cioè tutto l'insieme dei naturali

A-B=numeri dispari

B-A=numeri pari

A-B è detta anche complementare di B rispetto ad A

11. Prodotto cartesiano: dati due insieme A e B il prodotto cartesiano AXB è l'insieme

formato da tutte le coppie (a,b) con a€A e b€B

es: A = {5,6,4} B= {9,5}

AXB={(5,9),(5,5),(6,9),(6,5),(4,9),(4,5)}

12. Relazioni tra insiemi: la relazione R tra due insiemi A e B è un sottoinsieme del

prodotto cartesiano AXB.

Le relazioni possono essere d'equivalenza o d'ordine

Le relazioni sono d'equivalenza quando godono delle proprietà:

-Riflessiva: aRa (a è in relazione con a)

-Simmetrica: aRb => bRa (a è in rel con b e b è in rel con a)

-Transitiva: aRb e bRc => aRc (se aRb e bRc allora anche aRc)

Esempio: A = {1,2,3,4}

R1 = {(1,1),(2,2),(3,3),(4,4)} → riflessiva

R2 = {(1,2),(2,1),(1,3),(3,1)} → simmetrica

R3 = {(1,2),(2,4),(1,4)} → transitiva

Le relazioni d'ordine invece hanno queste tre proprietà

-Riflessiva: aRa (a è in relazione con a)

-Antisimmetrica: aRb e bRa <=> a=b(a è in rel con b e b è in rel con a solo se a=b)

-Transitiva: aRb e bRc => aRc (se aRb e bRc allora anche aRc)

Esempio: A = {1,2,3,4}

R1 = {(1,1),(2,2),(3,3),(4,4)} → riflessiva

R2 = {(2,2),(4,4)} → antisimmetrica

R3 = {(1,2),(2,4),(1,4)} → transitiva

Ordine parziale

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(1,3)}

riflessiva = si

antisimmetrica = si

transitiva = si (1,2),(2,3),(1,3)

Ordine totale

{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(1,4),(4,1),(2,3),(3,2),(2,4),(4,2),(3,4),

(4,3)} → tutte e tre le proprietà esistono e vengono presi tutti i valori

L'ordine si dice stretto nel caso in cui le proprietà di cui gode la R sono solo

asimmetrica cioè aRb => ¬ (bRa) e transitiva

es. {(1,3),(3,4),(1,4)}

| Preso un elemento a dell'insieme A, si definisce classe d'equivalenza un

sottoinsieme che contiene almeno l'elemento a stesso e si indica con [a] |

Le classi d'equivalenza devono

Essere dei sottoinsiemi non vuoti

Essere a 2 a 2 disgiunti, cioè devono dare un'intersezione vuota

La loro unione deve formare tutto l'insieme

13. Funzioni iniettive, suriettive e biunivoche.

I: quando ad ogni elemento di A corrisponde uno ed un solo elemento di B

S: quando ogni elemento di B è immagine di almeno un elemento di A

B: quando sono sia I che S

Condizioni

Iniettive |A|≤ |B| cioè cardinalità di A ≤ quella di B

Suriettive |A|≥|B| cioè cardinalità di A ≥ quella di B

Biunivoche |A|=|B| cioè cardinalità di A = quella di B

Cardinalità = numero degli elementi di un insieme

14. Principio di induzione e funzioni ricorsive:

Il principio di induzione serve a verificare che se per un determinato valore

assegnato ad n (per esempio 1) allora il predicato deve essere vero per (n+1)

Si dimostra ponendo due casi:

1. base dove, in genere, n=1, quindi basta sostituire 1 alla variabile n

2. per induzione, ponendo n=n+1

Esempio:

A = 5·3n + (−3)n.

n

per n=1 dimostrare che A =12

n

per n≥2 dimostrare che vale 9a n−2

quindi primo caso 5*3*1+(-3)*1 = 15-3 = 12

n n

secondo caso, aumentiamo di 1 la n in 5·3 + (−3) e diventa:

(n+1)

(n+1) (n+1) (n+1)

5*3 +(-3) = [3 ](5-1)= 4*3

aumentiamo di 1 la n in 9a e diventa 9a = 9a

n−2 n−2+1 n−1

n n (n-1) (n-1)

ci troviamo a da A = 5·3 + (−3) , quindi diventa 5*3 +(-3) =

n−1 n

(n-1) (n-1)

=3 (5-1)=4*3 (n-1)

ora sostituiamo in 9a il valore 4*3

n−1

(n-1) 2 2 (n-1) n-1+2 2 n+1

9(4*3 ) = 3 (2 *3 )=3 *2 =4*3

Nel secondo caso dell'induzione dobbiamo dimostrare che, oltre il caso base, il

nostro predicato sia vero per valori n-1 e n-2 (successioni ricorsive)

Una successione ricorsiva e una successione che ripete le operazioni precedenti per

ogni valori n e la più classica successione ricorsiva e la Successione di Fibonacci:

0 1 1 2 3 5 8 13 21 34 ….

dove fissati 0 e 1 come valori iniziali, gli altri valori vengono dati dalla somma dei

due precedenti

f(n)=0 se n = 0

f(n)=1 se n = 1

f(n)=(n-1)+(n-2) se n≥2 e ripetiamo sempre quest'operazione all'aumentare di n

Stesso discorso per la Torre di Hanoi dove noi dobbiamo ricorsivamente eseguire questi tre

passaggi:

Spostare n-1 dischi da A in B usando C come appoggio

Spostare il disco grande in C

Spostare n-1 dischi da B in C usando A come appoggio

e ripetere questi tre step fino al completamento del gioco

15. Disposizioni e combinazioni

Principio delle scelte multiple: serve per contare gli elementi di un insieme finito,

– almeno in alcuni casi particolari

Principio per 2 variabili:

– ogni elemento di A dipende dal valore di 2 variabile x e x

– 1 2

il numero di valori possibili di x è = a h

– 1 1

fissato un valore di x , il numero di valori possibili di x è h

– 1 2 2

quindi il numero di elementi di A è uguale a h h

1 2

Per k variabili ogni elemento di A dipende dai valori di n variabili x , x , …, x

1 2 n

il numero di valori possibili di x è = a h

– 1 1

fissato un valore di x , il numero di valori possibili di x è h

– 1 2 2

fissato un valore di x , il numero di valori possibili di x è h

– 2 3 3

fissato un valore di x , il numero di valori possibili di x è h

– n n+1 n+1

DISPOSIZIONI: di classe m degli n elementi un qualunque modo di scegliere

ordinatamente m tra gli n elementi

Posso essere semplici o con ripetizione

Semplici = D = n*m

n,m rn,m m

Con Ripetizione = D = n

Se n=m si parla di Permutazioni: sono tutti i diversi modi di disporre in ordine gli n

elementi dati e si calcola con n! (fattoriale) = n(n-1)(n-2)...(n-m+1)

COMBINAZIONI: Siano n, m due numeri naturali qualunque e A un insieme di cardinalità

n, contenente gli n elementi distinti, una combinazione di classe m degli n elementi è un

qualunque modo di scegliere m tra gli n elementi dati senza tener conto dell'ordine.

Possono essere semplici o con ripetizione:

n

Semplici = C = ( ) (n sopra m) coefficiente binomiale

n,m m n + m – 1

rn,m

Con Ripetizione = C = ( )

n – 1

Proprietà del coefficiente binomiale

TRIANGOLO DI TARTAGLIA-PASCAL