Forse per noia, forse perchè sto preparando l’esame di informatica che avrò dopo domani, ho deciso di scrivere questo breve riepilogo sull’informatica e gli algoritmi. Probabilmente non sarà chiaro alle persone che non si interessano di questo campo. E’ giusto un ripasso o una mini dispensa per chi si interessa di queste cose ;-)
Informatica
Scienza che studia la rappresentazione e l’elaborazione dell’informazione (mediante macchine dette calcolatori elettronici)
Definizione di Algoritmo
Dato un problema e un esecutore, l algoritmo è:
• una successione finita e ordinata di passi elementari (operazioni e direttive);
• eseguibili senza ambiguità (comprensibili) dall’esecutore che risolve il problema dato;
Proprietà degli Algoritmi
Procedimenti sequenziali: un passo dopo l’altro secondo un ordine specificato (flusso di esecuzione)
Correttezza: L’algoritmo perviene alla soluzione del compito cui è preposto senza soluzione del compito cui è preposto, senza difettare di alcun passo fondamentale
Efficienza: L’algoritmo perviene alla soluzione del problema nel modo più veloce possibile e/o usando la minima quantità di risorse fisiche
Determinismo: I passi elementari devono essere eseguiti in modo univoco dall’esecutore e devono essere descritti in una forma eseguibile per l’esecutore
La descrizione di un algoritmo per un esecutore deve avere una formulazione Generale:
- La soluzione individuata non deve dipendere solo da valori predefiniti dei dati, cosi che l’algoritmo sia utilizzabile nel maggior numero possibile di casi;
- Gli algoritmi prevedono particolari passi destinati ad acquisire i valori dei dati da utilizzare ed elaborare in ogni particolare esecuzione.
Terminazione: L’esecutore deve terminare in tempo finito per ogni insieme di valori in ingresso
- Insieme finito di istruzioni e ogni istruzione eseguita un numero finito di volte
- Realizzabilità pratica: L’esecutore deve essere in grado di eseguire l’algoritmo con le risorse a sua disposizione (informazioni + tecnologia).
Elementi:
- Oggetti: L’entità su cui operà l’algoritmo (dati iniziali, informazioni ausiliarie, risultati parziali e finali). Le informazioni sono dette dati e possono essere variabili o costanti.
- Operazioni: Interventi da effettuare sui dati (Acquisizione e produzione dati, operazioni aritmetiche, operazioni di confronto).
- Flusso di controllo: Sono tutti i possibili passi, anche ciclici, (e tutte le alternative) che portano alla soluzione.
- Flusso di Esecuzione: Dati dati, la sequenza delle operazione effettivamente eseguite sugli stessi.
Il linguaggio formalizzato è costituito da:
Vocabolario:insieme di elementi per la descrizione per la descrizione di oggetti, operazioni e flusso di controllo.
Sintassi: regole di composizione degli elementi e dei costrutti di controllo (istruz.)
Semantica: insieme di regole per l’interpretazione degli elementi e delle istruzioni.