Category Archives: PROBLEMI

Shaker sort

Si tratta di un bubble sort nei due sensi.
Si tenta di ridurre la lunghezza delle passate partendo dai due lati alternativamente.

Bubble Sort

Algoritmo molto diffuso perché intuitivo ma con prestazioni scadenti.

Una passataUna passata

Una passata con ordinamenti di due elementi su tutte le n-1 coppie, all’interno di un array, provoca lo spostamento in alto della bolla più grande.

Sia

V=(20, 15, 10, 3)

alla fine della passata l’elemento più grande 20 si trova in ultima posizione

V=(15, 10, 3, 20)

Bubble sort

N passate, sulle n-1 coppie, ordinano sicuramente l’array

In realtà sono necessarie al massimo N-1 passate su N-i coppie (di ciascuna passata)

Osserva,,,

Bubble Sort

Miglioramenti?

Nel caso in cui il vettore risulti ordinato dopo un certo numero di passate è possibile interrompere l’esecuzione del While() introducendo la variabile ANCORA

Il numero di passate dipende solo da ANCORA

Se la variabile ANCORA non interviene si ha una passata in più.

Elimino la differenza N-i

La lunghezza del vettore dipende da UltimoScambio piuttosto che da UltimaCoppia

In questo modo le passate diventano più corte.

Il While…Do esterno diventa Repeat…Until

Elimino la variabile FINITO


L’istruzione SCAMBIA() viene eseguita ogni volta che ha successo il controllo dell’istruzione If(...) Then.
Consideriamo il caso pessimo, cioè che succeda a ogni passo.
Quanti sono i controlli e le esecuzioni di SCAMBIA()?

i j TC TS
1 1…n-1 n-1 n-1
2 1…n-2 n-2 n-2
n-2 1…(n-(n-2))
1…2
2 2
n-1 1…(n-(n-1))
1…1
1 1

Quindi

TC(n)=TS(n)=(n-1)+(n-2)+...+1.

Quanto vale la somma?
Sappiamo che 1+2+...n=n(n+1)/2 e quindi

T(n)=(n-1)n/2=½n2-½n.

La complessità in tempo asintotica dell’algoritmo di ordinamento Bubble Sort è O(n2), sia per il numero di confronti che per il numero di scambi.

Nel caso ottimo, il vettore già ordinato, il numero di scambi è 0 ma rimane quadratico il numero di confronti.

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