I problemi
I problemi sono delle richieste che richiedono all’uomo un certo impegno fisico e/o intellettuale.
Ma tra tutti i problemi, di quali si occupa l’informatica?
| Assurdi? | Perché perdere tempo se la richiesta è assurda… |
| Impossibili? | Pur interessanti, è dimostrato che non ammettono soluzione, quindi… sono PROBLEMI NON COMPUTABILI |
| Intrattabili? | Le risorse hardware e/o il tempo necessario per ottenere la soluzione sono proibitivi, quindi… sono PROBLEMI INTRATTABILI |
| Banali? | Esiste un dispositivo dedicato adatto allo scopo, quindi… |
| Interessanti? | Se il problema non è assurdo, impossibile, intrattabile, banale allora… ce ne occupiamo |
Un’istanza di un problema è un caso specifico, particolare del problema stesso (perché sono fissati i dati del problema).
Gli esecutori
Da sempre l’uomo desidera avere un suo sostituto che lo sollevi dalla fatica oppure che gli risparmi le lunghe attese necessarie per avere la risposta a ogni istanza di un certo problema (qualsiasi problema…)
| Umanoidi | Automa, androide, schiavo, macchina, robot, cyborg, …. |
| Dispositivi | Ascensore, calcolatrice, decoder, pianola, … |
| Letteratura | Golem, Frankenstein, … |
| Cinema | Metropolis, Blade Runner, Terminator, Robocop, Io e Caterina, I robot, … |
Computabilità
Un problema è computabile, calcolabile, se esiste un (algoritmo per un) esecutore che è capace di produrre, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema.
Nel primo ‘900 sono stati proposti molti modelli astratti, formali, di esecutori che potessero calcolare la risposta per ogni istanza di un problema
| Autore | Sistema di calcolo |
| Stephen Kleene | Funzioni ricorsive (parziali) |
| Emil Post | Sistemi di riscrittura (sistemi formali) |
| Alonso Church | Lambda calcolo |
| Alan Mathison Turing | Macchina di Turing |
| John Von Neumann | Macchina a registri |
I primi tre esecutori sono dei sistemi di calcolo di tipo logico-matematico e permettono di calcolare la risposta applicando delle regole ad un insieme iniziale di formule logico-matematiche che rappresentano l’istanza del problema…
La macchina di Turing e la macchina a registri sono dei modelli più vicini alla realtà che hanno permesso di costruire le prime macchine calcolatrici.
Macchina universale
Se si definisce un insieme minimo di istruzioni riconosciute, ed eseguite, da una macchina allora essa diventa un sistema di calcolo universale.
Non è più necessario progettare fisicamente la macchina per un certo problema ma è sufficiente progettare un algoritmo, risolutivo per il problema, e farlo eseguire per una certa istanza.
È stato dimostrato che gli insiemi dei problemi computabili dai diversi sistemi di calcolo, finora proposti, sono equivalenti.
Quindi conviene utilizzare il sistema di calcolo più pratico perché non c’è alcun vantaggio teorico fra l’uno e l’altro.
Tesi di Church
Si ipotizza che la macchina di Turing sia sufficiente per tutti i problemi computabili (e quindi lo sono anche gli altri sistemi di calcolo).
Equivale a: “tutti i computer, presenti e futuri, hanno e avranno la stessa capacità di calcolo”.
Algoritmo
Il concetto di algoritmo si è evoluto insieme ai sistemi di calcolo.
Un algoritmo è
- una macchina di Turing che per ogni istanza del problema in esame restituisce, in tempo finito, le risposte attese
- un programma per una macchina di Turing universale che …
- un programma in forma comprensibile per una macchina programmabile che …
- un programma in forma comprensibile per l’uomo che … (questo punto è controverso!)
Un algoritmo è
- Un procedimento che permette di risolvere un certo problema tramite un numero finito di passi.
- Una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce ad un ben determinato risultato in un tempo finito.
- …
Non esiste un modello unico per rappresentare un algoritmo.
La scelta dipende dal problema, paradigma di programmazione, risolutore, esecutore, …
| Diagramma di stato | Stati e transizioni di stato: cerchi e frecce |
| Programma per la macchina di Turing | Quintuple di simboli |
| Diagramma di flusso | Flow-chart: rombi, rettangoli, cerchi, frecce Istruzioni, decisioni |
| Programma scritto con un linguaggio di basso livello | Istruzioni per la macchina a registri Linguaggio a salti… |
| … un linguaggio di alto livello | Istruzioni interpretate/compilate Linguaggio strutturato! |
| … uno pseudo-linguaggio | Istruzioni più vicine a formalismi già noti Linguaggio naturale, formalismo logico-matematico … |
Alcune considerazioni…
- le istruzioni (gli stati) sono in numero finito
- le singole istruzioni sono non ambigue per l’esecutore
- le singole istruzioni sono eseguibili in tempo finito
- l’intero algoritmo è eseguibile in tempo finito
- la risposta per una certa istanza è sempre la stessa…