# Algoritmi/Gli algoritmi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
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

* 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;
* shift a destra degli elementi ordinati;
* si inserisce l'elemento nella posizione ordinata.