Appunti di Fondamenti di informatica del corso di Ingegneria elettronica

[1] Basi di linguaggio C

Giovedì 18 settembre 2014 22:59

Problema della rappresentazione

Il passaggio dal file di testo contenente le istruzioni del linguaggio al linguaggio macchina in codice binario è il seguente: file di testo con estensione .c -> compilatore -> Assembler -> codice binario.

Tipi

Ogni valore ha un tipo, il quale è caratterizzato dall'insieme dei valori che rappresenta e dalle operazioni che è possibile eseguire su tale tipo.

Esistono vari tipi, tra cui:

• Int: interi con segno, occupano 4 byte, rappresenta valori tra [-2³¹, 2³¹-1].
• Unsigned int: interi senza segno.
• Float: razionali, valori in virgola mobile. Non rappresenta tutti i razionali all'interno di un intervallo.
• Double: float con doppia precisione.
• Char: rappresenta i 256 caratteri componibili con il codice ASCII.
• Void: tipo nullo.

Variabile

Locazione di memoria che contiene un certo valore di un certo tipo. Tale valore può variare nel corso della computazione, mentre il suo tipo è invariabile.

Ad ogni variabile bisogna associare un nome e un tipo secondo la seguente sintassi: <tipo> var_name;

Prima di essere utilizzabile, una variabile deve essere dichiarata all'interno del programma.

Array

Contenitore di un numero N di elementi dello stesso tipo, si dichiara con: <tipo> Ar_name[N]; dove N è un numero intero.

Per accedere a un valore contenuto in un array bisogna farlo attraverso il suo nome generale esplicitando l'indice nel quale si trova all'interno dell'array.

Ad esempio, per fare riferimento al valore in posizione i dell'array sopra: Ar_name[i];

Le posizioni di un array di N elementi sono comprese tra [0, N-1].

Espressione

Combinazione di variabili e costanti attraverso degli operatori, sono caratterizzate da:

• Valore restituito.
• Effetto sulle variabili.

Operatori

• Aritmetici: +, -, *, /, %.
• Relazionali: <, >, <=, >=, !, !=.
• Logici: &&, ||, !.
• Incremento: ++, --.
• Assegnamento: =.

[1.1] Istruzioni

Giovedì 18 settembre 2014 23:27

Istruzione

Espressione seguita da ";", la sua esecuzione consiste nel calcolare l'espressione e produrre i suoi "side effect", dopodiché passare all'istruzione successiva.

Es (1) a = 3;

Esistono vari tipi di istruzioni.

Espressione

Es (2) a = 3;

Sequenze di istruzioni

Es (3)

1. {
2. a = 3;
3. b = a+3;
4. }

Istruzione condizionale

Permette di condizionare l'esecuzione di un'istruzione (corpo) al valore restituito da un'espressione (guardia).

Es (4)

1. if(a>b){
2. c=10;
3. }

Condizionale con clausola else

Permette di eseguire alternativamente due corpi di istruzioni a seconda del valore restituito da un'espressione.

Es (5)

1. if(a>b){
2. c = 10
3. } else{
4. c = 20;
5. }

Istruzioni di iterazione

Permettono di eseguire ripetitivamente un'istruzione fino a che una certa condizione è vera.

Esistono 3 tipi diversi di iterazione:

• For: composto da un'espressione di inizializzazione, espressione di guardia, incremento.

Es (6): somma dei primi N numeri interi

1. int count;
2. int sum;
3. sum = 0;
4. for(count = 0; count < N; count++){
5. sum = sum + count;
6. }

• While: per spiegarlo implementiamo lo stesso esempio di prima.

Es (7)

1. int count;
2. int sum;
3. sum = 0;
4. count = 0;
5. while(count < N){
6. sum = sum + count;
7. count++;
8. }

• Do-while: la prima iterazione viene eseguita prima del controllo della guardia.

Es (8)

1. int count;
2. int sum;
3. sum = 0;
4. count = 0;
5. do {
6. sum = sum + count;
7. count++;
8. } while(count < N);

[1.2] Funzioni standard e sintassi

Sabato 20 settembre 2014 10:31

Main()

È una funzione; ogni programma inizia la sua esecuzione partendo dalla funzione main, la quale deve necessariamente essere presente.

Commenti

Sono parti di testo che vengono ignorate dal compilatore e non saranno quindi convertite in linguaggio macchina. Essi sono utili al programmatore al fine di annotare qualcosa nel file sorgente del programma.

Esistono due tipi di commento:

• Commenti fino a fine riga: si aprono con " // " e si concludono a fine riga.

Es (9) void main(){
a = 3; // Questo è un commento fino a fine riga
b = 5;
}

• Commenti su più righe: iniziano con " /* " e finiscono con " */ ".

Es (10) void main(){
a = 3; /* Questo è un commento che
inizia qui e termina
dopo questa riga */
5. b = 5;
6. }

Printf()

Permette di stampare a video dei parametri.

Appartiene alla collezione di funzioni della libreria standard.

La sintassi è la seguente: printf("Hello World.");. La quale permette di visualizzare il messaggio "Hello World.".

Scanf()

Permette all'utente di inserire dei valori da tastiera.

Appartiene alla collezione di funzioni della libreria standard.

La sintassi è la seguente: scanf("%d", &var);. La quale permette di associare un valore (in questo caso intero) alla variabile var.

La sintassi prevede quindi di specificare due parametri: il primo è il tipo di dato inserito (%d = intero), il secondo è l'indirizzo della variabile cui assegnare tale valore (l'operatore " & " restituisce l'indirizzo di memoria di una variabile).

Nota: printf() e scanf() sono entrambe definite all'interno della libreria "stdio.h".

Inclusione

È una direttiva che permette di includere, all'interno del sorgente del programma che si sta scrivendo, altri file contenenti codice compatibile.

Si utilizza per importare agevolmente librerie contenenti le definizioni di altre funzioni.

La sintassi è la seguente: #include <libreria>

Es (11): visualizzare la somma dei primi N numeri, con N inserito dall'utente.

1. #include <stdio.h>
2.
3. /* visualizzare la somma dei primi N numeri,
4. con N inserito dall'utente. */
5.
6. void main(){
7. int N, sum, count;
8. sum = 0;
9. printf("Inserisci valore N");
10. scanf("%d", &N); // esplicito il tipo di dato inserito (int) e la variabile(N)
11. for(count = 0; count < N; count++){
12. sum = sum + count;
13. }
14. // per visualizzare più variabili con printf() occorre inserire il tipo di variabile
15. // da visualizzare all'interno di " "" ", successivamente separare gli argomenti con
16. // la virgola e riportare, in ordine, i nomi delle variabili da visualizzare.
17. printf("\nLa somma dei primi %d numeri è %d", n, sum);
18. }

[2] Rappresentazione dei dati

Sabato 20 settembre 2014 11:36

Generale

Di un numero esistono varie rappresentazioni, esse dipendono da:

• Posizionalità della codifica.
• Base di numerazione.
• Numero di cifre.
• Rappresentazione del segno.
• Rappresentazione parti frazionarie.

Codifica posizionale

Ogni cifra ha un posto diverso a seconda della posizione che occupa.

Pertanto lo sviluppo polinomiale sarà:

Es:

Algoritmo di conversione della base di rappresentazione

• Algoritmo che impiega la base di arrivo.

Base 2 -> base 10

Es. (1001) 2

Base 10 -> base 2

Es.

• Algoritmo che impiega la base di partenza.
• (Algoritmo delle divisioni successive).

Base 10 -> base 2

Che può essere scritta

Che quindi è uguale a

Dalla (7) si evince che se a₀ = 1, allora A è dispari, altrimenti A è pari. a₀ è quindi il resto della divisione A/2.

Se ripercorressimo lo stesso procedimento utilizzando A=A/2 arriveremmo allo stesso risultato, quindi:

quindi

Base esadecimale

Rappresenta i numeri con cifre da 0 a 9 e lettere da A a F, si raggruppano i bit a gruppi di 4 (poiché 4 sono i bit che servono per rappresentare una cifra in base 16).

È la rappresentazione utilizzata per gli indirizzi di memoria.

Es

Algoritmo di conversione della base di rappresentazione delle parti frazionarie

• Algoritmo che impiega la base di arrivo.

Es.

• Algoritmo che impiega la base di partenza.
• (Algoritmo delle moltiplicazioni successive).

La sua definizione è:

Per cui

Quindi a₁ rappresenta la parte intera di 2A e a₁ = 1 <-> 2A≥1.

Es

[0.7]₁₀ = [0.10110]₂ Si dimostra che

0.7*2 = 1.4 -> 1.4 - 1 = 0.4 (1 è, in questo caso, la parte intera da sottrarre)

0.4*2 = 0.8 -> 0.8 - 0 = 0.8

0.8*2 = 1.6 -> 1.6 - 1 = 0.6

0.6*2 = 1.2 -> 1.2 - 1 = 0.2

0.2*2 = 0.4 -> 0.4 - 0 = 0.4

0.4*2 = 0.8 -> 0.8 - 0 = 0.8 raggiunto l'inizio della ricorsione, l'algoritmo si arresta.

[2.1] Rappresentazione binaria

Giovedì 25 settembre 2014 11:24

Interi senza segno (unsigned int)

Codifica posizionale in base 2 su N bit, dove N dipende dall'architettura del processore.

Il suo sviluppo polinomiale è: N-1

Si possono rappresentare quindi gli interi compresi nell'intervallo [0,2^N-1].

Caratteri (char)

Si rappresentano caratteri alfanumerici con gli interi senza segno su 8 bit, mediante conversione con il codice ASCII.

Lo 0 rappresenta il carattere di fine riga, mentre il suo equivalente in caratteri è rappresentato dal numero intero 48.

Interi con segno (int)

Sono rappresentati in complemento a due su N bit.

Lo sviluppo polinomiale di un int è:

La cifra più significativa ha quindi peso negativo, mentre tutte le altre hanno peso positivo.

Il massimo numero intero rappresentabile sarà:

Il minimo numero intero rappresentabile sarà: N-1 N-1

Con il tipo int sono pertanto rappresentabili tutti i valori interi nell'intervallo [-2^N-1, 2^N-1-1].

Calcolo dell'opposto di un numero intero

1. Rappresentazione del numero in complemento a uno
2. Sommare 1

Questa tecnica vale per tutti i numeri escluso il minimo numero, per il quale non è possibile calcolare il complementare, rappresentato in complemento a due, su N bit.

Overflow

Si verifica quando il risultato di un'operazione eccede l'intervallo di numeri rappresentabili.

• Nel caso di somma tra interi senza segno si ha overflow se ho riporto di una cifra più significativa.
• Nel caso di somma tra interi con segno si ha overflow solo se sommiamo due valori dello stesso segno e il risultato della somma ha segno opposto.

Es fai un esempio

Valori razionali (floating point)

Rappresentazione in forma esponenziale:

Dove:

• S è il segno.
• M è la mantissa: valore razionale non negativo.
• B è la base di rappresentazione.
• C è la caratteristica: indica l'intervallo esponenziale nel quale è contenuto il valore.

Forma normale

Un numero si definisce forma normale se m appartiene a [1,B].

Float: 32 bit

• Segno (s) = 1 bit: si codifica come (-1)^s. Pertanto un numero è negativo se è solo se s=1.
• Caratteristica (c) = 8 bit [-127,128] si rappresenta senza segno come c+127 [0,255].
• Mantissa (m) = 23 bit.

Lo sviluppo polinomiale della mantissa è: (8)

I 23 bit della mantissa sono usati per rappresentare le da m1 a m23.

Errore

L'errore che si commette utilizzando m=23 bit:

• Errore relativo < 2^23.
• Errore assoluto = |x -valore relativo | x * 2^-23 = m*c*2^-23 < 2*2^c * 2^-23.
• Se c = -1 -> e. Assoluto ~= e. Relativo x appartiene a [1/2, 1].

Caso di conversione da razionale a Float

Es(9)

[3] Rappresentazione delle istruzioni

Domenica 28 settembre 2014 01:28

Generale

Un programma è usualmente scritto usando un linguaggio di alto livello.

Per essere eseguita, la codifica di alto livello deve però essere tradotta in una sequenza di istruzioni di basso livello che possano essere tradotte in forma numerica, caricate nella memoria di un elaboratore ed eseguite da un processore.

Un semplice schema gerarchico del ciclo descritto sopra può essere rappresentato come segue:

1. Codice sorgente (file di testo .c):

• È un linguaggio simbolico, formato da variabili e operatori denotati per mezzo di simboli.
• Linguaggio ad alto livello: ogni istruzione in linguaggio C corrisponde a più istruzioni eseguite sul processore.

2. Codice assembler (ottenuto per mezzo del compilatore):

• Linguaggio simbolico.
• Linguaggio di basso livello: ogni istruzione scritta in assembler corrisponde a un'istruzione eseguita sul processore.
• Il linguaggio assembler viene tradotto dall'assemblatore (traduzione 1 a 1) e trasformato in linguaggio macchina.

3. Codice macchina:

• Linguaggio numerico: le variabili sono rappresentate attraverso il loro indirizzo in memoria.
• Linguaggio di basso livello.

Quindi:

• Il compilatore traduce il codice ad alto livello in codice assembler.
• L'assemblatore traduce il codice assembler in codice macchina.
• Il linker si occupa di collegare le varie parti di codice (funzioni, librerie).

Nota:

Ciascuno microcontrollore ha un proprio linguaggio assembler e un proprio linguaggio macchina.

[4] Assembler (per MIPS R400)

Venerdì 19 dicembre 2014 19:05

Il MIPS R4000 è un processore di tipo RISC (Reduced Instruction Set Computer) cioè privilegia un minor numero di istruzioni con tempi di esecuzione simili.

Le operazioni aritmetiche non sono eseguite su variabili in memoria, ma su registri contenuti all'interno della CPU, così da avere tempi di accesso ridotti.

L'architettura del MIPS R4000 prevede:

• Banco dei registri: contiene 32 registri da 32 bit ciascuno utilizzati per le operazioni aritmetiche sui valori. I registri sono denotati con la dicitura $n, quindi vanno da $0 fino a $31; il registro $0 è inizializzato con il valore 0. Il banco dei registri prevede la simultanea lettura di due registri e la scrittura su un terzo.
• Memoria: contiene locazioni contigue da 8 bit ciascuna che possono essere lette e scritte nel corso della computazione.
• Program Counter: è un registro di 32 bit destinato a contenere l'indirizzo dell'istruzione corrente, si aggiorna ad ogni ciclo di clock.
• ALU: (Arithmetic Logic Unit) esegue operazioni aritmetiche e logiche.
• Sommatore: esegue le sole addizioni tra due ingressi.
• Multiplexor: selettore di canale, riceve due ingressi e ne seleziona uno.
• Modulo di espansione da 16 a 32 bit: rende compatibili i dati per essere trattati dalla CPU.
• Control Unit: rete combinatoria che riceve in ingresso un codice di 6 bit che codifica il campo operativo dell'istruzione in esecuzione e genera una serie di segnali atti a controllare il funzionamento della CPU.
• Decoder: associato alla ALU genera il codice che pilota la specifica operazione.

[5] Definizione di linguaggio

Venerdì 19 dicembre 2014 19:06

Generale

Definizione di un linguaggio

• Sintassi: determina quali sono le espressioni legali del linguaggio.

Vocabolario V (insieme dei simboli)

V = var {+, -, *, /, (, ), ;}∪

Universo linguistico: V* è l'insieme di tutte le sequenze finite di simboli V. ∈

Se ad esempio V contiene i simboli p e c, allora V* contiene tutte le parole composte con le due lettere, di qualsiasi lunghezza, inclusa la parola nulla.

V = {p,c} -> V* = { _, p,c,pp,pc,cp,cc,ppp,ppc ...}

Linguaggio: L è definito su un vocabolario V ed è un sottoinsieme di V*.

Definire la sintassi di un linguaggio significa definire quali sono i limiti del sottoinsieme di V* che costituisce il linguaggio.

• Semantica: determina il significato delle espressioni legali del linguaggio.

Grammatica G = <V, N, S, P>

Dove V: vocabolario (gli elementi di V sono detti simboli terminali).

• N: insieme delle categorie sintattiche {expr, op, var}.
• S: simbolo iniziale. S∈N è la categoria sintattica di cui il linguaggio definisce le espressioni legali.
• ∈P⊆N x (N ∪ V)* insieme delle produzioni -> P è un insieme di coppie (m, n), con m ∈ N (categoria sintattica), n ∈ (N ∪ V)* sequenza finita di simboli di N o V.

P = {expr -> var, qualunque variabile = espressione legale(expr): espressione legale expr op expr: due expr combinate sono ancora un'espressione legale op -> +, op -> -, op ->*, op -> / }

Valutare la legalità di un'espressione

Un'espressione è legale quando è semplificabile in un'espressione expr.

Esempi: var + var * (var - var)

Applicando ripetutamente la produzione expr -> var possiamo scrivere:

var + var * (var -var) <- expr + expr * (expr - expr)

Applicando le produzioni op -> +, op -> -, op ->* possiamo scrivere:

expr + expr * (expr - expr) <- expr op expr op(expr op expr)

Applicando due volte expr -> expr op expr e poi expr -> (expr)

expr op expr op(expr op expr) <- expr op expr

Infine, applicando una ultima volta expr -> expr op expr e concatenando le riduzioni, otteniamo: a + b * (c - d) <- expr quindi è legale

Albero sintattico

Il processo con il quale una sequenza di simboli nel vocabolario V viene ridotta al simbolo iniziale S della grammatica di un linguaggio è convenientemente rappresentato attraverso un albero sintattico.

Un albero è un insieme di nodi sui quali è definita una relazione di successione nella quale ciascun nodo ha un unico predecessore e un numero non limitato di successori.

Un nodo speciale, detto radice, non ha alcun predecessore.

Nel caso dell’albero sintattico, i nodi rappresentano simboli elementari e produzioni e gli archi rappresentano relazioni di derivazione diretta tra i nodi in bas