Algoritmi e Strutture Dati Parte 1

Author: d3javu

Dettagli

Creato Martedì, 20 Marzo 2012 23:18

Data pubblicazione

Scritto da Antonio

Visite: 71

Introduzione: Questo articolo si propone di calcolare le prestazioni computazionali di un algoritmo, al fine di ottenerne uno performante, se eseguito su un numero arbitrario di elementi. E' rivolto a chi già ha dimestichezza con la programmazione in generale e nozioni di analisi matematica.

Se ancora non avete letto wikipedia, l'algoritmo è una descrizione informale di una procedura di calcolo, ed è indipendente da qualsiasi piattaforma. Descrive quindi una procedura computazionale ben definita che prende alcuni valori, o un insieme di valori, come INPUT e produce alcuni valori o un insieme di valori come OUTPUT.

Un algoritmo è un'astrazione di un programma che è legato al tipo di compilatore e interprete.

Per analizzare un programma bisogna tener conto del tipo di interprete o del tipo di compilatore utilizzato e il calcolatore su cui viene eseguito, da questo ne deriva il tempo di esecuzione globale.

L'analisi di un algoritmo comprende:

1. Correttezza
   
   • Dimostrazione formale (Matematica)
   • Ispezione formale
2. Utilizzo delle risorse (che varia a seconda della tipologia del problema da risolvere)
   • Tempo di utilizzo
   • Quantità di Memoria per eseguire i calcoli
   • Altre risorse (per es. banda di comunicazione ecc)
3. Semplicità
   • Deve essere facile da capire, modificare, manutenere