Riassunto fondamenti di informatica

F​ O N D A M E N T I D E L L ’ I N F O R M A T I C A 2 0 1 6 - 2 0 1 7

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Insiemi​ e operazioni

​ ​ ​ ​

Insieme dei numeri naturali (N)

: nascono dall’attività del contare. Sono infiniti quindi l’insieme

non​ ha​ un​ massimo,​ ogni​ numero​ (tranne​ lo​ 0 minimo)​ ha​ un​ precedente​ e un​ successivo.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→

​

Insieme dei numeri relativi (Z)

: composto da ogni numero naturale preceduto dal segno + o -,

non​ ha​ un​ minimo,​ ogni​ numero​ ha​ un​ precedente​ e un​ successivo.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​ ​

Insieme dei numeri razionali (Q)

: composto​ dai​ numeri​ ottenuti​ da​ rapporti​ (frazioni).

​ ​ ​ ​ ​ ​ ​ ​

​

Insieme dei numeri irrazionali (I)

: contiene i numeri che non possono essere rappresentati da

frazioni​ (es.​ radici).

​ ​ ​

Insieme dei numeri reali (R)

: tutti i numeri che ammettono una qualunque rappresentazione

decimale, composto dagli insiemi dei numeri razionali e irrazionali, può essere

rappresentato​ da​ una​ retta​ chiamata​ “retta​ reale”.

​ ​ ​ ​ ​ ​

​

Insieme dei numeri complessi (C)

: insieme dei numeri razionali in cui il concetto di “numero” è

più​ generalizzato​ e sono​ possibili​ tutte​ le​ operazioni.

​ ​ ​ ​ ​ ​ ​ ​

Dev’essere possibile stabilire senza ambiguità se un oggetto appartiene o meno a un

insieme. Gli insiemi si rappresentano con lettere maiuscole, gli elementi con lettere

minuscole.

​ ​ ​ ​ ​

Proprietà degli insiemi

:

- Riflessività​ A = A

​ ​ ​ ​ ​ ​ ​

→

- Simmetria​ A = B se​ B = A

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→

- Transitività​ se​ A = B e B = C allora​ A = C

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ​

Rappresentazione estensionale

: tutti gli elementi dell’insieme sono scritti una sola volta tra

parentesi graffe, l’ordine in cui compaiono è irrilevante. {x, y, z, …}; un elemento {a} A è

∈

definito​ singoletto.

​ ​

Rappresentazione intensionale

: mediante la proprietà caratteristica dell’insieme, di cui

godono​ tutti​ e soli​ gli​ elementi​ dell’insieme.​ S = {x​ | P}

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Se a gode della proprietà P, allora appartiene a S. Se a appartiene a S, allora gode della

proprietà​ P.

​ ​

Sottoinsieme proprio

: B A, un sottoinsieme B di A diverso da A e non vuoto (A e Ø sono

⊂

sottoinsiemi​ impropri).

​

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Proprietà dell’inclusione (sottoinsieme o uguale)

:

⊆

- Riflessività

- Transitività

- Antisimmetria​ se​ A B e B A,​ allora​ A = B

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ⊆ ⊆

​

Insieme potenza

: si dice insieme potenza (o delle parti) di S l’insieme formato da tutti i

x ​

sottoinsiemi (non ordinati) di S. Se S ha x elementi, l’insieme potenza ha 2​ elementi

(compreso​ Ø).

​

​ ​ ​ ​ ​ ​ ​

Unione di due insiemi

: insieme​ di​ tutti​ gli​ oggetti​ che​ sono​ elementi​ di​ S oppure​ di​ T.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​ ​ ​ ​ ​

Intersezione di due insiemi

: insieme​ di​ tutti​ gli​ oggetti​ che​ sono​ sia​ elementi​ di​ S che​ di​ T.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

Proprietà dell’unione (e intersezione )

:

∪ ∩

- Idempotenza​ S S = S

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ∪

- Commutatività​ S T = T S

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ∪ ∪

- Elemento​ neutro​ S Ø = S = Ø S ||​ S Ø = Ø = Ø S

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ∪ ∪ ∩ ∩

- Assorbimento​ S T = T se​ S T

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ∪ ⊆

- Associatività​ (S​ T)​ V = S (T​ V)

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

→ ∪ ∪ ∪ ∪

​

Complementazione di due insiemi

: la differenza di un sottoinsieme S rispetto a U (universo).

Quindi,​ gli​ elementi​ di​ U che​ non​ compaiono​ in​ S.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Differenza simmetrica

: l’unione​ dei​ sottoinsiemi​ risultanti​ da​ (A-B)​ e (B-A).

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​

Cardinalità di un insieme

: il numero dei suoi elementi. Gli insiemi con cardinalità non

numerabile​ sono​ infiniti.

​ ​ ​

Prodotto cartesiano

: AxB, operazione tra insiemi che restituisce tutte le possibili

combinazioni​ di​ coppie​ ordinate​ tra​ elementi.

​ ​ ​ ​ ​

​ ​ ​ ​ ​

Famiglia di insiemi

: insieme​ i cui​ elementi​ sono​ insiemi.​ L’unione​ di​ essi​ è l’insieme.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​

Partizione

: dato un insieme S + Ø, una partizione di S è una famiglia di sottoinsiemi F tale che

ogni elemento di S appartiene a qualche elemento di F, e due elementi qualunque di F sono

disgiunti. Due o più sottoinsiemi (blocchi) di A formano una partizione se nessuno dei due è

vuoto,​ la​ loro​ intersezione​ è vuota​ e la​ loro​ unione​ è A.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​

Insieme quoziente

: ha per elementi le classi di equivalenza S (tutti gli elementi equivalenti) di

A​ rispetto​ alla​ relazione​ R.

​ ​ ​ ​

​

Multinsieme

: insieme con componenti ripetuti