Fondamenti di informatica - Laurea triennale Informatica/Funzioni

Una funzione da un insieme X a un insieme Y associa a ogni elemento di X esattamente un elemento di Y.

L’insieme X si chiama dominio, Y si chiama codominio, mentre l’insieme dei valori effettivamente ottenuti si chiama immagine o range.

Una funzione può essere rappresentata in vari modi:

• come insieme di coppie ordinate;
• tramite un diagramma a frecce;
• con una formula, ad esempio f(x)=x2;
• con un grafico, quando dominio e codominio sono sottoinsiemi dei numeri reali.

Perché una relazione sia una funzione, ogni elemento del dominio deve avere una e una sola immagine. Se un elemento del dominio non ha immagine, oppure ne ha più di una, non si tratta di una funzione.

Funzioni e grafici

Quando una funzione ha dominio e codominio numerici, può essere rappresentata con un grafico. Un insieme di punti nel piano rappresenta una funzione solo se ogni retta verticale interseca il grafico al massimo in un punto. Questo criterio mostra che a ogni valore di x deve corrispondere un solo valore di y.

Operatore modulo

Se a è un intero e m è un intero positivo, a mod m è il resto della divisione di a per m.

Questo concetto viene usato in molti contesti, ad esempio:

• per calcolare giorni della settimana;
• negli algoritmi di controllo, come quello di Luhn;
• nelle funzioni hash, usate in informatica per memorizzare e recuperare dati;
• nella generazione di numeri pseudocasuali.

Funzioni hash e collisioni

Una funzione hash assegna a un dato una posizione in memoria. Ad esempio, usando h(n)= n mod 30, un numero viene associato a una delle celle disponibili.

Può accadere che due valori diversi siano assegnati alla stessa cella: questo fenomeno si chiama collisione. Per gestirlo serve una strategia di risoluzione, come cercare la cella libera successiva.

Numeri pseudocasuali

Questi numeri sembrano casuali, ma in realtà sono prodotti da una formula deterministica. Se si conoscono i parametri e il valore iniziale, detto seme, l’intera sequenza può essere prevista.

Floor e ceiling

• il floor di x, indicato con ⌊x⌋, è il più grande intero minore o uguale a x;
• il ceiling di x, indicato con ⌈x⌉, è il più piccolo intero maggiore o uguale a x.

Queste funzioni “arrotondano” rispettivamente verso il basso e verso l’alto. Sono utili, ad esempio, per calcolare tariffe postali basate su frazioni di peso.

Funzioni iniettive

Una funzione è one-to-one, cioè iniettiva, se elementi diversi del dominio hanno immagini diverse. Formalmente, se f(x1​)=f(x2​), allora deve essere x1​=x2​.

Per dimostrare che una funzione è iniettiva si parte dall’ipotesi f(x1​)=f(x2​) e si cerca di concludere che x1​=x2​.

Per dimostrare che non è iniettiva basta trovare due elementi diversi del dominio con la stessa immagine. In sostanza non ci devono essere due valori del dominio che puntano allo stesso valore del codominio.

Funzioni suriettive

Una funzione è onto, cioè suriettiva, se ogni elemento del codominio è immagine di almeno un elemento del dominio. In altre parole, il codominio coincide con l’immagine della funzione.

Per dimostrare che una funzione è suriettiva bisogna mostrare che, per ogni elemento y del codominio, esiste almeno un x del dominio tale che f(x)=y.

Per dimostrare che non è suriettiva basta trovare un elemento del codominio che non viene mai raggiunto.

Biezioni e funzioni inverse

Una funzione che è sia iniettiva sia suriettiva si chiama biezione. Se esiste una biezione tra due insiemi finiti, allora i due insiemi hanno lo stesso numero di elementi.

Una funzione biettiva possiede una funzione inversa, indicata con f⁻¹. L’inversa associa a ogni valore del codominio l’elemento del dominio da cui proveniva. Nei diagrammi a frecce, l’inversa si ottiene semplicemente invertendo la direzione delle frecce.

Un esempio importante è la funzione esponenziale f(x)=3^x, la cui inversa è il logaritmo in base 3.

Composizione di funzioni

Se g manda elementi di X in Y, e f manda elementi di Y in Z, allora la composizione f∘g manda direttamente elementi di X in Z.

La composizione si calcola applicando prima g e poi f: (f∘g)(x)=f(g(x)) La composizione è utile anche per scomporre funzioni complicate in funzioni più semplici.

Operatori binari e unari

• un operatore binario su un insieme X: una funzione da X×X a X, cioè un’operazione che prende due elementi di X e restituisce un elemento di X;
• un operatore unario su X: una funzione da X a X, cioè un’operazione che prende un solo elemento e restituisce un elemento dello stesso insieme.

Esempi di operatori binari sono le operazioni logiche come AND e OR, mentre un esempio di operatore unario è la negazione logica.

Idee principali da ricordare

Una funzione è una corrispondenza che assegna a ogni elemento del dominio un solo elemento del codominio. È fondamentale distinguere tra dominio, codominio e immagine. Le proprietà più importanti studiate nel capitolo sono l’iniettività, la suriettività e la biettività. Le funzioni biettive hanno inverse, mentre la composizione permette di combinare più funzioni in una sola.