Appunti di Fondamenti di Informatica

Appunti di Fondamenti di Informatica

Dal corso del docente Antonio Picariello

Autore: Mario Falanga

Gli appunti sono stati presi durante tutto il corso e in più ci sono pagine con

ricapitolazioni di argomenti, mappe concettuali, schemi di vario tipo, esercizi svolti ecc.

(Evidenzio la presenza di un indice piuttosto sintetico a fine documento). Per qualsiasi dubbio

non esitare a contattarmi all’indirizzo mario.falanga1998@gmail.com

Rappresentazione e Codifica dell'Informazione

Def di Informazione: deriva da in-formare, ossia dare forma. Essa è qualcosa che viene comunicato e accresce la conoscenza del destinatario.

Il processo comunicativo è composto da:

• S→ messaggio Codifica → O → Decodifica → D
• Sorgente
• Mezzo di comunicazione o media
• Destinatario

Per la comprensione del messaggio la sorgente e il destinatario si accordano sulle regole da seguire per la scrittura e la lettura del messaggio stesso. Queste vengono dette regole di codifica.

Se E∈E è l'evento, P{E} è la probabilità che quell'evento accada. Se esso è certo, allora la probabilità è 1. Se incerto, esso sarà è minore di 1.

Il CONTENUTO INFORMATIVO di un messaggio è pari a 1-P{E}, quindi più il evento è incerto, più il contenuto informativo è alto.

In questo caso, il contenuto informativo è sintetizzo col conetto di scelta.

Insieme STUDENT

finto: possiede un numero limitato di elementi

discreto: possiede elementi distinti

CARDINALITÀ (m): numero massimo degli elementi di un insieme.

Q = tale informazione, m = 1 non da informazione, mentre m = 2 è "il minimo che può" avere la cardinalità di un insieme per generare informazione.

TIPO: insieme a cui appartiene un valore.

ATTRIBUTO: il SIGNIFICATO dell'informazione, ossia il METADATA.

VALORE: ciò che quantifica l'informazione.

L'informazione dipende dal valore ed un attributo di un tipo.

I = (T, A, V) _valore

Sistema binario puro posizionale

Il sistema di numerazione binario consente di rappresentare numeri mediante la combinazione di due soli simboli: zero e uno.

• 00000000 = 0
• 10000000 = 128
• 11111111 = 255
• 0 1 1 1 1 1 1 1 = 127

In un byte, il bit più a destra è quello meno significativo - posizione 0 o Least Significant Bit (LSB). Mentre quello più a sinistra è quello più significativo - posizione 0 o Most Significant Bit (MSB).

Peso: 6 5 3 2 1 0

Sistemi di numerazione posizionali e non posizionali:

• Un sistema di numerazione può essere visto come un insieme di simboli (cifre) e regole che assegnano ad ogni sequenza di cifre uno ed un solo valore numerico.
• Nei sistemi posizionali ogni cifra della sequenza ha un'importanza variabile e ricavabile della relativa posizione.
• Nei sistemi non posizionali, ogni cifra esprime una quantità indipendentemente della posizione.

num = ∑ (i=0 to l-1) ci * bi

somma dei prodotti delle cifre per i pesi dove peso = base elevata a posizione

N = c0 * b0 + c1 * b1 + ... + cl * b1-1

Un sistema di numerazione posizionale è quindi definito dalla base (o radice) utilizzata per la rappresentazione. Inoltre, in un sistema in base b, servono b simboli. Per rappresentare i diversi valori delle cifre compresi fra 0 e (b-1).

1. Base 10: Decimale Valori delle cifre: 0 1 2 3 4 5 6 7 8 9
2. Base 2: Binario Valori delle cifre: 0 1
3. Base 8: Ottale Valori delle cifre: 0 1 2 3 4 5 6 7
4. Base 16: Esadecimale Valori delle cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F

Nel passaggio da una base all'altra alcune proprietà dei numeri si perdono. Ad esempio nel base 10: 10111011 = 1*2⁰ + 0*2¹ + 1*2² + 1*2³ + 1*2⁴ + 0*2⁵ + 1*2⁶ + 1*2⁷

Configurazioni particolari:

• Esponente e mantissa tutti 0: rappresentano 0
• Mantissa tutti 0 ed esponente tutti 1: rappresentano infinito
• Mantissa diversa da 0 e esponente tutti 1: valore indefinito - Not a Number (NAN)

Esercizio: codificare in modello standard 754 IEEE a precisione singola

- 120,125 ⇒ 1 10000011 11100100000000000000000

norm.: 120,125 ⇒ 0 1111000,001 ⇒ 1 11100100,001 : 2

6 + 127 = 133 ⇒ 10000101

+ 120,0

+ 10,50 ⇒ 0 100000101 010100...

norm.: 10,50 ⇒ 1 0101 : 2

3 + 127 = 130 10001010

Codifica il seguente standard 754 IEEE in binario

1 00000111 01001100...

⇒ -(1,15625×2^-5) = -0,296

135 - 127 = 8

Codifica in binario il seguente numero frazionario: 0,123

• 0,1 2 3 ×
• 0,2 4 6 0
• 0,4 9 2 0
• 0,8 1 4 3
• 1,5 6 9 6
• 3,1 2 8 1
• 6,2 5 6 2
• Una cifra indefinita perciò ad ogni passo il prodotto composto si numeri: 6-2-5-8 periodicamente.

5 8 1 0

0 3

Fondamenti di Informatica Lec. 9 (9/10/2017)

Introduzione all'Algebra di Boole

L'algebra di Boole fu introdotta nel 1854 come strumento per la definizione matematica di problemi di logica. Boole riuscì a formalizzare le leggi della logica.

Switching Theory = teoria dei circuiti.

Algebra ordinata

L'algebra è costituita da un insieme K detto sostegno dell'algebra.

Inoltre all'insieme definisco due operatori ordinati: "+", "·".

L'algebra di Boole è dotata della terna < K, +, · >. (struttura algebrica)

+ e · sono due operatori interni, cioè che ogni operazione compiuta donna un

risulto interno a K. Sono anche detti operatori binari.

L'algebra di Boole è un reticolo distributivo dotato di massimo, minimo e complemento.

Un'algebra ordinata è un reticolo se valgono le seguenti proprietà:

• commutativa: P0: a + b = b + a    P'0: a · b = b · a
• associativa: P1: (a + b) + c = a + (b + c)    P'1: (a · b) · c = a · (b · c)
• idemprotenza o elemento identità: P2: a + a = a    P'2: a · a = a
• assorbimento: P3: a + (a · b) = a (assorbita)   P'3: a · (a + b) = a

Proprietà dei reticoli

• I reticoli sono ordinati, ovvero possiedono una relazione d'ordine "≤" con elemento:

x ≤ y ↔ x + y = y    (x · y = x)

• riflessiva: x ≤ x
• antisimmetrica: x ≤ y & y ≤ x → x = y
• transitiva: x ≤ y & y ≤ z → x ≤ z

Fondamenti di Informatica - Lez. 11 (13/10/2017)

La memoria di lavoro è formata da registri: le contengono istruzioni e dati utili al processo. Prima di scrivere un programma, occorre specificare che tipo di dati la memoria dovrà contenere, quindi quanto spazio dovrà riservare nei registri.

I dati elaborati dal programma sono definiti come variabili:

• int = intero
• char = carattere
• float = reale a virgola mobile a precisione singola
• double = precisione doppia
• bool = boolean

Quindi ad ogni registro associa una variabile, dichiarandone il tipo.

Ogni tipo è caratterizzato da delle operazioni:

Es. per il tipo int

+, -, *, /, %

• divisione intera
• resto della divisione

assegnazione

a = ( * )

variabile / espressione

Fondamenti di Informatica - Lez. 12 (16/10/17)

Memorie

La memoria può essere vista come un insieme di registri numerati, bien definiti che contengono dati ed istruzioni. Ogni registro possiede un indirizzo che lo differenzia ed è composto da un blocco di flip-flop di dimensioni pari a un numero di bit.

Memorie con registri di otto bit sono dette a byte, o a carattere.

Con più di otto vengono dette memorie a word.

Flip-flop: dispositivo elettronico composto da un sistema R-S (set-reset).

Evento elettronico su flip-flop è una memoria volatile, poiché, spegnendo il sistema perde i dati.