Pagina 194 e successive del libro di testo
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
- correttezza dell’algoritmo
- qualità dell’interfaccia utente
- qualità del codice, comprensibilità / modificabilità
- piattaforma e strumenti di sviluppo utilizzati
- velocità di esecuzione
- dimensione dei dati, durante l’esecuzione
- dimensione dei dati in input
- dimensione dei dati in output
- dimensione dei dati in trasmissione.
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
- 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 il software prima di rilasciarlo: versioni alfa, beta, …
Interfaccia utente
- Sono fattori determinanti nella scelta di un sistema informatico
- la piacevolezza dell’interfaccia utente
- la sua facilità d’uso
- Le interfacce grafiche attuali richiedono
- molto tempo per lo sviluppo
- molte risorse hardware per la loro esecuzione
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 qualche settimana dalla stesura!
- Diventa essenziale la documentazione del codice con commenti, schemi, manuali, …
- 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.
- 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 oppure vengono sostituiti da nuovi modelli.
- 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 (GB/s) | ~ MB |
| RAM | ~ 0.5 GHz (GB/s) | ~ GB |
| HD | ~ 0,25 GHz (GB/s) | ~ TB |
A dimensioni inferiori del codice e dei dati corrispondono
- minor tempo di accesso
- minor tempo d’esecuzione.
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à dell’input
Se l’input di un problema ha dimensione esponenziale… - complessità dell’output
Se l’output di un problema ha dimensione esponenziale… - complessità di trasmissione
Se il tempo di trasmissione …
Nell’ipotesi che i criteri soggettivi siano sempre applicati, se ritenuti utili, ci concentriamo sul consumo di risorse hardware.
Tra le risorse hardware ci occupiamo principalmente della CPU e quindi della complessità in tempo.
Per valutare la complessità in tempo è necessario analizzare le singole istruzioni del programma (dell’algoritmo…).