Complessità: criteri

Vogliamo individuare dei criteri oggettivi da usare per scegliere l’algoritmo con prestazioni migliori tra tutti quelli che risolvono lo stesso problema.

Alcuni criteri per valutare un algoritmo e il software corrispondente potrebbero essere

  1. correttezza dell’algoritmo
  2. qualità dell’interfaccia utente
  3. comprensibilità ed espandibilità del codice
  4. piattaforma e strumenti di sviluppo
  5. velocità
  6. dimensione.

Correttezza

Diamo per scontato che gli algoritmi che stiamo analizzando siano corretti?

Un algoritmo risolve un problema se dà risposte esatte per ogni istanza del problema.

Un’istanza di un problema è un caso particolare del problema, cioè è il problema con fissati i valori dei dati in ingresso.

Come possiamo essere sicuri della correttezza di un software?
Non esiste un algoritmo che decida se un qualsiasi algoritmo è corretto (Problema della fermata, A. Turing).
Non esiste un software commerciale, di una certa dimensione, senza errori!

Per avere la ragionevole certezza che il problema sia stato risolto completamente

  1. si utilizza un ambiente di sviluppo integrato dotato di debugger
  2. si aggiungono delle istruzioni specifiche per facilitare le fasi di testing e debugging: assert, try, …

Interfaccia utente

La piacevolezza dell’interfaccia utente, e la sua facilità d’uso, sono fattori determinanti nella scelta di un sistema informatico.

Le interfacce grafiche attuali richiedono molto tempo per lo sviluppo e molte risorse hardware per la loro esecuzione (a scapito di tutto il resto…)

Codice sorgente

Un codice sorgente che risulta incomprensibile è da scartare, anche se risulta valido per tutti gli altri criteri!

Un codice può risultare incomprensibile anche al suo autore dopo poco tempo dalla stesura!

La documentazione del codice con commenti, schemi, manuali, … è essenziale.

Le tecniche di strutturazione del codice (sottoprogrammi, moduli, librerie…) lo rendono più comprensibile e facilmente aggiornabile / espandibile.

Purtroppo producono software più lungo e più lento!

Piattaforma e strumenti di sviluppo

Hardware (CPU, RAM, …), sistema operativo, linguaggio di programmazione, compilatore, … concorrono alle caratteristiche finali del codice.

Purtroppo…

  • Un sistema informatico aziendale in passato rimaneva praticamente immutabile per decenni.
  • I sistemi industriali devono durare più decenni per essere ammortizzare il loro costo.
  • Gli elettrodomestici intelligenti (console, decoder, TV, …)  non sono praticamente aggiornabili dopo l’acquisto.

Per semplificare supponiamo che piattaforma, strumenti software, … siano generici e fissati.

Velocità e dimensione

Occupiamoci del consumo atteso di risorse hardware generiche ma sempre presenti: CPU, RAM, memoria di massa.

La velocità di esecuzione di un programma è condizionata dalle diverse velocità di accesso e diverse capacità dei dispositivi di memorizzazione

Velocità effettive Capacità
CPU 2 GHz ~KB
Cache 1 GHz ~MB
RAM 0.5 GHz ~GB
HD 0,1 GHz ~TB

È evidente che utilizzare strutture dati quanto più piccole possibile significa garantire ad esse maggiore vicinanza al microprocessore  e di conseguenza

  • maggiore velocità di accesso
  • minor tempo d’esecuzione.

Vogliamo ottenere la massima velocità e la minima dimensione per il nostro prodotto!

Il consumo di memoria porta a definire dei criteri di complessità in spazio mentre quello della CPU viene caratterizzato dalla complessità in tempo (di occupazione della CPU).

I due criteri precedenti sono collegati tra loro: posso progettare un codice

  • molto corto (e veloce…) ma che si basa su enormi quantità di dati
  • molto lungo (e lento…) ma che si basa su minime quantità di dati.

Ulteriori criteri che prendono in considerazione le risorse hardware sono

  • complessità di input/output
  • complessità di trasmissione

Conclusione

Nell’ipotesi che i criteri soggettivi siano sempre applicati, se ritenuti utili, concentriamoci sul consumo di risorse hardware e in particolare sulla complessità in tempo.

Per valutare la complessità in tempo è necessario analizzare le singole istruzioni del programma (dell’algoritmo…).