Esame Elementi di informatica

Algoritmo

Il termine algoritmo è 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.

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, mentre altri 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.). Inoltre, per alcuni problemi non esistono soluzioni eseguibili in tempi ragionevoli.

funzionaAlgoritmo=Un insieme di operazioni/azioni• (dette istruzioni) da eseguire per risolvere ilproblema assegnato secondo un ordine prefissato ;

Esecutore=L'uomo o la macchina in grado di risolvere• il problema eseguendo l'algoritmo, non devecomprendere le singole istruzioni ma deve essereanche capace di eseguirle secondo un ordinerigidamente sequenziale e in parallelo eseguendopiù 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)E' una prima astrazione di macchina “dotata di memoria” che esegue algoritmi, essaintroduce il concetto fondamentale di “STATO” che informalmente può essere definitocome 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.
Rappresentazione tabellare
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à degli algoritmi
Definizione formale di Macchina di Turing
Definita dalla quintupla (A, S, f , f , f )
A è l'insieme finito dei simboli di ingresso e uscita
S è l'insieme finito degli stati (di cui uno è quello di terminazione)
f è la funzione di macchina A × S → A
f è la funzione di stato A × S → S
f è la funzione di direzione A × S → D = {Sinistra, Destra, Nessuna}
dLa macchina

è capace di:

• leggere un simbolo dal nastro
• scrivere sul nastro il simbolo specificato dalla funzione di macchina
• transitare in un nuovo stato interno specificato dalla funzione di stato
• spostarsi sul nastro di una posizione nella direzione indicata dalla funzione di direzione

La macchina si ferma quando raggiunge lo stato di terminazione.

La macchina di Turing la cui parte di controllo è capace di leggere da un nastro anche la descrizione dell’algoritmo, essa è UNIVERSALE l’interprete di un linguaggio.

Dividiamo i problemi risolvibili dalla macchina di Turing in:

• Problemi decidibili = sono meccanicamente risolvibili da una macchina di Turing
• Problemi indecidibili = non sono meccanicamente risolvibili da una macchina di Turing

Teoria della calcolabilità

Cerca di comprendere quali funzioni ammettono un procedimento di calcolo automatico, secondo la tesi di Church-Turing se un problema si può calcolare, allora esisterà una macchina di Turing in grado

di risolverlo, ovvero la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.

Confronto tra la macchina di Von Neumann e di Turing

Sono due modelli di calcolo fondamentali per caratterizzare la modalità di descrizione e di esecuzione degli algoritmi.

La macchina di Von Neumann è modellata dalla macchina di Turing Universale per ciò che attiene alle sue modalità di computazione, ha memoria limitata a differenza del nastro di Turing che ha lunghezza infinita e come modello di riferimento per sistemi non solo teorici, prevede anche la dimensione dell'interazione attraverso i suoi dispositivi di input ed output.

Calcolabilità e Trattabilità

Calcolabilità consente di dimostrare l'esistenza (ossia, la decidibilità) di un algoritmo risolvendo un problema assegnato ed indipendente da qualsiasi automa. La calcolabilità classifica i problemi in risolvibili e non risolvibili.

Il concetto di trattabilità è legato a quello di complessità computazionale, essa studia i costi intrinseci alla soluzione dei problemi e mira a comprendere le prestazioni massime raggiungibili da un algoritmo applicato a un problema.

Trattabilità studia l'eseguibilità di un algoritmo da parte di un sistema informatico, la trattabilità in "facili" e "difficili". Quindi individua i problemi risolvibili, detti trattabili, da un elaboratore con costi di risoluzione che crescano in modo ragionevole al crescere della dimensione del problema.

La complessità di un algoritmo corrisponde a una misura delle risorse di calcolo consumate durante la computazione ed è tanto più elevata quanto maggiori sono le risorse consumate.

Se un algoritmo presenta una soluzione però in tempi molto lenti allora la soluzione non è accettabile.

Tipi e misure di complessità

Esistono due tipi di misure di

La complessità è un concetto fondamentale nell'informatica e nell'analisi degli algoritmi. Si riferisce alla quantità di risorse (tempo, spazio, ecc.) richiesta per eseguire un determinato algoritmo o risolvere un problema. In particolare, la complessità può essere divisa in due categorie principali: la complessità temporale e la complessità spaziale. La complessità temporale indica il tempo richiesto per eseguire un algoritmo in base alla dimensione dell'input. Solitamente viene misurata in termini di "big O notation", che fornisce un limite superiore all'aumento del tempo di esecuzione all'aumentare della dimensione dell'input. Ad esempio, un algoritmo con complessità O(n) impiegherà un tempo proporzionale alla dimensione dell'input. La complessità spaziale, invece, indica la quantità di memoria richiesta per eseguire un algoritmo in base alla dimensione dell'input. Anche in questo caso, solitamente viene misurata utilizzando la "big O notation". Ad esempio, un algoritmo con complessità O(n) richiederà una quantità di memoria proporzionale alla dimensione dell'input. La complessità è un aspetto cruciale da considerare durante lo sviluppo di algoritmi, in quanto può influire significativamente sulle prestazioni e sull'efficienza di un programma.