Monthly Archives: Dicembre 2014

Ordinare due dati

Due soli dati da ordinare, cioè il più piccolo deve precedere il più grande.

Scambiare il contenuto di due variabili

Scambiare i valori contenuti nell’array V alle posizioni a e b

oppure

Ordinare un array di due elementi

oppure, senza la chiamata…

Esempio

Sia

V=(20, 15)

allora

produce

V=(15, 20)

Ordinare un sottoarray di due elementi

Esempio

Sia

V=(20, 15, 10, 3)

allora

produce

V=(20, 10, 15, 3)

Fusione di sequenze

A partire da due sequenze ordinate, v1 e v2, si vuole realizzare una terza sequenza ordinata v3.

Esempi

  1. v1=(1, 2, 4, 5)
    v2=()
    v3=(1, 2, 4, 5)
  2. v1=(1, 2, 4, 5)
    v2=(20, 30, 40, 60)
    v3=(1, 2, 4, 5, 20, 30, 40, 60)
  3. v1=(1, 2, 4, 5, 7, 10)
    v2=(2, 3, 4, 6)
    v3=(1, 2, 2, 3, 4, 4, 5, 6, 7, 10)

Algoritmo

Una scansione delle due sequenze sceglie, a ogni passo, l’elemento da copiare nella terza sequenza.
È sufficiente confrontare i primi elementi perché…

Esempio

v1 v2 v3
1, 2, 4, 5, 7, 10 2, 3, 4, 6 1
2, 4, 5, 7, 10 2, 3, 4, 6 1, 2
4, 5, 7, 10 2, 3, 4, 6 1, 2, 2
4, 5, 7, 10 3, 4, 6 1, 2, 2, 3
4, 5, 7, 0 4, 6 1, 2, 2, 3, 4
5, 7, 10 4, 6 1, 2, 2, 3, 4, 4
5, 7,10 6 1, 2, 2, 3, 4, 4, 5
7, 10 6 1, 2, 2, 3, 4, 4, 5, 6
7, 10 1, 2, 2, 3, 4, 4, 5, 6, 7
10 1, 2, 2, 3, 4, 4, 5, 6, 7, 10

Sottosequenze

Supponiamo che l’array V contenga due sottoarray adiacenti ordinati

  • V’, da inf a medio
  • V”, da medio+1 a sup

e che l’obbiettivo sia ordinare l’array da inf a sup.

Esempio 1

Con

V = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6)
inf=1, medio=6, sup=10

allora

V' = (1, 2, 4, 5, 7, 10)
V'' = (2, 3, 4, 6)
V = (1, 2, 2, 3, 4, 4, 5, 6, 7, 10)

Esempio 2

Con

V = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6)
inf=4, medio=6, sup=7

allora

V' = (5, 7, 10)
V'' = (2)
V = (1, 2, 4, 2, 5, 7, 10, 3, 4, 6)

Si può adattare il codice precedente in modo che i dati siano copiati, in ordine, su un array temporaneo VTemp e poi ricopiati su V, da inf a sup.

Ricerca binaria

La ricerca binaria si applica agli array ordinati.

Essa controlla se l’elemento richiesto si trova nella posizione centrale dell’array altrimenti concentra la ricerca nella parte

  • BASSA se ha trovato un elemento MAGGIORE
  • ALTA se ha trovato un elemento MINORE

e continua finché

  • non trova l’elemento,
  • oppure rimane da esaminare un sottoarray vuoto.

Esempio

Sia V = (10, 25, 30, 40, 41, 42, 60)

Nel caso ottimo, l’elemento richiesto occupa la posizione centrale e basta un unico passo rb1
Nel caso pessimo, sono necessari 3 passi rb2
Se l’elemento non è presente si scopre dopo i 3 passi del caso pessimo. rb3p

Semplifico


Analizziamo il codice

Utilizzando la tecnica di calcolo della complessità in tempo possiamo concludere che

T(x) = c1+c2x

con x il numero di volte che viene eseguito il ciclo.

I calcoli approssimati per T danno

  • vettore vuoto: ~7
  • elemento trovato al 1° passo (in mezzo): c1+c2*1
  • elemento trovato al 2° passo: c1+c2*2
  • elemento trovato all’ultimo passo: c1+c2*(m-1)
  • elemento non presente: c1+c2*m

Supponiamo pessimisticamente di dover aspettare sempre fino all’ultimo passo, allora

T(n)=c1+c2*m.

Quanto vale m?

La dimensione del vettore sul quale si effettua la ricerca passo-passo è

  • n
  • ~n/2
  • ~n/4
  • ~n/8
  • ...
  • 2
  • 1
  • 0

Quando il valore della potenza di 2 a denominatore raggiunge n il ciclo termina sicuramente, cioè per

2m = n
m = log2n

quindi, nel caso pessimo

T(n) = c1+c2m = c1+c2log2n

Esempi numerici

n m
24 16 4
28 256 8
210 1.024 10
216 65.536 16
220 1.048.576 20
230 1.073.741.824 30

L’algoritmo di ricerca binaria applicato a un vettore con un miliardo di elementi garantisce una risposta dopo appena 30 passi!

Ricerca sequenziale

Individuare la posizione di un certo elemento all’interno di una sequenza data.

Posizione di un valore k all’interno di un array v

Purtroppo restituisce la posizione dell’ultimo valore presente.

Posizione di un elemento (la prima…)

Semplifico il ciclo

La ricerca sequenziale effettua una scansione dell’array finché non trova il valore richiesto, se presente, o l’array finisce.

Array ordinato

Se l’array è ordinato e l’elemento non compare la ricerca sequenziale può essere interrotta se l’elemento esaminato è maggiore di quello cercato

Ricerca sequenziale con sentinella

Si tratta di una versione leggermente migliorata dell’algoritmo.

Il confronto (i <= n) ripetuto a ogni passo può essere eliminato se si introduce la sentinella, la chiave della ricerca, alla prima posizione libera nell'array.
Il ciclo si chiude comunque nel caso in cui la chiave non esista.

Array ordinato

Se l'array è ordinato si può introdurre un ulteriore miglioramento...


Analisi della complessità, in tempo e asintotica, dell'algoritmo di ricerca sequenziale.

Il codice analizzato è il seguente

presenta operazioni di

  • assegnamento: 1, 5, 8, 9
  • confronto: 2, 4, 7
  • aritmetico-logiche: 3, 6

Il tempo totale richiesto da questo sottoprogramma alla CPU è

T = T1+(T2+T3+T4+T5+T6)*x+(T2+T3+T4)+T7+T8|9

con

  • (T2+T3+T4+T5+T6), le operazioni svolte ad ogni passo del While
  • x, il numero di volte che viene eseguito il While (da 0 a n)
  • (T2+T3+T4), quando K viene individuato alla posizione i-esima oppure il vettore finisce
  • T8|9, una delle due istruzioni finali

Per semplificare i calcoli si decide di trascurare le differenze esistenti tra i tempi di esecuzione delle diverse operazioni e di stabilire un tempo costante per tutte, allora

T = 6+5x

I valori effettivi di T sono

  • vettore vuoto: T1+(T2+T3+T4)+T7+T8 = 6
  • elemento in 1° posizione: T1+(T2+T3+T4)+T7+T9 = 6
  • elemento in 2° posizione: T1+[T2+T3+T4+T5+T6]+(T2+T3+T4)+T7+T9 = 6+5*1 = 11
  • elemento in 3° posizione: T1+[T2+T3+T4+T5+T6]*2+ ... = 6+5*2 = 16
  • ...
  • elemento in ultima posizione: 6+5*(n-1)
  • elemento non presente: 6+5n

Analizziamo i casi più interessanti

  • Caso ottimo, quando il vettore è vuoto oppure l'elemento K compare in 1° posizione: T=6
  • Caso pessimo, se l'elemento K non è presente: T=6+5n
  • Caso medio, supponiamo di effettuare n ricerche con l'elemento presente alle diverse posizioni: T=3.5+2.5n

Conclusioni

Il tempo richiesto è, tranne che nei casi banali, una funzione lineare di n, il numero di elementi presenti nel vettore

T(n)=c1+c2n

I valori delle due costanti c1 e c2 sono modesti e comunque poco significativi.


I calcoli per il caso medio

T=[(6+5*0)+(6+5*1)+(6+5*2)+...+(6+5(n-1))]/n
=[6n+5(1+2+...+n-1)]/n
=[6n+5(n-1)*n/2]/n
=6+5(n-1)/2
=6+5/2*n-5/2
=7/2+5/2*n
=3.5+2.5*n

Osserva che
1+2+...n=n(n+1)/2

Problemino di Carla

Quando è necessario scegliere chi interrogare oppure chi spostare in classe potrebbe essere utili avere un  generatore automatico di sequenze casuali di vittime predestinate del sistema scolastico nazionale…

Algoritmo

  1. Quanti allievi in classe?
  2. Acquisisci tutti nomi
  3. Mescola i nomi in modo imparziale
  4. Comunica la sequenza di nomi

Esempio

  • Elenco prima = { ‘Antoniol’, ‘Canzio’, ‘Cappellaro’, ‘Casanova De Marco’, ‘Chiovaro’, …, ‘Zucco’ }
  • Elenco dopo = { ‘Chiovaro’, ‘Antoniol’, ‘Peratoner’, ‘Cappellaro’, ‘Casanova De Marco’, …, ‘Canzio’ }

Approfondimenti

  1. I nomi degli allievi sono stringhe
  2. La sequenza di nomi diventa un array
  3. Per mescolare in modo imparziale si usa Random() e SCAMBIA()
  4. Le permutazioni possibili per n nomi sono n!=n*(n-1)*(n-2)*...*2*1.

Meglio strutturare…

Continua

  1. Fai in modo che il programma possa essere utilizzato per qualsiasi classe
    Numero studenti? Nomi?
  2. Se la sequenza risultante non è soddisfacente?
    Aggiungi un menu con le opzioni input-mescola-output...

Attenzione!

Se si aggiungono delle condizioni, come

  • Tizio non può sedersi con Caio
  • Sempronio è miope…
  • le coppie (1°-2°, 3°-4°, …) devono essere sempre diverse
  • chi oggi occupa la prima fila la prossima volta deve passare in seconda..

allora ogni permutazione generata deve

  • superare tutte le condizioni stabilite,
  • … anche quelle rispetto alle permutazioni utilizzate precedentemente
  • … che quindi devono essere salvate su memoria di massa (file).

Il problema diventa più complesso…

Lanciare i dadi – 2

Lanciare 2 dadi più volte e conteggiare le uscite

  1. Ciascuna faccia del singolo dado ha probabilità 1/6 (16,6… %)
  2. La probabilità della somma dipende dalle combinazioni disponibili…
    Combinazioni # probabilità
    2 1+1 1 1/36 2,77.. %
    3 1+2 2+1 2 2/36 5,55.. %
    4 1+3 2+2 3+1 3 3/36 8,33.. %
    5 1+4 2+3 3+2 4+1 4 4/36 11,11.. %
    6 1+5 2+4 3+3 4+2 5+1 5 5/36 13,88.. %
    7 1+6 2+5 3+4 4+3 5+2 6+1 6 6/36 16,66.. %
    8 2+6 3+5 4+4 5+3 6+2 5 5/36 13,88.. %
    9 3+6 4+5 5+4 6+3 4 4/36 11,11.. %
    10 4+6 5+5 6+4 3 3/36 8,33.. %
    11 5+6 6+5 2 2/36 5,55.. %
    12 6+6 1 1/36 2,77.. %

    Tutte le combinazioni

    36

Output

Prova con 1.000 e 10.000 lanci

Lanciare i dadi – 1

Lanciare un dado più volte e conteggiare le uscite

  1. Ciascuna faccia del dado ha probabilità 1/6 (16,6… %)
  2. Quanti lanci sono necessari per avere dati attendibili?
  3. Frequenze assolute e/o relative?

Output

Confrontando i risultati di 2 esperimenti

o di 3

risulta più evidente la tendenza delle frequenze relative verso la probabilità teorica

Sistema lineare

Il problema

Risolvere un sistema lineare (2 equazioni, 2 variabili)

cramer1

Utilizzando uno dei metodi disponibili (sostituzione, confronto, …) si arriva alla soluzione

cramer2

Sono necessari un certo numero di passaggi e le formule finali sono di difficile memorizzazione.
Osserva che la divisione non è possibile se ad-bc=0.

Metodo di Cramer

L’algoritmo di Cramer è semplice da ricordare e da applicare

Considera la matrice dei coefficienti del sistema

cramer3

e le matrici con la colonna dei termini noti al posto di quelle di x e y rispettivamente

cramer4
cramer5

Adesso calcola i tre determinanti corrispondenti (differenza dei prodotti incrociati…)

cramer6
cramer7
cramer8

Le formule per x e y precedenti possono essere riscritte…

cramer9

Equazione 2° grado

Risolvere un’equazione di secondo grado ax2+bx+c=0, dati i coefficienti a, b e c.

secondo_gradoAnalisi

Un po’ di matematica…

 eq2_1

Esempi

Istanza Elaborazione Risposta
1 x2-5x+6=0 a=1
b=-5
c=6
D=b2-4ac=…
D=1>0
x1=…
x2=…
2
3
2 x2+2x+1=0 a=1
b=2
c=1
D=b2-4ac=…
D=0
x1,2=-2/2 -1
3 x2+x+1=0 a=1
b=1
c=1
D=b2-4ac=…
D=-3<0
Impossibile

Più compatto…


secondo_grado_2Se a=0 si discute l’equazione di primo grado bx+c=0, altrimenti si discute l’equazione di secondo grado ax2+bx+c=0

eq2_2


Se il discriminante è minore di zero si calcolano le 2 soluzioni complesse coniugate

eq2_3

Equazione 1° grado

Risolvere un’equazione di primo grado ax+b=0, dati i valori dei coefficienti a e b.

primo_gradoAnalisi

Un po’ di matematica…

eq1

Esempi

Istanza Elaborazione Risposta
1 x+2=0 a=1
b=2
x=-2/1 -2
2 2x-3=0 a=2
b=-3
x=-(-3)/2 3/2
3 0x+0=0 a=0
b=0
0=0 Indeterminata
4 0x+2=0 a=0
b=2
2=0 Impossibile

Più compatto…