INFORMATICA

MATTEO CRISTANI

INDICE CICLO DELLE LEZIONI

LEZ. 1INTRODUZIONE AL CORSO

LEZ. 2I CALCOLATORI ELETTRONICI

LEZ. 3ELEMENTI DI TEORIA DELL’INFORMAZIONE

LEZ. 4MISURE DELLA INFORMAZIONE

LEZ. 5CALCOLO BINARIO: CONVERSIONI DI BASE

LEZ. 6CALCOLO BINARIO: OPERAZIONI IN BASE 2

LEZ. 7ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 8ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 9PORTE LOGICHE

LEZ. 10PROGETTO DI CIRCUITI DIGITALI

LEZ. 11INTRODUZIONE AGLI ALGORITMI

LEZ. 12PRODUTTIVITA’ INDIVIDUALE

LEZ. 13IL WEB

LEZ. 14RICERCA DI DOCUMENTI

LEZ. 15USO DEI MOTORI DI RICERCA

LEZ. 16SICUREZZA INFORMATICA

LEZ. 17ELEMENTI DI CRITTOGRAFIA

LEZ. 18ESERCITAZIONE DI CRITTOGRAFIA

LEZ. 19ESERCITAZIONE GENERALE

LEZ. 20SOMMARIO DEL CORSO

AGENDA RAPPRESENTAZIONE POSIZIONALE RAPPRESENTAZIONE NUMERICA BASE IN BASE

2 CONVERTIRE NUMERI TRA LE BASI METODI SPECIALI DI CONVERSIONE

RAPPRESENTAZIONE POSIZIONALE La rappresentazione dei numeri in forma

posizionale è basata su tre principi1. La rappresentazione delle 0;2. La scelta di un insieme K di simboli che

valgono come i numeri da 0 alla numerosità di K meno 1;

3. Il meccanismo di pesatura del valore di un simbolo.

LA FORMA POLINOMIALE Ogni simbolo dell’insieme K ha un peso che

è funzione della sua posizione all’interno della rappresentazione.

Esempio: Posso rappresentare il numero

duemilatrecentoventisette come: 2327 = 2*103 +3*102 +2*101 +7*100 Il simbolo “2” ha un peso diverso a seconda

della sua posizione.

BASI NUMERICHE La scelta delle basi numeriche per la

rappresentazione posizionale hanno effetti misurabili Sulla lunghezza dei numeri; Sulla complessità del calcolo.

TABELLINE Dato un sistema posizionale in base n le

tabelline di quel sistema sono, teoricamente, al massimo n

Tuttavia… 0 ed 1 non hanno tabelline, ovviamente. La tabellina del 2 è sempre elementare, dato

che rileva i soli numeri pari. Inoltre, la tabellina di (n-1), qualsiasi sia la

base è banale

ESEMPIO ESEMPIO

La tabellina del 6 in base 7 è la seguente

2 6 153 6 244 6 335 6 426 6 51

ANALISI In una base la complessità del calcolo è

determinata dal numero delle tabelline di moltiplicazione che occorre mandare a memoria per effettuare le operazioni;

La lunghezza dei numeri invece, dipende dall’ampiezza della base;

Il numero di operazioni di moltiplicazione da effettuare, quindi, è determinato dalla lunghezza dei numeri.

ESEMPI BASE 10

Tabelline 3, 4, 5, 6, 7, 8 Numeri di lunghezza 2 rappresentazione fino a

100; Operazioni su numeri

di lunghezza 2 complessità notevole BASE 5

Tabelline 3 Numeri di lunghezza 2 rappresentazione fino a

25; Operazioni su numeri

di lunghezza 2 complessità molto modesta

LA BASE 2 Lunghezza: massima Complessità del calcolo: minima

CONVERSIONI DI BASE DALLA BASE 2 ALLA BASE 10 DALLA BASE 10 ALLA BASE 2

CONVERSIONE DALLA BASE 2 Un numero in base 2 è una sequenza di 0 e di 1 Il significato della cifra 0 è ovviamente lo stesso in

qualsiasi posizione Il significato della cifra 1 invece è 2n dove n è la

posizione della cifra 1da destra, diminuita di 1

110101002 0 20 + 0 21 + 1 22 + 0 23 + 1 24 + 0 25 + 1 26 + 1 27 =21210

CONVERSIONE DALLA BASE 10 Dato un numero in base 10, l’ultima cifra della

sua rappresentazione in base 2 può essere determinata dal seguente ragionamento: Se il numero è pari, l’ultima cifra sarà senz’altro 0,

e viceversa se il numero è dispari 1. Altrimenti, nel calcolo della conversione dalla base 2 alla base 10 la presenza di una cifra 1 alla fine avrebbe generato un numero dispari (e viceversa)

Lo stesso ragionamento si applica alle ultime due cifre: 00 divisibile per quattro 10 divisibile per due ma non per quattro 01 dispari 11 bidispari (dispari e tale per cui il quoto

della divisione per due è dispari)

SCHEMA DI DIVISIONE

212 2 0 106 2 0 53 2 1 26 2 0 13 2 1 6 2 0 3 2 1 1 2 1 0

CONVERSIONI IN BASE 4, 8, 16 Da base 10 a base 2 Da base 10 a base 4 Da base 10 a base 8 Da base 10 a base 16

CONVERSIONI DA BASE 10 IN BASE 2

230 2 0 115 2

1 57 2 1 28 2 0 14 2 0 7 2 1 3 2 1 1 2 1 0

CONVERSIONI DA BASE 10 IN BASE 4

230 4 2 57 4

1 14 4 2 3 4 3 0

CONVERSIONI DA BASE 10 IN BASE 8

230 8 6 28 8 4 3 8 3 0

CONVERSIONI DA BASE 10 IN BASE 16

230 16 14 14 16

14 0

CONVERSIONI INDIRETTE ESEMPIO: DA BASE 3 A BASE 6

CONVERSIONE DEL NUMERO IN BASE 3 ALLA BASE 10

CONVERSIONE DA BASE 10 A BASE 6

CONVERSIONI INDIRETTE 211213 CONVERSIONE IN BASE 10

21121 = 1*30+2*31+1*32+1*33+2*34 = 1+6+9+27+162= 205

205 CONVERSIONE IN BASE 6

211213 =1456

205 6 1 34 6 4 5 6 5 0

CONVERSIONI DIRETTE Se due basi sono una potenza dell’altra, allora

la conversione può avvenire in modo diretto Da base X a base Y con Y potenza di X

Si opera un raggruppamento da destra a sinistra per gruppi lunghi quanto l’esponente dell’elevamento a potenza corrispondente

Si convertono gli elementi Da base Y a base X con Y potenza di X

Si trasformano le cifre in base Y in k-uple di cifre in base X con k pari all’esponente dell’elevamento a potenza

ESEMPI 1100101010111 dalla base 2 alla base 4,

8, 16

231222123 dalla base 4 alla base 16

12212 dalla base 3 alla base 9

5EF9 dalla base 16 alla base 2, 4, 8

77516 dalla base 9 alla base 3

CONVERSIONE 2-4

0 1 1 0 0 1 0 1 0 1 0 1 1 1V V V V V V V1 2 1 1 1 1 3

CONVERSIONE 2-8

0 0 1 1 0 0 1 0 1 0 1 0 1 1 1V V V V V1 4 5 2 7

CONVERSIONE 2-16

0001100101010111V V V V1 9 5 7