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

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

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

fn=k=1n4k+3

Dal cilindro il prof ci ha estratto questa formula:

fn=k=1n4k+3=2n2+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:

k=1nk=k·k+12

che crea la serie

  • P1 = 1
  • P2 = P1 + 2 = 3
  • P3 = P2 + 3 = 6
  • P4 = P3 + 4 = 10
  • P5 = P4 + 5 = 15
  • P6 = P5 + 6 = 21
  • P7 = P6 + 7 = 28
  • P... = P... + ... = ...

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

k=1n3k=???

  • P1 = 3
  • P2 = P1 + 6 = 9
  • P3 = P2 + 9 = 18
  • P4 = P3 + 12 = 30
  • P5 = P4 + 15 = 45
  • P6 = P5 + 18 = 63
  • P7 = P6 + 21 = 84
  • P... = P... + ... = ...

La soluzione non può essere molto distante da

k·k+12

Infatti, dopo qualche tentativo, ho trovato questa formula:

3k·k+12

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.

k=1nk+4=???

  • P1 = 5
  • P2 = P1 + 2 + 4 = 11
  • P3 = P2 + 3 + 4 = 18
  • P4 = P3 + 4 + 4 = 26
  • P5 = P4 + 5 + 4 = 35
  • P6 = P5 + 6 + 4 = 45
  • P7 = P6 + 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:

k·k+12+4k

(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.

fn=k=1n4k+3

diventa

4k·k+12+3k

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

4k·k+12+3k=4k22+4k2+3k=2k2+2k+3k=2k2+5k

e abbiamo ottenuto la Formula del Prof©

Matematica discreta / 6 - 16/10/2015

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 n2>7n+1 ∀ n>8.

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

Base: per n=8, n2=64 e 64>57, quindi P(8) è vera.

Passo induttivo.
Supponiamo vero P(n).

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

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

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

n2+2n+1 > 7n+7+1 +2n+1-7

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

Otteniamo

n2+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)2 > 7(n+1)+1 ∀ n>8

Seconda forma (forte) del Principio di Induzione

Mentre la prima forma richiede un'ipotesi di base P(1) è 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ì:

  • U1 = 1
  • U2 = 5
  • Un+1 = 5Un-6Un-1 ∀ n≥2

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

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

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

Base

Verifico U1, che è 31-21 = 1.

Verifico U2, che è 32-22 = 5.

Passo induttivo

Un+1 = 5Un-6Un-1

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

Un+1 = 5(3n-2n)-6(3n-1-2n-1)

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

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

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

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

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

ora, 9 = 33, quindi 9·3n-1 = 3·3·3n-1 = 3·3n = 3n+1

discorso omologo per -4·2n-1

Ottengo 3n+1-2n+1, che dimostra che anche Pn+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, Φ(2) = 1, quelli successivi sono dati dalla somma del precedente e di quello prima.

  1. Φ(1) = 1
  2. Φ(2) = 1
  3. Φ(3) = 2
  4. Φ(4) = 3
  5. Φ(5) = 5
  6. Φ(6) = 8
  7. Φ(7) = 13
  8. Φ(8) = 21
  9. Φ(9) = 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. n2+2n ≤ 60}, trovare, se esiste, minimo e massimo.

Il numero più piccolo che possiamo "dare in pasto" a n2+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(1) è vero? Sì, perché contiene 1, che è minimo di ℕ.

Passo induttivo: supponiamo che Si 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 / 4 - 09/10/2015

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

tanxdx

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

sinxcosxdx

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

--sinx·1cosxdx=log|cosx|+C

1sin2xdx

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

12sinxcosxdx

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

12cosxsinxcos2xdx

Possiamo scomporre la frazione nelle sue parti:

12cosxsinx1cos2xdx

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

12cosxsinx1cos2xdx=121tanx1cos2xdx

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

log|tanx|+C

 

 

Ricordiamo la regola per la derivazione delle funzioni composte:

fgx

è la notazione equivalente a

fgx

la cui derivata si ricava con questa regola:

fgx'=f'gx·g'x

Integrali: Esercizi svolti con spiegazione / 2

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

arcsinfx=f'x1-fx2

Mentre

arctanfx=f'x1+fx2

3ex1+e2xdx

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

3arctgex+C

1x1-log2xdx

Separiamo la derivata di log(x):

1x·11-log2xdx

La soluzione è

arcsinlogx+C