Riassunto fondamenti di informatica

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 n volte, quindi se f(a) = 3, a sarà ripetuto 3

volte. ​

Coppia ordinata

: ha un primo e un secondo elemento. Le coppie ordinate di un prodotto

cartesiano​ formano​ una​ relazione​ binaria.

​ ​ ​ ​

- <x,​ y>​ ≠ <y,​ x>

​ ​ ​ ​ ​

- <x,​ y>​ = <r,​ s>​ se​ e solo​ se​ x = r,​ y = s

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

- <x,​ y>​ = {{x},​ {x,​ y}}

​ ​ ​ ​ ​ ​

​ ​ ​

Relazione complementare

: coppie​ ordinate​ che​ non​ appartengono​ a R.

​ ​ ​ ​ ​ ​ ​ ​ ​

​

Relazione inversa

: primo elemento della coppia scambiato con il secondo. Perché sia

possibile,​ la​ funzione​ deve​ essere​ iniettiva.

​ ​ ​ ​ ​

​ ​ ​ ​ ​

Relazione di equivalenza

: riflessiva,​ simmetrica​ e transitiva.

​ ​ ​ ​ ​ ​

Funzioni

​

Funzione

: associazione di un insieme A a un insieme B tale che a ogni elemento di B

corrisponda​ al​ più​ un​ elemento​ di​ A.

​ ​ ​ ​ ​ ​

​ ​ ​ ​ ​

Dominio di R

: insieme​ degli​ oggetti​ x tale​ che​ <x,​ y>​ R per​ qualche​ y.

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

∈

​

Codominio di R

: insieme degli oggetti y tale che <x, y> R per qualche x. La funzione

∈

inversa del codominio corrisponde al dominio (esiste solo se la funzione è iniettiva, quindi

l’inversa​ è suriettiva).

​ ​ ​

​ ​ ​

Funzione iniettiva

: detta​ anche​ funzione​ ingettiva

​ ​ ​ ​ ​

oppure​ iniezione,​ è una​ funzione​ che​ associa​ ad

​ ​ ​ ​ ​ ​ ​ ​

elementi​ distinti​ del​ dominio,​ elementi​ distinti

​ ​ ​ ​ ​

del​ codominio​ (uno​ e uno​ solo).​ S T tale​ che​ a

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

→

ogni​ elemento​ di​ S corrisponde​ al​ più​ un

​ ​ ​ ​ ​ ​ ​ ​

elemento​ di​ T.

​ ​

​ ​ ​ ​

Funzione s

uriettiva

: ogni​ elemento​ del

​ ​ ​ ​

codominio​ è immagine​ di​ almeno​ un​ elemento

​ ​ ​ ​ ​ ​ ​

del​ dominio.​ In​ tal​ caso​ si​ ha​ che​ l'immagine

​ ​ ​ ​ ​ ​ ​ ​

coincide​ con​ il​ codominio.

​ ​ ​

​ ​ ​

Funzione biunivoca

: La​ funzione​ è sia​ iniettiva​ sia

​ ​ ​ ​ ​ ​ ​ ​

suriettiva​ (il​ dominio​ coincide​ con​ il​ codominio).

​ ​ ​ ​ ​ ​

​ ​ ​

Funzione totale

: definita​ su​ ogni​ elemento​ del

​ ​ ​ ​ ​ ​

dominio​ (es.​ sottrazione​ in​ Z).

​ ​ ​ ​

​ ​ ​

Funzione parziale

: non​ è definita​ su​ ogni​ elemento​ del​ codominio​ (es.​ divisione​ in​ N).

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

​ ​ ​

Punto fisso

: ogni​ valore​ dato​ a quella​ funzione​ corrisponde​ a un​ unico​ valore,​ l’elemento

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

coincide​ con​ la​ sua​ immagine.

​ ​ ​ ​

​ ​ ​

Funzione composta

: f о g,​ applicazione​ di​ una​ funzione​ g a una​ funzione​ f.​ Se​ l’arietà​ della

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

funzione​ da​ applicare​ è maggiore,​ non​ è possibile​ applicarla.​ Quindi,​ se​ una​ funzione​ è in

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

NxN​ non​ va​ mai​ applicata​ a funzioni​ in​ N.

​ ​ ​ ​ ​ ​ ​ ​ ​

La​ funzione​ f deve​ avere​ come​ codominio​ un​ sottoinsieme​ del​ dominio​ di​ g.

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

​

Una​ funzione​ è invertibile solo​ se​ la​ sua​ inversa​ è una​ funzione,​ quindi​ se​ è iniettiva;​ l’inversa

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

è​ totale​ se​ f è suriettiva​ (e​ viceversa).

​ ​ ​ ​ ​ ​ ​ ​ ​

​

Principio della piccionaia

: se A e B sono due insiemi finiti e |A| > |B|, non esiste alcuna

funzione​ iniettiva​ totale​ da​ A a B.

​ ​ ​ ​ ​ ​ ​ ​ ​

Arietà di una funzione o relazione

: numero degli insiemi su cui è definita la funzione o

relazione​ (unaria,​ binaria​ ecc.).

​ ​ ​

Strutture​ relazionali,​ grafi​ e ordinamenti

​ ​ ​ ​ ​

​

DAG

: grafo diretto (frecce) senza cicli, formato da coppie ordinate di punti. Il numero di archi

uscenti/entranti​ in​ un​ nodo​ è detto​ grado​ di​ ingresso/uscita.

​ ​ ​ ​ ​ ​ ​ ​ ​

​

Grafo connesso

: ogni coppia di vertici è connessa da un cammino, fortemente connesso se

esiste​ un​ cammino​ tra​ ogni​ coppia​ di​ vertici​ (quindi​ anche​ nel​ verso​ opposto).

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

​

Cammino

: sequenza di frecce orientate per raggiungere un nodo a partire da un altro nodo.

La​ lunghezza​ è pari​ al​ numero​ di​ nodi​ - 1.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​

Semicammino

: cammino​ che​ non​ tiene​ conto​ della​ direzione​ delle​ frecce.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Ciclo (semiciclo)

: cammino​ (semicammino)​ dove​ il​ nodo​ di​ partenza​ è lo​ stesso​ di​ arrivo.

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

​

Albero

: un DAG con un nodo sorgente detto padre, e nodi figli. I nodi privi di figli sono detti

foglie. Un cammino è il percorso da un nodo per raggiungerne un altro, la lunghezza di un

cammino​ è detta​ profondità​ mentre​ la​ profondità​ massima​ è detta​ altezza.

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

​

Albero binario

: ogni nodo ha al massimo due figli. Può essere attraversato in profondità, in

ordine​ anticipato,​ simmetrico​ o posticipato.

​ ​ ​ ​ ​

​

Pre-ordine

: relazione​ binaria,​ riflessiva​ e transitiva.

​ ​ ​ ​ ​ ​ ​

​

Quasi-ordine

: relazione​ binaria,​ irriflessiva​ e transitiva.

​ ​ ​ ​ ​ ​ ​

​

Partially Ordered SET

: struttura relazionale (insieme di coppie) con relazione di ordine

parziale (transitivo, antisimmetrico e riflessivo). Il semiordinamento è anche un ordinamento

o​ ordine​ totale​ se​ x = y,​ oppure​ <x,​ y>​ R,​ oppure​ <y,​ x>​ R (tricotomia).

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

∈ ∈

​

- Riflessivo

: <x,​ x>​ R.

​ ​ ​ ​ ​ ​

∈

- Ogni​ nodo​ ha​ un​ cappio,​ nella​ tabella​ le​ x sono​ sulla​ diagonale.

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

​

- Antisimmetrico

: <x,​ y>​ R e <y,​ x>​ R (quindi​ x = y).

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

∈ ∈

- Ogni freccia ha solo una punta, e nella tabella non ci sono x simmetriche

rispetto​ alla​ diagonale.

​ ​

​

- Transitivo

: <x,​ y>​ R e <y,​ z>​ R quindi​ <x,​ z>​ R.

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

∈ ∈ ∈

- Se​ s è collegato​ a t,​ t è collegato​ a r,​ allora​ s è collegato​ a r.

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

​

Copertura

: y è una copertura di x se non ci sono elementi che si frappongono nella relazione

di​ ordinamento.

​ ​ ​ ​

Elementi estremali

: ​

- Minimale/minimo

: non​ esiste​ un​ elemento​ minore​ di​ s.

​ ​ ​ ​ ​ ​ ​ ​

​

- Massimale/massimo

: non​ esiste​ un​ elemento​ maggiore​ di​ s.

​ ​ ​ ​ ​ ​ ​ ​

Nei​ sottoinsiemi​ di​ un​ grafo:

​ ​ ​ ​

​

- Minorante

: tutti​ gli​ altri​ elementi​ sono​ maggiori​ o uguali​ a s.

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

​

- Maggiorante

: tutti​ gli​ altri​ elementi​ sono​ minori​ o uguali​ a s.

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

​ ​ ​

- Massimo minorante

: il​ maggiore​ tra​ i minoranti.

​ ​ ​ ​ ​ ​ ​

​

- Minimo maggiorante

: il minore tra i maggioranti. Un ordinamento è detto buono se ha

un​ minimo.

​

​

Reticolo

: poset in cui per ogni coppia ordinata esiste un massimo minorante (meet, e un

⊓)

minimo maggiorante (join Un reticolo è completo se ogni sottoinsieme ha un minimo e un

​

⊔).

​

massimo,​ è limitato se​ esistono​ massimo​ e minimo.

​ ​ ​ ​ ​ ​ ​ ​ ​

​

Proprietà​ di​ un​ reticolo​ distributivo (devono​ valere​ per​ tutte​ le​ coppie):

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

- a​ (b​ c)​ = (a​ b)​ (a​ c)

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

⊔ ⊓ ⊔ ⊓ ⊔

- a​ (b​ c)​ = (a​ b)​ (a​ c)

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

⊓ ⊔ ⊓ ⊔ ⊓

- Se​ un​ reticolo​ ha​ un​ nodo​ in​