Appunti e formulario per teoria di Fondamenti di informatica

QUANTIZZAZIONE UNIFORME

Tutti gli intervalli in cui si suddivide il range R (in figura 0-Fs) dei valori possibili hanno la stessa dimensione P (precisione).

Tutti i valori che cadono in un intervallo vengono rappresentati da un unico valore discreto.

Errore di quantizzazione

Se ho un segnale digitalizzato posso solo fare un’approssimazione del valore di partenza: si chiama errore di quantizzazione.

Si tratta della differenza tra il valore quantizzato e il suo valore reale nel campo continuo

Formule

Aumentando la precisione, aumentano gli intervalli.

All’aumentare della precisione aumenta anche il numero di bit

che mi servono per rappresentare gli intervalli

Esercizio

CONVERSIONE ANALOGICO-DIGITALE

È conveniente effettuare una trasmissione o elaborazione in forma numerica. È necessario convertire i segnali analogici in numerici e,

dopo aver effettuato la trasmissione o l’elaborazione, riconvertirli in segnali analogici

Processo di trasformazione di una grandezza analogica, continua nel tempo e in ampiezza, in una grandezza digitale, discreta nel tempo e in ampiezza.

Processi di discretizzazione

1. CAMPIONAMENTO: processo di discretizzazione nel dominio del tempo

Consiste nell’acquisire il valore del segnale in determinati istanti. Se i valori vengono acquisiti ad istanti di tempo equispaziati (a distanza ΔTc), si parla di

campionamento uniforme.

2. QUANTIZZAZIONE: processo di discretizzazione in ampiezza

Consiste nel codificare i valori x(kΔTc) assegnando ad ognuno di essi un valore discreto. ΔTc è l’intervallo di campionamento.

CAMPIONAMENTO

Def: tecnica che consiste nel convertire un segnale continuo nel tempo in un segnale discreto, valutandone l'ampiezza a intervalli di tempo regolari.

Campionare un segnale La frequenza di campionamento è la misura

Ogni valore misurato si chiama CAMPIONE e l’operazione prende il nome di CAMPIONAMENTO. espressa in hertz del numero di volte al secondo

In generale, campionare un segnale è un metodo per registrare un valore istantaneo di quel segnale. in cui un segnale analogico viene misurato e

memorizzato in forma digitale.

Teorema del campionamento

Il teorema del campionamento (Nyquist-Shannon, 1949) afferma che la minima frequenza di campionamento Fc necessaria per evitare ambiguità

nella ricostruzione del segnale con larghezza di banda finita e nota B è pari al doppio della sua massima frequenza B.

Running

· M PIReady

-

Blocked

mPz

Non ci possono essere due processi in running, solo uno alla volta oppure zero. Ci

possono essere due processi in blocked

·

1 ALGORITMI E FLOWCHART

DEFINIZIONE DI ALGORITMO

L’algoritmo è una sequenza di operazioni. Queste operazioni devono essere definite in modo preciso, eseguite un numero finito di volte in modo da poter

portare a termine un compito. Se queste operazioni vengono svolte in un certo ordine riescono a risolvere un problema (i dati in ingresso opportunamente

trasformati danno i dati in uscita).

La definizione di algoritmo serve per rendere automatica la risoluzione del problema da parte del calcolatore (esecutore dei problemi). Si tratta di

programmi che risolvono problemi generici (esempio: non 2+2 ma la somma di due numeri) non problemi specifici in cui i dati sono tutti noti.

Per risolvere un problema bisogna:

1. Comprendere il problema

2. Organizzare i dati in memoria

3. Definire l’algoritmo (procedimento risolutivo per il problema)

4. Implementare l’algoritmo in un linguaggio di programmazione

Per risolvere un problema bisogna definire un procedimento risolutivo, ossia una sequenza logica di istruzioni elementari (univocamente interpretabili) che,

eseguite secondo un ordine prestabilito, permettono di giungere alla soluzione a partire dai dati.

Def: l’ALGORITMO è una successione finita di passi contenenti istruzioni che specificano le operazioni da compiere per risolvere una classe di problemi

Def: l’algoritmo deve essere espresso in termini delle istruzioni di un esecutore automatico detto CALCOLATORE

IL RUOLO DEL COMPUTER

ALGORITMI E LINGUAGGI

Un algoritmo deve poter essere eseguito da chiunque.

Gli algoritmi devono essere formalizzati per mezzo di appositi linguaggi dotati di strutture linguistiche che garantiscono precisione e sintesi

Linguaggi naturali:

1. Ambigui = la stessa parola può assumere significati diversi a seconda del contesto

2. Ridondanti = lo stesso concetto può essere espresso in molti modi diversi

LINGUAGGI E TRADUTTORI

GENERAZIONI DI LINGUAGGI

1. Linguaggio macchina

- es: binario

- direttamente eseguibile

- linguaggio specifico della CPU

2. Linguaggi simbolici (codice assembler)

- es: x86, MIPS, PowerPC

- strettamente legato all’architettura

- linguaggi specifici del singolo processore

3. Linguaggi ad alto livello

- es: C, Basic, Java

- indipendente dall’architettura

CARATTERISTICHE LINGUAGGI

a. Necessità di traduzione

b. Complessità del traduttore

c. Portabilità = il linguaggio può scrivere programmi traducibili su piattaforme diverse (ci sono programmi non portabili come per esempio il binario)

d. Leggibilità

e. Efficienza = tempo di esecuzione di un programma e uso ottimizzato delle risorse, uso della memoria

f. Facilità d’uso

g. Probabilità di errore

LINGUAGGIO MACCHINA

- utilizzano la codifica binaria di codice operativo e operandi

- le istruzioni sono quelle direttamente eseguibili dalla CPU

- i programmi sono utilizzabili solo su elaboratori equipaggiati con la CPU corrispondente al linguaggio (non portabile)

- programmazione difficile

- pessima leggibilità

- facilità di errori

- alta efficienza (dipende dal programmatore)

LINGUAGGI ASSEMBLATIVI (SIMBOLICI)

- le istruzioni sono quelle eseguibili dalla CPU

- rappresentazione simbolica, tramite brevi mnemonici, di codici operativi e operandi

- riferimento alle variabili tramite il nome

- necessità di un traduttore in linguaggio macchina (assemblatore)

- possibilità di definire ed utilizzare macroistruzioni

- i programmi sono utilizzabili solo su elaboratori equipaggiati con la CPU corrispondente al linguaggio (non portabili)

- programmazione abbastanza difficile

- scarsa leggibilità

- alta efficienza (dipende dal programmatore)

LINGUAGGI DI ALTO LIVELLO

- le istruzioni esprimono operazioni significative nella logica del programmatore non coincidenti con quelle eseguite dalla CPU

- necessità di un traduttore (compilatore o interprete)

- la traduzione trasforma un’istruzione in una sequenza di istruzioni macchina

- efficienza ridotta rispetto ai linguaggi assemblativi (dipende dal compilatore), ma possibilità di ottimizzazioni

- portabilità di un programma su tutti gli elaboratori che dispongono di un traduttore per il linguaggio

- introduzione di costrutti logici

- maggiore facilità d’uso

- buona leggibilità

ASSEMBLATORI o TRADUTTORI

Gli assemblatori sono dei programmi che traducono un programma scritto in assembler in linguaggio macchina. L’assemblatore prende una a una tutte le

righe del programma assembler e isola i vari pezzettini. Una volta che ha verificato che la struttura delle istruzioni è corretta si procede con la traduzione

vera e propria del codice in binario

CLASSIFICAZIONE LINGUAGGI TERZA GENERAZIONE

I linguaggi ad alto livello vengono classificati in:

1. PROCEDURALI

2. FUNZIONALI

3. BASATI SULLA LOGICA

3. ORIENTATI AGLI OGGETTI

SCELTA DI UN LINGUAGGIO

La scelta di un linguaggio va fatta in funzione di certi parametri:

a. Adattabilità al problema

b. Facilità di apprendimento

c. Facilità d’uso

d. Comprensibilità e modificabilità dei programmi

e. Portabilità dei programmi

f. Efficienza

g. Software di supporto

h. Esistenza delle librerie (librerie = funzioni già elaborate da altri)

LINGUAGGI PROCEDURALI

Sono basati sul modello computazionale di Von Neumann, in cui un programma è visto come una sequenza di

istruzioni tendente a modificare il contenuto della memoria.

Caratteristiche:

- indipendenti dalla macchina

- possibile l’uso di nomi simbolici per i dati

- sintassi vicina al linguaggio naturale

- basati su istruzioni e assegnazioni

- permettono astrazioni sui dati: possibilità di definire tipi di dati e operazioni sui tipi

COMPILATORE

Un compilatore di un linguaggio L (Pascal, C, FORTRAN, ...) per una macchina X, è un programma che:

1. preso in ingresso un programma P scritto nel linguaggio L

2. produce in uscita un programma P’ equivalente a P scritto nel linguaggio della macchina X

ESERCIZI

Leggere 100 valori e stampare la somma dei positivi e la somma dei negativi

Leggere 100 valori e calcolare la media dei numeri pari e dei numeri dispari e stampare la maggiore

Calcolare la potenza n e stampare

i1, i2 e i3 per quale algoritmo sono le misure dei lati del triangolo rettangolo

FORMULARIO

Sistemi di numerazione

Valore assoluto attenzione: solo per numero positivi

Conversione dalla base A alla base B (parte intera) La parte intera va letta dal basso verso l’alto

Conversione dalla base A alla base B (parte frazionaria) La parte frazionaria va letta dall’alto verso il basso

Raggruppare a partire da destra le cifre in gruppi di 4 e scrivere il corrispondente esadecimale

Da binario a esadecimale

Da esadecimale a binario Espandere ciascuna cifra esadecimale con i 4 bit corrispondenti in binario

Raggruppare a partire da destra le cifre in gruppi di 3 e scrivere il corrispondente ottale

Da binario a ottale Espandere ciascuna cifra ottale con i 3 bit corrispondenti in binario

Da ottale a binario

Operazioni binarie Si utilizza un bit per rappresentare il segno del numero considerato: 0 per i positivi, 1 per i negativi

Modulo e segno

Complemento alla base b attenzione: se il numero è negativo metto il meno - davanti al risultato ottenuto

Sommo una costante fissa N al numero dotato di segno e il risultato lo converto in binario

Eccesso

Virgola mobile

Valori rappresentabili In caso di esponente negativo viene

rappresentato in complemento alla base

Standard IEEE 754 È presente un bit nascosto (1) che non viene memorizzato nella mantissa

L’esponente viene memorizzato sommando il valore costante 127 (range dei valori dell’esponente: -126 - +127)

da virgola mobile a decimale Trovo il valore assoluto dell’esponente e sottraggo 127

da decimale a virgola mobile Sommo all’esponente 127 (eccesso 127) e traduco il numero in binario

Traduco il numero in binario in modo da ottenere il bit nascosto 1

Sistemi di codifica Numero dell’insieme

C = cardinalità insieme

n = numero di bit da utilizzare per codificare tutti i simboli dell’insieme

M = minimo numeri di bit necessa