Algoritmi e calcolabilità - Lezione in semi-presenza

7. Complessità degli algoritmi: scegliere tra algoritmi diversi che risolvono lo stesso problema

L’algoritmo migliore per riordinare i fogli è quello di fare dei mucchietti perché divide il problema in tante parti. Poi analizza e risolve ogni parte e in fine le mette insieme e trova la soluzione del problema.

Perché quand’eravamo bambini, e poi quando siamo cresciuti, ci hanno insegnato un algoritmo in particolare (ad esempio per risolvere la somma) e non l’altro?L’algoritmo del pallottoliere viene generalmente insegnato ai bambini piccoli perché è più semplice da comprendere e più divertente da svolgere se vogliamo. Solo qualche anno dopo gli viene insegnato l’algoritmo “ normale” per risolvere la somma.

Il metodo del pallottoliere è più semplice, ma, la differenza sostanziale non è la semplicità, oppure si direbbe che il metodo da scegliere, quello più conveniente, è quello del pallottoliere. Al contrario, il metodo più conveniente per risolvere un problema è quello “ normale” perché la differenza sta nel tempo impiegato per risolvere il problema con entrambi i metodi; importante è misurare l’aspettativa del tempo richiesto per risolvere un problema. Anche se, come abbiamo detto, può essere infinito.

Usando il metodo del pallottoliere, immaginando che dovessimo sommare 45 e 63, dovremmo fare 63 passi. Nel caso generale, se dobbiamo sommare 2 numeri, A e B, usando il metodo del pallottoliere, dovremo fare B passi. Usando il metodo “ normale”, vediamo che i passi sono due, infatti, c’è n + 1, lì dove n sono le cifre di B.

N è di solito minore di B: se B è uguale a 50, N è uguale a 2. quindi il secondo algoritmo per risolvere la somma (l’algoritmo “ normale”) è più veloce.

Se quindi ci fermiamo ad osservare gli algoritmi in sé, sicuramente il giudizio sarà che il più conveniente, in quanto più semplice, è quello del pallottoliere, ma se osserviamo i processi, ci rendiamo conto che l’algoritmo migliore è quello della somma tradizionale (quello che ci viene insegnato).

Il problema sta nelle parole perché. Un passo è un’operazione base. Passi è l’operazione base che viene ripetuta tutte le volte ovvero saper sommare e sottrarre un numero tutte le volte.

Il passo del secondo algoritmo è più complesso perché bisogna sommare due cifre all’istante. Si tratta, quindi, di due capacità-base differenti.

Si riesce a arrivare dai passi-pallottoliere ai passi normali? Si, ma per fare 1 passi normale occorre fare 9 passi del pallottoliere. Allora i passi del pallottoliere non convengono eppure c’è ancora oggi qualcuno che conta con le mani.

Era l’argomentazione che era sbagliata, l’argomentazione per convincere che il secondo algoritmo è migliore di quello del pallottoliere.

Il criterio per scegliere un algoritmo è quello che risolve il problema, una volta che abbiamo appurato che due algoritmi risolvono lo stesso problema, si sceglie quello più veloce.

Per scegliere l'algoritmo migliore si deve individuare l'esecuzione più rapida e tenere in considerazione:

• come è scritto l'algoritmo ovvero quali sono le istruzioni (comprensibilità e numero d'istruzioni)
• osservare le ipotetiche istruzioni ovvero i possibili processi (i numeri di passi da fare).