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

Fondamenti di informatica

Concetti di base

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)

Sistemi di numerazione

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

• Byte = 8 bit
• Kilobyte = 2¹⁰ bit
• Megabyte = 2²⁰ bit
• Gigabyte = 2³⁰ bit
• 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.

Rappresentazione dei numeri

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

000001010011100101110111

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 = ∑ 200 1 2

31010 = 0 ∗ 2 + 1 ∗ 2 + 0 ∗ 2 + 1 ∗ 2 = 10

Numeri binari

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

Operazioni aritmetiche

-23 10MS 2MS+0 +0 −7 1 0 0 −10 0 0 0 1= == =+1 +1 −6 1 0 1 0 −20 0 0 1+2 +2 −5 1 0 1 1 −30 0 1 0+3 +3 −40 – -40 0 1 1 1 01 === =+4 +4 −51 1 0 1 – -30 1 0 0+5 +5 −61 1 1 0 – -20 1 0 1+6 0 1 1 0 +6 −1 = −71 == = 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 permette di avere agilità nell’elaborazione:

• = −1310 22 rappresento il modulo di x nel sistema binario come se fosse → || = 13 2

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, allora c’è un overflow.

Se gli operandi sono discordi è impossibile avere overflow.

Metodi per trovare l'opposto di una codifica

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 = +1210 = −310

Voglio scrivere -3 con più bit per avere la stessa lunghezza di +12, aggiungo quindi zeri 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 00001 00012 00103 00114 01005 01016 01107 01118 10009 1001A 1010B 1011C 1100D 1101E 1110F 1111

Numeri razionali

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.11013.7510 2 trascrivo quello che c’è prima sulla destra = 111.010100 …7.3210 2.

Notazione scientifica

1= 1.375 ∗ 1013.7510 31101 = 1.101 ∗ 22

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 che 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.

Codifica dei caratteri

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).

Struttura di un algoritmo

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 acquisisce 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 !=

Esempi di algoritmi

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 delle 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

Acquisizione e output

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;→

Costrutto if

Il costrutto if:

if(espressione) {
    istruzione_V;
}
if(espressione)
    istr_V1;
istr_V2;
istr_V3;

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(!...