Introduzione allo studio dell'informatica teorica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 14:
Quando si inizia a studiare un nuovo argomento ha senso riflettere sul contesto in cui è inserito; non fa eccezione l'informatica teorica, per la quale vale la pena di spendere qualche parola.
La
La scomposizione del presente corso in tre moduli ci permette di strutturare la presentazione in tre parti: la prima centrata sul concetto di formalismo, la seconda sulle idee riguardanti la computabilità e la terza sulla complessità computazionale.
=I formalismi=
Indubbiamente, la necessità di valutare le qualità di un
I motivi sono tanti: il più significativo risiede nella sottile differenza tra quanto studiato dall'informatica teorica (
▲Una domanda sorge spontanea: vista l'attuale abbondanza di calcolatori elettronici digitali, macchine particolarmente adatte all'esecuzione di programmi che implementano algoritmi, che interesse può ancora esserci per lo studio dei formalismi? In un certo senso, specialmente la categoria degli automi è in buona sostanza un precursore dei moderni calcolatori; perché dunque affidarsi ad uno strumento che pare anacronistico?
▲I motivi sono tanti: il più significativo risiede nella sottile differenza tra quanto studiato dall'informatica teorica (gli algoritmi) e quanto eseguito dai computer (i programmi); anche se un programma implementa uno o più algoritmi è molto importante non confondere il primo coi secondi.
Le prestazioni di un programma, infatti, dipendono in modo decisivo dallo hardware su cui viene eseguito, hardware che subisce continui aggiornamenti. Se affidassimo lo studio delle proprietà degli algoritmi ai programmi da essi derivati, le loro prestazioni cambierebbero quindi in modo importante nel tempo: basti pensare a come sono cambiate le prestazioni di un personal computer negli ultimi 30 anni!
Line 31 ⟶ 29:
É importante, quindi, riconoscere che si può parlare di prestazioni di un algoritmo anche in assenza di un programma che lo implementi; e qui nasce il problema: come si fa a ''rappresentare'' un algoritmo? Come si fa ad ''analizzare'' un algoritmo?
I metodi di rappresentazione si sprecano, uno su tutti i diagrammi di flusso; queste tecniche, tuttavia, sono state concepite allo scopo di ''comunicare'' il contenuto dell'algoritmo impiegando una notazione più o meno rigorosa, ma disinteressandosi degli aspetti analitici, di vitale importanza per stimare le prestazioni.
I metodi che consentono anche l'analisi, quindi, devono disporre di due caratteristiche: essere slegati dalle macchine commercialmente disponibili ed offrire a chi li utilizza tutti gli strumenti per trarre utili indicazioni in merito all'efficacia ed all'efficienza dell'algoritmo in questione.
Line 40 ⟶ 38:
==Gli automi==
Sebbene gli automi non siano gli unici formalismi possibili
Storicamente, infatti, è proprio lo studio degli automi che ha portato alla realizzazione dei primi calcolatori elettronici; il debito che la nostra società ha con Alan Turing, ad esempio, è altissimo proprio perché il suo formalismo principale, la ''macchina di Turing'', contiene in sé tutti gli elementi dei moderni (e soprattutto dei futuri) calcolatori elettronici.
Vale davvero la pena, quindi, spendere due parole sulla struttura (piuttosto simile) che accomuna tutti gli automi: ognuno di essi può comunicare con l'ambiente e dispone anche di uno stato interno che cambia in funzione degli stimoli provenienti dal mondo esterno. Più precisamente, in ogni formalismo riconosciamo quattro
# un ''ingresso'' che permette all'automa di acquisire dati dall'ambiente;
# uno ''stato'' che indica l'attuale condizione operativa dell'automa;
# un'''uscita'' che consente all'automa di comunicare con l'ambiente;
# un ''programma'' che coordina le attività dell'automa.
=La teoria della computabilità=
Il concetto di ''
Questa osservazione fa nascere alcune domande: che cos'è un problema? Sarà vero che
La teoria della computabilità cerca di rispondere a questi interrogativi, offrendo una serie di strumenti concettuali utili per indagare le condizioni che portano all'esistenza di un algoritmo.
Line 72 ⟶ 69:
La teoria della complessità cerca di dare una risposta a questi interrogativi, sviluppando strumenti utili per l'analisi degli algoritmi e per sviluppare previsioni ragionate sulle loro prestazioni in genere.
=Il concetto di computazione=
| |||