Appunti completi corso Fondamenti di Informatica

CARATTERE

Si considera carattere ogni simbolo che appartiene alla codifica ASCII. Ogni carattere è

associato ad un numero che li rappresenta, perciò è un insieme ordinato. Il carattere "1"

per esempio è assegnato al numero 49. La convenzione sta nella mappatura tra simboli e

interi ed è tanto importante che è gestita direttamente dal sistema operativo e non dai

singoli programmi. L'ASCII è la prima standardizzazione e contiene 128 caratteri (codifica

a 7 bit). È per questo che se riceviamo una mail con lettere strane, allora è perché quei

caratteri non sono presenti nello standard utilizzato. Gli occidentali usano l'ISO-8859 con 8

bit (256 caratteri) con tanti sottogruppi (Europa Occidentale, Europa Orientale ecc...).

Quello universale è invece lo standard UNICODE che contiene tutti i caratteri del mondo

con le due varianti UTF-8 e UTF-16. Ovviamente questi caratteri occupano più spazio, ma

sono importanti per applicazioni destinate a funzionare in più lingue.

INTERI

È il tipo più intuitivo, ma è anche molto vasto. Esistono vari modi per dichiarare un tipo

intero in base alla grandezza del numero che vogliamo rappresentare e alla memoria che

abbiamo a disposizione. Si può persino usare un char al posto di un intero in quanto

occupa solo 1 byte (e ne consegue che caratteri e interi in C++ sono affini, ed è una

caratteristica insolita)! Anche il SEGNO occupa 1 bit di spazio: utilizzandolo dimezzi i

numeri positivi che puoi usare, ma puoi usare anche quelli negativi (ed è ciò che succede

automaticamente). In 8 bit senza segno vai da 0 a 255 mentre con il segno vai da -128 a

+127. Per inizializzare un numero senza segno si antepone unsigned. Bisogna però

essere sicurissimi che la variabile non ottenga per qualche motivo un valore negativo,

altrimenti si va in OVERFLOW (si spiegherà meglio in un'altra lezione che cos'è, in sintesi

si ottiene un valore sbagliato).

FLOAT

Contiene i numeri razionali ed anche qui esistono più tipi float in base alla precisione

richiesta e alla memoria a disposizione.

Abbiamo detto che C++ fa delle conversioni automatiche e permette l’uso di tipi diversi

nella stessa espressione. Si parla allora di CAST IMPLICITO (quando effettuata in

automatico dal compilatore) e di CAST ESPLICITO (quando esplicitata dall’utente nel

codice). Tra i cast impliciti bisogna dire che:

• In un’espressione con float e intero, l’intero viene promosso a float ed il risultato

sarà un float;

• Una divisione tra numeri interi ritorna un numero intero;

• Nell’assegnamento, se rvalue ed lvalue hanno tipi diversi, l’rvalue deve per forza

adattarsi e c’è il rischio di una perdita di informazione (esempio int i = 3.14;

significa i = 3);

• Se un bool viene convertito a int, questo varrà o 0 o 1 (esempio bool b = 42; int i =

b; significa i = 1);

• Non bisogna mischiare tipi signed e unsigned, perché portano al rischio di un

valore negativo (e quindi all'overflow).

Il cast esplicito si può utilizzare per mezzo delle parentesi tonde: si inserisce tra parentesi

tonde il tipo e poi la variabile. Eventualmente, se vogliamo convertire più di una variabile,

possiamo inserirle tutte in parentesi tonde. Degli esempi: x = (double)n / m fa sì che una

divisione tra interi ritorni un float, mentre float x=3, y=2; cout << (int)(x / y) ritorna un

intero da una divisione tra float. Ricordati assolutamente che il cast esplicito cambia il

tipo DELL'ESPRESSIONE: se dici “della variabile” il prof ti spenna.

In una espressione bisogna sapere la precedenza degli operatori e che il tipo finale

dell’espressione dipende dai tipi delle variabili utilizzati e dai vari cast impliciti. Ricordati

che le variabili hanno un tipo noto a priori che NON CAMBIA MAI (siamo in C++). Gli

operatori possono essere:

• OPERATORI UNARI: se agiscono su un singolo operando (esempio - * & ...)

• OPERATORI BINARI: se agiscono su almeno due operandi (+ - * / % = == …)

Sulla precedenza degli operatori bisogna dire che quelli matematici seguono le regole

dell’aritmetica (il % ha la stessa precedenza di moltiplicazioni e divisioni) mentre quelli

logici hanno le priorità not > and > or. Questi operatori sono scritti rispettivamente come !

a, a && b, a || b. Nota quindi che ! ha l'associatività da destra e non da sinistra (come di

fatto fa anche =).

Sappiamo che tutti gli operandi delle espressioni logiche vengono valutati da sinistra a

destra, ma esiste una interessante REGOLA DEL CORTOCIRCUITO, per cui è inutile

valutare gli operandi successivi se con AND l'operando di sinistra è false o se con

OR l'operando di sinistra è true.

Esistono anche i tipi composti. Qui li elenchiamo e ne spieghiamo uno solo.

Successivamente li scopriremo tutti.

• const

• reference

• pointer

• array

• class

• struct (poco usate)

Le variabili const sono costanti, ovvero il valore di inizializzazione è quello e rimane tale

per tutta l’esecuzione del programma. Questo significa anche che è obbligatorio

inizializzare le variabili const. Un modo analogo per rendere una variabile costante è l’uso

di una MACRO e di una DIRETTIVA, cioè una parte di codice indirizzata al preprocessore

(non è considerato codice!). La direttiva è ciò che inizia con #: una variabile costante e

visibile per tutti si può creare con #define PIGRECO 3.14159. La direttiva non si considera

istruzione (non termina in punto e virgola e il preprocessore considera carattere per

carattere). Per convenzione le direttive si scrivono in maiuscolo e con l’underscore al

posto dello spazio. Altre direttive sono #include (già visto) e #undef (che annulla una

variabile rendendola non più definita).

Ricordati i quattro termini fondamentali:

• ISTRUZIONE: un'espressione che termina in punto e virgola

• ESPRESSIONE: un oggetto linguistico che interpretato ritorna un valore

• DICHIARAZIONE: fornire nome e tipo ad una variabile o funzione

• DEFINIZIONE: allocare memoria per una variabile

Sappiamo già che le istruzioni sono semplici o composte, ma si possono ulteriormente

classificare in:

• CONDIZIONALI: if, else, switch

• ITERATIVE: for, while, do-while

• DI SALTO: break, continue, goto, exit

I calcolatori si basano interamente sull'algebra di Boole, nella quale esistono solo i valori

True (1) e False (0). Gli operatori fondamentali sono AND, OR e NOT, dove AND viene

anche chiamato prodotto logico e OR somma logica. Questi operatori sono binari. NOT

è detto negazione ed è un operatore unario. Esistono operatori derivati chiamati XOR,

NAND, NOR e XNOR, ma in informatica non si usano (raramente XOR).

Tutto si può riassumere nelle tabelle di verità.

L'ordine di precedenza è NOT > AND > OR. Per questo motivo AND viene associato al * e

OR al +. n

Le soluzioni di un'espressione booleana di n variabili sono 2 .

Ogni operatore può essere indicato con diversi simboli a seconda del contesto:

ʌ

AND * ∩ & &&

OR + v U | ||

NOT ¯ ~ !

⊕

XOR ^

NAND ↑

NOR ↓

TAUTOLOGIA: un'espressione che è sempre vera, qualunque sia il valore delle sue

variabili, come A | !A (tertium non datur)

CONTRADDIZIONE: un'espressione che è sempre falsa, qualunque sia il valore delle sue

variabili, come A & !A (principio di non contraddizione)

EQUIVALENZA: si indica con <=> e si ha quando due espressioni con gli stessi input

danno gli stessi output.

LEGGI DI DE MORGAN

!(A & B) = !A | !B

!(A | B) = !A & !B

• Proprietà commutativa e associativa per AND, OR, XOR:

A & B = B & A - (A & B) & C = A & (B & C)

A | B = B | A - (A | B) | C = A | (B | C)

A ^ B = B ^ A - (A ^ B) ^ C = A ^ (B ^ C)

• Proprietà distributiva per AND, OR:

A & (B | C) = (A & B) | (A & C)

A | (B & C) = (A | B) & (A | C)

• Proprietà dell'assorbimento per AND, OR:

A & (A | B) = A

A | (A & B) = A

• Elemento neutro e zero di ogni operatore:

A & A = A A | A = A A ^ A = 0

A & !A = 0 A | !A = 1 A ^ !A = 1

A & 0 = 0 A | 0 = A A ^ 0 = A

Un esempio carino che mostra le proprietà degli operatori booleani (in particolare di XOR)

è l'algoritmo xorswap, cioè l'inversione del valore di due variabili attraverso l'operatore

XOR. Date due variabili x e y, i loro valori possono essere invertiti con queste istruzioni:

x = x ^ y

y = x ^ y

x = x ^ y

Ammettendo che A e B siano i valori contenuti nelle variabili, la dimostrazione

dell'algoritmo è la seguente:

x y

Situazione iniziale A B

Passo 1 x = x ^ y A ^ B B

Passo 2 y = x ^ y A ^ B (A ^ B) ^ B

A ^ (B ^ B)

A ^ 0

A

Passo 3 x = x ^ y (A ^ B) ^ A A

(A ^ A) ^ B

0 ^ B

B

Situazione finale B A

E fu così che le variabili si scambiarono il loro valore.

CODIFICA: relazione che porta un significato ad un simbolo.

INTERPRETAZIONE: prende un simbolo e lo porta ad un significato.

Per capirci il nostro linguaggio è una codifica, perché un concetto universale viene

codificato diversamente in ogni lingua. Si dice CODIFICA RIDONDANTE.

Sole > Sun, suno, sol, nap, sooraj...

Si parla di CODIFICA AMBIGUA quando invece più significati hanno lo stesso simbolo.

Libero, gratuito, aperto > Free

Come negli alfabeti, abbiamo bisogno di pochi simboli per codificare tanti concetti. Per

esempio nei numeri: le cifre sono dieci, ma possiamo codificare infiniti numeri. L'insieme

dei simboli si indica con la A maiuscola scritta tutta elegante come le lettere degli insiemi

numerici e si chiama alfabeto.

I nostri numeri hanno la notazione posizionale, cioè i simboli cambiano valore in base

alla posizione. La notazione romana non è posizionale perché si usa un simbolo nuovo

con l'aumentare dei numeri (I, V, X, L, C, D, M). Esiste una fighissima notazione

babilonese che usa 60 simboli :P

BIT (binary digit) è la singola cifra, l'unità più piccola di informazione che abbiamo. In un

n n

numero di n cifre possiamo codificare 2 numeri (in un numero decimale 10 ). Un BYTE è

una sequenza di 8 bit.

I metodi precisi per convertire bin > dec e dec > bin sono più facili di quanto si pensi.

0 1 2

Da bin a dec: prendi ogni cifra a partire da destra e la moltiplichi per 2 , per 2 , per 2 ... e

sommi tutti i risultati.

Da dec a bin: dividi il numero per 2 elencando il re