Algebra e Geometria

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

ALGEBRA E GEOMETRIA

DIDATTICA Lunedì 14 Settembre 2020

Questo corso serve per costruzioni crittogra che, che cerchino di garantire segretezza dei dati,

pur garantendo un servizio.

L’algebra si occupa della trasformazione delle strutture, quasi tutto si può rappresentare

algebricamente. Ogni programma lavora con l’algebra.

La geometria è un’applicazione dell’algebra, nasce dalle strutture algebriche, che vengono

visualizzate tramite rappresentazione geometrica.

La geometria fornisce un’intuizione, dà l’dea della situazione, l’algebra, tramite procedure

standard, veri ca ciò che la geometria rappresenta.

Quasi tutta la matematica parte da situazioni concrete per creare modelli, in modo tale da

analizzarli.

NOZIONI PRELIMINARI

Il linguaggio degli insiemi

Teoria degli insiemi: l’insieme è una collezione di oggetti su cui si possono dare predicati. La

teoria assiomatica consente di de nire in modo rigoroso gli insiemi.

a ∈ A a ∉ A x ∉ A

L’insieme A: collezione di oggetti tale che ha senso il predicato o o .

A nito: A = a, b, c, d

L’insieme può essere de nito dando l’elenco dei suoi elementi o in termini di sottoinsieme di un

insieme dato: A 2n n Z

∈

Insiemi numerici:

N insieme numeri naturali (>0)

• N₀ insieme numeri naturali incluso lo zero

• Z insieme numeri interi

• Q insieme numeri razionali

• R insieme numeri reali

• C insieme numeri complessi a+ b a, b R

• ∈

N ⊆ N ⊆ Z ⊆ Q ⊆ R ⊆ C

0 a + i

Fra gli elementi di C possiamo trovare quelli della forma e questi si comportano come

0

a

numeri reali. Tra i numeri reali esistono quelli che si scrivono con a, b interi

b

Tutta l’analisi numerica a ronta il problema di approssimare un numero in numeri reali

A ⊆ B ↔ ∀a ∈ A, a ∈ B Pagina 1

fi fi fi ff ℹ︎ fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

A ⊆ B i due insiemi possono essere uguali

A ⊂ B ↔ A ⊆ B, A ≠ B ∀a ∈ A, a ∈ B ∃b ∈ B : b ∉ A

, che si può dire anche allora

A = B ↔ A ⊆ B ∧ B ⊆ A

↔ ∀a ∈ A : a ∈ B

↔ ∀b ∈ B : b ∈ A

Operazioni fra insiemi

A ∩ B a ∈ A a ∈ B

: intersezione tra A e B (elementi che appartengo sia ad A che a B), cioè ⎮

A ∪ B : unione tra A e B (elementi che appartengono ad almeno uno dei due insiemi), che signi ca

x x ∈ A x ∈ B

oppure

⎮

A\B : di erenza tra a e B, insieme elementi che appartengono ad A e non a B

x ∈ A ∧ x ∉ B

A\B = x ⎮

A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) distributività di rispetto a

∩ ∪

A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C ) distributività di rispetto a

∪ ∩

Applicazioni tra insiemi

Cos’è una coppia ordinata? Siano A, B insiemi

a ∈ A, b ∈ B

(a, b) con . Conta l’ordine e sono ammesse ripetizioni

(a, b) = a , a, b (è un insieme)

(a=b) => (a, b) = {{a}}

a ≠ b => (a, b) => { {a} , {a, b} } Tutti i casi sono distinti

(b, a) => {b} , {a, b} }

A × B = (a, b) a ∈ A, b ∈ B è il prodotto cartesiano, ovvero l’insieme delle coppie

⎮

ordinate aventi il primo elemento in A e il secondo in B.

Terminologia: a, b, c

• insieme di elementi (a, b, c . . . )

• Sequenze di elementi

[a, b, c . . . ]

• Sistema di elementi Collezione di oggetti

a, b, c a, c, b a, a, b, c

• Insieme non ordinato senza ripetizioni = = (in un insieme

se ci sono due elementi ripetuti, se ne tiene uno solo; l’ordine di scrittura non conta). Questi

insiemi sono equivalenti.

Sistema (detto anche mulitinsieme), è una collezione non ordinata con ripetizioni (l’elemento

• può comparire n volte) [a, b, c] = [a , c, b] ≠ [b , c, a]

Sequenza: è una collezione di oggetti ordinata e con ripetizione

• (a, b, c) ≠ (a, c, b) ≠ (a, a, b, c)

Liste (o array): è una sequenza, de nibile attraverso le coppie ordinate. Una sequenza di n

• a a a , a

≈

elementi (a₁, a₂ , …, a , a ) l’insieme di tutte le coppie ( , ( ,…, ( )))…)

n−1 n 1 2 n−1 n

n

A A × A × . . . × A

≈

In generale A insieme = insieme di tutte le sequenze di elementi di A di

lunghezza n.

n

A a × . . . × a i = 1...n, a ∈ A

= ( ) ⎮∀

1 n i

A × (A × A) a ∈ A

= (a₁, (a₂,a₃) ) ⎮ i

(A × A) × A a ∈ A

= ( (a₁,a₂), a₃) ) Sono diversi, ma si comportano allo stesso modo

⎮ i

NB: IL PRODOTTO CARTESIANO DI INSIEMI NON E’ ASSOCIATIVO Pagina 2

ff fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

C ⊆ A × B

De nizione: siano A e B insiemi, si dice corrispondenza fra A e B ogni .

C : A → B

Due corrispondenze coincidono se e solo se quando sono de nite dagli stessi insiemi (stesso

A × B

dominio A e codominio B) e contengono li stessi valori del prodotto cartesiano .

De nizione: una corrispondenza C è detta

∀a ∈ A ∃b ∈ B : (a, b) ⊆ C

Ovunque de nita se

• ∃

∀a ∈ A b ∈ B : (a, b) ⊆ C

Funzionale se (esiste al più 1) (se da ogni A

• ≤1

parte al più una freccia) Pagina 3

fi

fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

∀b ∈ B ∃a : (a, b) ⊆ C

Suriettiva se (ad ogni B arriva almeno una freccia)

• ∀b ∈ B ∃ a ∈ A : (a, b) ∈ C

Iniettiva se (ad ogni elemento di B arriva al più

• ≤1

una freccia)

De nizione: C è detto funzione da A in B se C è funzionale e ovunque de nita

C : A → B

C è detto biunivoco se C funzione iniettiva e suriettiva

A × B

Osservazione: Una funzione è sottoinsieme di che soddisfa le proprietà di essere funzione

e ovunque è de nita. Mercoledì 16 Settembre 2020

Sono tabelle di elementi suddivisi in righe e colonne

m × n m × n

a coe cienti in k una tabella di elementi disposti in m righe ed n colonne.

De niamo le matrici ad m righe ed n colonne

Mat ( )

m,n

1 ≤ i ≤ m

Indice di riga 1 ≤ j ≤ n

Indice di colonna Mat ( )

Matrice quadrata SE m=n n

Matrici quadrate particolari Pagina 4

fi

fi ffi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

a = 0 ∀i > j

Triangolare superiore se (triangolo superiore alla diagonale

• i, j

principale, tutti gli elementi al di sotto della diagonale principale sono nulli)

a = 0 ∀j < i

Triangolare inferiore se (tutti gli elementi al di sopra della diagonale

• i, j

principale sono nulli)

a = 0 ∀i ≠ j

Diagonale se (tutti gli elementi al di fuori della diagonale principale

• i, j

sono nulli) a = k

Scalare, è una matrice diagonale con

• i, j

• Identica di ordine n, detta anche matrice identità (deve essere diagonale

a = 1

e , ovvero tutti 1 sulla diagonale principale e zero altrove)

i,i

0 a = 0 ∀i, j

Nulla se (tutti gli elementi sono nulli; la matrice diagonale sia

• i, j

triangolare superiore che inferiore) T t

Mat ( ) A A

Data A appartenente si dice trasposta di A , o , ottenuta da A scambiando le

m,n

righe con le colonne.

1 3

A = 2 -4

0 1

T

A ∈ Mat ( )

m,n T

A = A

Si dice simmetrica se . Per essere simmetrica deve essere quadrata, ovvero m=n

2 3 2 3

T

A

A = =

3 1 3 1

Operazioni fra matrici: A, B ∈ Mat ( ) C = A + B

Addizione: si dice somma di A e B la , con C

• m,n

Mat ( ) C := a + b SOMMO SE HA STESSA

, i cui elementi

m,n i, j i, j i, j

DIMENSIONE E SE SI ESTENDE PER UN n FINITO DI MATRICI.

• Vale la proprietà:

• Associativa

• Commutativa

∃ 0 A + 0 = A

• elemento neutro :

∃ −a

elemento opposto -A = ( ) e -A+A=0

• i, j

T T T

(A + B) A + B

• =

(Mat ( ), + ) è gruppo abeliano

m,n

Prodotto di una matrice per uno scalare:

A ∈ Mat (K ) k ∈ K

Serve una matrice e .

m,n

C = K ⋅ A ∈ Mat ( ) C = k ⋅ a

È prodotto K per A: . Vale la proprietà:

n i, j i, j

k ⋅ A = A ⋅ k

• h ⋅ (k ⋅ A) = h k ⋅ A

• K ⋅ (A + B) = k A + k B

• (h + k) ⋅ A = h A + k A

• T T

(k A) = k A

•

Prodotto tra due matrici (prodotto righe per colonne):

A ∈ Mat ( ) B ∈ Mat ( )

e , il prodotto di righe per colonne di A per B è

m,p p,n Pagina 5

è

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

C = A ⋅ B ∈ Mat ( ) C

, dove si trovano sommando i prodotti termine a termine della i-

m,n i, j LE RIGHE DI A DEVONO ESSERE DELLO STESSO

esima riga di A per la j-esima colonna di B.

NUMERO DI COLONNE DI B.

• NON vale la proprietà commutativa! A ⋅ B = 0

Osservazione: non vale la legge dell’annullamento del prodotto; infatti se ho ciò non

signi ca necessariamente che A o B siano matrici nulle.

Calcolo determinante

(di matrici quadrate!)

| |

A ∈ Mat ( ) A

) , o det(A)

n ∈

A è scalare k K

Come si calcola? | |

A ∈ Mat ( ) A = il valore dell’unico elemento che contiene; A(4) |A|=4

• 1

A ∈ Mat ( ) il suo determinate è dato dalla di erenza tra il prodotto degli elementi

• 2

sulla diagonale principale e il prodotto di quelli sulla diagonale secondaria

A ∈ Mat ( ) SARRUS

• 3

1. Accosto a destra della matrice la prima e la seconda colonna

2. Sommo i prodotti degli elementi della diagonale principale con i

prodotti degli elementi delle sue due sovradiagonali

3. Da 2. sottraggo i prodotti degli elementi della diagonale secondaria e i

prodotti degli elementi delle sue due sottodiagonali

• Se è una triangolare superiore, il determinante è il prodotto di tutti gli elementi

della diagonale principale

| |

I = 1 ∀n ≥ 2

Matrice diagonale: ha

• n Giovedì 17 Settembre 2020

A ∈ Mat ( ) n ≥ 2 REGOLA DI LAPLACE:

Se generica con posso usare la

n n i+j

∑ | |

| |

A = × (−1) × a × A

1. Fissata una qualsiasi riga o colonna di A, i, j i, j

j=1

A

dove è la matrice che si ottiene da A togliendo la i-esima RIGA e la j-esima

i, j

COLONNA

i+j | |

(−1) A a

De nizione: il valore è detto complemento algebrico di

i, j i, j

Osservazione: applico Laplace ssando una qualsiasi riga/colonna, ma se voglio velocizzare i

calcoli conviene scegliere, se ci sono, con il maggior numero di zeri (0) all’interno.

Proprietà dei determinanti:

| |

I ≈ A ∀ ≥ 1

1. n n

| |

A = π a

2. A triangolare/diagonale, allora i,i

i=1

t

| | | |

A = A

3. | | | | | |

A × B = A × B

REGOLA DI BINET

4. (in generale, NON vale per la somma)

| |

⇒ A = 0

5. Se in A c’è una riga (o colonna) nulla

6. Scambiando due righe/colonne, il determinante cambia di segno | |

⇒ A = 0

combinazione lineare

7. Se una riga/colonna è di altre righe/colonne

⇒ se si può scrivere utilizzando le altre righe/colonne combinate con

operazioni di somma e/o prodotto per scalare. Osservazione: se una riga/

⇒

colonna è multipla di un’altra riga/colonna è una sua combinazione lineare

| |

A = 0

e

8. Sommando ad una riga/colonna una combinazione lineare delle altre righe/

colonne, il determinante non cambia Pagina 6

fi fi fi ff

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

| | | |

A′ = A

Per la proprietà 8. posso scrivere una matrice A’, ma che ha sempre Venerdì 18 Settembre 2020

De nizione di funzione f : A → B

Corrispondenza funzionale ovunque de nita

f ⊆ A × B

∀A ∈ A∃!b ∈ B : (a, b) ∈ f

f (a) = b ≡ (a, b) = f

A : dominio

B: codominio

Più è facile una funzione, più esiste un modo più semplice per scriverla. Il codec è un sistema per

trasmettere in modo ottimale un video, sono funzioni so sticate, sfruttano la regolarità e

prevedibilità di ciò che vediamo, così da trasmettere il video in maniera ottimale.

f : A → B g : C → D A = C B = D f = g

Due funzioni e sono uguali se e , come insiemi.

f : A → B Im( f ) ⊆ B

Sia una funzione, si dice immagine tale che

Im( f ) = b ∈ B : ∃(a, b) ∈ f

{ }

Im( f ) = B ⇒

Se f è suriettiva

f : A → B A′ ⊆ A f : A′ → B

Sia e sia , si dice restrizione di f ad A’ e tale che

A′

(a, b) ∈ f ⟺ a ∈ A′

, (a, b) ∈ f

A′ f : A → B Im( f ) ⊆ B′ f : A → B f ⊆ A × B′

Si dice troncamento di f , la funzione tale che e

B′ B′

(a, b) ∈ f ⟺ (a, b) ∈ f

B′ Im( f )

Osservazione: il troncamento di f ad è suriettivo

R → R

F: 2

x → x + |

Im( f ) = R = x ∈ R x ≥ 0

{ }

ℕ → R

0

f ℕ =

0 2

n → n

Im( f ℕ ) ⊆ ℕ

0 0

Composizione di funzioni

f : A → B

g : B → C

g ∘ f : A → C (si legge f composto g!) Pagina 7





 



     

fi fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

(a, c) ∈ (g ∘ f ) ⟺ ∃b ∈ B (a, b) ∈ f (b, c) ∈ g

con &

(g ∘ f )(a) = g( f (a))

Teorema: siano

f : A → B

g : B → C Tre funzioni

h : C → D

h ∘ (g ∘ f ) : A → D (h ∘ g) ∘ f : A → D PROPRIETÀ

è una funzione e coincide con

ASSOCIATIVA (quella che si usa in particolare nel prodotto di matrici).

−1 −1

f : A → B ∃ f : B → A f ∘ f : A → A

Sia , si dice che f è invertibile se tale che ,

−1

f ∘ f : B → B

−1 |

f ∘ f = (a, a) a ∈ A

e { }

−1 |

f ∘ f = (b, b) b ∈ B

{ } funzioni identiche

⟺

Teorema: f è invertibile f è biiettiva (i.e. suriettività+iniettività).

∼ ∼ ∼

f : f ∘ f : A → A f : B → A f

Se esiste (è l’identità) , . Allora

è iniettiva.

∃f B

̂ → A f ∘ f ̂ B → B →

Se tale che è l’identità se B f è

suriettiva.

Im( f ) ⊊ B

Im( f ∘ f ̂ ) ⊊ B

Im( f ∘ f ̂ ) ≠ B

e

⇒ f ∘ f ̂

sicuramente non è l’identità su B!

R → R 1

f : → →

NON ESISTE INVERSA (-1) 1 =1

2

x → x

Operazioni binarie su di un insieme

*: A × A → A

A × A → A x ≥ 0

Funzione da Pagina 8

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

(A; * . . . . )

Una struttura algebrica è data da un insieme A e da una o più operazioni su esso.

* (a, b) ≡ a * b

(A, * ) * : A × A → A

Il Gruppo è una struttura algebrica A insieme operazione binaria tale che:

∃c ∈ A : ∀a ∈ A, c * a = a * c = a

1. (elemento neutro)

∀a ∈ A ∃a′ ∈ A : a * a′ = a′ * a = c

2. (inverso)

∀a, b, c ∈ A : (a * b) * c = a * (b * c)

3. (proprietà associativa)

∀a, b, c ∈ A : a * b = b * a

Un gruppo è detto abeliano o commutativo se

(N, + ) +: N × N → N

esempi: NO, non c’è l’elemento neutro per +

(ℕ , + ) NO, non ci sono inversi

0

(ℤ, + ) ∀a ∈ ℤ, (−a) ∈ ℤ

è un gruppo abeliano, l’elemento neutro è zero. &

a + (−a) = 0 inverso

associativa

(1 − 2) − 3 = − 4

1 − (2 − 3) = 1 + 1 = 2

a + (−b) = a − b

(ℤ, ⋅ ) → c’è l’elemento neutro, è associativa, non ha inverso

(ℚ, + )

(ℚ, ⋅ )

Q * = Q− (Q * , + )

{0} allora

(R, + ) è un gruppo

(R * , ⋅ ) è un gruppo

Osservazione: tutti i gruppi visti prima sono abeliani, ma ci sono anche gruppi non commutativi.

GL(n, K ) n × n

Se K campo, = insieme matrici con

≠ 0

entrate in K & det è un gruppo.

X S(x) := f : X → X S(x)

Sia un insieme e { , biiettve} .

con la composizione di funzioni è un gruppo.

Per codi care usiamo una funzione, per decodi care

usiamo l’inversa.

X = a, b, c S(x)

{ } e consideriamo . Rappresento ogni

f ∈ S(x) ( f (a), f (b), f (c))

con una terna

(a, b, c) = i (funzione identica)

(a, c, b) = f

1

(b, a, c) = f

2

(b, c, a) = f

3

(c, a, b) = f

4

(c, b, a) = f

5

| | | |

x = n S(x) = n!

S(x) non è commutativo. Pagina 9

  

fi fi

Martina Contestabile Ingegneria Informatica Comune A-L, A.A. 2020/21

Lunedì 21 Settembre 2020