Dati e Algoritmi 1 - appunti essenziali ed esercizi

Introduzione al corso

• Cos'é un algoritmo?

  É un metodo risolutivo di un problema attraverso una sequenza finita di passi. Risolve problemi computazionali che prevedono dato un certo input di produrre un certo output.

• Differenza tra un algoritmo e un programma?

  L'algoritmo sta alla base di un programma e ne cattura l'idea essenziale che c'é nella risoluzione ed é un distillato del programma (codice).

• Cos'é una struttura dati e perché le strutture dati sono importanti per gli algoritmi?

  É un'organizzazione logica dei dati. Un algoritmo, che deve risolvere un problema ha bisogno che i dati sono organizzati in una certa maniera. La scelta di questa organizzazione é fondamentale per la qualità dell'algoritmo (es. vettore di interi e ricerca di un valore: conviene che il vettore sia ordinato così da poter fare ricerca binaria).

• Quali caratteristiche deve avere un buon algoritmo?

  Svolgere il suo compito ed essere efficiente e parsimonioso nell'uso delle risorse computazionali.

• Cosa rende difficile il progetto di algoritmi buoni?

  Per risolvere un problema esiste sempre un algoritmo banale, che spesso non é l'algoritmo migliore.

• Perché é importante studiare algoritmi e strutture dati?

  Un ingegnere é spesso chiamato a dover risolvere computazionalmente un problema con alta probabilità di dover realizzare una soluzione ad hoc.

Introduzione al corso

• Cos'è un algoritmo?

  È un metodo risolutivo di un problema attraverso una sequenza finita di passi. Risolve problemi computazionali che prevedono dato un certo input di produrre un certo output.

• Differenza tra un algoritmo e un programma?

  L'algoritmo sta alla base di un programma e ne cattura l'idea essenziale che c'è nella risoluzione ed è un distillato del programma (codice).

• Cos'è una struttura dati e perché le strutture dati sono importanti per gli algoritmi?

  È un'organizzazione logica dei dati. Un algoritmo, che deve risolvere un problema ha bisogno che i dati siano organizzati in una certa maniera. La scelta di questa organizzazione è fondamentale per la qualità dell’algoritmo (Es. vettore di interi, e ricerca di un valore conviene che il vettore sia ordinato così da poter fare ricerca binaria).

• Quali caratteristiche deve avere un buon algoritmo?

  Svolgere il suo compito ed essere efficiente e parsimonioso nell’uso delle risorse computazionali.

• Cosa rende difficile il progetto di algoritmi buoni?

  Per risolvere un problema esiste sempre un algoritmo banale, che spesso non è l’algoritmo migliore.

• Perché è importante studiare algoritmi e strutture dati?

  Un ingegnere è spesso chiamato a dover risolvere computazionalmente un problema con alta probabilità di dover realizzare una soluzione ad hoc.

Complessità in Tempo

Dire che InsertionSort è O(n²), data un'istanza di taglia n l'algoritmo risolve il problema in al più n² operazioni elementari.

Se le operazioni che consideriamo sono davvero elementari possiamo considerare l'esecuzione di queste operazioni come un'unità di Tempo.

In realtà una moltiplicazione costa più di una somma e un accesso in memoria costa più di un accesso in memoria cache.

Approssimando a meno di costanti possiamo considerare le operazioni elementari come un'unità di misura del Tempo.

Con questa approssimazione il numero di operazioni elementari è una buona approssimazione del Tempo di esecuzione.

Riepilogo:

La complessità in Tempo deve essere una stima del Tempo di esecuzione. Non possiamo misurare il Tempo di esecuzione per vari problemi (vedi slides). La nostra stima è il numero di operazioni elementari che l'algoritmo esegue per risolvere un'istanza. Le istanze le raggruppiamo in funzione della Taglia e per ogni Taglia consideriamo l'istanza peggiore.

Consideriamo quindi il massimo numero di operazioni fatte dall'algoritmo per risolvere quella data istanza.

Questa è la complessità al caso pessimo dell'algoritmo.

Trovare il numero max di operazioni fatte dall'algoritmo per un'istanza di taglia n non è facile perché è difficile determinare l'istanza peggiore e fare un conteggio esatto delle operazioni è complicato → analisi asintotica.

3nlog₂(n) ≤ 3nlog₂(n) + 5n + 5log