Elementi di Programamzione

Analisi di un esempio di computazione

è possibile data una configurazione inizialevalutare apriori che l’esecuzione della MdT giunga a termine, ovvero che si giunga ad unaconfigurazione finale: questo è il grande limite delle macchine di Turing che prende il nome diindecidibilità della fermata. Turing studiò in particolare la cosiddetta Macchina Universale,ovvero una macchina di Turing in grado di imitare una qualsiasi particolare macchina di Turing.Quest’ultima ha costituito il primo modello del futuro computer programmabile, in un certo sensogli odierni computer programmabili sono macchine universali di Turing, le quali sono state messein pratica con l’architettura di Von Neumann.

1.4. Algoritmi

La programmazione è l'attività di sviluppare programmi per un calcolatore, lo scopo della scritturadi un programma è la risoluzione di un determinato problema, operazione che richiede degli step:

 Formulare il problema (specifica dei requisiti) in modo

più o meno formale.

1. Capire il problema e scomporlo in parti gestibili (analisi del problema). Soltanto i problemi per cui è possibile una formalizzazione matematica possono essere risolti con la programmazione informatica.
2. Progettare una soluzione (algoritmo).
3. Implementare la soluzione (scrittura del codice).
4. Testare la soluzione e correggere eventuali errori (verifica del programma, testing e debugging).
5. Tenere sempre aggiornato il programma (manutenzione).

In genere i problemi vengono scomposti in una sequenza di sottoproblemi più piccoli: la soluzione di tutti i sottoproblemi implica anche la soluzione del problema. Per ciascuno di questi sottoproblemi occorre sviluppare un determinato algoritmo. Si definisce algoritmo una sequenza finita di passi che risolve automaticamente un problema, e tale sequenza deve essere discreta, di lunghezza finita, deterministica (dopo ogni passo si sa precisamente qual è il prossimo) e ripetibile.

Esempi di

• Sequenza: le azioni vengono svolte una alla volta (non c'è parallelismo);
• Finita: la lista della spesa è un qualcosa di finito ed inoltre il numero di azioni che si svolgono è sempre finito (non si rischia di stare in eterno nel supermercato!);
• Passi: ogni singolo passo (riempire il carrello, cercare sullo scaffale, ...) non implica per se il concetto di spesa: è solo nella sequenza (ossia nella concatenazione intelligente di tali passi) che il problema viene risolto;
• Automaticamente: una volta scritto e lanciato l'algoritmo, non c'è bisogno di intervento esterno; l'esecutore ha tutti gli elementi per poter risolvere il problema.
• Osservabile: ogni passo deve avere un effetto osservabile, cioè deve produrre qualcosa, ad esempio il carrello si riempie di un prodotto.

• Riproducibile: a partire dallo stesso stato iniziale, lo stesso algoritmo deve produrre sempre lo stesso risultato.

Un algoritmo per risolvere un problema deve lavorare su dei dati, che possono essere di tre tipi:

1. Dati in input: Sono i dati in ingresso di un algoritmo. Possono essere digitati dall'utente con la tastiera oppure letti da un file o ricevuti telematicamente via modem.
2. Dati di elaborazione: Sono i dati temporanei creati durante l'esecuzione del programma. Non sono dati né di input, né di output.
3. Dati in output: Sono i dati in uscita di un algoritmo, ossia il risultato dell'operazione. Possono essere stampati a video, su una stampante oppure salvati su un file o trasmessi via modem.

Procedendo però con ordine, si mostrano gli stadi di progettazione di un programma:

1. La prima fase consiste nella ricerca della soluzione migliore al problema, successivamente si converte l'idea in una soluzione formale, ovvero in

un testo che descrive la soluzione in modo formale (algoritmo). L'algoritmo viene tradotto in una sequenza di istruzioni comprensibile all'esecutore (in questo caso l'elaboratore elettronico, ma anche un umano può eseguire un algoritmo): questa sequenza si chiama programma. Si nota che l'operazione di formalizzazione della soluzione consente una più semplice traduzione nelle regole di realizzazione. Per passare dal problema alla Soluzione aiuta molto l'esperienza, mentre nel passaggio dalla Soluzione alla Soluzione Formale esistono diversi strumenti automatici o metodi formali di cui il programmatore può avvalersi; infine nel passaggio dalla Soluzione Formale al Programma vengono in aiuto le Tecniche di Programmazione. Il programma deve essere provato con un insieme significativo di dati per garantire che funzionerà in ogni occasione (qualsiasi siano i dati di input). Infine occorre documentare opportunamente il programma a beneficio di

Chi lo userà ed eventualmente lo modificherà. Per maggiore chiarezza viene mostrato un esempio di progettazione di una soluzione:

Sono disponibili numerosi strumenti per rappresentare una soluzione in modo formale (algoritmo), i più utilizzati sono:

• Pseudo-Codice: è un modo testuale di rappresentare un algoritmo a metà fra il linguaggio naturale ed un linguaggio di programmazione, lo svantaggio è che a volte l'interpretazione può essere più complicata perché non esiste un unico pseudo-linguaggio standardizzato.
• Diagrammi di Flusso: anche detti Flow Chart, descrivono gli algoritmi utilizzando un approccio grafico che è molto intuitivo e astratto, ma richiede l'apprendimento della funzione dei vari tipi di blocco.
• Linguaggio Naturale: è il modo testuale di rappresentare informalmente un algoritmo più semplice in assoluto perché consiste nel descrivere l'algoritmo a parole.

Linguaggio di Programmazione: è un modo testuale di descrivere formalmente un algoritmo, si utilizza la sintassi e la semantica di un certo linguaggio di programmazione che però è necessario conoscere per comprendere l'algoritmo.

L'approccio che più si utilizza è quello dei Flow Chart, che è composto da una serie di blocchi elementari che descrivono azioni o decisioni, ed archi orientati che collegano i vari blocchi per descrivere la sequenza di svolgimento delle azioni. Di seguito sono riportati i blocchi elementari ed anche un piccolo esempio per comprenderne meglio l'utilizzo, che effettua la stampa del valore assoluto di un numero A:

La teoria degli algoritmi fornisce algoritmi notevoli per risolvere determinati problemi, e classifica la complessità dei problemi intesa come la complessità del migliore algoritmo che lo risolve. Per complessità di un algoritmo si intende invece la misura del numero di passi che

• Problemi decidibili: hanno una soluzione algoritmica.
• Problemi Indecidibili: NON hanno una soluzione algoritmica.

• Problemi Trattabili (n): ammettono algoritmi di soluzione efficiente, ad esempio la ricerca del massimo e l'ordinamento di n numeri.
• Problemi Intrattabili (k): non possono essere risolti per loro natura da algoritmi efficienti, ad esempio il problema della cricca.
• Problemi Da Capire: non sono stati ancora trovati algoritmi efficienti che li risolvano.

programmazioneSOURCE (codice sorgente), per esempio il linguaggio C, in istruzioni di un linguaggio TARGET, c