Esame Elementi di informatica

Informatica e algoritmi

L'informatica consiste nello studio sistematico dei processi che servono al trattamento delle informazioni o più in generale della definizione della soluzione di problemi assegnati. Algoritmo è il termine introdotto in matematica per indicare la sequenza precisa di azioni elaborative necessarie per la soluzione di un problema assegnato, l'elaborazione del concetto matematico di funzione Y=F(X) dove X sono i dati iniziali da elaborare, Y i dati finali o risultati e F è la regola di trasformazione.

L'informatica è lo studio sistematico degli algoritmi, il calcolatore è il più potente esecutore di algoritmi. Le macchine informatiche trovano soluzioni ad un gran numero di problemi in modo più veloce e conveniente degli esseri umani. Tuttavia, dobbiamo osservare che per alcuni problemi non esiste una soluzione, altri invece hanno più soluzioni possibili (si calcola quella più vantaggiosa sulla base di un insieme di parametri prefissati: costo della soluzione, tempi di attuazione, risorse necessarie alla sua realizzazione, ecc.), per alcuni problemi non esistono soluzioni eseguibili in tempi ragionevoli.

Funzionamento di un algoritmo

Algoritmo = Un insieme di operazioni/azioni (dette istruzioni) da eseguire per risolvere il problema assegnato secondo un ordine prefissato.

Esecutore = L'uomo o la macchina in grado di risolvere il problema eseguendo l'algoritmo. Non deve comprendere le singole istruzioni ma deve essere anche capace di eseguirle secondo un ordine rigidamente sequenziale e in parallelo, eseguendo più istruzioni contemporaneamente.

Informazioni di ingresso = Le informazioni da fornire affinché avvengano le trasformazioni desiderate.

Informazioni di uscita = I risultati prodotti dall'esecutore del dato algoritmo.

Automa a stati finiti (ASF)

È una prima astrazione di macchina "dotata di memoria" che esegue algoritmi. Essa introduce il concetto fondamentale di "stato" che informalmente può essere definito come particolare condizione di funzionamento in cui può trovarsi la macchina.

Rappresentazione grafica di un ASF

È possibile rappresentare graficamente un ASF mediante un grafo detto diagramma degli stati.

Macchine di Turing

È un particolare automa per il quale sono definiti: l'insieme degli ingressi e delle uscite come insiemi di simboli; è un particolare meccanismo di lettura e scrittura delle informazioni composto da una testina di scrittura/lettura su nastro bidirezionale potenzialmente illimitato. Permette di raggiungere risultati teorici sulla calcolabilità e sulla complessità.