Che materia stai cercando?

Appunti Corso Algoritmi e Programmazione

Appunti el corso di Algoritmi e Programmazione: punti chiave del corso (non comprese le strutture dati).
Gli appunti sono basati su una versione del corso da 12 CFU con riferimenti soprattutto alle lezioni del professor Camurati. Scarica il file in formato PDF!

Esame di Algoritmi e programmazione avanzata docente Prof. G. Cabodi

Anteprima

ESTRATTO DOCUMENTO

Collezioni di dati e operazioni sulle liste

Sequenza lineare: insieme finito di elementi disposti consecutivamente in cui a ogni elemento è associato

univocamente un indice. Sulle coppie di elementi è definita una relazione di predecessore/successore.

Vettore (o array): è la modalità di memorizzazione per la quale i dati vengono salvati in posizioni contigue in

memoria. Gli elementi di essi sono ad accesso diretto di costo unitario O(1).

Liste: è la modalità di memorizzazione per la quale i dati vengono immagazzinati in posizioni non contigue in

memoria. Gli elementi sono accessibili solo scorrendo quelli che vengono prima, quindi sono ad accesso

sequenziale di costo (massimo) lineare O(n).

Operazioni sulle liste:

o Ricerca di un elemento il cui campo chiave di ricerca è uguale alla chiave data.

o Inserzione di un elemento in testa, in coda o in posizione specifica che non comprometta la stabilità.

o Estrazione di un elemento che si trova in testa, in coda o che abbia un campo con chiave uguale alla

chiave di cancellazione.

Code generalizzate: sono collezioni di oggetti (dati) per le quali è possibile solo un accesso sequenziale.

Operazioni sulle code:

o Insert: inserisci un nuovo oggetto alla collezione.

o Search: cerca se l’oggetto è nella collezione.

o Delete: elimina l’oggetto dalla collezione.

o Cronologico

▪ LIFO: Last-In First-Out, cioè l’eliminazione del contenuto inserito più recentemente.

L’inserzione si chiama push e l’estrazione pop. [tipico dello stack (o pila)].

▪ FIFO: First-In First-Out, cioè l’eliminazione del contenuto inserito meno

recentemente. L’insersione avviene in coda (tail) e si chiama enqueue e l’estrazione

avviene dalla testa (head) e si chiama dequeue. [tipico della queue (o coda)].

o Prioritario: l’inserzione garantisce che, estraendo dalla testa si ottenga il dato di priorità

massima [coda a priorità].

o Per Contenuto: l’estrazione ritorna un contenuto secondo determinati criteri [tabelle di

simboli].

o Altro: inizializzazione della coda, conteggio degli oggetti, distruzione o copia della coda.

05. RICORSIONE E PARADIGMA DIVIDE ET IMPERA

La ricorsione in informatica è quel metodo di programmazione che porta un particolare processo a richiamare

sé stesso: esso durante la sua esecuzione chiamerà un suo clone per svolgere il suo stesso lavoro su un sotto

problema più semplice aspettando che esso restituisca il risultato utile per calcolare la soluzione al problema

più grande. Questo implica che il problema debba essere scomponibile in sotto problemi e che esista una

soluzione al problema banale. La ricorsione può “scendere per molti livelli”: il processo si può richiamare per

un numero indefinito di volte. Vediamo alcuni esempi semplici di problemi risolti tramite ricorsione.

• Fattoriale: si calcoli il fattoriale di n:

long fact(long n)

{ //soluzione al problema banale

if(n==0||n==1) return 1;

//chiamata ricorsiva

return n*fact(n-1);

}

• Fibonacci: si calcoli l’n-esimo numero di Fibonacci:

long fib(int n)

{ //soluzioni ai problemi banali

if(n==0||n==1) return n;

//chiamata ricorsiva

return fib(n-1)+fib(n-2);

}

• Ricerca dicotomica in un vettore:

int binarySearch(int *v,int l,int r,item key)

{//v è il vettore, l è l'estremo sx,r il dx e

key è ciò che cerchiamo

//NB: il vettore è ordinato

int i=(r-l)/2; //prendiamo l'elemento in

mezzo

if(v[i]<key)//vuol dire che la chiave sta

dopo e si ricorre sul sottovettore destro

return binarySearch(v,i+1,r,key);

if(v[i]>key)//la chiave sta prima quindi

si ricorre sul sottovettore sinistro

return binarySearch(v,l,i-1,key);

//se non è nè maggiore nè minore allora è uguale

return i;

}

NB: 1. L’esplorazione di un albero binario comporta una complessità lineare. 2. Esistono 2 paradigmi di

ricorsione: Divide et Impera (es. ricerca binaria), Decrease and Conquer (es. fattoriale). Uno si basa su un

fattore di riduzione del problema non costante e l’altro comporta una riduzione fissata ad ogni passo

ricorsivo. 3. Una funzione ricorsiva può occupare molto spazio nello stack di esecuzione del programma (se

si sforano i limiti si dice stack overflow), quindi quando si può è meglio usare funzioni tail-recursive: funzioni

ricorsive che ritornano il valore della funzione chiamata (il compilatore gestisce meglio questo genere di

ricorsione). 4. Ogni funzione ricorsiva può essere scritta in forma iterativa e viceversa!

06. GLI ORDINAMENTI RICORSIVI (Versioni dei codici non commentate in fondo)

MERGE SORT

Il Merge Sort è un ordinamento ricorsivo che consiste nell’unire due sotto vettori ordinati in un vettore a sua

volta ordinato tramite una funzione di merge. Questo ordinamento ha pro e un contro: è stabile e garantisce

una complessità linearitmica, ma non è in loco! La sua utilità dipende dalle esigenze che si hanno nel

momento di scegliere l’ordinamento.

FUNZIONE RICORSIVA: FUNZIONE DI MERGING:

//Mergesort Top Down (esiste bottom up) void merge(Item *a,int l,int m,int r)

void mergeSort(Item *a, int l, int r) { //dichiariamo i 3 indici

{ //Dividiamo il vettore in 2 sotto vettori int i,j,k;

//come per la ricerca binaria //allochiamo il vettore ausiliario

int m = (r+l)/2; Item *aux = malloc((r-l)* sizeof(Item));

//terminazione della ricorsione //salviamo nel vettore ausiliario gli

//soluzione banale: vettore di 1 elemento elementi di a

//è già ordinato //facendo attenzione che i maggiori siano

if(r<=l) return; in mezzo e

//Sotto vettore sinistro //i più piccoli sugli estremi

mergeSort(a,l,m); for(i=m+1; i>l; i--) aux[i-1] = a[i-1];

//sotto vettore destro //la parte sinistra è ok

mergeSort(a,m+1,r); for(j=m; j<r; j++) aux[r+m-j] = a[j+1];

//unione dei sottovettori //leggi con attenzione

merge(a,l,m,r); //in questo ciclo andiamo a ricopiare in a

} i valori in modo

//ordinato come se avessimo i due vettori

del modello classico

for(k=l; k<=r; k++)

a[k]= (less(aux[j],aux[i]))?

(aux[j--]):(aux[i++]);

}

ANALISI DI COMPLESSITA NEL CASO PEGGIORE:

QUICK SORT

Il Quick sort è un algoritmo di ordinamento ricorsivo che prevede la scelta, ad ogni passo della ricorsione, di

un elemento, detto pivot, che alla fine della funzione di partizione sarà nella sua posizione finale e

contemporaneamente dividerà il vettore in 2 sotto vettori su cui ricorrere e partizionare nuovamente.

//Quick Sort di base int partition(Item *a,int l,int r)

void quickSort(Item *a,int l, int r) { //v è l'elemento più a destra che

{ int i; //dopo la partition sarà nella sua

//cond di terminazione: se l'indice posizione

//sfora durante la chiamata ricorsiva //finale di ordinamento (pivot)

if(r<=l) return; int i,j; Item v = a[r];

//i è l'indice dell'elemento ordinato //ciclo for per dividere gli elementi con

//partition divide gli elementi e ritorna il

i //pivot al centro

i=partition(a,l,r); for(i = l-1, j = r; i < j;) {

//a sinistra di i sono minori di a[i] //questi sono quelli più piccoli

quickSort(a,l,i-1); //e si trova l'indice del primo

//a destra sono maggiori //non più piccolo

quickSort(a,i+1,r); for(;less(a[i],v);++i);

} //stesso ma col primo non più grande

for(;(j!=1)&&(less(v,a[j]));--j);

//se non si sono scavalcati gli indici

//si scambiano gli elementi del

vettore if(i<j)

swap(a[i],a[j]);

}

//infine si scambia l'elemento che sta al

//posto del pivot con il pivot

swap(a[i],a[r]);

return i;

}

Nonostante il caso peggiore (vettore ordinato nel

senso opposto di ordinamento). L’analisi della

complessità di questo algoritmo garantisce che nel

caso medio la complessità è di tipo linearitmico. Per

questo il Quick Sort è l’algoritmo più utilizzato.

MERGE SORT (Non commentato) QUICK SORT (Non Commentato)

void quickSort(Item *a,int l, int r)

void mergeSort(Item *a, int l, int r) {

{ int i;

int m = (r+l)/2; if(r<=l) return;

if(r<=l) return; i=partition(a,l,r);

mergeSort(a,l,m); quickSort(a,l,i-1);

mergeSort(a,m+1,r); quickSort(a,i+1,r);

merge(a,l,m,r); }

}

void merge(Item *a,int l,int m,int r) int partition(Item *a,int l,int r)

{ {

int i,j,k; int i,j; Item v = a[r];

Item *aux = malloc((r-l)* sizeof(Item)); for(i = l-1, j = r; i < j;) {

for(i=m+1; i>l; i--) aux[i-1] = a[i-1]; for(;less(a[i],v);++i);

for(j=m; j<r; j++) aux[r+m-j] = a[j+1]; for(;(j!=1)&&(less(v,a[j]));--j);

for(k=l; k<=r; k++) if(i<j)

a[k]= swap(a[i],a[j]);

(less(aux[j],aux[i]))? (aux[j--]):(aux[i++]); }

} swap(a[i],a[r]);

return i;

}

07.PROBLEMI DI RICERCA E OTTIMIZZAZIONE (08.ESEMPI SE VUOI CAPIRE O RIPASSARE)

I problemi di ricerca sono quei problemi per i quali è necessario esplorare lo spazio delle soluzioni per

cercarne almeno una valida, quelli di ottimizzazione necessitano della soluzione che più delle altre soddisfi

determinati requisiti.

Nello spazio delle soluzioni chiamiamo soluzione ottima quella soluzione che soddisfa questi requisiti a livello

globale (altrimenti ottima localmente).

Un algoritmo di ricerca che opera su strutture dati procede in passi definiti:

1.mette la soluzione iniziale nella struttura dati

2.estrae una soluzione parziale dalla struttura dati finché non trova una soluzione valida e la estrae

3.ripete il punto 2 finché la struttura dati non si svuota o non ci sono più soluzioni

4.termina.

Se la struttura dati è

• una coda la ricerca è in ampiezza.

• una pila la ricerca è in profondità.

Se l’algoritmo

• non conosce nulla del problema, si dice non informato.

• se ha conoscenza specifica (euristica), si dice informato.

• se è in grado di esplorare tutto lo spazio si dice completo.

Noi operiamo su spazi di soluzioni con algoritmi di profondità, non informati, completi e ricorsivi:

schematizzabili come alberi binari (di ricerca) dei quali la radice è la soluzione nulla e le foglie sono tutte le

soluzioni che compongono lo spazio.

RICHIAMI DI CALCOLO COMBINATORIO E METODI DI ESPLORAZIONE DELLO SPAZIO DELLE SOLUZIONI

(codici associati allegati)

MODELLO: Moltiplicazione

SCOPO: non so spiegare, esempio: ci sono 2 antipasti, 3 primi e 2 secondi, quanti menu posso comporre?

(2x3x2=12).


PAGINE

23

PESO

4.08 MB

PUBBLICATO

6 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher vale78420 di informazioni apprese con la frequenza delle lezioni di Algoritmi e programmazione avanzata e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Torino - Polito o del prof Cabodi Giampiero.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Algoritmi e programmazione avanzata

Riassunto - APA (Algoritmi e Programmazione Avanzata) - Teoria per gli esercizi - Professore Camurati
Appunto
Riassunto di Algoritmi e Programmazione Avanzata (APA)
Appunto
Riassunto - APA (Algoritmi e Programmazione Avanzata) - Teoria per gli esercizi - Professore Camurati
Appunto
Riassunto esame Sistemi Operativi, prof. Laface
Appunto