FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 1. Gli algoritmi.
Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  2. L'analisi di complessità degli algoritmi
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

2 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 problemiModifica

5 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 decisionaliModifica

I problemi decisionali si dividono in decidibili e indecidibili.

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

Problemi decidibiliModifica

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

8 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.

9 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

10 È 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 vettoreModifica

13 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.
15 Ricerca binaria/dicotomica

insieme ordinato: cerco di metà in metà
numero massimo di accessi: \log_2{n}

Introduzione agli algoritmi di ordinamentoModifica

17 algoritmo di ordinamento: si fa con le permutazioni.

18 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.

20 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 sortModifica

Insertion sort

22 Insertion sort.

  1. 21 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.
Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  2. L'analisi di complessità degli algoritmi

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale