Schemi della teoria di Algoritmi e strutture dati

ALGORITMI e STRUTTURE DATI

Con il termine "algoritmo" intendiamo un procedimento di calcolo che ci permette di risolvere problemi partendo da dei dati di input per produrre dati di output. Le strutture dati sono progettate per memorizzare e manipolare i dati degli algoritmi in maniera efficiente. Sono la rappresentazione logica o fisica dei dati e offrono un'interfaccia per accedervi.

STRUTTURE DATI ELEMENTARI

Le strutture dati elementari sono fondamentali come blocchi di costruzione per creare strutture dati più complesse. Quelle più comuni sono:

• Array → Sequenza di elementi omogenei in posizioni contigue, è una struttura statica.
• Liste → Sequenza di nodi contenenti dati arbitrari e 1 o 2 puntatori. (Possibili implementazioni: ArrayList, LinkedList...)
• Insiemi → Collezione di elementi unici e non ordinati, è possibile eseguire operazioni di unione, intersezione...
• Dizionari → Coppie di associazione chiave-valore che appartengono ad un dominio e un codominio.
• Pile → Sequenza di elementi basata sul principio "LIFO".
• Code → Sequenza di elementi basata sul principio "FIFO".

Analisi degli Algoritmi

Come si sceglie l'algoritmo "migliore"? Occorre una misura astratta che tenga maggiormente conto del "metodo di risoluzione", ovvero il costo computazionale.

Il costo computazionale si riferisce alla misura delle quantità necessarie di risorse computazionali come tempo, spazio di memoria, prestazioni...

Uno degli aspetti chiave del costo computazionale è il tempo di esecuzione che può variare in base alla dimensione degli input. Si misura utilizzando O() grande.

Una delle parti più importanti nella valutazione del costo computazionale è il costo computazionale asintotico (o complessità computazionale), ovvero la valutazione del costo di un algoritmo quando il numero n di dati in input tende a infinito.

Ecco una scala crescente degli ordini di costo:

• Migliore: O(1)Costante: non dipende dagli input
• O(log n)Logaritmico: associato ad algoritmi che dividono in input più piccoli ripetutamente
• O(n)Lineare: cresce linearmente
• O(n log n)Lineare logaritmico
• Peggiore: O(n^2), O(n^c), 2^nQuadratico, cubico, esponenziale, fattoriale...

Esempi

• Accesso ad un elemento di un array
• Ricerca binaria
• Somma degli elementi di un array
• Merge sort
• Bubble sort, moltiplicazione matrici, backtracking

Quando si valuta un algoritmo occorre sempre considerare: il caso pessimo, il caso medio e il caso ottimo.

Tutte le 4 condizioni sono rispettate!

Altezza nera: bhn_i = 2

L'altezza nera è una misura che indica il numero di nodi neri lungo qualsiasi cammino dalla radice ad una delle sue foglie. Questa misura è utilizzata per garantire che qualsiasi strada abbia la stessa quantità di nodi neri ed è fondamentale per il bilanciamento.

In questo tipo di albero, sia l'operazione di inserimento che di rimozione garantiscono ancora il bilanciamento grazie all'uso di rotazioni e cambi di colore.

In conclusione si può affermare che per ogni operazione (inserimento, rimozione e ricerca) un albero red-black ha complessità totale uguale a O(log n) dove n è il numero di nodi dell'albero.

Minimum Spanning Tree (MST)

Dato un grafo G=(V,E) non orientato e pesato, il MST è un albero che copre tutti i suoi nodi in modo che la somma dei pesi degli archi sia il più bassa possibile.

Per la costruzione del MST esistono due algoritmi principali:

• Algoritmo di Kruskal: dopo aver ordinato gli archi in ordine crescente, si aggiungono nodi all'albero selezionando l'arco con peso minimo.

• Algoritmo di Prim: l'albero parte da un nodo arbitrario e cresce con l'aggiunta di archi di peso minimo fino a quando copre tutti i vertici.

Costruzione del MST con algoritmo generico

Algoritmi di Ordinamento

Gli algoritmi di ordinamento sono utilizzati per ordinare una sequenza di n elementi secondo un determinato criterio (di solito ordine crescente).

Esistono diversi algoritmi, alcuni sfruttano la tecnica divide e impera.

Selection sort

Partendo da un array non ordinato, l'idea base sarebbe quella di tenere l'array diviso in una parte ordinata e una non ordinata durante la sua esecuzione:

1. Si considera l'intero array non ordinato, la parte ordinata è vuota.
2. Si cerca l'elemento più piccolo della parte non ordinata e lo si sposta nella parte ordinata all'indice i.
3. Si ripete il passo 2 fino a che la parte non ordinata è vuota.

Nonostante la semplicità, l'algoritmo ha una complessità O(n²) dovuta all'uso di un doppio ciclo: quello esterno che scorre tutto l'array e quello interno che scorre la parte non ordinata.

Insertion sort

Partendo da un array non ordinato, l'idea base anche qua è tenere l'array diviso in una parte ordinata e una non ordinata:

1. Si considera il primo elemento come parte ordinata e il resto non ordinato.
2. Si scorre la parte non ordinata rimuovendo un elemento alla volta e inserendolo nella posizione corretta della parte ordinata.