Algoritmi/Gli algoritmi

L'algoritmo è una sequenza di istruzioni elementari per risolvere un problema:

• non ambigue: dev'essere chiara la semantica;
• numero finito di passi: ciò che non finisce non si può chiamare algoritmo.

Classificazione dei problemi

I problemi si dividono in due categorie:

• problemi decisionali: "Sì o no?";
• problemi di ottimizzazione: trovare la soluzione che minimizza il costo da pagare.

Problemi decisionali

I problemi decisionali si dividono in decidibili e indecidibili.

I problemi indecidibili sono quelli per cui non esiste alcun algoritmo che li risolve (ad es. problema di Turing, congettura di Goldbach).

Problemi decidibili

Un problema è trattabile se è noto un algoritmo polinomiale ($n^{c}$) che lo risolve in tempi ragionevoli.

Un problema è non trattabile se non potrà mai essere risolvibile tramite algoritmi polinomiali, ma potrebbe esserlo tramite un algoritmo complesso (ad es. esponenziale) non ancora noto.

Di un problema NP sono noti degli algoritmi esponenziali che lo risolvono, ma non si sa se esiste un algoritmo polinomiale che lo risolve. Se verrà trovato un algoritmo polinomiale, il problema NP diventerà di classe P:

$P\subseteq NP$

P è sottoinsieme improprio di NP, cioè non si può dire: $P\subset NP$

È possibile inviduare alcuni problemi NP che attraverso semplici trasformazioni si possono far diventare altri: questi fanno parte della classe NP-completa.

Ricerca di un elemento in un vettore

Ricerca sequenziale/lineare

• caso migliore (l'elemento viene trovato subito): 1 accesso;
• caso medio: ${\tfrac {n}{2}}$ accessi;
• caso peggiore (l'elemento non viene trovato): $n$ accessi.

Ricerca binaria/dicotomica

insieme ordinato: cerco di metà in metà
numero massimo di accessi: $\log _{2}{n}$

Introduzione agli algoritmi di ordinamento

algoritmo di ordinamento: si fa con le permutazioni.

Esempio: CPU scheduling: si hanno n task ciascuno con una specifica durata, e bisogna eseguirli con il minimo tempo medio di attesa → li si mette in ordine crescente di durata.

Approccio di un tipico algoritmo di ordinamento: Il vettore dei dati da ordinare viene suddiviso in 2 sottovettori sinistro e destro. Il sottovettore sinistro è ordinato, il sottovettore destro non è ordinato. A ogni passo si sposta un elemento nel sottovettore sinistro mantenendo l'invarianza della proprietà di ordinamento, cioè tenendolo ordinato.

Un vettore contenente un solo dato è per definizione ordinato.

Insertion sort

Insertion sort.

1. si scandisce il sottovettore ordinato (dall'indice i + 1) da sinistra a destra, fino a quando non si trova una chiave minore dell'elemento i-esimo;
2. shift a destra degli elementi ordinati;
3. si inserisce l'elemento nella posizione ordinata.