Algoritmi e Strutture Dati

appuntiDiIngegneria

Algoritmi e Strutture

Dati

Sommario

1.1. Algoritmi ...........................................................................................................................................2

1.1.1. Algoritmi di Ordinamento di un Array ............................................................................................6

1.1.2. Algoritmi di Ricerca in un Array ................................................................................................... 12

1.2. Strutture Dati .................................................................................................................................. 14

1.2.1. Lista ............................................................................................................................................ 14

1.2.2. Stack ........................................................................................................................................... 16

1.2.3. Coda ............................................................................................................................................ 17

1.2.4. Grafo ........................................................................................................................................... 20

1.2.5. Albero ......................................................................................................................................... 25

1

1.1. Algoritmi

La programmazione è l'attività di sviluppare programmi per un calcolatore, lo scopo della scrittura

di un programma è la risoluzione di un determinato problema, operazione che richiede degli step:

 Formulare il problema (specifica dei requisiti) in modo più o meno formale.

 Capire il problema e scomporlo in parti gestibili (analisi del problema). Soltanto i problemi

per cui è possibile una formalizzazione matematica possono essere risolti con la

programmazione informatica.

 Progettare una soluzione (algoritmo).

 Implementare la soluzione (scrittura del codice).

 Testare la soluzione e correggere eventuali errori (verifica del programma, testing e

debugging).

 Tenere sempre aggiornato il programma (manutenzione).

In genere i problemi vengono scomposti in una sequenza di sottoproblemi più piccoli: la soluzione

di tutti i sottoproblemi implica anche la soluzione del problema. Per ciascuno di questi

sottoproblemi occorre sviluppare un determinato algoritmo. Si definisce algoritmo una sequenza

finita di passi che risolve automaticamente un problema, e tale sequenza deve essere discreta, di

lunghezza finita, deterministica (dopo ogni passo si sa precisamente qual è il prossimo) e ripetibile.

Esempi di algoritmi si possono trovare nella vita di tutti i giorni, un tipico esempio è la spesa al

supermercato, che viene schematizzata nel seguente modo:

 Sequenza: le azioni vengono svolte una alla volta (non c’è parallelismo);

 Finita: la lista della spesa è un qualcosa di finito ed inoltre il numero di azioni che si

svolgono è sempre finito (non si rischia di stare in eterno nel supermercato!);

 Passi: ogni singolo passo (riempire il carrello, cercare sullo scaffale, ...) non implica per se il

concetto di spesa: è solo nella sequenza (ossia nella concatenazione intelligente di tali

passi) che il problema viene risolto;

 Automaticamente: una volta scritto e lanciato l’algoritmo, non c’è bisogno di intervento

esterno; l’esecutore ha tutti gli elementi per poter risolvere il problema. 2

 Osservabile: ogni passo deve avere un effetto osservabile, cioè deve produrre qualcosa, ad

esempio il carrello si riempie di un nuovo prodotto.

 Riproducibile: a partire dallo stesso stato iniziale, lo stesso algoritmo deve produrre

sempre lo stesso risultato.

Un algoritmo per risolvere un problema deve lavorare su dei dati, che possono essere di tre tipi:

 Dati in input: Sono i dati in ingresso di un algoritmo. Possono essere digitati dall'utente con la

tastiera oppure letti da un file o ricevuti telematicamente via modem.

 Dati di elaborazione: Sono i dati temporanei creati durante l'esecuzione del programma. Non

sono dati né di input, né di output.

 Dati in output: Sono i dati in uscita di un algoritmo, ossia il risultato dell'operazione. Possono

essere stampati a video, su una stampante oppure salvati su un file o trasmessi via modem.

Procedendo però con ordine, si mostrano gli stadi di progettazione di un programma:

La prima fase consiste nella ricerca della soluzione migliore al problema, successivamente si

converte l’idea in una soluzione formale, ovvero in un testo che descrive la soluzione in modo

formale (algoritmo). L’algoritmo viene tradotto in una sequenza di istruzioni comprensibili

all’esecutore (in questo caso l’elaboratore elettronico, ma anche un umano può eseguire un

algoritmo): questa sequenza si chiama programma. Si nota che l’operazione di formalizzazione

della soluzione consente una più semplice traduzione nelle regole di realizzazione. Per passare dal

problema alla Soluzione aiuta molto l’esperienza, mentre nel passaggio dalla Soluzione alla

Soluzione Formale esistono diversi strumenti automatici o metodi formali di cui il programmatore

può avvalersi; infine nel passaggio dalla Soluzione Formale al Programma vengono in aiuto le

Tecniche di Programmazione. Il programma deve essere provato con un insieme significativo di

dati per garantire che funzionerà in ogni occasione (qualsiasi siano i dati di input). Infine occorre

3

documentare opportunamente il programma a beneficio di chi lo userà ed eventualmente lo

modificherà. Per maggiore chiarezza viene mostrato un esempio di progettazione di una soluzione:

Sono disponibili numerosi strumenti per rappresentare una soluzione in modo formale

(algoritmo), i più utilizzati sono:

 Pseudo-Codice: è un modo testuale di rappresentare un algoritmo a metà fra il linguaggio

naturale ed un linguaggio di programmazione, lo svantaggio è che a volte l’interpretazione

può essere più complicata perché non esiste un unico pseudo-linguaggio standardizzato.

 Diagrammi di Flusso: anche detti Flow Chart, descrivono gli algoritmi utilizzando un

approccio grafico che è molto intuitivo e astratto, ma richiede l’apprendimento della

funzione dei vari tipi di blocco.

 Linguaggio Naturale: è il modo testuale di rappresentare informalmente un algoritmo più

semplice in assoluto perché consiste nel descrivere l’algoritmo a parole.

 Linguaggio di Programmazione: è un modo testuale di descrivere formalmente un

algoritmo, si utilizza la sintassi e la semantica di un certo linguaggio di programmazione che

però è necessario conoscere per comprendere l’algoritmo.

L’approccio che più si utilizza è quello dei Flow Chart, che è composto da una serie di blocchi

elementari che descrivono azioni o decisioni, ed archi orientati che collegano i vari blocchi per

descrivere la sequenza di svolgimento delle azioni. Di seguito sono riportati i blocchi elementari ed

anche un piccolo esempio per comprenderne meglio l’utilizzo, che effettua la stampa del valore

assoluto di un numero A: 4

La teoria degli algoritmi fornisce algoritmi notevoli per risolvere determinati problemi, e classifica

la complessità dei problemi intesa come la complessità del migliore algoritmo che lo risolve. Per

complessità di un algoritmo si intende invece la misura del numero di passi che si devono eseguire

per risolvere un problema. I problemi possono essere di 2 tipi.

 Problemi decidibili: hanno una soluzione algoritmica.

 Problemi Indecidibili: NON hanno una soluzione algoritmica.

È possibile classificare i problemi in base alla quantità di risorse necessarie per ottenere la

soluzione, e siccome per certi tipi di problemi le difficoltà incontrate per trovare un algoritmo

efficiente sono le stesse, è possibile raggruppare i problemi in tre categorie:

 k

Problemi Trattabili (n ): ammettono algoritmi di

soluzione efficiente, ad esempio la ricerca del

massimo e l’ordinamento di n numeri.

 n

Problemi Intrattabili : non possono essere

(k )

risolti per loro natura da algoritmi efficienti, ad

esempio il problema della cricca.

 Problemi Da Capire: non sono stati ancora trovati

algoritmi efficienti che li risolvano.

Sono state definite diverse classi di complessità dei Problemi che adesso si vanno ad analizzare:

Classe di Complessità P: comprende i cosiddetti Problemi Polinomiali, cioè i problemi per

il quale esistono soluzioni praticabili, cioè di complessità O(f(n)), dove f(n) è un polinomio

oppure è una funzione limitata superiormente da un polinomio. In altre parole sarebbero i

problemi che prima sono stati chiamati Trattabili. I problemi Intrattabili sono invece quelli

che non possono essere risolti in un tempo polinomiale, ma in un tempo esponenziale

oppure asintoticamente superiore ad ogni polinomio.

Classe di Complessità NP: comprende quei problemi che, posti in una qualsiasi forma di

riconoscimento o di decisione, sono verificabili in tempo polinomiale. Non si tratta perciò

5

di decidere in tempo polinomiale se l’istanza è affermativa o meno, ma di verificare il

problema in tempo polinomiale, data un’istanza affermativa del problema. L’appartenenza

alla classe NP appare, quindi, meno riduttiva dell’appartenenza a P; infatti, affinché un

problema sia in NP non è necessario che sia risolubile in tempo polinomiale, ma solo che,

se l’istanza è affermativa, esso sia verificabile in tempo polinomiale. Al contrario, è certo

che se un problema è polinomiale allora appartiene a NP. Quindi NP è una classe più

generale della P che la contiene.

Classe di Complessità NP Completa: sono dei problemi NP che hanno la seguente

proprietà: una soluzione deterministica polinomiale in termini di tempo per ognuno di essi

fornirebbe anche una soluzione polinomiale per tutti gli altri problemi in NP. Quindi se si

dimostra che anche solo per uno dei problemi NP completi esiste una soluzione

deterministica polinomiale allora P ed NP sono equivalenti.

1.1.1. Algoritmi di Ordinamento di un Array

Su di un vettore è possibile applicare una moltitudine di algoritmi notevoli, ad esempio per

ricercare il max o il min, oppure per ordinare in ordine crescente o decrescente tutti i suoi

elementi, oppure per ricercare un determinato valore. In particolare si analizzano gli algoritmi di

ordinamento (sorting algorithm), i quali hanno come obiettivo quello di ordinare una sequenza di

elementi in base a una certa relazione d’ordine. I principali algoritmi sono:

1) Naive Sort: semplice, intuitivo, poco efficiente. Esso è anche chiamato Selection Sort, e si basa

su un processo iterativo che ha come obiettivo la selezione dell’elemento della sequenza di

origine che contiene il valore maggiore (nel caso di ordinamento crescente), e lo scambio di

tale valore con il valore contenuto nell’ultima posizione, in modo da ridurre la sequenza di

origine (la dimensione dell’array) di un elemento ad ogni iterazione (infatti se l’ultimo

elemento del vettore adesso contiene il massimo sarà inutile considerarlo nelle successive

iterazioni). Per valutare la complessità dell’algoritmo basta analizzare il numero di confronti

effettuati, e si nota subito che l’algoritmo è poco efficiente perché esso effettua gli stessi

confronti sia per un array disordinato, sia per un array già ordinato. Il numero di confronti

necessari vale sempre: (N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 = O( /2) perché per ogni

iterazione occorre fare i confronti per ricercare il massimo del vettore. Nel caso peggiore, il

numero di scambi necessari è N-1, infatti viene effettuato al più uno scambio per iterazione,

ed il numero di confronti è /2. 6

void naiveSort(int v[], int n){

int p;

while (n>1) {

p = trovaPosMax(v,n);

if (p<n-1) scambia(&v[p],&v[n-1]);

n--;

}

}

int trovaPosMax(int v[], int n){

int i, posMax=0;

for (i=1; i<n; i++){

if (v[posMax]<v[i]) posMax=i;

}

return posMax;

}

2) Bubble Sort: semplice, un po’ più efficiente del Naive Sort, esso corregge il difetto principale

del naïve sort, che è quello di non accorgersi se l’array, ad un certo punto, è già ordinato. Il

Bubble Sort (letteralmente: ordinamento a bolla) è un semplice algoritmo di ordinamento

basato sullo scambio di elementi adiacenti: ad ogni iterazione, considera una ad una tutte le

possibili coppie di elementi adiacenti, scambiandoli se risultano nell’ordine errato, così, dopo

ogni iterazione, l’elemento massimo viene collocato alla parte di array considerata. Quando

non si verificano scambi, l’array è ordinato, e l’algoritmo termina. L’algoritmo deve il suo nome

al modo in cui gli elementi vengono ordinati cioè quelli più piccoli "risalgono" verso

un'estremità della lista, così come fanno le bollicine in un bicchiere di spumante; al contrario

quelli più grandi "affondano" verso l