Informatica e Algoritmi

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.