Appunti di Informatica

FONDAMENTI DI INFORMATICA

Appunti di teoria + slides su moodle + esercizi

INTRODUZIONE

Informatica (Informazione automatica)

●​ Deriva dalla contrazione di due termini e riguarda la trattazione automatizzata delle

informazioni (con l’uso di calcolatori...). Termine coniato nel 1968 da Philippe Dreyfus:

infor(mation) + (auto)matique.

Computer Science

●​ Termine che si utilizza nel mondo anglosassone. Studio dei fondamenti teorici

dell'informazione, della sua computazione a livello logico e delle tecniche pratiche per

la sua implementazione e applicazione tramite calcolatori elettronici.

GLOSSARIO

CAP. 1 Rappresentazione Dati da pag. 1 a pag. 5

CAP. 2 Linguaggio Python da pag. 6 a pag. 27

- Variabili, operatori, espressioni

- Condizioni e iterazioni

- Funzioni

- Scovare e risolvere bug

- Oggetti, valori e mutabilità

- Ricorsione

CAP. 3 Strutture Dati da pag. 28 a pag. 45

- Liste e Stringhe

- Tuple, Dizionari e Set

- Numeri casuali

- Classi e oggetti

- Alberi binari di ricerca

CAP. 4 Algoritmi e Complessità da pag. 46 a pag. 51

RAPPRESENTAZIONE DATI

Un calcolatore elettronico deve memorizzare dati e istruzioni. Lo fa attraverso dei dispositivi,

chiamati circuiti elettronici. Tali dispositivi sono detti bistabili perché possono avere solo 2 stati:

Acceso (1) o Spento (0).

Ma come fa un calcolatore a memorizzare dati e istruzioni se abbiamo a disposizione solo due valori,

0 e 1? Si usano delle codifiche per memorizzare con lo stesso circuito numeri interi, positivi e

negativi, con la virgola e senza, e caratteri.

Se scrivo 42 in base 10: con

Es. 42 42 = 4×10¹ + 2¹×10⁰ = 4×B¹ + 2×B⁰ B=10

Con la stessa strategia possiamo memorizzare numeri usando solo 2 cifre.

[42]₁₀ = 2⁵ + 2³ + 2¹ = 32 + 8 + 2 = [101010]₂

Scelta la base B in cui rappresentiamo il numero posso scrivere, per una

codifica posizionale: 1

Posso fare anche le operazioni della somma e del prodotto:

- Somma Es. 5+3=8 5=[5]₁₀=[101]₂ 3=[3]₁₀=[11]₂

Sapendo che: · 1+1=10 · 1+0=1 · 0+0=0

Il risultato è corretto, infatti [1000]₂ = 1×2³ + 0×2² + 0×2¹ + 0×2⁰ = 8

- Prodotto Es. 5×2=10 5=[5]₁₀=[101]₂ 2=[2]₁₀=[10]₂

Sapendo che: · 1×1=1 · 1×0=0 · 0×0=0

Il risultato è corretto, infatti [1010]₂ = 1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 10

La conversione da base 10 a base 2 avviene usando la regola dei “resti successivi”.

Sapendo che la divisione intera è l’operazione che dato un dividendo N e un divisore D definisce due

numeri Q e R tali che N=Q×D+R, e che nel nostro caso D=2 e R=a₀, posso scrivere che

Quindi ad ogni divisione per la base, cioè 2, il resto è l’ultima cifra nella rappresentazione

posizionale.

Es. [125]₁₀ = [???]₂

Poichè è molto complesso memorizzare cifre in rappresentazione binaria, la rappresentazione in

base 16 ci consente di rappresentare le stringhe di bit in maniera compatta. Per lavorare in base 16

occorrono 15 simboli oltre lo 0: [0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F].

Es. [125]₁₀ = [???]₁₆ [125]₁₀ = [1111101]₂ = [0111 1101]₂ = [7 D]₁₆ = [7D]₁₆

Esercizi

a) Convertire 47 usando i resti successivi

b) Indicare la rappresentazione in base 10 di 1101 2

Sommiamo due bit A e B in un circuito sommatore gestendo il riporto in ingresso Cin e in uscita

Cout. La prima cifra si calcola usando la porta XOR sui bit A,B e C. Il riporto Cout si crea se A+B=1 E

C=1 oppure se A=1 E B=1.

A

B Cout

Cin S

Combinando tanti sommatori da 1 bit possiamo sommare interi di qualunque dimensione.

Possiamo quindi, dato un numero limitato di bit N, rappresentare interi senza segno con valori

Per esempio, un intero su 8 bit (ovvero su un byte)

compresi nell’intervallo [0, 2ᴺ-1 ]. potrà rappresentare numeri tra 0 e 255. Come

ovvio più bit si avranno a disposizione maggiore

sarà l’intervallo di valori rappresentabile.

Per rappresentare un intero con segno (ad esempio -12) occorre codificare questa informazione

aggiuntiva. Una soluzione immediata potrebbe essere usare un bit per indicare il segno: così facendo

però si avrebbero due valori per lo zero, -0 e +0, e inoltre dovrei specializzare il mio circuito per

somme e sottrazioni gestendo la presenza del bit di segno.

Quindi per i numeri negativi nella pratica si utilizza il ‘complemento a 2’.

Una rappresentazione posizionale in cui il bit più significativo ha peso

negativo.

Definizione: Il complemento a B per un numero r a N cifre è dato da [v] = Bᴺ - r.

CA2

(Esempio: per un intero r su 4 bit in base 2 [v] = 2⁴ - r)

CA2

Usando il complemento a 2 si rappresentano I valori tra [−2ᴺ⁻¹, 2ᴺ⁻¹ − 1 ]. Con 8 bit ad esempio

avremo valori in [-128, 127], mentre se usiamo tutti gli 8 bit per numeri positivi il range è [0, 255].

Esiste un algoritmo di conversione per facilitare il calcolo del complemento a 2. Dobbiamo:

1. Invertire tutti i bit 2. Aggiungere 1

Mi servono almeno 6 bit: [-32,31]

Es. [-23]₁₀ = [???]₂ [23]₁₀ = [010111]₂ [101000] + 1 = [101001] = -2⁵ + 2³ + 2⁰ = -23

CA1 CA2

Es. [-2]₁₀ = [???]₂ (su 4 bit) 2⁴ - 2 = 10000 − 00010 = (01111 + 1) − 00010 = 01111 − 00010 + 00001

= 1111 - 0010 + 0001 = 1101 + 0001 = 1110

Per fare 1111 − 0010 ho flippato tutti i bit del numero da complementare

Es. [8-23]₁₀ = [???]₂ -23 = [-23]₁₀ = - [00010111] = [11101000] = [11101001] 8 = [8]₁₀ = [00001000]

2 CA1 CA 2

Risultato negativo come atteso. Proviamo a convertirlo per

controllare il risultato:

[1111 0001] - 1 = [1111 0000] = - [0000 1111]₂ = -[15]₁₀

CA2 CA1

In python usiamo questa rappresentazione quando ad esempio scriviamo >> value = -12 3

Con un circuito sommatore progettato per sommare interi di N bit posso sommare e sottrarre senza

modifiche a patto di usare il complemento a 2 per i numeri negativi. Si verifica un Overflow quando

il risultato della somma necessita di più bit di quelli degli addendi.

Nel complemento a 2 si scartano i riporti. Si è verificato overflow e il risultato non è valido se il

risultato di (+x) + (+z) è negativo oppure se (-w) + (-q) è positivo.

Gli interi così rappresentati hanno un massimo e minimo valore rappresentabile. In python gli interi

(int) sono rappresentati a precisione arbitraria. Finché una variabile è mantenibile su 64 bit la

rappresenta come visto sinora, ma se la variabile ‘sfora’ i 64 bit, l’interprete rappresenta l’intero

come una sequenza di interi a 30 bit.

Infine possiamo rappresentare i numeri con virgola mobile (float), ovvero i numeri razionali. L’idea

ᶜ

è rappresentare i numeri nella forma segno x mantissa x B . In base 10 avremmo qualcosa del tipo:

0.00121 = (+1) x (0.121) x 10⁻². Secondo lo standard IEEE 754 la rappresentazione a 32 bit di un float

è la seguente:

- Il segno si rappresenta con un bit: 1 per i negativi, 0 per i positivi.

- La mantissa viene rappresentata con 23 bit.

I numeri vengono portati in forma ‘normalizzata’ per evitare ambiguità al calcolatore. In forma

normale la mantissa rispetta il vincolo 1 ≤ m < B, quindi in base 2 sarà vero che 1 ≤ m < 2 e quindi è

un numero rappresentabile come:

Per ottenere la parte frazionaria di un numero reale si può procedere nel seguente modo:

[0.a a …a ]₂ = a 2⁻¹ + a 2⁻² + … + a 2ᴷ. Moltiplicando iterativamente per 2 ottengo le cifre (0 o 1) della

1 2 k 1 2 k

parte frazionaria.

Es. [0.625]₁₀ = [???]₂ [0.625]₁₀ = [0.101]₂

Invece che rappresentare la caratteristica direttamente in complemento a due si codifica un intero a

8 bit (e, detto esponente) secondo la seguente: e=c+(2⁷-1). Quindi ad esempio e=178 allora

c=178-127=51, il numero sarà s x m x 2⁵¹.

ͤ

In sintesi (−1)ᔆ x 1. m x 2 ¹²⁷

⁻

La parte intera la otteniamo coi resti successivi

Es. [-118.625]₁₀ = [???]₂ 118 = 1110110

La parte frazionaria moltiplicando per due iterativamente 0.625 = 0.101

Ricapitolando: - segno s = 1

- mantissa m = 1110110.101, m>2, quindi va normalizzata 1.110110101⋅2⁶,

si omette il primo 1, deve essere 23 bit, quindi m = 11011010100000000000000

esponente quindi

- e -127 = 6 e = 6+127 = [133]₁₀ = [10000101]₂ e = 10000101

→

Risultato: [-118.625]₁₀ = [1 10000101 11011010100000000000000]₂

I numeri in virgola mobile (float) non rappresentano tutti i razionali e gli interi (int) non sono un

sottoinsieme dei numeri in virgola mobile. Ad esempio, un intero rappresentato su più di 24 bit non

ammette un’esatta rappresentazione in virgola mobile (infatti [2²⁴+1]₁₀ risulterebbe uguale a [2²⁴]₁₀). 4

I caratteri sono rappresentati come interi di 8 bit. Ad esempio, il carattere ‘3’ è ben diverso dal

valore 3, in particolare il carattere ‘3’ è codificato con un byte il cui valore visto come decimale è 51.

Per indicare lo stesso carattere sia in maiuscolo che in minuscolo occorrono due codifiche differenti.

Le stringhe sono invece sequenze di caratteri.

Importante anche capire quanta RAM (memoria ad accesso casuale) stiamo utilizzando. Se, per

esempio, un fotogramma video a 1080x720 a colori (RGB, 3 byte per pixel) viene memorizzato

usando 1 byte per ogni canale, la ram che mi serve per tenere in memoria un video decompresso di

10 secondi, considerando il video a 25 frame al secondo è uguale a: 1080×720×3×1×10×25 =∼ 500Mb.

Esercizi

a) Dato il numero decimale 935: Convertire il numero in binario mostrando lo svolgimento delle

divisioni successive, convertire il numero in esadecimale mostrando i passi della conversione.

b) Determinare alcuni possibili valori delle basi b e bʹ tali che sia verificata la seguente

uguaglianza: [32] = [22]

b bʹ

c) Quanti bit servono per memorizzare il valore di un dado a 6 facce?

d) Combinando porte OR e AND rilevare overflow per sommatori per numeri con complemento a 2 5

LINGUAGGIO PYTHON

Nel primo capitolo abbiamo visto che lo scopo del programmatore è definire un algoritmo in un

linguaggio interpretabile dalla macchina. In python scriveremo gli algoritmi come sequenze di

istruzioni. Ogni istruzione modificherà la memoria del calcolatore avvicinandoci al risultato finale

(e.g. calcolo sqrt). Le istruzioni sono costituite da costrutti ed espressioni.

Variabili, operatori, espressioni

In python i dati hanno un tipo. Scriveremo in memoria delle informazioni come stringhe di bit

secondo delle convenzioni. Ogni area di memoria sarà caratterizzata dal valore che vi è scritto e dal

tipo di dato che rappresenta. I tipi sono matematicamente degli insiemi che definiscono quali valori

sono rappresentabili nell’elaboratore tramite il tipo scelto (int, float, str, chr, bool).

Interi -

●​ int

Si usano per rappresentare numeri naturali con e senza segno. In python hanno precisione

arbitraria.

#questo è un valore intero (int) assegnato ad una variabile a

1 #questo è un valore intero negativo (int) assegnato ad una variabile a

-1

Virgola mobile -

●​ float

Si usano per rappresentare i numeri razionali.

#questo è un float assegnato ad una variabile a

1.2

Caratteri -

●​ chr

Si usano per rappresentare i caratteri usando la codifica ASCII.

#si usa per rappresentare un carattere tramite un intero a 8 bit

a

Stringhe

●​ - str

Sono una sequenza di caratteri. Si definiscono usando apici singoli o doppi

#una stringa

‘ciao!’ #una stringa

“ciao!”

Sintassi

Useremo spesso una notazione per descrivere la sintassi ammessa per un certo tipo di istruzione.

Questo linguaggio si usa per definire al grammatica di altri linguaggi ed è detto EBNF: extended

Backus-Naur form.

<non_terminale>:=<non_terminale> terminale

<> per indicare un simbolo che può espandersi

#Uso

<non_terminale>:= terminale1 | terminale2

#Uso | per indicare l’alternativa

<non_terminale>:= [terminale opzionale] terminale | terminale

#Uso [] per indicare l’opzionalità di un simbolo (sia terminale che non terminale)

Costanti

Una costante denota un valore che non si può modificare durante l’esecuzione di un programma. Le

useremo assieme agli operatori e alle variabili per creare delle espressioni.

#costante intera

10 #costante float

10.1 #costante str

‘c’ 6

Variabili <var_decl>:= <var_name> = <expr>

Una variabile dà il nome ad una locazione di memoria in cui è memorizzato un valore di un certo

tipo. In python i tipi delle variabili sono inferiti al momento dell’assegnazione. Nel dubbio possiamo

usare per scoprire il tipo di una variabile.

type(variable)

Es. Es.

a = 10 a = 10.0

type(a) type(a)

<class 'int'> <class ‘float'>

Le variabili esistono da quando gli viene assegnato un valore per la prima volta.

Regole per i nomi di variabile o identificatori non possono iniziare con un numero.

<var_name>:

Possono contenere tutti i caratteri alfanumerici compresi gli _. Le variabili devono avere

possibilmente un nome evocativo. La stringa che indica la variabile deve descrivere il suo contenuto.

Es. time1 = 10 #C style

time_to_live = 1 #JAVA style o CamelCase Es. corretto

HomeAddress = 'Via S. Marta 3’ #si può iniziare con _

_value = 2 #non si può definire una variabile senza legarla ad un valore

Es. time #il – è ambiguo e essere scambiato per un operatore Es. errato

age-person #non si può iniziare una variabile con un numero

12time = 10 #a meno che non siano numeri generici

Es. Es. corretto

x, y, z = 10, 20, 30 #il vostro programma funzionerà… ma poco

gianni, pinotto = 10, 20 #ma rileggendolo non avrà senso… funzionale

pippo = 64

Conversioni

E’ possible, conveniente e spesso necessario convertire i dati da un tipo ad un altro. Le conversioni

possono avvenire in modo implicito o esplicito. Il caso implicito più semplice e frequente è la

conversione da a

int float.

#questa è una variabile int

Es. a = 1 #la somma di un int e un float (1.2) restituisce un float

b = a + 1.2

b vale 2.2, a viene prima convertito a float (a=1.0), successivamente viene applicata la somma tra

float

La conversione da a si verifica se applichiamo un operatore definito solo per come

float int int,

la divisione intera //. #questa è una variabile float

Es. a = 1.2 #la divisione intera tra un float e un int restituisce un int

b = a // 2

b vale 0, a viene prima convertito in int, successivamente viene applicato l’operatore divisione intera

La conversione di una variabile da un tipo ad un altro può anche essere forzata in maniera esplicita.

Non sono molti i casi in cui questo è necessario: #la variabile voto è di tipo str

Es. voto = input(‘Inserire Voto’)

Supponiamo che si voglia calcolare la media dei voti e di conseguenza occorra fare operazioni

di somma e divisione. “voto” va convertito ad esempio in float.

#assegnerà alla variabile voto invece che la stringa ’27’ il float

voto = float(voto)

27.0 7

Espressioni

Combinano variabili e costanti tramite operatori. Ogni istruzione termina con un a capo.

Es. a = 10 + 1

a = a + 1

a = (b + c) / 12.0

La semantica di ciascuna espressione è suddivisibile in:

-​ Valore assunto dall’espressione (ciascuna espressione assume un valore):

#il valore assunto è 2

a = 1 + 1

a = 10 #il valore assunto è 20

a + a

-​ Side-effects sulle variabili usate (alcune espressioni modificano il valore delle variabili che

contengono) #la variabile a viene modificata e vale 10

a = 10 #la variabile viene incrementata di 1

a = a + 1

La sintassi delle espressioni si può definire con:

<expr>:= <const>|<var>|(<expr>)|…

:= <expr><op2><expr>|<op1><expr>|...

<op2> := + | - | * |**| / | // | % | …

:=< | <= | == | != | >= | > |…

:= and | or

<op1>::= not | - | +

Python quando si presenta un’espressione effettua il parsing sintattico. Questo è l’albero sintattico

dell’espressione.

- Ogni elemento terminale (es. <op>) viene riconosciuto

- La combinazione di più elementi terminali dà origine ad elementi non terminali (<expr>)

- Al termine se l’albero si conclude con <expr> l’espressione è sintatticamente corretta

- Gli operatori si applicano in un ordine di precedenza prestabilito ( es. per gli aritmetici: * / + -)

- In generale è consigliabile usare le parentesi sempre per essere certi e massimamente espressivi

sull’ordine in cui vogliamo che le espressioni siano valutate 8

Operatori binari aritmetici: - + / // * %

Si usano per creare espressioni di tipo aritmetico, la loro semantica è ovvia,

salvo casi particolari. L’espressione a+b ha il valore della somma dei valori

di a e b. Se ad esempio a = 1 e b = 2, scrivere a+b è come scrivere 3.

#la somma del valore di a e 1

Es. a + 1 #il resto della divisione intera tra il valore di a e 2

a % 2 #la divisione intera tra 23 e 2 vale 11

23 // 2 #la divisione tra 23 e 2 vale 11.5

23 / 2.0

Operatore assegnazione: =

E’ un operatore binario e si usa per assegnare un valore ad una variabile. La sua semantica consiste

nel variare il valore dell’operando sinistro sostituendovi il valore dell’operando destro. Non è

commutativo: a=b è diverso da b=a. L’operando sinistro non può ovviamente essere una costante o

un’espressione ma solo una variabile.

#d’ora in poi a vale 1<