Appunti di lezione Fondamenti di Informatica per il Web Design

INFORMATICA

lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione in modo funzionale agli

obiettivi: la loro teoria, analisi, progetto, ef cienza, realizzazione e applicazione.

L'informazione ha l'obiettivo di creare una rappresentazione dei dati in modo da estrarre conoscenza oppure

migliorare la loro interpretazione da parte dell’utente.

In caso di grandi quantità di dati e sia necessaria un'elaborazione veloce dell'informazione, si usano i

CALCOLATORI ELETTRONICI, che permettono una rappresentazione ef cace, sistematica, veloce e pratica

dell’informazione; eseguono algoritmi per l'elaborazione ed utilizza elementi di memoria per immagazzinare

le informazioni che sta elaborando.

 

Informazione di ingresso Calcolatore Informazione in uscita (dato oggettivo) / Conoscenza (osservazione

che facciamo sui dati)

ALGORITMO

una sequenza nita di operazioni elementari (eseguibili e non ambigue) che giunge certamente a

terminazione. L’algoritmo permette di risolvere uno speci co compito o problema.

La descrizione di un algoritmo per un esecutore deve avere una formulazione generale:

• Gli algoritmi devono acquisire i valori dei dati da utilizzare ed elaborare in ogni speci ca esecuzione;

• La soluzione individuata deve essere generale e deve funzionare per ogni valore ammesso dalla speci ca.

Rappresentazione di un algoritmo:

• Descrizione delle operazioni eseguibili e dei dati

• Descrizione di tutte le possibili sequenze di operazioni da eseguire per risolvere il problema dato ( usso di

controllo)

• Deve essere univoco (sia da parte del programmatore che dell’esecutore) il modo di andare da dati in

ingresso a dati di uscita ( usso di esecuzione**)

** la sequenza di operazioni effettivamente eseguite durante una particolare esecuzione dell’algoritmo e che

dipende dagli speci ci valori che i dati assumono in quell’esecuzione.

CARATTERISTICHE

L’algoritmo ottiene la soluzione del compito cui è preposto —> il calcolatore eseguirà l’algoritmo a

• prescindere che sia giusto o sbagliato; è compito del programmatore garantire che l’algoritmo sia corretto,

e de nire come ottenere un modo più veloce o come usare la minima quantità di risorse siche.

Se l’algoritmo arriva a una soluzione sbagliata, la colpa è del programmatore.

PROPRIETÀ

Flusso di esecuzione: l’algoritmo è un procedimento passo per passo con un ordine speci cato.

• Determinismo: a ogni passo, il successivo deve essere uno e uno solo, ben determinato.

• Non ambiguità: i passi elementari devono essere eseguiti in modo univoco dall’esecutore,

• Atomicità: ogni operazione deve essere elementare, cioè non ulteriormente scomponibile.

• Finitezza: l’algoritmo deve essere composto da un numero nito di passi e richiedere una quantità nita di

• dati in ingresso.

Terminazione: l’esecutore deve terminare in tempo nito per ogni insieme di valori in ingresso.

• Osservabilità: l’algoritmo deve produrre un effetto osservabile dopo l’esecuzione.

• Effettività: deve produrre lo stesso effetto ogni volta che viene eseguita a partire dalle stesse condizioni

• iniziali. 1

fi fi fi fl fi fi fi fi fi fi fi fi fl fi fi

ELEMENTI DEGLI ALGORITMI

Dati: gli oggetti su cui opera l’algoritmo; possono essere variabili o costanti; devono essere sempre

rappresentati in modo univoco e comprensibile per il calcolatore

Operazioni: elaborazioni da effettuare sui dati —> calcoli, confronti, assegnamenti, acquisizioni, emissioni…

Flusso di controllo: speci ca delle possibili successioni dei passi dell’algoritmo

VARIABILI

sono un contenitore di valori salvati in memoria. (Anche informazioni) Ad una variabile è sempre associato un

valore alla volta. Non è mai vuota (al massimo non è inizializzata e quindi ha un valore “a caso”).

La variabile è identi cata tramite un nome simbolico. Le operazioni descritte nell’algoritmo possono essere

eseguite di volta in volta sui diversi valori assegnati alle variabili (formulazione generale dell’algoritmo).

Possiamo eseguire 2 operazioni fondamentali su una variabile:

Lettura: recuperiamo il valore contenuto

Scrittura: salviamo il nuovo valore in memoria

ELEMENTI PER DESCRIVERE I FLUSSI DI CONTROLLO

Blocco di inizio: identi ca l’inizio dell’algoritmo

Blocco di terminazione: determina la ne dell’algoritmo

Blocco di ingresso dati: permette di acquisire dati

Blocco di uscita dati: permette di visualizzare dati

Blocco esecutivo: de nisce le operazioni sui dati

Blocco condizionale: permette di effettuare scelte, vero o falso

Ogni blocco è ATOMICO: deve contenere una e una sola operazione: Nel caso servano più operazioni, è

necessario usare più blocchi consecutivi.

Blocchi di ingresso e uscita sono necessari per acquisire dati dall’utente e visualizzare risultati

• (proprietà di osservabilità e generalità).

Assegnamenti ed operazioni: negli schemi a blocchi, operazioni e condizioni sono rappresentate in

• modo testuale e tramite simboli che rappresentano gli operatori aritmetici, di confronto, ecc.

Assegnamento: =

• A sinistra c’è sempre una variabile (destinazione)

• Il valore a destra dell’assegnamento è copiato nella variabile a sinistra

Es: x=6,y=x, z=x+6,...

Operatori aritmetici: +, -, * , /, %

Un’operazione deve sempre essere accompagnata da un assegnamento (osservabilità)

• Eseguono l’operazione sui due operandi speci cati (variabili o costanti)

• Producono un valore numerico

• Es: a+5, 3+6, w+x,...

•

Condizioni: operazioni ed espressioni

• Operatori di confronto: >, <, ==, >=, ...

• Eseguono l’operazione sui due operandi speci cati 2

fi fi fi fi fi fi fi

• Gli operandi possono essere variabili o costanti

• Producono un valore logico (vero o falso)

• Es: x>5, y<=x,...

Operatori logici: and, or, not

Eseguono l’operazione sui due operandi speci cati

• Gli operandi possono essere variabili o costanti

• Producono un valore logico (vero o falso)

• Sono utilizzanti principalmente per esprimere condizioni complesse

•

Espressioni

È possibile comporre gli operatori sopra speci cati per ottenere espressioni complesse che

• restituiscono un risultato aritmetico (assegnamento) o logico (condizione)

Es: x+y >10 and y < 3

•

Uso delle condizioni per creare iterazioni

La freccia «Vero» in uscita da un blocco condizionale può essere diretta

verso un precedente blocco nel usso di controllo.

In questo modo è possibile esprimere la ripetizione (iterazione o ciclo)

di un insieme di istruzioni

•L’insieme di istruzioni ripetute è il corpo del ciclo

•La condizione di permanenza del ciclo determina no a quando il ciclo

deve essere ripetuto.

•Il corpo del ciclo è ripetuto un numero nito di volte

Attenzione a non creare cicli in niti e cicli che non saranno mai eseguiti!

Tipologie di cicli

Il modo in cui la condizione è collegata al corpo del ciclo (e al resto del usso di controllo) determina la

tipologia del ciclo che viene implementata.

Ciclo a condizione nale: il corpo del ciclo viene eseguito sempre almeno una volta

Ciclo a condizione iniziale: il corpo del ciclo potrebbe non essere mai eseguito

Con opportune trasformazioni è possibile passare da una forma all’altra.

RAPPRESENTAZIONE DELL’INFORMAZIONE

La rappresentazione unaria è la codi ca più semplice dei numeri (basata su un sistema additivo). La

dimensione della rappresentazione cresce in modo lineare con il numero da rappresentare. Impraticabile per

gestire numeri grandi.

Es. La barretta I rappresenta il numero 1 —> la sequenza IIIIII denota il numero 6 e così via

Numeri romani: sistema additivo che minimizza la dimensione della rappresentazione usando simboli per

multipli di 5. Numeri naturali sono una combinazione di simboli (I, V, X, L …)

Per sempli care la notazione, si usa un sistema in parte posizionale, es. 4 viene codi cato come 5-1 e quindi

scritto IV.

Rappresentazione decimale: codi ca posizionale basata sul numero 10 (chiamata base). Gli stessi numeri

assumono valore diverso in base alla posizione. Ad ogni posizione è associata una potenza di 10 (mille,

diecimila, ecc.) a partire da destra verso sinistra.

La notazione posizionale può essere utilizzata in qualsiasi base cambiando il valore della base. 3

fi fi fl fi fi fi

fi fi fi fi fl fi

Alfabeto: {0 1 2 3 4 5 6 7 8 9}

Codi ca binaria (base 2): codi ca posizionale usata dal calcolatore per tutte le informazioni.

BIT: unità elementare di informazione; facile da implementare: dispositivi che assumono due stati —> acceso/

spento corrispondente ai due valori di tensione (Vdd e Vgnd)

Numeri Razionali

Utilizzando opportune convenzioni possiamo pensare di rappresentare non solo interi ma anche numeri

razionali.

Virgola ssa: si ssa il numero di cifre della parte intera e decimale

• Necessario utilizzare potenze di 2 sia positive (prima della virgola) che negative (dopo la virgola)

Virgola mobile: rappresentazione in cui la virgola decimale varia a seconda del numero per rappresentare sia

numeri molto piccoli (grandi).

• Si usa una rappresentazione del tipo: Valore= +/-1.mantissa x 2+/-esponente

• La mantissa viene normalizzata per ottenere una rappresentazione unica (1.mantissa)

Standard IEEE

Dato che il numero di bit per esponente e mantissa può variare, è necessario de nire uno “standard” (accordo

internazionale) per la rappresentazione di numeri in virgola mobile.

«Precisione doppia» ha molti più bit per rappresentare la parte decimale: precisione molto maggiore. 4

fi fi fi fi fi

STRUTTURA DEI CALCOLATORI

Sistema informatico: ampia gamma di strumenti utilizzati per svolgere algoritmi in modo automatico.

Hardware: componenti siche —> circuiti, schede, memorie, periferiche, stampanti, monitor…

Software: programmi eseguibili —> istruzioni e dati che consentono all'hardware di compiere determinate

funzioni.

Elementi principali

CPU (Unità di elaborazione)

elabora dati, coordina trasferimento dei dati; segue i programmi, cioè interpreta ed esegue le loro istruzioni.

Contiene gli elementi circuitali che regolano il funzionamento del calcolatore:

L’orologio di sistema (clock) permette di sincronizzare le operazioni temporizzando il funzionamento del

• calcolatore

L’unità di controllo è responsabile della decodi ca e dell’esecuzione delle istruzioni. È la parte che

• “dirige” l’esecuzione di tutte le altre parti

L’unità aritmetico-logica (ALU) realizza le operazioni aritmetiche e logiche eventualmente richieste

• dall’unità di controllo per l’esecuzione dell’istruzione. È priva di facoltà di scelta.

I registri sono piccole memorie velocemente accessibili, utilizzate per memorizzare risultati parziali o

• informazioni necessarie al controllo. L’insieme dei valori contenuti nell'insieme di tutti i registri in un dato

istante dell’elaborazione viene chiamato contesto.

Tipologia di istruzioni

• Istruzioni di elaborazione dei dati: eseguono un’operazione aritmetico/logica/di confronto sui dati speci cati

in due registri (o un registro ed una costante) e salvano il risultato in uno dei registri.

• Istruzioni di trasferimento dei dati: eseguono un’operazione di trasferimento di un dato da un registro di

lavoro alla memoria o viceversa; possono esserci anche operazioni di trasferimento più complesse con le

periferiche. 5

fi