Riassunto esame Fondamenti di informatica, Prof. Bolchini Cristiana, libro consigliato Il linguaggio C, P. Deitel, H. Deitel

Fondamenti di informatica

Alfabeto = simboli utilizzabili

• Codice = sequenze di simboli o regole per definire le combinazioni ammissibili

• Dati = insieme degli elementi da rappresentare

•

Configurazioni = tutte di uguale dimensione

Dimensione= dipende dall'alfabeto dei simboli e dalla quantità di elementi da rappresentare

Alfabeto dei simboli: S= {…}

Cardinalità dei simboli: |S| (quanti simboli ho)

Elementi = n

Dimensione configurazioni = k �log �

= ||

Sistema binario = alfabeto {0,1} – cifra della codifica = binary digit = bit (cifre)

Byte = 8 bit

- 10 bit

Kilobyte = 2

- 20

Megabyte = 2 bit

- 30

Gigabyte = 2 bit

- 40

Terabyte = 2 bit

-

Elementi da considerare:

Elementi da rappresentare

• Codifica che semplifichi le operazioni

• Codifica che “conservi” le proprietà dell’insieme degli elementi da rappresentare

•

Rappresentiamo dei valori

Bisogna trovare un corrispondente per qualsiasi valore in base 10 nel sistema binario

Es.: 315 ≠ 135 notazione posizionale – valore ∑

Least significant digit = quella più a destra, cambia valore a ogni configurazione alternandosi

Most significant digit = quella più a sinistra

La cifra successiva cambia valore ogni due volte

La terza cifra cambia ogni quattro configurazioni

000

001

010

011

100

101

110

111

Definisco un codice che associa al valore numerico una configurazione

Se voglio rappresentare il 17, devo rappresentare tutti i valori tra 0 e 17 (18 elementi)

n = valore da rappresentare ⌈log

= ( + 1)⌉

2

Valore = ∑ 2

0

0 1 2 3

1010 = 0 ∗ 2 + 1 ∗ 2 + 0 ∗ 2 + 1 ∗ 2 = 10

Come faccio a rappresentare il 17 nel sistema binario?

• I numeri naturali si rappresentano in questo modo:

Ogni volta che la codifica binaria finisce con un 1 sto esprimendo un numero dispari, con lo 0 un numero pari

In base 10 si rappresentano i valori con la notazione modulo e segno, cosa che nel sistema binario non c’è

= convenzionalmente il primo bit indica il + con lo 0 o il – con l’1 e il resto delle cifre indica la configurazione

effettiva

= ?

-23 10MS 2MS

+0 +0 −7 1 0 0 −1

0 0 0 0 1

= =

= =

+1 +1 −6 1 0 1 0 −2

0 0 0 1

+2 +2 −5 1 0 1 1 −3

0 0 1 0

+3 +3 −4

0

−4

0 0 1 1 1 0

1 =

=

= =

+4 +4 −5

1 1 0 1

−3

0 1 0 0

+5 +5 −6

1 1 1 0

−2

0 1 0 1

+6 0 1 1 0 +6 −1 = −7

1 =

= = 1 1 1

+7 0 1 1 1 +7

−8 1 0 0 0 −0

Analisi dei segni delle configurazioni da sommare per vedere se sono concordi o no

• Somma dei valori assoluti nel caso i segni siano uguali e poi ripristinare il segno

- Sottrazione partendo da quello con valore assoluto maggiore e poi ripristino il segno

-

Per facilitare l’aritmetica (somme e sottrazioni) sistema della notazione in complemento alla base, che

→

permetta di avere agilità nell’elaborazione

=?

= −13

10 22

rappresento il modulo di x nel sistema binario come se fosse

→

|| = 13

2

L’overflow

Come mi accorgo che c’è un overflow? Quando sommando due valori concordi il risultato è discorde da loro

( sommo due positivi e ottengo un negativo)

Overflow si, perché operandi concordi e risultato da essi discorde

Se i primi bit degli operandi sono uguali, ma il primo bit del risultato è discorde da questi, allore c’è

- overflow

Se gli operandi sono discordi è impossibile avere overflow

-

Per trovare l’opposto di una codifica ci sono tre metodi:

1. trovo le cifre che sommate alla codifica di partenza danno tutte 0

2. sommo il complemento della codifica di partenza a un bit

3. partendo dalla cifra meno significativa copiare la codifica fino al primo 1 e poi complementare

2 valori x e y

= +12

10

= −3

10

Voglio scrivere -3 con più bit

per avere la stessa lunghezza

di +12, aggiungo quindi zeri No overflow, perché operandi discordi

al valore assoluto, che

diventeranno uni nell’opposto

Nel sistema binario la notazione vincente è quella in complemento alla base, cioè 2

La base 16 facilita la conversione con 2 ed è più veloce da scrivere

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

A 1010

B 1011

C 1100

D 1101

E 1110

F 1111

Valori numerici razionali Con due bit dopo la virgola

ogni due numeri interi ho

tre valori

Se ho poche cifre dopo la virgola a disposizione la precisione è limitata

Più cifre ho a disposizione minore è l’errore di approssimazione che commetto

costante

Errore assoluto

Errore relativo

=

Notazione in virgola mobile (floating point) = la densità dei punti tra un interno e l’altro cambia lungo l’asse

Fa in modo che l’errore relativo rimanga costante, e l’errore assoluto invece aumenti lungo l’asse

Quando il numero è piccolo in valore assoluto, si dedica più spazio ai decimali per avere maggior precisione

Per i numeri razionali la notazione è in modulo-segno Considero solo la parte

dopo la virgola e

= 101.110

13.75

10 2 trascrivo quello che c’è

prima sulla destra

= 111.010100 …

7.32

10 2

Notazione scientifica: 1

= 1.375 ∗ 10

13.75

10 3

1101 = 1.101 ∗ 2

2

Notazione → 1. ____ ∗ 2

∙ (1 ∙ ) × 2

= (−1)

Normalizzata = 1.M

Denormalizzata = 0.M (campo esponente con tutti zeri e mantissa con un numero)

lo scrivo con tutti 1 all’esponente e zeri alla mantissa

∞ indica qualcosa cche non è più un numero (tutti 1 all’esponente e mantissa con numero)

→ 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Configurazioni di due bit in base 3

00 +0

01 +1

02 +2

10 +3

11 +4

12 -4

20 -3

21 -2

22 -1

Rappresentazione dell’informazione non numerica

Codifica dei caratteri

codice ASCII (American Standard Code for Information Interchange) base: 7 bit

- codice ASCII esteso: 8 bit (1 byte)

- codice ASCII base per le prime 128 configurazioni

• caratteri nazionali à è é

• simboli caratteri semigrafici

• cornici

•

Codice ASCII

caratteri numerici prima dei caratteri alfabetici

• maiuscole prima delle minuscole

• la distanza tra due caratteri numerici è pari alla differenza tra il valore dei corrispondenti codici ASCII

•

Algoritmi

L’algoritmo è un procedimento, una sequenza di passi, che a partire dai dati iniziali in un numero finito

- di passi produce un risultato che costituisce la risposta al problema che l’algoritmo vuole risolvere

Ciascun passo manipola dati, oppure serve a decidere quale deve essere il passo successivo

- L’algoritmo deve essere una sequenza di passi non ambigui e non può essere a discrezione di chi lo

- legge

L’algoritmo deve terminare entro un numero finito di passi

- L’algoritmo deve essere deterministico (= a parità di dati d’ingresso con esecuzioni successive

- produco sempre lo stesso risultato)

Com’è fatto un algoritmo?

Ogni algoritmo ha uno o più ingressi e uno o più uscite

Variabili

Rettangolo = azione operativa, che produce dei dati

Blocchi di ingresso e uscita

Sequenza

Selezione

Interazione= si tende a rifare operazioni più volte produrre un valore e restituirlo

Algoritmo che aquisisce un valore intero in ingresso strettamente positivo e calcola e visualizza perimetro e

area di un cerchio avente quel valore come raggio

Operatore di assegnamento a=b sto assegnando ad a il valore di b

Operatori aritmetici (l’elevamento a potenza e la radice non esistono)

+ − ∗ / %

Operatori logici:

prodotto logico &&(and)

somma logica ||(or)

negazione !(not)

Operatori relazionali:

maggiore >

- minore <

- maggiore uguale >=

- minore uguale <=

- uguale ==

- diverso !=

-

Algoritmo che acquisisce un valore intero in ingresso che rappresenta un tempo espresso in secondi, vogliamo

sapere a quante ore, quanti minuti e secondi corrisponde (328s)

Inserisci un valore intero e calcola e visualizza il suo valore assoluto

bisogna avere l’operazione da fare nel caso la

condizione sia vera

Iterazione

L’utente dà un importo in euro e stabilisco quante monete da 5, 2 e 1 devo usare per calcolare quell’importo

Il resto della divisione lo facciamo quando gli operandi sono interi

Algoritmo che acquisiti tre valori interi visualizzi 1 nel momento in cui corrispondano a una terna pitagorica,

0 se non lo sono

Calcolo il massimo tra 10 valori

Acquisisce un valore intero strettamente positivo e visualizziamo 1 se è dispari, 0 se è pari

Algoritmo che acquisisce un valore intero strettamente positivo e calcola e visualizza 1 quando il valore

acquisito fa riferimento a un anno bisestile, altrimenti visualizzo 0

Algoritmo che acquisisce un numero intero positivo e calcola di quante cifre è composto

Il linguaggio C

#include <stdio.h> all’inizio di ogni programma, per includere le librerie

→

Il linguaggio C è sensibile alle maiuscole e minuscole

inizio programma int main (int argc, char*argv[])

→

{ /*programma*/

return 0;

}

Dichiarazione variabili

char = carattere

int = intero

float = reale

double = reale più grosso

long-int = intero più grosso

ogni istruzione termina con un ;

se più variabili condividono lo stesso tipo posso scrivere:

, nome

int nome 1 2

Operazione di assegnamento

nome = 25 assegnare un valore a una variabile

→

1 = nome assegnare a una variabile il contenuto di un’altra variabile

nome →

1 2

nome = nome *5*10 assegnare con calcoli in mezzo

→

1 2

quando dichiariamo una variabile diciamo quanto spazio occupa in memoria

int op int = int

float op float = float

int op float = float

float op int = float

Scrivo un programma che chiede all’utente il raggio e restituisce perimetro e area del cerchio

Acquisire informazioni

scanf(“%d”, &a);

scanf(“%d%d”, &a, &b); se voglio acquisire 2 valori interi

→

%d int

%c char

%f, %g float

Se voglio far apparire a video

printf(“benvenuto nel mio programma”);

printf(“il risultato è: %f %f”, per, area);

caratteri speciali

\n = new line

\t = tab

Chiedi un valore reale positivo e visualizza il valore intero arrotondato per difetto

Operazioni di cast per calcolare la media

gcc- Wall-std=c89-pedantic -o NOMEFILEESEGUIBILE NOMEFILESORGENTE

Wall segnala tutti I warning

- →

std=c89 controlla standard ANSI c89

- →

pedantic le violazioni degli standard vengono segnalate

- →

errori = non si produce l’eseguibile (problemi di sintassi)

warning=viene creato un eseguibile (possibili problemi di semantica)

num = num +1; ++ num++; ++num;

→

num = num -1; -- num--; --num;

→

var op ; var op = ;

→

ris=ris/val; ris/=val;

→

tot=tot+cont; tot+=cont;

→

Il costrutto if

if(espressione){

istruzione_V;

}

if(espressione) ;

istr_V

1

istr_V ;

2 ;

istr_V

3

Scrivo un programma che, acquisito un valore, calcola e visualizza il suo valore assoluto

Acquisisce un valore intero, visualizza + se positivo, - se negativo e spazio se nullo

if(a==0) if(!