Dall’Algoritmo al Programma

Sono presentate alcune nozioni di algoritmica. in particolare, sono definite ed illustrate con esempi le nozioni di problema computazionale, funzione matematica, rappresentazione di dati, progettazione di algoritmi, analisi di efficienza di algoritmi, linguaggi per la descrizione di algoritmi, e modelli di calcolo per l'esecuzione di algoritmi. Sono presentati alcuni problemi fondamentali (moltiplicazione tra interi, ricerca del minimo in un insieme, ordinamento di una sequenza di interi) insieme a semplici algoritmi per la loro risoluzione. Viene illustrata la differenza tra problemi trattabili (che possono essere risolti con algoritmi efficienti), problemi intrattabili (che possono essere risolti, ma non con algoritmi efficienti), e problemi insolubili (che non possono essere sempre risolti). Sono illustrati i costrutti principali dei linguaggi di programmazione ad alto livello (sequenza, iterazione, condizionale) che servono per la descrizione precisa e non ambigua di algoritmi. Sono brevemente descritti anche i principali modelli di calcolo (automi a stati finiti, macchina di Turing, macchina di von Neumann). Sono infine brevemente descritti dei semplici algoritmi per tre importanti applicazioni (ricerca di parole in testi, cifratura di messaggi, ray tracing).