Appunti Fondamenti di informatica

→A

dominio di operatori in Ω (o anche con operatori in Ω).

Gli elementi di Ω vengono di solito denotati con lettere greche e sono detti anche

scalari. ★ ★

L’immagine mediante della coppia (α, x) è spesso denotata con α x e detta

★.

composto di α e x in

Esempio:

★ : (α, x) Q R x è un operazione esterna di R con operatori in Q;

  →α  R

1

★ : (α, x) R R α x R è un operazione esterna di R con operatori in R;

  →  

2

★ : (α, (x, y)) R R x, α y) è un operazione esterna di R con operatori

  →(α   R

2 2 2

3

in R. Strutture algebriche

Un insieme A dotato di una o più operazioni interne o esterne è detto struttura

algebrica.

Se l’operazione è unica allora A è detto struttura algebrica semplice.

★1

Esempio: (Z, +, (R, +, ), (P(S), \) sono strutture algebriche; (N , +) è una

), , , 0

struttura algebrica semplice.

pag. 18

Semigruppi, monoidi e gruppi

La struttura (A, con operazione interna, è detta:

⊥), ⊥

- semigruppo se è associativa;

⊥

- monoide se è associativa e, inoltre, è dotata di elemento neutro;

⊥

- gruppo se è associativa, dotata di elemento neutro e ogni elemento di A

⊥

è simmetrizzabile;

- gruppo abeliano se è un gruppo e, inoltre, l’operazione è commutativa.

⊥

Esempio: (N, +) è un semigruppo, ma non è un monoide(N0 , +) è un monoide, ma

non è un gruppo (Z, +) è un gruppo abeliano

Anelli

La struttura (A, T), con e T operazioni interne, è detta anello se (A, è un

⊥, ⊥ ⊥)

gruppo abeliano e Tè associativa ed è distributiva rispetto a ⊥.

- Se esiste anche l’elemento neutro rispetto a T, l’anello è detto unitario.

- Se inoltre T è commutativa, l’anello è detto commutativo.

Esempio: (Z, +, è un anello commutativo unitario; (P(S), è un anello

) , )

commutativo unitario.

Corpi e campi

Un anello unitario (A, T) è detto corpo se ha più di un elemento e ogni elemento

⊥,

distinto dall’elemento neutro è simmetrizzabile rispetto a T.

Se (A, T) è un corpo ed inoltre T è commutativa, allora (A, T) è detto campo.

⊥, ⊥,

Esempio: (Q, +, e (R, +, sono campi.

) )

Omomorfismi

Siano (A, e (B, T) strutture algebriche con un’operazione interna: – Una funzione

⊥)

f : A B è detta omomorfismo di (A, in (B, T) se si ha f(x y) = f(x) Tf(y) per ogni

→ ⊥) ⊥

x, y A.



- Un omomorfismo iniettivo è detto monomorfismo.

- Un omomorfismo suriettivo è detto epimorfismo.

- Un omomorfismo biettivo è detto isomorfismo.

- Un omomorfismo di una struttura (A, in sé stessa è detto endomorfismo (o

⊥)

automorfismo).

Esempio: g : n N 2 è un monomorfismo di (N , +) in (N,

 → N ).

n

0 0

pag. 19

Calcolo combinatorio

Principio di addizione e inclusione-esclusione

Principio di addizione: siano A e B due insiemi finiti disgiunti. Allora |AB|=|A|+|B.

Sia A un insieme finito.

- Se C A, allora |A \ C| = |A| - |C|.



- Se B è un insieme qualunque, allora si ha che |A\B| = |A|-|AB|.

Principio di inclusione-esclusione: siano A e B due insiemi finiti.

Si ha che |A B| = |A| + |B| - |A

 B|.

Esempio: i numeri naturali positivi minori di 31 e divisibili per 2 o per 3 sono 20.

Principio di moltiplicazione

Siano A e B due insiemi finiti. Allora |A B| = |A| |B|.

 

Più in generale, siano A1 , A2 , …, Ak insiemi finiti con k ≥ 2. Si ha |A1A2…Ak|=

|A1 | |A2 | … |Ak|.

  

Nota. Il principio di moltiplicazione può essere interpretato in questo modo:

se E1 , … Ek sono eventi indipendenti tali che ci siano n possibilità per E1 , n2

1

possibilità per E2 , …, nk possibilità per Ek, allora il numero di possibilità per la

sequenza E1E2…Ek è n1 n2 … nk .

  

Da ciò deriva:

- Sia A un insieme finito. Allora |P(A)| = 2|A|.

- Siano A e B insiemi finiti. Allora l’insieme B delle funzioni di A in B ha

A

cardinalità |B| .

|A|

Fattoriale

Sia n un numero naturale positivo.

Il prodotto 1 2 … n è detto fattoriale di ne denotato con il simbolo n!

  

Si pone inoltre 0! := 1.

Nota: questo equivale a porre con n 0! := 1 e induttivamente (n+1)! := n!

N (n+1).

0

Esempio:

1! = 1

2! = 1 2 = 2



3! = 1 2 3 = 6

 

4! = 1 2 3 4 = 24

  

5! = 1 2 3 4 5 = 120

   

pag. 20

Permutazioni

Sia X un insieme finito. Una funzione biettiva di X in X è detta permutazione (o

sostituzione) di X.

L’insieme delle permutazioni di X è di solito denotato con SX .

Sia X un insieme finito. Se |X| = n, si ha |SX| = n!

Esempio: le permutazioni di un qualunque insieme di cardinalità 2 sono 2, di

cardinalità 3 sono 6, di cardinalità 4 sono 24.

Esempio: volendo contare in quanti modi si possono allineare 3 dischetti di diverso

colore, basta determinare il numero delle permutazioni di un insieme di cardinalità

3. Pertanto ci sono 6 possibili allineamenti.

Permutazioni con ripetizioni

Si considerino k oggetti a , a , …, a a due a due distinti (k ≥ 1), sia n = n + n + …

1 2 k 1 2

n con ogni ni ≥ 1, e siano b , b … b n oggetti.

k 1 2 n

Una n-upla (b , b … b ) in cui a compare n volte, a compare n volte, …, a

1 2 n 1 1 2 2 k

compare n volte, è denotata con il simbolo b … b ed è detta permutazione con

k 1 n

ripetizioni dei k oggetti a , a , …, a in cui a1 si ripete n volte, a si ripete n volte,

1 2 k 1 2 2

…, a si ripete n volte.

k k

Esempio: 1131733739 è una permutazione con ripetizioni dei 4 numeri 1, 3, 7, 9, in

cui 1 si ripete 3 volte, 3 si ripete 4 volte, 7 si ripete 2 volte e 9 si ripete una volta.

Siano k, n , n , n numeri naturali positivi e si ponga n = n + n + … n .

1 2 k 1 2 k

Allora il numero delle permutazioni con ripetizione dei k oggetti a , a , …, a in cui

1 2 k

a1 si ripete n volte, a si ripete n volte, …, a si ripete n è dato da:

1 2 2 k k

Esempio: il numero di permutazioni con ripetizione dei 4 numeri 1, 3, 7, 9, in cui 1 si

ripete 3 volte, 3 si ripete 4 volte, 7 si ripete 2 volte e 9 si ripete una volta è 10! / (3! 

4! 2! 1!) = 12600.

 

Disposizioni

Siano n e h numeri naturali positivi. Il

numero d delle disposizioni di n

n,h

elementi su h posti è definito come

segue:

Per h ≤ n, d è pertanto calcolato come il prodotto dei primi h numeri presi in

n,h

ordine decrescente a partire da n. Questo equivale

a scrivere:

pag. 21

Esempio: le parole non necessariamente di senso compiuto che si possono

scrivere con 4 lettere distinte scelte nell’insieme {A, C, D, E, I, S, O} sono d = 7 6

 

7,4

5 4 = 840.



Esempio: si ha una possibilità su 1680 di indovinare l’ordine esatto di arrivo dei primi

4 classificati in una gara cui partecipano 8 concorrenti. Infatti d = 1680.

8,4

Il numero di funzioni iniettive di un insieme di cardinalità h in un insieme di

cardinalità n, con h, n > 0 è d .

n,h

Esempio: il numero delle funzioni iniettive di A = {a, b, c, d, e} in B= {9, 10, 11, 12, 13,

14, 15, 16} è d8,5 = 8 7 6 5 4 = 6720.

   

Disposizioni con ripetizione

Disporre su h posti oggetti scelti tra n, permettendo ripetizioni, equivale a definire

una funzione di un insieme di cardinalità h nell’insieme costituito dagli noggetti. Il

numero di tali funzioni è n .

h

Quindi: il numero di disposizioni con ripetizione di noggetti su h posti è n .

h

Esempio: i numeri naturali positivi costituiti da 4 cifre dispari non necessariamente

distinte sono 5 = 625.

4

Esempio: nel gioco Mastermind le sequenze di 4 colori non necessariamente

distinti scelti tra 6 colori sono 6 = 1296.

4

Combinazioni

Siano n e h numeri naturali con 0 < h ≤ n. Il numero c delle combinazioni semplici

n,h

di n elementi ad h ad h è definito come:

Si pone inoltre per ogni n N , c := 1.

 0 n,0

Esempio: il numero di terni che si possono giocare al Lotto sono quanti le

combinazioni di 90 elementi a 3 a 3, ossia c = (90 89 88) / 3! = 117480.

 

90,3

Esempio: il numero di bouquet distinti che si possono comporre con 7 fiori presi 5 a

5 è c = 21.

7,5

Si noti che c = n! / n! = 1 = c

n,n n,0

Inoltre con 0 < h ≤ n si ha che:

c è sempre un numero intero.

n,h

Se n e h sono numeri interi, con 0 < h ≤ n, il numero dei sottoinsiemi di cardinalità h

di un insieme di cardinalità n è c .

n,h

pag. 22 Coefficienti binomiali

A volte, invece di usare il simbolo c il numero di combinazioni semplici di n

n,h

elementi ad h ad h si denota con il coefficiente binomiale n su h:

Se n e h sono numeri interi, con 0 < h ≤ n, si ha che:

Combinazioni con ripetizione

Volendo contare in quanti modi è possibile scegliere h oggetti, non

necessariamente distinti, tra n possibilità, tale numero – detto numero di

combinazioni con ripetizione di h oggetti tra n –è:

Esempio: al mercato sono disponibili mele, pere, banane, arance e kiwi. Volendo

acquistare due frutti non necessariamente diversi si hanno tante scelte quante

sono le combinazioni con ripetizione di 2 oggetti tra 5: (2 + 5 – 1)! / (2! 4!) = 15.



Introduzione all’informatica e alla

programmazione

Introduzione alla programmazione in C++

Software

Informalmente un programma può essere definito come una serie di operazioni

elementari, eseguite in sequenza, che trasformano un insieme di dati di ingresso

(input) in un insieme di dati di uscita (output).

L’insieme dei programmi e dei dati presenti su di un calcolatore ne costituiscono il

software.

Programmazione

La programmazione è l’attività di progettare e sviluppare programmi per un

calcolatore.

Informalmente, è come se il programmatore “insegnasse” al calcolatore come

svolgere un determinato compito.

pag. 23

Scopo della scrittura di un programma è la risoluzione automatica di un problema.

Il risult