Monthly Archives: dicembre 2014

Unità Date

Analisi

Unità

Test

Unità Logici

Analisi

  • Elementi: VERO, FALSO
  • Struttura: semplice
  • Dominio: VERO, FALSO
  • Operazioni: Leggi(), Scrivi(), MyAnd(), MyOr(), MyNot(), MyXor()

Specifica delle operazioni

LEGGI()
  • Interfaccia: Procedure LEGGI(A: LOGICO);
  • Effetti: inserimento del valore logico VERO(1) o FALSO (0) in A
  • Prerequisiti: input controllato di una stringa di tipo ‘Vero’/’Falso’
  • Esempio: Leggi(A);
SCRIVI()
  • Interfaccia: Procedure SCRIVI(A: LOGICO);
  • Effetti: stampa il valore logico associato alla variabile A
  • Prerequisiti: – – –
  • Esempio: Scrivi(A);
MYAND()
  • Interfaccia: Function MYAND(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione AND
  • Prerequisiti: – – –
  • Esempio: C:=MYAND(A,B);
MYOR()
  • Interfaccia: Function MYOR(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione OR
  • Prerequisiti: – – –
  • Esempio: C:=MYOR(A,B);
MYNOT()
  • Interfaccia: Function MYNOT(A: LOGICO): LOGICO;
  • Effetti: Simula la funzione NOT
  • Prerequisiti: – – –
  • Esempio: A:=MYNOT(A);
MYXOR()
  • Interfaccia: Function MYXOR(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione XOR
  • Prerequisiti: – – –
  • Esempio: C:=MYXOR(A,B);

Unità

Test

Lista multipla

Una possibile combinazione di lista multipla è la seguente

  • lista primaria (A-B-C): a doppi puntatori con puntatore di testa e puntatore di coda
  • liste secondarie (p, q-r-s, …): semplici con puntatore di testa e puntatore di coda

image

Dichiarazioni

Lista bidirezionale

Puntatore di testa, puntatore di coda e tre nodi con puntatori nelle due direzioni

image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa

Aggiungere un nodo in Coda

Aggiungere un nodo in Ordine

Lista circolare

Puntatore di testa e tre nodi con informazioni A-B-C

image

o meglio, con puntatore di coda…

image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa


Aggiungere un nodo in Coda


Aggiungere un nodo in Ordine

Lista con testa e coda

Puntatore di testa, puntatore di coda e tre nodi con informazioni A-B-C
image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa

Aggiungere un nodo in Coda

Aggiungere un nodo in Ordine

Eliminare un nodo in Testa

Lista semplice

Puntatore di testa e tre nodi con informazioni A-B-C

image

Dichiarazioni

Operazioni

Aggiungere un nodo in TESTA

Aggiungere un nodo in CODA

Aggiungere un nodo in ORDINE

Aggiungere un nodo DOPO un certo nodo

Per ipotesi Q esiste.

Eliminare un nodo in TESTA

Eliminare un nodo DOPO un certo nodo

Per ipotesi Q esiste mentre Q^.Succ…

Contare i nodi

Eliminare TUTTI i nodi

Confronta

Esercizi

  1. Visualizzare il contenuto della lista
  2. Quanti nodi con una certa informazione?
  3. Ricerca sequenziale (puntatore e/o indice…)
  4. Minimo, massimo, …, totale, media?
  5. Copiare, appendere, concatenare
  6. Eliminare un nodo con chiave, con puntatore
  7. Scambiare le informazioni di due nodi
  8. Ordinare

Insertion sort

Algoritmo alternativo al bubble sort ma più complesso…

A ogni passata l’elemento i-esimo viene parcheggiato in X.
Gli elementi più grandi, che lo precedono, vengono spostati in avanti di una posizione e X viene posizionato al posto giusto.
In questo modo il sottovettore da 1 a i è sicuramente ordinato.

Osserva…

is1

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.