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

  1. Diamo per scontato che gli algoritmi che stiamo analizzando siano corretti?
  2. 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.
  3. 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!
  4. Per avere la ragionevole certezza che il problema sia stato risolto completamente
    • si utilizza un ambiente di sviluppo integrato dotato di debugger
    • si aggiungono delle istruzioni specifiche per facilitare le fasi di testing e debugging: assert, try, …
    • si testa a lungo prima di rilasciarlo: versioni alfa, beta, …

Interfaccia utente

Sono fattori determinanti nella scelta di un sistema informatico

  1. la piacevolezza dell’interfaccia utente
  2. la sua facilità d’uso
    Ma 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

  1. 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!
  2. La documentazione del codice con commenti, schemi, manuali, … è essenziale.
  3. Le tecniche di strutturazione del codice più moderne (sottoprogrammi, moduli, librerie, OOP, …) lo rendono più comprensibile e facilmente aggiornabile / espandibile.
    Ma 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.

Ma

  • Un sistema informatico aziendale in passato rimaneva praticamente immutabile per decenni.
  • I sistemi industriali devono durare più decenni per 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,25 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.

Il software deve avere velocità massima e dimensione minima.

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

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…).


Vedremo che per ogni problema esiste una complessità sotto la quale non si può scendere, la complessità in tempo e quella in spazio sono collegate:

Posso progettare un algoritmo/programma

molto corto (e veloce…) ma che si basa su enormi quantità di dati

oppure

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