I problemiGli eventi che richiedono un impegno fisico e/o "intellettuale" da parte dell'uomo
| Inesistenti | Impossibili: non esiste la soluzione |
|---|
| Intrattabili: le risorse (tempo, spazio, ...) necessarie per ottenere la soluzione sono "proibitive" | | Improponibili: nessuno č disposto a perderci tempo (...) | | Banali | Esiste un dispositivo "dedicato" adatto allo scopo |
|---|
| Interessanti | ? |
|---|
Un'istanza di un problema č un caso specifico del problema stesso (sono fissati i dati del problema). Gli esecutoriL'uomo sogna, da sempre, un sostituto per avere (senza sforzo o in poco tempo) le risposte per ogni istanza di un problema (di ogni problema…).
| Macchine | Ascensore, Calcolatrice |
|---|
| Automi | Pianola |
|---|
| Robot | Metropolis, Terminator, ... |
|---|
| Cyborg | Robocop |
|---|
Un problema č computabile (calcolabile) se esiste un esecutore che, in tempo finito, produce le risposte corrispondenti a qualsiasi istanza. Sistemi di calcolo
| Stephen Kleene | Funzioni ricorsive (parziali) |
|---|
| Emil Post | Sistemi di riscrittura (sistemi formali) |
|---|
| Alonso Church | Lambda calcolo |
|---|
| Alan Turing | Macchina di Turing |
|---|
| John Von Neumann | Macchina a registri |
|---|
I primi tre esecutori sono dei sistemi di calcolo astratti (matematici) che permettono di calcolare le risposte applicando delle regole ad un insieme iniziale di formule che rappresentano il problema… La macchina di Turing e la macchina a registri sono dei dispositivi "fisici" che bisogna costruire volta per volta a seconda del problema da risolvere. Se si definisce un insieme minimo di istruzioni riconosciute (ed eseguite) da queste macchine allora diventano dei sistemi di calcolo universali: un problema deve essere trasformato in una sequenza di istruzioni che costituiranno l'algoritmo risolutivo, il programma da eseguire. Č stato dimostrato che le classi dei problemi computabili dai diversi sistemi di calcolo, finora proposti, sono equivalenti.Tesi di ChurchLa classe dei (di tutti i) problemi computabili coincide con quella della macchina di Turing (con una qualsiasi delle precedenti...) 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 tale che … |
| Un programma, in forma "comprensibile" per una macchina programmabile qualsiasi, tale che… |
| Un programma espresso in forma "comprensibile" per l'uomo tale che… |
La rappresentazione degli algoritmi
| Diagramma di stato | Stati, transizioni |
|---|
| Programma per la MdT | Quintuple |
|---|
| Programma a salti | Jump, Branch, Goto |
|---|
| Diagramma di flusso | Istruzioni, decisioni |
|---|
| Programma strutturato | Linguaggio di alto livello |
|---|
|
