Dal problema alla risposta – Approfondimento

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

L’insieme dei problemi computabili coincide con quello della macchina di Turing.

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!)
Vedi le definizioni fornite da Wikipedia:Algoritmo

Un algoritmo è

  1. Un procedimento che permette di risolvere un certo problema tramite un numero finito di passi.
  2. 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…
Notice: This work is licensed under a BY-NC-SA. Permalink: Dal problema alla risposta – Approfondimento

Comments are closed.