Complete course notes

Page 1

Algoritmi (5): Un algoritmo è una sequenza finita di operazioni elementari, comprensibili da un esecutore, che portano alla realizzazione di un compito. Esecutore: chiunque sappia comprendere la specifica delle operazioni, tipicamente uno strumento automatico. Compito: la risoluzione di un problema. Negli algoritmi è importante la sequenza con cui le azioni vedono eseguite. Ogni algoritmo risolve una sola classe di problemi. Definizione: Dati un problema specifico e un esecutore specifico, un algoritmo è una sequenza finita di passi elementari tale che: 1. I passi sono effettuabili senza ambiguità da parte dell’esecutore; 2. La successione risolve il problema dato. Nel nostro caso utilizziamo degli algoritmi sequenziali in cui i passi si eseguono in ordine, uno alla volta. Criteri di valutazione di un algoritmo: Correttezza: capacità di pervenire alla soluzione in tutti i casi significativi possibili. Efficienza: proprietà strettamente correlata al tempo di esecuzione e alla memoria occupata. Sintassi e semantica: - Sintassi: come si scrivono le istruzioni (forme e struttura) - Semantica: come si interpretano le istruzioni (significato) Linguaggio di codifica semi-formali: Gli algoritmi si possono scrivere in due tipi di linguaggio: - I linguaggi semi-formali: specifiche iniziali ancora leggibili solo all’essere umano (linguaggio naturale) - I linguaggi formali: programmi da eseguire leggibili anche alla macchina (linguaggio di programmazione) Sottoprogrammi: Operazioni elementari: direttamente eseguibili dall'esecutore. Direttive complesse: devono essere raffinate ed espresse in termini di operazioni elementari. Raffinamento di direttive complesse: realizzabile a parte rispetto all'algoritmo principale. Le direttive complesse possono essere considerate come sottoproblemi da…