Diario di Marco Pagnin

Strutture dati

Posted by Marco Pagnin On Ottobre 22, 2015 Gennaio 10, 2016 Filed under Algoritmi e strutture dati

Riepilogo le strutture dati principali e le loro caratteristiche

Array

Struttura dati composta da un indice ordinato e un elemento.

0	Elem1
1	Elem2
2	Elem3
3	Elem4
4	Elem5

Tipicamente l'indice va da zero a n-1, quindi in un array di 5 elementi gli indici sono 0, 1, 2, 3, 4.

L'array ha dimensioni fisse, quindi non è possibile aggiungere o togliere elementi; inoltre gli indici sono attribuiti automaticamente, quindi non è possibile assegnare loro dei valori.

Record

Struttura composta da un indice e un elemento.

A differenza degli array, l'indice non è ordinato, ma assegnato dalla macchina, che generalmente usa un indirizzo di memoria virtuale.

Per questo motivo, mentre due array nello stesso programma hanno un indice = 0 che si riferisce a due zone di memoria diverse - perché sono di due array diversi - nel caso dei record l'indirizzo di memoria è unico per il programma.

Questo comporta che un record possa essere inserito e eliminato, "allungando" e "accorciando" la dimensione della struttura in cui è utilizzato.

In una lista ogni elemento deve contenere il proprio indice, l'elemento e un indice che punta all'elemento successivo.

I record possono essere concatenati in vari modi, dando luogo a strutture dati diverse:

lista semplice (solo avanti)
lista doppia (avanti e indietro)
lista circolare semplice e doppia

Nella lista semplice ogni elemento contiene un puntatore all'elemento successivo, per questo può essere scorsa solo in avanti.

Nella lista doppia ogni elemento contiene anche un puntatore all'elemento precedente, così è possibile scorrerla sia in avanti sia indietro.

Nella lista circolare non esiste un ultimo elemento, perché quello che "sarebbe" l'ultimo elemento è collegato con il primo, da cui la struttura circolare.

Pila / Coda

La pila e la coda sono due strutture dati in cui è possibile inserire e rimuovere un elemento in una lista ordinata.

La differenza tra pila e coda è che la pila è una lista di tipo LI-FO (last-in, first-out): come in un ascensore, l'ultimo a entrare è il primo a uscire, mentre la coda è una lista FI-FO (first-in, first-out): come alle poste, il primo che entra è il primo che esce.

Alberi

Un albero è una struttura dotata di nodi e archi; gli archi collegano tra loro nodi.

I nodi sono organizzati secondo una gerarchia, per cui esiste un nodo radice, che può avere uno o più figli.

Ogni nodo può avere più nodi figli, ma un solo nodo padre (in questo sistema la "madre" non è contemplata :-))

Se un nodo non ha figli, è chiamato foglia.

La profondità è il numero di archi che bisogna attraversare per raggiungere il nodo:

La radice ha profondità zero
Se un nodo ha profondità k, tutti i suoi figli hanno profondità k+1

Rappresentazioni degli alberi

Per implementare un albero è possibile scegliere tra queste strutture, tutte con pro e contro:

vettore padri: ogni elemento contiene la propria informazione e un puntatore al padre (null se l'elemento è radice). Risalire al padre ha tempo O(1), mentre risalire ai figli O(n)
vettore posizionale: se ogni nodo ha un numero fissato di figli, è possibile rappresentare l'albero come un semplice vettore e calcolare la posizione di un nodo tramite la sua posizione nell'array. Per esempio in un albero binario la radice è 1, i due figli sono 2, 3, i nipoti sono 4, 5, 6, 7 eccetera, e tutto questo non presenta ambiguità, poiché ogni nodo ha esattamente due figli
rappresentazioni collegate: contengono, oltre all'informazione, un puntatore al nodo padre e un accesso ai figli di vario tipo:
- se sappiamo a priori quanti figli massimi può avere un nodo, possiamo predisporre per ogni nodo un numero di puntatori ai figli
- se NON sappiamo il numero dei figli, possiamo aggiungere un puntatore a una lista di puntatori ai figli. Questo occupa più memoria, ma permette di estendere il numero dei figli in modo illimitato
- se NON sappiamo il numero dei figli, possiamo aggiungere due puntatori per ogni nodo, uno al primo figlio e un altro al fratello successivo. La struttura è più snella dal punto di vista della memoria ma leggermente più lenta perché per accedere a un figlio è possibile dover scorrere tutta la lista di fratelli.

Heap

Gli heap sono alberi binari in cui vale sempre la proprietà che un nodo ha valore maggiore (max-heap) o minore (min-heap) di ciascuno dei suoi sotto-nodi.

Non esistono vincoli di tipo destra-sinistra, l'unico aspetto che deve essere sempre rispettato è che il padre, se esiste è maggiore del figlio e se non esiste è il nodo massimo (per max-heap; per min-heap vale il discorso contrario).

Past simple and present perfect

Posted by Marco Pagnin On Ottobre 21, 2015 Agosto 28, 2016 Filed under Inglese

Per studiare con profitto i tempi e i modi inglesi, bisogna distaccarsi dal modo di ragionare e di pensare ai verbi in italiano.

Ciò che guida la scelta del verbo in inglese è se l'azione è continuata o puntuale e se l'azione ha conseguenze nel presente o meno.

In particolare, se l'azione è chiusa, finita nel passato, si usa il past simple (quello che, nei verbi regolari, termina con -ed). Si riconosce principalmente dalla presenza nella frase di alcune parole chiave:

when
what time
for (nell'accezione italiana di "per...tempo")

Viceversa il present perfect si usa quando l'azione iniziata o svolta nel passato determina la situazione presente in maniera diretta.

I have lost my passport => so I can't go to China
In my life...
- I have never been in Scotland
- I have studied Latin
DA: (da quanto tempo sei qui? => how long have you been here?)

Esempi

Quando ero piccolo ho rotto un vetro => when I was young I broke a glass

Non ho mai rotto uno specchio in vita mia => I have never broke a glass in all my life

Ho perso il mio orologio => I lost my watch

Non posso dirti l'ora perché ho perso il mio orologio => I can't say you what time is it because I have lost my watch

Pay attention

Rispetto al passato prossimo italiano, che si forma con il presente dell'ausiliario e il participio passato (es. ho fatto), il costrutto più simile in inglese (I have done) non ha lo stesso uso!

Nel primo caso (italiano) si indica un'azione svolta e conclusa nel passato, nel secondo caso di un'azione accaduta nel passato, ma con una "conseguenza viva" nel presente.

Da sommatoria a formula

Posted by Marco Pagnin On Ottobre 20, 2015 Ottobre 20, 2015 Filed under Matematica discreta

Durante una delle lezioni ci è stata proposta la seguente serie, descritta come sommatoria:

$f (n) = \sum_{k = 1}^{n} 4 k + 3$

Dal cilindro il prof ci ha estratto questa formula:

$f (n) = \sum_{k = 1}^{n} 4 k + 3 =$ 2n²+5n

Poi, con il principio di induzione, ha dimostrato che è vera. E ci ha anche detto che a volte è richiesto che lo studente risalga a questa funzione da solo.

Panico.
Panico da Settimana Enigmistica, ma comunque panico.

Come si risale da una sommatoria a una funzione? Questa è una domanda molto importante soprattutto quando si studiano algoritmi e strutture dati, perché una serie che considera il risultato precedente ha delle prestazioni decisamente più scadenti di una "formuletta" non ricorsiva.

Per risolvere l'enigma, ho pensato alla semplice sommatoria di tutti i numeri da 1 a n:

$\sum_{k = 1}^{n} k = \frac{k \cdot (k + 1)}{2}$

che crea la serie

P₁ = 1
P₂ = P₁ + 2 = 3
P₃ = P₂ + 3 = 6
P₄ = P₃ + 4 = 10
P₅ = P₄ + 5 = 15
P₆ = P₅ + 6 = 21
P₇ = P₆ + 7 = 28
P_... = P_... + ... = ...

Cosa succede se moltiplico per (ad esempio) 3 l'indice?

$\sum_{k = 1}^{n} 3 k = ???$

P₁ = 3
P₂ = P₁ + 6 = 9
P₃ = P₂ + 9 = 18
P₄ = P₃ + 12 = 30
P₅ = P₄ + 15 = 45
P₆ = P₅ + 18 = 63
P₇ = P₆ + 21 = 84
P_... = P_... + ... = ...

La soluzione non può essere molto distante da

$\frac{k \cdot (k + 1)}{2}$

Infatti, dopo qualche tentativo, ho trovato questa formula:

$\frac{3 k \cdot (k + 1)}{2}$

Apparentemente la formula sembra applicarsi ai numeri razionali, e non ai naturali, perché è evidente il 3/2.
Però è vero anche che tra n e n+1 uno dei due DEVE essere pari, e quello si semplifica con il 2 al denominatore.

Poi ho provato ad aggiungere una costante alla sommatoria, per cercare in che modo la costante cambia la formula.

$\sum_{k = 1}^{n} k + 4 = ???$

P₁ = 5
P₂ = P₁ + 2 + 4 = 11
P₃ = P₂ + 3 + 4 = 18
P₄ = P₃ + 4 + 4 = 26
P₅ = P₄ + 5 + 4 = 35
P₆ = P₅ + 6 + 4 = 45
P₇ = P₆ + 7 + 4 = 56
P_... = P_... + ... = ...

Siccome ogni volta che aggiungo la costante me la "porto dietro" per k volte, ho provato semplicemente ad aggiungere k 4 volte alla formula:

$\frac{k \cdot (k + 1)}{2} + 4 k$

(no, non ci sono arrivato subito, al primo tentativo, in maniera brillante e sicura)

A questo punto ho tutto quanto mi serve per affrontare la serie proposta dal prof.

$f (n) = \sum_{k = 1}^{n} 4 k + 3$

diventa

$\frac{4 k \cdot (k + 1)}{2} + 3 k$

Questo non assomiglia per niente alla 2n²+5n, ma proviamo a fare qualche passaggio in più.

$\frac{4 k \cdot (k + 1)}{2} + 3 k = \frac{{4 k}^{2}}{2} + \frac{4 k}{2} + 3 k = 2 k^{2} + 2k+3k=2k^{2}+5k$

e abbiamo ottenuto la Formula del Prof©

Matematica discreta / 6 - 16/10/2015

Posted by Marco Pagnin On Ottobre 19, 2015 Filed under Matematica discreta

Una delle definizioni alternative di principio di induzione prevede che P_(n) sia vero solo per un n>x tale che x>1, come sempre con x e n ∈ℕ.
Per esempio, si provi che n²>7n+1 ∀ n>8.

(nota mia: in realtà è facile capire anche che n²>8n+1 ∀ n>9, n²>9n+1 ∀ n>10 eccetera)

Base: per n=8, n²=64 e 64>57, quindi P₍₈₎ è vera.

Passo induttivo.
Supponiamo vero P_(n).

(n+1)² equivale a n²+2n+1

Siccome l'ipotesi induttiva dice che n² > 7n+1, allora possiamo dire che n²+2n+1 > 7n+1+2n+1

Vogliamo ottenere 7(n+1)+1 più qualcos'altro per concludere la dimostrazione, quindi aggiungiamo +7 e -7:

n²+2n+1 > 7n+7+1 +2n+1-7

raccogliamo 7 nell'espressione 7n+7 e sommiamo +1 e -7

Otteniamo

n²+2n+1 > 7(n+1)+1 +2n-6

2n-6 è una quantità sempre positiva, perché vale come minimo 10 (per n=8, poi cresce sempre), quindi

(n+1)² > 7(n+1)+1 ∀ n>8

Seconda forma (forte) del Principio di Induzione

Mentre la prima forma richiede un'ipotesi di base P₍₁₎ è vera e "se P_(n) è vera allora è vera anche P_(n+1)" è vera, e quindi è necessario che siano vere solo la base e P_(n), nella seconda forma è richiesto che sia vero qualunque elemento minore di n.

Prima forma:
1, 2, 3, 4, 5,..., n ⇒ n+1

Seconda forma:
1, 2, 3, 4, 5,..., n-3, n-2, n-1 ⇒ n

Nell'esempio riportato a lezione, dimostriamo che, data una funzione U definita così:

U₁ = 1
U₂ = 5
U_n+1 = 5U_n-6U_n-1 ∀ n≥2

si provi che U_n = 3ⁿ-2ⁿ ∀ n∈ℕ.

Il principio di induzione nella sua prima forma non torna utile, perché la mia ipotesi induttiva può considerare U_n, ma non può fare ipotesi su U_n-1!

Nella seconda forma posso dare per veri tutti gli elementi minori di n, compreso n-1.

Base

Verifico U₁, che è 3¹-2¹ = 1.

Verifico U₂, che è 3²-2² = 5.

Passo induttivo

U_n+1 = 5U_n-6U_n-1

Sostituisco U_n con la formula 3ⁿ-2ⁿ, provata per tutti i naturali fino a n.

U_n+1 = 5(3ⁿ-2ⁿ)-6(3^n-1-2^n-1)

Siccome 3ⁿ = 3·3^n-1 e 2ⁿ = 2·2^n-1, posso riscrivere l'espressione come

U_n+1 = 5(3·3^n-1-2·2^n-1)-6(3^n-1-2^n-1)

e poi moltiplico la prima parte per il 5 fuori dalla parentesi e la seconda per 6

U_n+1 = 5(3·3^n-1-2·2^n-1)-6(3^n-1-2^n-1) = 5·3·3^n-1 - 5·2·2^n-1-6·3^n-1+6·2^n-1

Raccolgo 3^n-1 e 2^n-1
U_n+1 = 5·3·3^n-1 - 5·2·2^n-1-6·3^n-1+6·2^n-1 = 9·3^n-1-4·2^n-1

ora, 9 = 3³, quindi 9·3^n-1 = 3·3·3^n-1 = 3·3ⁿ = 3ⁿ⁺¹

discorso omologo per -4·2^n-1

Ottengo 3ⁿ⁺¹-2ⁿ⁺¹, che dimostra che anche P_n+1 è vera.

Per il PdI posso affermare che P_(n) è vero ∀ n∈ℕ.

Ricorrenza

Molto brevemente, si definisce un numero (o più numeri) e si ricavano i successivi dal primo.

I due "classici" esempi scelti sono il fattoriale e la serie di Fibonacci.

Fattoriale

Il fattoriale di un numero naturale è il prodotto del numero stesso per tutti i numeri precedenti. Si indica con un punto esclamativo dopo il numero o l'incognita.

1! = 1

2! = 1x2 = 2

3! = 2! x 3 = 6

4! = 3! x 4 = 24

5! = 4! x 5 = 120

6! = 5! x 6 = 720

Fibonacci

Un numero di Fibonacci Φ₍₁₎ = 1, Φ₍₂₎ = 1, quelli successivi sono dati dalla somma del precedente e di quello prima.

Φ₍₁₎ = 1
Φ₍₂₎ = 1
Φ₍₃₎ = 2
Φ₍₄₎ = 3
Φ₍₅₎ = 5
Φ₍₆₎ = 8
Φ₍₇₎ = 13
Φ₍₈₎ = 21
Φ₍₉₎ = 28

Funzioni

Su funzioni, minimi e massimi ho già scritto qui: https://diario.softml.it/prima-lezione.
Quanto scritto si applica ai numeri reali ℝ, mentre minimo e massimo in ℕ sono leggermente diversi.

Mentre ℕ non ha massimo, perché per ogni numero n∈ℕ che voglio tentare di considerare massimo, posso pensare a un n+1, al contrario ha un minimo definito = 1.

Anche i sottoinsiemi ≠∅ di ℕ possono avere minimo e massimo (es. i numeri minori di 10) oppure possono non avere massimo (es. i numeri pari), ma ogni sottoinsieme ≠∅ ha sempre un minimo.

Esempio: sia un insieme X = {n∈ℕ t.c. n²+2n ≤ 60}, trovare, se esiste, minimo e massimo.

Il numero più piccolo che possiamo "dare in pasto" a n²+2n perché il risultato sia minore o uguale a 60 è 1, che è quindi il nostro minimo.

Il massimo, andando per tentativi, è 6.

Dimostrazione dell'esistenza del minimo.

Usiamo il PdI nella seconda forma.

S(n); se X ⊆ ℕ, n∈X, allora X ha minimo

Base: S₍₁₎ è vero? Sì, perché contiene 1, che è minimo di ℕ.

Passo induttivo: supponiamo che S_i sia vero ∀ i ≥ 1 e i ≤ k.
Consideriamo S_(k+1), k+1∈X.

Distinguiamo due casi:

∀ x∈X si ha x>k ⇒ k+1 è il minimo di X
∃ y∈X, 1≤y≤k, allora S_(y) è vero

Per ipotesi induttiva, X ha minimo.

Matematica discreta / 5 - 12/10/2015

Posted by Marco Pagnin On Ottobre 17, 2015 Ottobre 17, 2015 Filed under Matematica discreta

Una delle formulazioni del principio di induzione è il seguente:dati m, n ∈ ℕ, non è possibile che m < n < m+1In altre parole, tra due numeri consecutivi non esiste alcun altro numero.Tolto il PdI, gli altri assiomi sono validi anche per altri insiemi, come ℤ⁺ e ℝ⁺ (gli interi e i reali positivi).
Keep reading →

Matematica discreta / 4 - 09/10/2015

Posted by Marco Pagnin On Ottobre 10, 2015 Ottobre 17, 2015 Filed under Matematica discreta

Note preliminari

per la corretta visualizzazione di questa pagina occorre utilizzare un browser che supporta mathml.
il testo di riferimento (in inglese) è Discrete mathematics di Norman L. Biggs
sono utilizzati i seguenti caratteri, di cui si suppone che il lettore conosca il significato:
- ℕ l'insieme dei numeri naturali
- ∩ intersezione di insiemi
- ∅ insieme vuoto
- ∈ appartiene all'insieme (es. n∈ℕ significa n appartiene all'insieme dei naturali)
- ∀ per ogni (es. n+1=n+1 ∀ n∈ℕ si legge n+1=n+1 per ogni n appartenente di naturali)
- ∃ Esiste
- ⇒ determina (es. a<b, b<c ⇒ a<c)
- < minore, > maggiore, ≤ minore o uguale, ≥ maggiore o uguale, ≠ diverso

Numeri naturali

I numeri naturali sono il primo insieme, che tutti pensano di conoscere

Keep reading →

Integrali: Esercizi svolti con spiegazione / 3

Posted by Marco Pagnin On Ottobre 7, 2015 Febbraio 29, 2016 Filed under Esercitazioni di calcolo 1

$\int tan (x) dx$

Come noto, la tangente è il rapporto tra seno e coseno:

$\int \frac{sin (x)}{cos (x)} dx$

Moltiplichiamo per -1 e -1, infatti -(-f(x)) = f(x), ma un "meno" lo portiamo fuori, l'altro "meno" si applica a sen(x), che diventa così la derivata di cos(x).
1/cos(x) equivale a cos(x)^-1.

Alla luce di questo possiamo trasformare l'integrale così, come reciproco di una funzione e derivata

$- \int - sin (x) \cdot \frac{1}{cos (x)} dx = log | cos (x) | + C$

$\int \frac{1}{sin (2 x)} dx$

Ricordiamo che sin(2x) = 2·sinx·cosx

$\int \frac{1}{2 sin (x) cos (x)} dx$

Aggiungiamo cos(x) / cos(x) ed "estraiamo" il 1/2:

$\frac{1}{2} \int \frac{cos (x)}{sin (x) {cos}^{2} (x)} dx$

Possiamo scomporre la frazione nelle sue parti:

$\frac{1}{2} \int \frac{cos (x)}{sin (x)} \frac{1}{{cos}^{2} (x)} dx$

Otteniamo la cotangente di x (cioè 1/tan(x)) e dall'altra parte la secante² di x (cioè 1/cos^2(x))

$\frac{1}{2} \int \frac{cos (x)}{sin (x)} \frac{1}{{cos}^{2} (x)} dx = \frac{1}{2} \int \frac{1}{tan (x)} \frac{1}{{cos}^{2} (x)} dx$

1/cos²(x) è la derivata di tan(x), così il risultato dell'integrale è:

$log | tan (x) | + C$

Ricordiamo la regola per la derivazione delle funzioni composte:

$f \circ g (x)$

è la notazione equivalente a

$f (g (x))$

la cui derivata si ricava con questa regola:

$(f (g (x)))' = f' (g (x)) \cdot g' (x)$

Integrali: Esercizi svolti con spiegazione / 2

Posted by Marco Pagnin On Ottobre 6, 2015 Filed under Appunti di calcolo

Il "trucco" di questi integrali è ricordare la derivata delle funzioni trigonometriche inverse (arcoseno e arcotangente):

$arcsin (f (x)) = \frac{f' (x)}{\sqrt{1 - {f (x)}^{2}}}$

Mentre

$arctan (f (x)) = \frac{f' (x)}{1 + {f (x)}^{2}}$

$\int \frac{3 e^{x}}{1 + e^{2 x}} dx$

Se "esportiamo" il 3, possiamo identificare l'integrale dell'arcotangente e la funzione e^x. Infatti e^2x = (e^x)².
La soluzione è

$3 arctg (e^{x}) + C$

$\int \frac{1}{x \sqrt{1 - {log}^{2} x}} dx$

Separiamo la derivata di log(x):

$\int \frac{1}{x} \cdot \frac{1}{\sqrt{1 - {log}^{2} x}} dx$

La soluzione è

$arcsin (log (x) + C)$

Integrali: Esercizi svolti con spiegazione / 1

Posted by Marco Pagnin On Ottobre 4, 2015 Ottobre 20, 2015 Filed under Appunti di calcolo

La regola con cui risolvere questi integrale è: se trovi f'(x)f(x)ⁿ (cioè una funzione elevata a potenza per la sua derivata) la soluzione immediata è:

$\frac{1}{n + 1} f {(x)}^{n + 1}$

Ricordiamo che √x = x^1/2 e che 1/x = x^-1.
Keep reading →

Ottobre 2015 Archive