Algoritmi e Strutture Dati

Algoritmi e strutture dati

Introduzione

La soluzione di un problema attraverso un computer si suddivide in tre attività principali: analisi, programmazione ed elaborazione (di dati, per ottenere un risultato). Solo l’ultima fase viene effettuata dalla macchina, le restanti fasi vengono effettuate dall’utente.

Problema - Analisi - Algoritmo - Programmazione - Programma - Elaborazione - Strutture dati - Risultato - Dati.

La fase di analisi richiede che il problema venga analizzato logicamente, infatti esso deve essere ben posto e completo, ossia che non richieda dati non disponibili o metodi risolutivi sconosciuti.

Il passo successivo è quello di formalizzare i dati disponibili in strutture astratte di dati e in metodi di risoluzione (ossia algoritmi), che non devono dipendere né dalla macchina su cui verranno implementati, né dal linguaggio di programmazione usato.

Un algoritmo è un insieme finito di istruzioni definite e non ambigue, che, partendo da assegnate condizioni iniziali, produce il risultato di una classe di problemi e termina in tempo finito; le caratteristiche fondamentali di un algoritmo sono: finitezza, non ambiguità e generalità.

Le strutture dati sono dei modi di rappresentare ed elaborare le informazioni (o dati). Fondamentale per un algoritmo è la sua analisi, ossia prevedere le risorse di tempo e memoria necessarie alla sua esecuzione; la memoria di base viene usata per memorizzare le istruzioni e i dati (ed eventuali variabili di appoggio), ma alcuni algoritmi richiedono uno spazio aggiuntivo, ad esempio, usato per fare una copia dei dati.

Successivamente vi è la fase di programmazione, dove le strutture dati astratte vengono tradotte in strutture concrete gestibili dal computer e allo stesso modo gli algoritmi vengono tradotti in programmi eseguibili.

Ottenuto, quindi, un programma, si passa al passo di elaborazione, nel quale vengono ricevuti in input dal programma stesso i dati necessari alla risoluzione del problema iniziale e dopo questa fase si otterrà in output un risultato, corrispondente alla soluzione del problema.

Valutazione di un algoritmo (complessità)

Per progettare un buon algoritmo è necessario tener conto di alcuni aspetti qualitativi e quantitativi. Alcune buone qualità di un algoritmo possono essere le seguenti:

• Aspetti qualitativi: Generalità, Correttezza, Semplicità.
• Aspetti quantitativi: Spazio, Tempo (numero di istruzioni).

Per misurare le prestazioni di un algoritmo si fissa un modello di calcolo che consente di valutare, a variare della dimensione del problema, la sua complessità totale. Viene, quindi, indicato con n la quantità dei dati che vengono processati.

Per valutarne la complessità, bisogna stabilire quale è l’operazione astratta principale su cui è basato l’algoritmo stesso. Per rappresentare le funzioni che delimitano il tempo di esecuzione di un algoritmo viene usata la notazione di ordine “O grande”. Ad esempio, in un algoritmo la cui operazione dominante viene eseguita cn volte, con c costante non nulla, si dice che esso ha complessità di ordine n² e si indica con O(n²).

Basta, quindi, individuare il grado maggiore di una funzione per capirne l’ordine di grandezza. Un “O grande” è una funzione g(n) O(f(n)) se esiste una costante c ≠ 0 ed un valore n₀ > 0 per cui g(n) ≤ cf(n) per ogni n > n₀.

Nell’analizzare un algoritmo si considerano di solito due misure: il comportamento nel caso pessimo e nel caso medio. La complessità nel caso pessimo per una certa dimensione n di un problema, corrisponde al numero massimo di operazioni svolte dall’algoritmo. La complessità nel caso medio corrisponde alla valutazione di tutte le complessità in base a tutti i casi possibili, sommarle e dividere il tutto per il numero dei casi possibili.

Esistono cinque classi differenti di complessità:

• log n
• n
• n log n
• n²
• nⁿ

La dipendenza da n può appartenere, dunque, a cinque classi differenti, tra i casi migliori vi è la dipendenza logaritmica, mentre tra i casi peggiori vi è quella esponenziale.

I problemi si possono suddividere in decidibili ed in indecidibili. Tra i decidibili troviamo i problemi trattabili, ossia risolvibili in un tempo relativamente breve, e quelli intrattabili, che hanno complessità esponenziale e richiedono molto più tempo per essere risolti.

Esempio valutazione Algoritmo di Ricerca Sequenziale

v₀, v₁, …, v_n-1 n elementi in una lista, devo cercare k

• i = 0; C₁: eseguita 1 volta (assegnazione)
• finché i < n e v_i ≠ k C₂: eseguita n volte (controllo)
• esegui i = i + 1; C₃: eseguita n volte (assegnazione)
• se i = n allora scrivi "ricerca fallita"; C₄: eseguita 1 volta (controllo)
• altrimenti restituisci v_i;

T_max(n) = 1·C₁ + n·C₂ + n·C₃ + 1·C₄ = C₁ + C₄ + n(C₂ + C₃) = A + B·n —> equazione di una retta, quindi ha un costo costante/lineare

Relazioni di Ricorrenza

Molti algoritmi sono basati sul principio di scomporre un problema in problemi più piccoli. A causa di ciò, la complessità dell’algoritmo è data dalla complessità e dal numero dei sottoproblemi e dal costo della decomposizione. Molti di questi sottoproblemi sono frequenti in diversi algoritmi, da ciò ne deriva il fatto che esistono relazioni di complessità molto frequenti.

Relazione 1: Tipica della ricerca sequenziale.

Relazione 2: Tipica di algoritmi ricorsivi, che ad ogni passo, con una sola operazione, dimezzano l’insieme di dati su cui procedere.

Relazione 3: Tipica di algoritmi ricorsivi che ciclano sui dati in input eliminandone uno alla volta (come Selection Sort).

Relazione 4: Tipica di algoritmi in cui l’input viene dimezzato ad ogni passo, ma per eseguire questa operazione è necessario esaminare tutti i dati.

Relazione 5: Tipica di algoritmi che analizzano tutti i dati dividendoli in due parti e poi proseguono separatamente su entrambi.

Strutture dati

Strutture dati astratte e interne

Le strutture dati si dividono principalmente in astratte ed interne.

Strutture astratte sono strutture dati indipendenti dall’elaboratore e sono rappresentazioni dei dati di un problema; durante la fase di programmazione, queste strutture vengono tradotte in una forma rappresentabile nella memoria della macchina utilizzata, quindi in strutture interne.

Esistendo diversi tipi di dati astratti (ossia di strutture e le operazioni caratteristiche della struttura stessa), è utile vedere quale struttura interna è più utile a rappresentarne uno.

Strutture interne

Strutture elementari

• Sono quelle strutture dati che non possono essere scomposte in altre strutture più semplici. Al livello più basso vi sono i bit, che rappresentano le cifre binarie. Poi vi sono i byte, rappresentati da sequenze di 8 bit. Due byte formano una parola. Ultima struttura elementare è l’indirizzo (di memoria).

Strutture sequenziali

• Sono quelle strutture dati costituite da elementi fisicamente adiacenti, quindi rispettano fedelmente l’organizzazione della memoria di un computer. Caratteristiche di ogni struttura sequenziale sono la lunghezza, intesa come il numero di elementi di cui essa è formata, e l’occupazione, intesa come il numero di celle di memoria che essa occupa. Tra le strutture sequenziali troviamo i vettori, le matrici, le stringhe e i record.

Strutture concatenate

• Sono quelle strutture dati la cui sequenzialità degli elementi non è fisica, ma logica; sono particolarmente efficienti riguardo le operazioni di inserimento e cancellazione. Tra le strutture concatenate troviamo le catene, gli anelli e le catene doppie.

Vettori

La struttura sequenziale più semplice è il vettore (o Array). È definito da un indirizzo base B, che indica la prima posizione a partire dalla quale è memorizzato, il numero massimo n di elementi e il tipo dei suoi elementi. Richiedendo una lunghezza fissata a priori, il massimo numero dei suoi elementi deve essere dichiarato al momento della sua creazione, il vettore risulta essere una struttura interna molto rigida. Inoltre, le sue operazioni di inserimento e cancellazione di un elemento richiedono un costo proporzionale alla sua occupazione.

Per inserire un elemento k in un vettore V di lunghezza n, contenente di già m < n elementi memorizzati (nelle posizioni 0, 1, …, m-1), nella sua posizione j-esima, con 0 ≤ j ≤ m, è necessario spostare a destra di una posizione, da sinistra verso destra, tutti gli elementi che occupano le posizioni dalla j-esima alla (m-1)-esima.

Algoritmo di Inserimento nella posizione j-esima di un Vettore:

• Se m = n stop;
• Per i = m-1, …, j: V[i+1] = V[i];
• V[j] = k; m = m+1;

Costi Algoritmo

• Caso pessimo: C = m O(m)
• Caso medio: C = m/2 O(m)

Per quanto riguarda la cancellazione di un elemento, se non si vuol lasciare vuota la posizione j dell’elemento cancellato, richiede lo stesso numero di spostamenti, questa volta da sinistra verso destra, come illustrato nel sottostante algoritmo.

Algoritmo di Cancellazione nella posizione j-esima di un Vettore:

• Se m = 0 stop;
• Per i = j, …, m-2: V[i] = V[i+1];
• m = m-1;

Matrici

La matrice è una struttura sequenziale che può essere ricondotta ad un vettore. Una matrice n x m è un insieme di n x m elementi dello stesso tipo, individuati da due indici i e j. Una matrice può essere trasformata in un vettore tramite un processo di linearizzazione per righe, ossia memorizzando la prima riga, poi la seconda e così via, oppure per colonne.

Stringhe

La stringa è un'altra struttura sequenziale e può essere pensata come un vettore di caratteri, la cui prima posizione è un numero intero n, detto lunghezza della stringa, che rappresenta il numero di caratteri di cui è composta la stringa stessa. Con codifica Unicode, una stringa occupa 2(n+1) byte.

Catene

La struttura concatenata più semplice è la catena. Essa è costituita da un puntatore testa della catena e da una successione di elementi contenenti almeno due campi: un campo dato e un campo puntatore all’elemento successivo. Il puntatore testa permette di accedere al primo elemento della catena, dal quale tramite il suo campo puntatore si può accedere al secondo e così via. Il puntatore dell’ultimo elemento sarà un puntatore nullo, indicato con ∅.

È una struttura ad accesso sequenziale, quindi anche la ricerca al suo interno può avvenire solo in maniera sequenziale. Per inserire un nuovo elemento k nella catena A tra gli elementi A(j) e A(j+1) è necessario allocare una nuova posizione di memoria per l’elemento k, modificare il puntatore di A(j) per farlo puntare a k e far puntare il puntatore di k a A(j+1).

Costo medio: C = O(1)

Per cancellare l’elemento A(j) bisogna, invece, modificare il puntatore di A(j-1), facendolo puntare all’elemento A(j+1).

Costo medio: C = O(1)

Vettore vs Catena

Anello

L’anello è un’altra struttura concatenata. Risulta essere una catena, il cui puntatore dell’ultimo elemento, invece di essere nullo, indica il primo elemento della catena stessa. Questa caratteristica la rende una struttura circolare e consente di proseguire a scorrere la struttura dal punto in cui ci si trova, senza dover ripartire sempre dall’inizio.

Catena Doppia

La catena doppia, invece, presenta due puntatori per elemento, uno all’elemento successivo ed uno al precedente. Oltre a ciò, è dotata anche di due puntatori esterni, uno alla testa e uno alla coda: in questo modo la si può percorrere in entrambi i sensi.

Strutture astratte

Strutture elementari

• Tra le strutture astratte elementari troviamo i numeri, i caratteri e le stringhe.

Strutture lineari

• Tra le strutture astratte lineari troviamo le liste lineari, le più semplici strutture astratte composte, le pile, le code e le code con priorità.

Strutture non lineari

• Tra le strutture astratte lineari troviamo gli alberi e i grafi.

Lista Lineare

La struttura astratta lineare più semplice è la lista lineare. Essa è un insieme ordinato di n elementi (x₁, x₂, x₃, … , x_n), dove n è la lunghezza della lista. Può avere una lunghezza fissa o variabile, in base al suo contenuto.

Operazioni su una lista lineare

• Carattere Locale: Inserimento, Cancellazione, Ricerca, Modifica.
• Carattere Globale: Ordinamento, Fusione, Split.

Può essere implementata sia attraverso un vettore che in una catena. Si usa il vettore se la lista ha una dimensione statica o di poco variabile, in caso contrario si usa una catena.

Successivamente sono illustrate delle particolari liste lineari che presentano vincoli di accesso: le pile (Last In First Out), le code (First In First Out) e le code con priorità (Largest In First Out).

Pila

Una pila (o Stack) è una lista lineare a lunghezza variabile, dove inserimenti ed estrazioni vengono effettuate solo in un estremo, detto testa (o top) della pila. Si basa sul principio del “last in first out”, LIFO, ossia che l’ultimo elemento ad essere inserito è poi il primo ad essere estratto.

Operazioni su una Pila

• push(e): Operazione di inserimento. Viene inserito un elemento e al top della pila.
• pop(): Operazione di estrazione. Viene estratto l’elemento in quel momento presente al top della pila.
• isEmpty(): Operazione di controllo se la pila è vuota (restituisce true) o meno (restituisce false).

Una pila può essere implementata sia tramite una catena, con le operazioni di push e pop che avverranno in testa alla catena, che tramite un vettore. Per quanto riguarda l’implementazione attraverso un vettore, è necessario stabilire a priori la dimensione n massima della pila e sarà necessario tenere conto della posizione dell’elemento top attraverso un contatore, che sarà l’elemento nella posizione non vuota più a destra nel vettore.

Assumendo che top = -1 indichi la pila vuota, le due operazioni di inserimento ed estrazione possono essere schematizzate come segue:

Operazione di inserimento: push(e)

• top = top + 1;
• se top ≥ n allora overflow; altrimenti v[top] = e;

Costo Algoritmo: O(1)

Operazione di estrazione: pop()

• se top = -1 allora underflow; altrimenti restituisci v[top]; top = top - 1;

Costo Algoritmo: O(1)

Espressioni infisse e postfisse con una pila

Attraverso una pila è possibile trasformare una espressione infissa in una espressione postfissa (ossia un’espressione scritta con l’operatore dopo i suoi operandi) e valutare, inoltre, quest’ultima. Entrambi i processi di trasformazione e valutazione sono illustrati qui sotto.

Infissa a Postfissa

• Se “(“ niente;
• Se operando scrivi nel risultato;
• Se operatore push(operatore);
• Se “)” scrivi(pop()) nel risultato;

Valutazione Postfissa

• Se operando push(operando);
• Se operatore push(pop₂() operatore pop₁());

Coda

Una coda (o Queue) è una lista lineare, dove l’inserimento viene effettuato ad un estremo fondo (o real) e l’estrazione dall’altro estremo testa (o front). Si basa sul principio del “first in first out”, FIFO, ossia che il primo elemento ad essere inserito è poi anche il primo ad essere estratto.

Operazioni su una Coda

• put(e): Operazione di inserimento. Viene inserito un elemento e al rear della coda.
• get(): Operazione di estrazione. Viene estratto l’elemento in quel momento presente al front della coda.
• isEmpty(): Operazione di controllo se la coda è vuota (restituisce true) o meno (restituisce false).

Come una pila, anche una coda può essere facilmente implementata attraverso un vettore. Dunque, è necessario stabilire a priori la dimensione n massima della coda e sarà necessario tenere conto della posizione nel vettore del front (testa) e del rear (fondo), attraverso due contatori F e R. F è, quindi, l’indice della posizione del vettore contenente la testa della coda; se la coda è vuota il valore di F sarà uguale ad R (F = R).