Appunti completi corso Algoritmi

Corso difficile di algoritmi e strutture dati

In questo fighissimo corso che sembra facile ma in realtà è il più difficile, impareremo tante cose belle! Impareremo i principi per scrivere algoritmi efficienti insieme alle strutture dati più adatte per le nostre esigenze.

Concetti generali di strutture dati e algoritmi

La struttura dati è il modo in cui i dati sono organizzati e definisce le operazioni che si possono svolgere su di essi. L'efficienza di un algoritmo si valuta considerando l'uso di risorse come il tempo, la memoria ed eventualmente la banda. Per il nostro corso maggiore importanza assumerà il tempo di esecuzione. La scelta della struttura dati è un passo delicato, perché non esiste una struttura dati universale che funziona sempre: in base all'applicazione che dobbiamo creare risulterà più efficiente una struttura piuttosto che un'altra.

Un algoritmo è una sequenza di azioni che un esecutore compie per arrivare alla soluzione di un problema. Il problema è la definizione che permette di passare da un input ad un output desiderato. Per un medesimo problema possono esistere vari algoritmi (per esempio l'ordinamento) ed ogni algoritmo può essere implementato in diversi linguaggi di programmazione, i quali a loro volta verranno tradotti nei vari linguaggi macchina. In sostanza noi abbiamo studiato i linguaggi di programmazione in Fondamenti di Informatica, il linguaggio macchina in ACSO e ora è il turno degli algoritmi, che sono il livello di astrazione più alto.

Efficienza e complessità degli algoritmi

Lo studio dell'efficienza di un algoritmo avviene analizzando la sua complessità, ovvero la relazione tra la quantità di risorse utilizzate e la dimensione dell'input. Indicative sono anche le informazioni riguardanti il caso migliore, peggiore e medio:

• Caso migliore: è poco significativo e caratterizza poco l'algoritmo, a meno che non si verifichi frequentemente.
• Caso peggiore: è quello che caratterizza maggiormente l'efficienza dell'algoritmo in esame.
• Caso medio: anche questo è piuttosto indicativo e rappresenta il comportamento tipico, ma è più difficile da calcolare perché richiede una conoscenza sulla distribuzione dei dati.

Possiamo esprimere il consumo di risorse attraverso una funzione di variabile intera n indicante la dimensione dell'input, ma a noi non interessa l'espressione esatta di questa funzione, ci interessa il tasso di crescita e il suo comportamento asintotico: togliamo di mezzo quindi costanti, coefficienti e infiniti di ordine inferiore! Ricordiamo però che questo ha senso perché consideriamo n → ∞: nel caso in cui dobbiamo progettare un algoritmo che dovrà processare una quantità piccola di dati, bisogna tenere conto delle costanti e agire diversamente.

Notazioni asintotiche

• O Grande (O): rappresenta un limite asintotico superiore, ovvero dire che 10n − 2 + 3n + 7 è O(n) significa dire che esiste una costante c per cui, da un certo punto in poi, cn è sempre superiore alla funzione di partenza.
• Omega Grande (Ω): rappresenta un limite asintotico inferiore, quindi l'è stesso di prima ma al contrario.
• Theta Grande (Θ): rappresenta un limite asintotico sia inferiore sia superiore, quindi è le due cose di prima insieme con due costanti differenti. Valgono le proprietà di transitività e di riflessività.

Calcolo della complessità

Due proprietà importanti sono la somma e il prodotto:

• La complessità della somma è il massimo tra tutte le complessità.
• La complessità del prodotto è il prodotto delle complessità.

Esempi di calcolo della complessità

Ecco alcuni esempi di calcolo della complessità su vari frammenti di codice:

• sum = 0; for (i = 1; i <= n; ++i) sum += n;

  Gli assegnamenti hanno tempo costante O(1). Il ciclo for viene eseguito n volte, quindi questo frammento di codice ha complessità O(n).

• sum = 0; for (j = 1; j <= n; ++j) for (i = 1; i <= j; ++i) sum++; for (k = 0; k < n; ++k) A[k] = k;

  Il ciclo esterno viene eseguito n volte, quello interno viene eseguito prima 1, poi 2, poi 3, poi 4 volte... fino a n. Ovvero . Ora sì che possiamo affermare che i due cicli annidati hanno complessità O(n²). Il secondo ciclo è evidente a tutti che ha complessità O(n). Qual è la complessità dell'intero programma? Per la proprietà della somma, è la più alta tra tutte, quindi O(n²).

• sum1 = 0; for (k = 1; k <= n; k *= 2) for (j = 1; j <= n; ++j) ++sum1; sum2 = 0; for (k = 1; k <= n; k *= 2) for (j = 1; j <= k; ++j) ++sum2;

  I primi due cicli annidati sono indipendenti, per cui possiamo moltiplicare le due complessità e otteniamo O(n log n). Gli ultimi due cicli differiscono solo nel fatto che sono dipendenti, e la complessità è diversa! Infatti vengono eseguiti cicli e il risultato è O(n). La complessità perciò è O(n).

• for (i = n/2; i <= n; ++i) for (k = 2; k <= n; k = k*k) for (j = i; j <= n; ++j) ++count;

  Iniziamo con le cose difficili. Il primo ciclo viene eseguito n/2 + 1 volte, il secondo volte e sono indipendenti. Con un po' di calcoletti scopri che il terzo viene eseguito volte perciò ha complessità O(n² log log n).

• for (i = 1; i < (N^2); i *= 2) for (k = 1; k < N; k *= 3) for (j = 1; j < (i^2); ++j) ++sum;

  Smanettando un po' dovrebbe venir fuori che la complessità è O(n⁴).

Analisi delle funzioni ricorsive

In altre strutture di controllo (come while, if, switch) bisogna sempre considerare la complessità massima per il calcolo. Le funzioni ricorsive invece si possono esaminare attraverso le equazioni di ricorrenza e procedendo per sostituzione, oppure effettuando una analisi per livelli. Ma il metodo più bello è il Master Theorem. Bisogna scrivere l'equazione della funzione nella forma T(n) = aT(n/b) + f(n) con n la dimensione dell'input, a il numero di chiamate ricorsive nella funzione, n/b la dimensione della chiamata ricorsiva e f(n) è la complessità del codice della funzione. Si deve confrontare la funzione n^log_ba con f(n). A questo punto avremo tre casi:

• Caso 1: se f(n) è O(n^log_ba−ε) con ε > 0 allora la complessità sarà n^log_ba (cioè f(n) viene superata da n^log_ba).
• Caso 2: se f(n) è Ω(n^log_ba+ε) con ε > 0 allora la complessità sarà f(n) (cioè f(n) supera n^log_ba).
• Caso 3: se f(n) è Θ(n^log_ba) allora la complessità sarà log n * f(n).

Tipi di dato astratto (TDA)

Prima di vedere il nostro primo tipo di struttura dati, dobbiamo parlare di tipo di dato astratto o TDA. Noi sappiamo già che il tipo di una variabile indica i valori che essa può assumere e le operazioni che vi si possono compiere. Le strutture dati sono una sorta di tipo, perché ogni struttura può essere rappresentata dai valori che può memorizzare e dalle operazioni che vi si possono effettuare. Nel caso di una lista queste operazioni possono essere l'inserimento di un elemento in coda, la rimozione di un elemento, lo svuotamento ecc... Sono anche “astratte” nel senso che la loro definizione è indipendente dall'implementazione e dal linguaggio di programmazione usato per realizzarle. Per esempio una lista rimane tale, che essa sia implementata con un array o con una lista concatenata. È proprio questo il tipo di dato astratto: un tipo che definisce solo l'interfaccia e le funzioni disponibili sul tipo di dato, indipendentemente da come è implementato. Questo significa che se dovessimo cambiare l'implementazione in un programma già scritto per migliorare le prestazioni, non romperemo i programmi che fanno uso dell'implementazione vecchia.

TDA in C++

In C++ i tipi di dato astratto si possono rappresentare per mezzo delle classi astratte, delle particolari classi che:

• Specificano solo l'interfaccia.
• Non sono istanziabili.
• Fungono da classe base per ereditare classi più complesse.

Per rendere astratta una classe, basta inserirci almeno una funzione virtuale pura, ovvero nella forma virtual void foo() = 0;. Faremo anche uso della programmazione generica, in cui una funzione è definita indipendentemente dal tipo di dato che riceve in ingresso, in quanto esso stesso è un parametro. Ciò si ottiene per mezzo dei template. Per esempio, per definire una funzione che ritorna il massimo tra due elementi potremmo usare questa dichiarazione: template <class T> T max(T a, T b).

Implementazioni di liste

Liste basate su array

Ora abbiamo le conoscenze preliminari necessarie per poter parlare di liste. Una lista è una sequenza finita e ordinata di elementi. Ogni elemento nella lista è caratterizzato da una posizione. Iniziamo a definire una classe astratta per la nostra lista, poi la specializzeremo fornendo varie implementazioni:

template <class Elem> 
class List {
public: 
    virtual void clear() = 0;
    virtual bool insert(const Elem &) = 0;
    virtual bool append(const Elem &) = 0;
    virtual bool remove(Elem &) = 0;
    virtual void setStart() = 0;
    virtual void setEnd() = 0;
    virtual void prev() = 0;
    virtual void next() = 0;
    virtual int leftLength() const = 0;
    virtual int rightLength() const = 0;
    virtual bool setPos(int pos) = 0;
    virtual bool getValue(Elem &) const = 0;
    virtual void print() const = 0;
};

Le due implementazioni standard per una lista sono l'array e la lista concatenata con puntatori. Vediamo ora la classe lista basata su array.

template <class Elem> // Array-based list
class AList : public List<Elem> {
private:
    int maxSize;
    int listSize;
    int fence;
    Elem *listArray;
public:
    AList(int size = DefaultListSize) {
        maxSize = size;
        listSize = fence = 0;
        listArray = new Elem[maxSize];
    }
    void prev() {
        if (fence != 0) --fence;
    }
    bool setPos(int pos) {
        if ((pos >= 0) && (pos <= listSize)) fence = pos;
        return (pos >= 0) && (pos <= listSize);
    }
};

template <class Elem>
bool AList<Elem>::insert(const Elem &item) {
    if (listSize == maxSize) return false;
    for (int i = listSize; i > fence; --i) {
        listArray[i] = listArray[i-1]; // Shift Elems up to make room
    }
    listArray[fence] = item;
    ++listSize; // Increment list size
    return true;
}

template <class Elem>
bool AList<Elem>::append(const Elem &item) {
    if (listSize == maxSize) return false;
    listArray[listSize++] = item;
    return true;
}

// Remove and return first Elem in right partition
template <class Elem>
bool AList<Elem>::remove(Elem &it) {
    if (rightLength() == 0) return false;
    it = listArray[fence]; // Copy Elem
    for (int i = fence; i < listSize-1; ++i) listArray[i] = listArray[i+1]; // Shift them down
    --listSize; // Decrement size
    return true;
}

Liste concatenate

Questa è invece l'implementazione con una lista concatenata, dove creiamo una classe in più per identificare i nodi.

template <class Elem> 
class Link { // Singly-linked list node
public:
    Elem element; // Value for this node
    Link *next; // pointer to next node
    // constructor with initial value
    Link(const Elem &elemval, Link *nextval = nullptr) {
        element = elemval;
        next = nextval;
    }
    // constructor without initial value
    Link(Link *nextval = nullptr) {
        next = nextval;
    }
};

// Linked list implementation
template <class Elem> 
class LList : public List<Elem> {
private:
    Link<Elem> *head; // Point to list header
    Link<Elem> *tail; // Pointer to last Elem
    Link<Elem> *fence; // Last element on left
    int leftcnt; // Size of left
    int rightcnt; // Size of right
    void init() { // Initialization routine
        fence = tail = head = new Link<Elem>;
        leftcnt = rightcnt = 0;
    }
    void removeall() { //Return link nodes to free store
        while (head != nullptr) {
            fence = head;
            head = head->next;
            delete fence;
        }
    }
public:
    LList(int size = DefaultListSize) { init(); }
    ~LList() { removeall(); }
};

// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem &item) {
    fence->next = new Link<Elem>(item, fence->next);
    if (tail == fence) tail = fence->next;
    ++rightcnt;
    return true;
}

// Append Elem to end of the list
template <class Elem>
bool LList<Elem>::append(const Elem &item) {
    tail = tail->next = new Link<Elem>(item, nullptr);
    ++rightcnt;
    return true;
}

// Remove and return first Elem in right partition
template <class Elem>
bool LList<Elem>::remove(Elem &it) {
    if (fence->next == nullptr) return false;
    it = fence->next->element; // Remember val
    Link<Elem> *ltemp = fence->next; // Remember link node
    fence->next = ltemp->next; // Remove
    if (tail == ltemp) // Reset tail
        tail = fence;
    delete ltemp; // Reclaim space
    --rightcnt;
    return true;
}

// Move fence one step left; no change if left is empty
template <class Elem>
void LList<Elem>::prev() {
    Link<Elem> *temp = head;
    if (fence == head) return; // No prev Elem
    while (temp->next != fence) temp = temp->next;
    fence = temp;
    --leftcnt;
    ++rightcnt;
}

// Set the size of left partition to pos
template <class Elem>
bool LList<Elem>::setPos(int pos) {
    if ((pos < 0) || (pos > rightcnt + leftcnt))
        return false;
    fence = head;
    for (int i = 0; i < pos; ++i) fence = fence->next;
    return true;
}

Vantaggi e svantaggi delle implementazioni

Dal codice si possono subito notare quali sono i vantaggi e gli svantaggi tra le due implementazioni:

• L'array è veloce nell'accesso agli elementi, avendo complessità costante O(1), ma l'inserimento e la rimozione richiedono una complessità lineare O(n).
• La lista concatenata invece ha le caratteristiche opposte: è veloce nell'inserire e rimuovere elementi, ma richiede più tempo nell'accesso.

In termini di spazio, l'array è di dimensione statica, perciò la memoria viene sprecata se gli elementi sono pochi. Nel caso della lista concatenata invece c'è un nodo per ogni elemento, che però occupa più spazio dovendo anche memorizzare il puntatore.

Estensioni delle liste concatenate

Esistono delle estensioni della lista concatenata, due delle quali sono la free list e la lista puntata doppia. Le operazioni di new e delete sono costose per il sistema, come potremmo evitare di usarle? Idea! Usiamo la classe Link per contenere una free list, ovvero quando si elimina un elemento, lo si inserisce nella free list. Quando vogliamo creare un elemento, lo preleviamo dalla free list. Se questa è vuota, allora facciamo new.

// Singly-linked list node with freelist
template <class Elem> 
class Link {
private:
    static Link<Elem> *freelist; // Head
public:
    Elem element; // Value for this node
    Link *next; // Point to next node
    Link(const Elem &elemval, Link *nextval = nullptr) {
        element = elemval;
        next = nextval;
    }
    Link(Link *nextval = nullptr) {
        next = nextval;
    }
    void * operator new(size_t); // Overload
    void operator delete(void *); // Overload
};

template <class Elem>
Link<Elem> *Link<Elem>::freelist = nullptr;

template <class Elem>
// Overload for new
void *Link<Elem>::operator new(size_t) {
    if (freelist == nullptr)
        return ::new Link;
    Link<Elem> *temp = freelist; // Reuse
    freelist = freelist->next;
    return temp; // Return the link
}

template <class Elem>
// Overload delete
void Link<Elem>::operator delete(void *ptr) {
    ((Link<Elem> *)ptr)->next = freelist;
    freelist = (Link<Elem> *)ptr;
}

Nella lista doppia ogni nodo contiene anche il puntatore all'elemento precedente. Questo velocizza le operazioni di cancellazione.

// Doubly-linked list link node
template <class Elem> 
class Link {
public:
    Elem element; // Value for this node
    Link *next; // Pointer to next node
    Link *prev; // Pointer to previous node
    Link(const Elem &e, Link *prevp = nullptr, Link *nextp = nullptr) {
        element = e;
        prev = prevp;
        next = nextp;
    }
    Link(Link *prevp = nullptr, Link *nextp = nullptr) {
        prev = prevp;
        next = nextp;
    }
};

L'aggiunta di un secondo puntatore aumenta ancora di più lo spazio occupato. Un modo per ovviare a questo è usare le proprietà dello XOR per cui (L^R)^R = L e (L^R)^L = R. In pratica ogni nodo non contiene due puntatori ma ne contiene uno solo che è lo XOR bit a bit dei due puntatori. Scorrendo la lista e usando le proprietà logiche dello XOR possiamo ricavare tutti i puntatori che ci servono.