Appunti di Informatica

Appunti di informatica

Introduzione

L’informatica si occupa del processamento automatico dell’informazione. Il calcolatore elettronico funziona utilizzando la logica binaria, quindi è in grado di processare l’informazione in un alfabeto fatto solo di 1 e 0.

Codifica

La rappresentazione dei numeri in base decimale è un sistema di tipo posizionale, ovvero le cifre di un numero rappresentano il peso che viene moltiplicato per una potenza del 10 a seconda della loro posizione. Ad esempio, 45 = 4*10¹ + 5*10⁰.

Esistono poi altri tipi di codifiche tra cui:

• La codifica esadecimale: è un sistema posizionale in base 16, ossia rappresenta i numeri su di un alfabeto dato da: 0123456789ABCDEF.
• La codifica binaria: che è quella usata dal computer, è anch’essa un sistema posizionale in base 2, fatto da 0 e 1. Anche il sistema binario è di tipo posizionale, infatti, le cifre hanno peso pari a potenze del due crescenti: 3 2 1 0. Ad esempio, 1011₂ = 1*2³ + 0*2² + 1*2¹ + 1*2⁰.

Conversione numerica

Come convertire un numero dal sistema decimale a quello binario:

• Quanti bit servono per rappresentare un numero decimale? Basta effettuare la seguente operazione: log₂ N (dove N è il numero decimale).
• Quanti numeri si riescono a rappresentare con m bit? Basta fare 2^m e trovo i numeri che posso rappresentare. Ovviamente più bit uso (8, 16, 32, 64, 128) e più cresce esponenzialmente il range di numeri che è possibile rappresentare.

Codifica per Z

Per i numeri interi bisogna pure considerare il segno, per questo motivo posso applicare due tipi diversi di codifica:

• Modulo e segno: Basta aggiungere un bit a sinistra per rappresentare il segno (0 se è positivo, 1 se è negativo). Se ad esempio voglio rappresentare un numero a 8 bit farò i seguenti passaggi: codificare il numero normalmente, aggiungere zeri fino ad avere 7 cifre, mettere l’ultimo bit a destra in base al segno del mio numero.
• Complemento a 2: In questo modo posso rappresentare un numero in più rispetto a quella precedente, motivo per cui si possono costruire circuiti sommatori molto veloci. Come rappresentare un numero in complemento a 2: codificare il numero normalmente, aggiungere zeri a sinistra fino al bit m-1. Se poi il numero è negativo si invertono i bit e si somma in colonna 1.

Codifica per Q

In questo caso ci saranno da considerare anche i numeri dopo la virgola, ci sono anche qui due tipi di codifica:

• Codifica a virgola fissa: Si stabilisce per convenzione che degli m bit che codificano un numero, gli ultimi f sono dopo la virgola. Il numero prima della virgola è la parte intera, quello dopo la virgola viene diviso per 2^f.
• Codifica a virgola mobile: Prendo il numero e lo esprimo in notazione esponenziale con base 2, codifico la mantissa come frazione, codifico l’esponente in binario, codifico anche il segno di mantissa ed esponente.

Ad esempio: n = 13.25 = 1.325 x 10¹⁰, codifico 13.25 con la codifica in virgola fissa = 1101.01 = 1.10101 x 2². Ora codifico l’esponente: si somma l’esponente a 127 = 127+3=130. Metto 1 se il segno è negativo e 0 se il segno è positivo. Si avrà: 0 1000001 10101000000000000000000 (segno (1) esponente(8) mantissa(23)).

Codifica delle stringhe

Per la codifica delle stringhe si usa la tabella di riferimento ASCII dove sostanzialmente ogni lettera è un numero fatto da 7 bit.

Algoritmi

È la modalità con cui descriviamo la soluzione ad un problema, esso può essere definito da una sequenza di operazioni elementari tali che:

• Siano comprensibili ad uno specifico esecutore;
• Possano essere eseguite senza ambiguità;
• Permettano di risolvere uno specifico problema.

In informatica la soluzione ad un problema è un dato prodotto in uscita a partire da dati presenti in ingresso. Un algoritmo è caratterizzato quindi da:

• Una descrizione dei passi da effettuare;
• Una descrizione dei dati in ingresso e di quelli prodotti in uscita;
• Un esecutore che esegue i passi specificati.

Firma di un algoritmo

Descrive i dati che l’algoritmo riceve in ingresso e quelli che emette in uscita. Il dato in ingresso prende il nome di parametro mentre quello in uscita si chiama valore di ritorno.

Flowchart

Servono per risolvere un algoritmo semplice. Simbologia:

• Inizio e fine = ovali;
• Passaggi intermedi = rettangoli;
• Domande = rombi;
• Dati di input e output = parallelogrammi.

Il calcolatore

Un calcolatore è programmabile, quello che può fare è limitato dalla quantità di memoria, dalle periferiche a disposizione, dalla velocità di calcolo. In un calcolatore la memoria non contiene solo dati di un problema, ma anche le istruzioni per risolverlo.

Il modello astratto di riferimento è chiamato macchina di Von Neumann. Essa è composta da:

• La CPU che è adibita a eseguire i comandi;
• La memoria centrale che la CPU utilizza per accedere a dati e programmi;
• Le periferiche che la CPU utilizza per comunicare con il mondo esterno;
• Il bus, un’astrazione delle interconnessioni tra la CPU e memoria e periferiche.

La memoria centrale

Essa è composta da un insieme ordinato di celle ognuna delle quali è in grado di contenere una parola di memoria, un numero binario di m bit. Ogni cella di memoria ha associato un indirizzo che la identifica univocamente e che viene usato dalla CPU per selezionare a quale cella accedere. Le celle non hanno nessun altro attributo oltre all’indirizzo, infatti, la memoria non conosce l’operazione che si racchiude dentro la cella.

La memoria è connessa al bus tramite il quale la CPU può accedere alla memoria stessa. La CPU può accedere ad una sola cella per volta e può:

• Scrivere: spazza via il contenuto precedente della cella e lo sostituisce con uno nuovo;
• Leggere: legge il contenuto attualmente conservato nella cella.

Per evitare confusione i programmi di norma dividono la memoria in due zone: una zona formata da celle che contengono istruzioni e una zona da celle che contengono dati.

CPU

La CPU è l’esecutore di algoritmi della macchina di Von Neumann, essa è in grado di comprendere un insieme finito di istruzioni dette instruction set. Essa agisce come segue:

• Preleva un’istruzione dalla memoria;
• Decodifica l’istruzione per comprendere di quale si tratta, tra l'instruction set;
• Esegue l’istruzione;
• Torna allo step 1.

Componenti della CPU

La CPU è composta da:

• Unità di controllo: gestisce il ciclo di esecuzione delle istruzioni;
• Unità aritmetico-logica: effettua le operazioni matematiche;
• Registri: elementi di memoria all’interno della CPU;
• Clock: scandisce il tempo delle operazioni.

I registri della CPU hanno una funzione particolare:

• Contatore di programma (PC): contiene l’indirizzo di memoria dell’istruzione da eseguire;
• Registro istruzione corrente (CIR): contiene l’istruzione da eseguire;
• Registro di stato (SR): contiene informazioni sull’ultima operazione aritmetico-logica;
• Registro indirizzi (AR): connesso alla memoria tramite il bus, consente alla CPU di chiedere quale cella di memoria leggere o scrivere;
• Registro dati (DR): connesso alla memoria tramite il bus, contiene la memoria da scrivere in memoria o quella appena letta da essa.

Per prelevare un’istruzione dalla memoria, la CPU opera nel seguente modo:

• Mette il contenuto del registro PC nel registro AR;
• Effettua la lettura della memoria;
• Mette il contenuto del registro DR nel registro CIR;
• La decodifica dell’istruzione viene fatta dall’unità di controllo analizzando il contenuto del registro CIR.

Esecuzione delle istruzioni

L’esecuzione dell’istruzione non è però ancora terminata, occorre aggiornare il contenuto del registro PC in modo da puntare alla prossima istruzione da eseguire. Nella maggior parte delle istruzioni il PC viene semplicemente incrementato, in modo da passare all’istruzione all’indirizzo immediatamente successivo. In questi casi si dice che l’esecuzione del programma continua in modo sequenziale. Ci sono poi delle istruzioni chiamate istruzioni di salto (tipo la break o continue in C).

Somma di numeri interi

• Somma di numeri interi senza segno:
• Somma di numeri interi senza segno senza overflow:
• Somma di numeri interi senza segno con overflow: quindi il riporto perduto indica un overflow, per cui il numero troncato ad 8 bit non è corretto.
• Somma di numeri interi con segno: in complemento a due cambia la gestione dell’overflow. Nella somma a complemento a due il riporto perduto non indica un overflow, il risultato troncato a 8 bit è già corretto.
• Ora con overflow: in questo caso il risultato non è corretto in quanto negativo; quindi, in complemento a due si ha overflow quando due numeri hanno stesso segno e il risultato ha segno opposto. In questo caso per trovare il risultato corretto basta fare il complemento a 2 del valore trovato.

Sottrazione di interi con segno

Basta invertire il segno del secondo operando. Se devo estendere i bit di un numero, basta aggiungere zeri a sinistra se è positivo e 1 se è negativo in complemento a due. Se non sono in complemento a due si fa sempre aggiungendo solo zeri.

Linguaggi di programmazione

La lingua madre del calcolatore, l’unico linguaggio che è in grado di comprendere direttamente, è il linguaggio macchina. Il problema del linguaggio macchina è che è estremamente difficile per un essere umano da imparare, e anche una volta imparato è molto facile commettere errori nella scrittura di programmi. Sono quindi stati inventati altri linguaggi con un crescente livello di astrazione.

Livelli di astrazione dei linguaggi

Salendo di un gradino di astrazione troviamo il linguaggio assembly, in cui le operazioni supportate dalla CPU vengono espresse con delle stringhe testuali. Le istruzioni disponibili nel linguaggio assembly sono tutte e sole quelle supportate dalla CPU. I programmi in assembly non possono però essere eseguiti direttamente. Occorre prima far girare un altro programma, detto assemblatore, che traduca le stringhe nel linguaggio macchina. Il problema del linguaggio assembly è che non è portabile, un programma scritto per una certa CPU non può funzionare su una CPU che abbia un insieme di istruzioni differenti.

Salendo ancora come astrazione troviamo i linguaggi ad alto livello, le cui istruzioni non si mappano 1 a 1 con l’insieme di istruzioni della macchina. Una singola istruzione ad alto livello potrebbe tradursi anche in decine o centinaia di istruzioni macchina: un intero sottoprogramma. Tali linguaggi sono stati progettati sulla base di un certo numero di paradigmi:

• Compilati o interpretati;
• Fortemente tipizzati o non fortemente tipizzati;
• Imperativi o descrittivi.

Linguaggi compilati VS linguaggi interpretati

Un linguaggio compilato richiede un programma, detto compilatore, per tradurre le istruzioni del linguaggio ad alto livello nel corrispondente linguaggio macchina. Si ha un file di nome programma.c. Il compilatore prende in input questo file, traduce ogni istruzione in una o più istruzioni macchina, e scrive queste istruzioni in un file programma.exe. Quando l’utente fa doppio click su programma.exe, il sistema operativo lo carica in memoria e la CPU esegue le istruzioni macchina chiedendo all’utente il numero, ecc. ecc.

Un linguaggio interpretato richiede un programma, detto interprete, che legga le istruzioni del linguaggio ad alto livello e le esegua. Si ha un file di nome programma.m. L’interprete prende in input questo file, e inizia a eseguire direttamente le istruzioni in essa contenute. Quindi, l’interprete si fermerà alla prima istruzione aspettando che l’utente inserisca il numero, poi sommerà 2, ecc. ecc. Non verrà prodotto nessun file con del codice macchina.

• Un programma in un linguaggio compilato non richiede all’utente finale di installare nessun interprete, ma può girare solo su CPU con lo stesso insieme di istruzioni per cui è stato compilato; gira alla velocità “nativa” del calcolatore perché la CPU esegue direttamente codice macchina;
• Un programma in un linguaggio interpretato può girare su ogni CPU indipendentemente dal suo insieme di istruzioni compilato, ma richiede che qualcuno abbia scritto un interprete per quella CPU e che l’utente lo abbia installato; gira più lentamente di un programma nativo perché l’interprete impiega tempo per comprendere ogni istruzione prima di poterla eseguire.

Tipizzazione dei linguaggi

I linguaggi ad alto livello introducono il concetto di tipo, cioè ad ogni variabile (che rappresenta un’astrazione delle celle di memoria) viene associato un tipo. Certi linguaggi come il C sono fortemente tipizzati e richiedono sempre di specificare il tipo delle variabili che non può cambiare nel corso del programma. Altri linguaggi come, ad esempio, Matlab sono fortemente tipizzati, non serve dichiarare i tipi e il tipo di una variabile può cambiare nel corso del programma.

Linguaggi imperativi o descrittivi

Entrambi i linguaggi che vedremo in questo corso sono imperativi, nel senso che scriveremo i nostri algoritmi nella forma di comandi che il calcolatore eseguirà per noi. Esistono poi dei linguaggi descrittivi in cui si descrive la soluzione desiderata e si lascia al calcolatore il compito di capire come ottenerla.

Linguaggio C

Il C è un linguaggio compilato, per produrre un file eseguibile da un programma C occorre seguire un determinato flusso di compilazione. Il primo step consiste nell’eseguire il compilatore, un programma che traduce il file C in ingresso in un file contenente codice macchina. Questo file non è ancora eseguibile direttamente, perché i programmi C possono fare uso di sotto algoritmi contenuti in delle librerie di algoritmi. Il secondo step consiste nel collegamento o linking, esso si effettua tramite un secondo programma che combina il codice macchina del vostro programma con i sotto algoritmi richiesti, producendo a questo punto un file eseguibile.

In C gli algoritmi si scrivono all’interno di un costrutto detto funzione. "main" è una funzione, ed è l’algoritmo che stiamo scrivendo. Tutti i programmi in C devono avere un main, esso è l’algoritmo che viene lanciato quando eseguiamo il programma. "int main()" è la firma dell’algoritmo, mentre i passi dell’algoritmo si scrivono tra parentesi graffe, separati da un punto e virgola.

Per poter usare algoritmi di libreria dobbiamo però includere la libreria corrispondente. #include <stdio.h> include la libreria di input/output standard che comprende printf. Tutte le #include vanno messe in cima al file. Return non è una funzione ma una parola chiave del linguaggio C. Le keyword sono parole che hanno un significato particolare nella sintassi del linguaggio. Return segna la terminazione dell’algoritmo. NON bisogna chiamare funzioni o variabili con lo stesso nome delle keyword.

Commenti in C

• /*___________*/ = Quando devo fare un commento su più righe.
• //_________ = Se devo fare un commento che non va a capo.

Variabili in C

In C sono un’astrazione delle celle di memoria; una variabile in C ha nome, tipo e valore, e di questi solo il valore può variare durante l’esecuzione di un programma. Tutte le variabili vanno dichiarate prima di poterle utilizzare mettendo il tipo seguito dal nome. Ad esempio: int ciao;

La definizione di una variabile invece assegna anche un valore, e si effettua con il carattere uguale (=). Se io dichiaro una variabile ma non la definisco allora la mia variabile si chiama “variabile non inizializzata”. Il tipo di una variabile segnala le celle di memoria utilizzate e la codifica utilizzata; il compilatore verifica che tutti gli usi di una variabile siano coerenti con il tipo (sennò ti segnala errore).

Tipi base del C

• int = interi con segno (32 bit);
• unsigned int = interi senza segno (32 bit);
• float = numeri a virgola mobile (32 bit);
• double = numeri a virgola mobile (64 bit);
• char = caratteri (8 bit).

Se voglio più bit per gli interi si può usare long int o long long int. Per tutti i tipi, incluso char, sono predefinite anche un certo numero di operazioni:

• Operazioni aritmetiche: + - * /
• Resto della divisione intera: %
• Shorthand delle operazioni: i++ ad esempio
• Per i tipi a virgola mobile con math.h posso fare un sacco di altri calcoli.

Inoltre, posso anche fare delle operazioni di cast, ossia ad esempio trasformare un numero da float a int. Come trasformare un float in un int:

float a = 14.36; int b = (int)a; // prende solo 14.

La funzione printf

Essa è usata per stampare al terminale.

• Accetta un numero variabile di parametri;
• Il primo parametro è forzatamente una stringa;
• Gli altri parametri possono essere di vari tipi, ma devono essere specificati nella stringa usando delle stringhe di formattazione.

Ad esempio: elenco delle più comuni format strings:

• %d per stampare gli interi;
• %f per stampare i numeri float;
• %c per i char;
• %s per le stringhe di caratteri.

Per stampare con degli spazi prima: printf("%10d\n", bjbv); // 10 è solo un esempio, metti il numero che ti serve.