FormularioFondamenti di Informatica: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Il calcolatore e i linguaggi

Struttura di un elaboratore

Definizione (modello di von Neumann). Un calcolatore moderno segue (con varianti) l'architettura di von Neumann: dati e istruzioni del programma stanno nella stessa memoria e una CPU li legge in sequenza.

Componente	Ruolo
CPU (processore)	esegue le istruzioni: unità di controllo + ALU + registri
Memoria centrale (RAM)	contiene programma in esecuzione e dati; volatile, accesso diretto per indirizzo
Memoria di massa (SSD, HDD)	persistente, molto più lenta; contiene file e programmi non in esecuzione
Periferiche di I/O	tastiera, schermo, rete, dischi: comunicano con CPU e memoria tramite controller
Bus	collegamenti condivisi: bus dati, bus indirizzi, bus di controllo

Formula (celle indirizzabili con $k$ bit). Sequenza di celle (tipicamente di 1 byte = 8 bit), ognuna con un indirizzo numerico. Con indirizzi a $k$ bit si indirizzano $2^k$ celle. Una variabile di un programma occupa una o più celle consecutive: in C l'indirizzo è esplicito (vedi Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →), in Python è nascosto.

Definizione (ciclo fetch-decode-execute)

1. Fetch: legge dalla memoria l'istruzione all'indirizzo contenuto nel PC e la copia nell'IR; incrementa il PC.
2. Decode: la CU interpreta il codice operativo e individua gli operandi.
3. Execute: l'ALU (o l'unità di memoria/I/O) esegue l'operazione; il risultato va in un registro o in memoria.

Rappresentazione binaria dei dati

Formula (valore di un numero in base $b$). Un numero in base $b$ con cifre $c_{n-1} \dots c_1 c_0$ vale

$$\sum_{i=0}^{n-1} c_i \, b^i$$

Proprietà (conversioni tra basi 10, 2 e 16)

• Da base 10 a base 2: divisioni successive per 2, i resti letti dal basso verso l'alto. $45 \to 22\,r1 \to 11\,r0 \to 5\,r1 \to 2\,r1 \to 1\,r0 \to 0\,r1$, quindi $101101_2$.
• Base 2 ↔ 16: ogni cifra esadecimale corrisponde a 4 bit ($0010\,1101_2 = 2D_{16}$). Per questo gli indirizzi di memoria e i byte si scrivono in esadecimale.

Definizione (interi senza segno e overflow). Con $n$ bit: valori da $0$ a $2^n - 1$. Somma binaria in colonna con riporto; se il risultato non sta in $n$ bit si ha overflow e il bit di riporto finale si perde (il risultato è preso modulo $2^n$).

Formula (valore in complemento a 2). Con $n$ bit il bit più significativo ha peso negativo $-2^{n-1}$:

$$x = -c_{n-1} 2^{n-1} + \sum_{i=0}^{n-2} c_i 2^i$$

Proprietà (complemento a 2: intervallo, opposto e overflow)

• Intervallo: da $-2^{n-1}$ a $2^{n-1} - 1$ (8 bit: da $-128$ a $127$). Asimmetrico: c'è un negativo in più.
• Bit più significativo = 1 ⇔ numero negativo. Lo zero ha una sola rappresentazione.
• Opposto di un numero: si invertono tutti i bit e si somma 1. Esempio a 8 bit: $5 = 00000101$, inverto → $11111010$, +1 → $11111011 = -5$.
• La sommatrice è la stessa degli interi senza segno: è il motivo per cui il complemento a 2 si usa ovunque.
• Overflow: sommando due numeri dello stesso segno si ottiene un risultato di segno opposto. A 8 bit: $127 + 1 = 10000000 = -128$.

Definizione (virgola mobile IEEE 754). Un reale è rappresentato come $(-1)^s \cdot 1.m \cdot 2^{e - \text{bias}}$:

Formato	Bit totali	Segno $s$	Esponente $e$	Mantissa $m$	Cifre decimali circa
singola precisione (float in C)	32	1	8 (bias 127)	23	7
doppia precisione (float in Python, double in C)	64	1	11 (bias 1023)	52	15–16

Proprietà (confronto di numeri in virgola mobile). Regola: mai confrontare float con ==; usare una tolleranza (math.isclose o abs(a - b) < eps).

Definizione (ASCII, Unicode e UTF-8)

• ASCII: 7 bit, 128 caratteri (lettere inglesi, cifre, punteggiatura, controllo). 'A' = 65, 'a' = 97, '0' = 48: le lettere e le cifre sono consecutive.
• Unicode: assegna un numero (code point) a ogni carattere di ogni lingua ('è' = U+00E8 = 232, '€' = U+20AC).
• UTF-8: codifica Unicode in 1–4 byte; i caratteri ASCII occupano 1 byte ed hanno lo stesso codice. È la codifica standard per i file di testo.

Paradigmi di programmazione e linguaggi

Definizione (algoritmo, programma, sintassi e semantica)

• Algoritmo: sequenza finita di passi non ambigui che risolve un problema (trasforma un input in un output) e termina.
• Programma: algoritmo scritto in un linguaggio di programmazione, eseguibile da un calcolatore.
• Un linguaggio ha una sintassi (quali testi sono programmi validi) e una semantica (che cosa fa un programma valido).

Definizione (paradigmi di programmazione)

Paradigma	Idea	Esempi
Imperativo	sequenza di istruzioni che modificano lo stato (variabili)	C, Python, assembly
Procedurale	imperativo organizzato in procedure/funzioni	C, Python
A oggetti	dati e operazioni raggruppati in oggetti; classi, incapsulamento, ereditarietà	Python, Java, C++
Funzionale	il programma è composizione di funzioni senza effetti collaterali; niente assegnamenti	Haskell; in parte Python (lambda, map, comprensioni)
Dichiarativo / logico	si descrive che cosa si vuole, non come ottenerlo	SQL, Prolog

Definizione (compilatore e interprete)

	Compilatore	Interprete
Quando traduce	tutto il sorgente prima dell'esecuzione	istruzione per istruzione durante l'esecuzione
Prodotto	file eseguibile in linguaggio macchina	nessun eseguibile separato
Errori di tipo/sintassi	segnalati in compilazione	molti emergono solo quando la riga viene eseguita
Velocità	alta	più bassa
Esempio	gcc per il C	python

II. Python: variabili, tipi ed espressioni

Eseguire un programma Python

Definizione (istruzione, espressione e blocco)

• Istruzione: unità eseguibile (assegnamento, if, for, chiamata di funzione...). Di norma una per riga.
• Espressione: combinazione di valori, variabili, operatori e chiamate che produce un valore (2 * x + 1). Un'espressione può comparire dove serve un valore; un'istruzione no.
• Blocchi definiti dall'indentazione (convenzione: 4 spazi). La riga che apre un blocco termina con :.

Definizione (tipi di errore)

• Errore di sintassi (SyntaxError, IndentationError): il file non viene eseguito affatto.
• Errore a tempo di esecuzione (eccezione: NameError, TypeError, ZeroDivisionError...): il programma si ferma alla riga che lo provoca, con un traceback. Vedi Eccezioni in PythonEccezioni e traceback, eccezioni predefinite più comuni, try/except/else/finally, raise per segnalare errori, propagazione lungo le chiamate.Eccezioni in Python →.
• Errore logico: il programma termina ma il risultato è sbagliato. Vedi Debugging e testingTipi di errore, metodo per localizzare un bug, lettura del traceback, stampe di controllo, debugger (VS Code, pdb, gdb), assert e strumenti per la memoria in C; test di unità, casi limite e partizioni, doctest e unittest.Debugging e testing →.

Variabili, oggetti e riferimenti

Definizione (oggetto in Python: tipo, identità e valore). Ogni dato in Python è un oggetto con:

• tipo (type(x)): determina valori possibili e operazioni ammesse; non cambia;
• identità (id(x)): di fatto l'indirizzo in memoria; non cambia;
• valore: può cambiare solo se l'oggetto è mutabile.

Definizione (assegnamento e variabile come nome). Una variabile è un nome che si riferisce a un oggetto, non una "scatola" con il valore dentro. L'assegnamento x = espressione:

1. valuta l'espressione a destra, ottenendo un oggetto;
2. lega il nome x a quell'oggetto (creando il nome se non esiste).

Definizione (oggetti mutabili e immutabili)

Immutabili	Mutabili
int, float, bool, complex, str, tuple, frozenset, None	list, dict, set, oggetti di classi definite dall'utente (di norma)

Con un immutabile, ogni "modifica" crea un nuovo oggetto e rilega il nome:

s = "ciao"
t = s
s += "!"           # nuovo oggetto "ciao!"; t è ancora "ciao"

Definizione (aliasing). Con un mutabile, la modifica avviene sul posto ed è visibile da tutti i nomi che si riferiscono all'oggetto (aliasing):

a = [1, 2, 3]
b = a              # alias, non copia
b.append(4)
print(a)           # [1, 2, 3, 4]
c = a.copy()       # copia (superficiale): oggetto diverso

Definizione (== e is)

• a == b: i valori sono uguali.
• a is b: sono lo stesso oggetto (stessa identità).

Tipi numerici ed espressioni

Definizione (operatori aritmetici di Python)

Operatore	Significato	7 op 2	-7 op 2
+ - *	somma, differenza, prodotto	9, 5, 14
/	divisione reale, sempre float	3.5	-3.5
//	divisione intera (arrotonda verso $-\infty$)	3	-4
%	resto, stesso segno del divisore	1	1
**	potenza	49

Formula (relazione tra // e %). Vale sempre a == (a // b) * b + a % b. Attenzione: in C la divisione intera tronca verso zero e -7 / 2 vale -3 (vedi Tipi, operatori e controllo del flusso in CTipi interi e reali del C con dimensioni e limiti, conversioni implicite e cast, divisione intera, operatori di incremento, logici e bit a bit; if, switch, while, do-while, for, break e continue.Tipi, operatori e controllo del flusso in C →).

Proprietà (tipo del risultato di un'operazione)

• int op int → int (tranne / → float).
• Se un operando è float, il risultato è float: 2 * 3.0 == 6.0.
• int ** int negativo → float: 2 ** -1 == 0.5.

Definizione (precedenza degli operatori)

1. ** (associativo a destra: 2 ** 3 ** 2 == 2 ** 9)
2. +x, -x unari (-2 ** 2 == -4)
3. *, /, //, %
4. +, -
5. confronti <, <=, ==, !=, >, >=, in, is
6. not
7. and
8. or

III. Decisioni e cicli

Logica booleana e istruzione if

Definizione (operatori booleani NOT, AND, OR e XOR). Variabili con due valori (vero/falso) e tre operatori fondamentali:

$A$	$B$	$\lnot A$	$A \land B$	$A \lor B$	$A \oplus B$ (xor)
F	F	V	F	F	F
F	V	V	F	V	V
V	F	F	F	V	V
V	V	F	V	V	F

Legge (di De Morgan). Leggi di De Morgan: $\lnot(A \land B) = \lnot A \lor \lnot B$ e $\lnot(A \lor B) = \lnot A \land \lnot B$. Servono per negare una condizione composta:

# "x NON è in [0, 10]"
not (0 <= x <= 10)
x < 0 or x > 10          # equivalente per De Morgan

Definizione (valutazione a corto circuito). and e or valutano il secondo operando solo se serve:

• A and B: se A è falso, B non viene valutato.
• A or B: se A è vero, B non viene valutato.

Proprietà (and e or restituiscono un operando). and/or restituiscono uno degli operandi, non necessariamente un bool: "" or "default" vale "default".

Definizione (truthiness). In un contesto booleano (if, while, and...) ogni oggetto ha un valore di verità. Sono falsi: False, None, 0, 0.0, "", [], (), {}, set(). Tutto il resto è vero.

Definizione (istruzione if, elif ed else)

if voto >= 18:
    esito = "promosso"
elif voto >= 15:
    esito = "orale di recupero"
else:
    esito = "respinto"

• I rami elif sono controllati nell'ordine; si esegue solo il primo vero.
• else e elif sono facoltativi.
• Blocco vuoto: pass.

Definizione (espressione condizionale)

segno = "pari" if n % 2 == 0 else "dispari"
massimo = a if a >= b else b

Ciclo while

Definizione (ciclo while)

while condizione:
    corpo

La condizione viene valutata prima di ogni iterazione; se è falsa all'inizio il corpo non viene mai eseguito. Il corpo deve modificare qualcosa da cui dipende la condizione, altrimenti il ciclo è infinito.

Definizione (break, continue ed else nei cicli). ## break, continue, else

• break: esce subito dal ciclo più interno.
• continue: salta il resto del corpo e torna al controllo della condizione.
• else dopo il ciclo: eseguito se il ciclo termina senza break (tipico nelle ricerche).

Proprietà (terminazione e invariante di un ciclo)

• Terminazione: si individua una quantità intera non negativa che diminuisce a ogni iterazione (in Euclide: b, perché a % b < b).
• Invariante di ciclo: proprietà vera prima e dopo ogni iterazione; alla fine, insieme alla condizione falsa, dà il risultato. Nel ciclo della somma con sentinella: "somma è la somma dei valori letti finora, escluso l'ultimo".

Ciclo for e range

Definizione (ciclo for e iterabili)

for elemento in iterabile:
    corpo

A ogni iterazione elemento viene legato al successivo valore dell'iterabile (lista, stringa, tupla, range, dizionario, file...). Il ciclo termina quando gli elementi finiscono. A differenza del C, il for di Python non ha un contatore implicito: scorre valori.

Definizione (range). range(start, stop, step) produce gli interi da start (incluso) a stop (escluso) con passo step. Non crea una lista: genera i valori al bisogno.

Chiamata	Valori
range(5)	0, 1, 2, 3, 4
range(2, 6)	2, 3, 4, 5
range(0, 10, 3)	0, 3, 6, 9
range(5, 0, -1)	5, 4, 3, 2, 1
range(5, 0)	nessuno

Proprietà (cicli annidati). Il ciclo interno viene eseguito per intero a ogni iterazione dell'esterno: $n$ iterazioni esterne × $m$ interne = $n \cdot m$ esecuzioni del corpo (vedi Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →). break esce solo dal ciclo interno.

IV. Funzioni e moduli

Funzioni in Python

Definizione (def, parametri e return)

• def crea un oggetto funzione e lo lega al nome. Il corpo viene eseguito solo alla chiamata.
• Parametri (nella definizione) e argomenti (nella chiamata).
• return expr termina la funzione e restituisce il valore; senza return (o con return vuoto) restituisce None.
• Più valori: return q, r restituisce una tupla, che si spacchetta con q, r = f(...) (vedi Tuple e unpackingtuple come sequenze immutabili; quando usarle al posto delle liste; spacchettamento, scambio, asterisco; tuple come valori di ritorno multipli e come chiavi di dizionario.Tuple e unpacking →).

Definizione (parametri predefiniti, args e kwargs)

• I parametri con valore predefinito vanno dopo quelli senza.
• *args raccoglie gli argomenti posizionali in più in una tupla; **kwargs quelli con nome in un dizionario.

Proprietà (valore predefinito mutabile). Il valore predefinito viene valutato una volta sola, alla definizione:

def aggiungi(x, lista=[]):      # SBAGLIATO: la stessa lista è condivisa tra le chiamate
    lista.append(x)
    return lista

def aggiungi(x, lista=None):    # corretto
    if lista is None:
        lista = []
    lista.append(x)
    return lista

Definizione (passaggio degli argomenti per riferimento a oggetto). Python passa riferimenti a oggetti (call by object reference): il parametro diventa un nuovo nome per lo stesso oggetto dell'argomento.

• Riassegnare il parametro non tocca il chiamante.
• Modificare sul posto un argomento mutabile è visibile al chiamante.

Definizione (ambito delle variabili LEGB). Un nome viene cercato nell'ordine LEGB: Locale (funzione corrente) → Enclosing (funzioni che la contengono) → Globale (modulo) → Built-in.

• Ogni nome assegnato dentro una funzione è locale a quella funzione, salvo dichiarazione global (o nonlocal).
• Leggere una globale da una funzione è lecito; assegnarla senza global crea una locale.

Definizione (funzioni come oggetti e lambda). Le funzioni si possono assegnare, passare come argomenti e restituire.

Moduli e libreria standard

Definizione (modulo, pacchetto e import). Un modulo è un file .py: le funzioni, le classi e le variabili definite al suo livello più esterno diventano suoi attributi. Un pacchetto è una cartella di moduli.

import math                 # si usa math.sqrt(2)
import math as m            # alias: m.sqrt(2)
from math import sqrt, pi   # si usa sqrt(2) direttamente
from math import *          # importa tutto: sconsigliato (nomi che si sovrascrivono)

Definizione (blocco principale di un modulo). La variabile __name__ vale "__main__" nel file avviato da riga di comando e il nome del modulo negli altri casi. Il blocco finale serve a mettere nello stesso file funzioni riusabili e codice di prova.

Definizione (moduli più usati della libreria standard)

Modulo	Contenuto
math	funzioni matematiche, costanti, isclose, gcd
random	random(), randint(a, b) (estremi inclusi), choice, shuffle, seed
sys	sys.argv (argomenti da riga di comando), sys.exit(), sys.getrecursionlimit()
os, pathlib	file e cartelle, percorsi
time	time.perf_counter() per misurare tempi (vedi Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →)
collections	deque, Counter, defaultdict (vedi Pila e codaPila (LIFO) e coda (FIFO) come ADT: operazioni e costi; realizzazione in Python con list e collections.deque; realizzazione in C con array e indici, coda circolare; applicazioni (parentesi bilanciate, stack delle chiamate, visite).Pila e coda →, Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →)
csv	lettura/scrittura di file CSV (vedi File di testo in Pythonopen con modalità e codifica, il costrutto with, lettura riga per riga, read e readlines, scrittura con write e print, percorsi relativi, file CSV con il modulo csv.File di testo in Python →)
copy	copy.deepcopy (vedi Liste in Pythonlist come sequenza mutabile (array dinamico); indici, slicing e assegnamento a fette; metodi e loro costo; aliasing, copia superficiale e profonda; list comprehension; liste annidate e matrici.Liste in Python →)
unittest	test automatici (vedi Debugging e testingTipi di errore, metodo per localizzare un bug, lettura del traceback, stampe di controllo, debugger (VS Code, pdb, gdb), assert e strumenti per la memoria in C; test di unità, casi limite e partizioni, doctest e unittest.Debugging e testing →)

V. Stringhe, liste e tuple

Stringhe in Python

Definizione (str). Il tipo è str: sequenza immutabile di caratteri Unicode (vedi Rappresentazione binaria dei datiBasi 2, 8 e 16; interi senza segno e in complemento a 2 con overflow; virgola mobile IEEE 754 e sue approssimazioni; caratteri ASCII, Unicode e UTF-8.Rappresentazione binaria dei dati →). Non esiste un tipo carattere: un carattere è una stringa di lunghezza 1.

Definizione (indici e slicing)

s = "ciao mondo"
s[0], s[-1]          # ('c', 'o')
s[5:]                # 'mondo'
s[:4]                # 'ciao'
s[2:7]               # 'ao mo'  (indice 7 escluso)
s[::2]               # 'ca od'  (passo 2)
s[::-1]              # 'odnom oaic'  (rovesciata)

• s[i] con i fuori intervallo → IndexError; lo slicing invece non dà mai errore (s[100:] è "").
• s[i:j] ha lunghezza j - i (per indici validi).
• s[0] = "C" → TypeError: le stringhe sono immutabili. Si costruisce una stringa nuova: "C" + s[1:].

Definizione (metodi principali delle stringhe)

Metodo	Esempio	Risultato
upper(), lower(), capitalize(), title()	"ciao".upper()	'CIAO'
strip(), lstrip(), rstrip()	" x \n".strip()	'x'
split(sep)	"a,b,,c".split(",")	['a', 'b', '', 'c']
split() senza argomenti	" a b ".split()	['a', 'b'] (spazi multipli)
sep.join(seq)	"-".join(["a", "b"])	'a-b'
find(sub), index(sub)	"ciao".find("a")	2 (find dà -1 se manca, index solleva ValueError)
count(sub)	"banana".count("a")	3
replace(old, new)	"aaa".replace("a", "b", 2)	'bba'
startswith(), endswith()	"file.py".endswith(".py")	True
isdigit(), isalpha(), isspace(), isupper()	"123".isdigit()	True

Definizione (specificatori delle f-string). Specificatori dopo :: allineamento (<, >, ^), larghezza, .n cifre decimali, tipo (d intero, f virgola fissa, e esponenziale, % percentuale). Il metodo "{}".format(x) fa la stessa cosa con sintassi più vecchia.

Liste in Python

Definizione (lista mutabile). Indici, indici negativi, slicing, len, in, +, * funzionano come per le Stringhe in Pythonstr come sequenza immutabile di caratteri Unicode; indici e slicing; operatori; metodi principali (split, join, strip, find, replace...); f-string e formattazione; confronto lessicografico.Stringhe in Python →. La differenza è che la lista è mutabile:

numeri[0] = 10           # [10, 1, 4, 1, 5]
numeri[1:3] = [7, 7, 7]  # assegnamento a una fetta: [10, 7, 7, 7, 1, 5]
del numeri[0]            # [7, 7, 7, 1, 5]

Proprietà (metodi delle liste e loro costo)

Operazione	Effetto	Costo
l[i], l[i] = x	lettura/scrittura per indice	$O(1)$
l.append(x)	aggiunge in fondo	$O(1)$ ammortizzato
l.pop()	toglie e restituisce l'ultimo	$O(1)$
l.pop(i), l.insert(i, x)	toglie/inserisce in posizione i, sposta gli elementi successivi	$O(n)$
l.remove(x)	toglie la prima occorrenza di x (ValueError se manca)	$O(n)$
x in l, l.index(x), l.count(x)	ricerca lineare	$O(n)$
l.extend(seq)	aggiunge tutti gli elementi di seq	$O(k)$
l.sort()	ordina sul posto, restituisce None	$O(n \log n)$
l.reverse()	rovescia sul posto	$O(n)$
sorted(l), reversed(l)	nuova lista ordinata / iteratore al contrario
min(l), max(l), sum(l)		$O(n)$

Definizione (copia superficiale e profonda). Copia superficiale: nuova lista, ma gli elementi sono gli stessi oggetti. Con liste annidate non basta:

import copy
m = [[1, 2], [3, 4]]
s = m.copy()
s[0][0] = 99       # modifica anche m[0][0]: le righe sono condivise
d = copy.deepcopy(m)   # copia profonda: anche le righe sono nuove

Definizione (list comprehension). [espressione for x in iterabile if condizione] costruisce una nuova lista.

Tuple e unpacking

Definizione (tupla). Una tuple è una sequenza immutabile di oggetti qualsiasi.

p = (3, 4)
q = 3, 4             # le parentesi sono facoltative: è la virgola che crea la tupla
singola = (5,)       # tupla di un elemento: serve la virgola; (5) è solo l'intero 5
vuota = ()
t = tuple([1, 2])    # da lista

Proprietà (tuple hashable come chiavi di dizionario). Le tuple sono hashable (se lo sono i loro elementi) e quindi possono essere chiavi di dizionario o elementi di insieme; le liste no (vedi Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →).

distanze = {("Padova", "Venezia"): 37, ("Padova", "Verona"): 85}

Definizione (unpacking)

x, y = p                     # x = 3, y = 4
a, b = b, a                  # scambio: a destra si crea la tupla (b, a)
nome, _, voto = ("Ada", "Lovelace", 30)   # _ per un valore da ignorare
primo, *resto = [1, 2, 3, 4]              # primo = 1, resto = [2, 3, 4]
*inizio, ultimo = "ciao"                  # inizio = ['c', 'i', 'a'], ultimo = 'o'

Il numero di nomi deve corrispondere al numero di elementi (salvo l'asterisco): altrimenti ValueError: too many values to unpack.

VI. Input/Output ed eccezioni

Input e output da console

Definizione (flussi standard)

Flusso	Python	C	Di default
standard input	sys.stdin	stdin	tastiera
standard output	sys.stdout	stdout	schermo
standard error	sys.stderr	stderr	schermo

Definizione (input). input(prompt) stampa il prompt, legge una riga fino all'invio e la restituisce senza il carattere di a capo, sempre come str.

Definizione (print). print(*oggetti, sep=" ", end="\n", file=sys.stdout) converte ogni oggetto con str(), li separa con sep e termina con end.

File di testo in Python

Definizione (modalità di apertura di un file)

Modalità	Significato
"r"	lettura (default); FileNotFoundError se il file non esiste
"w"	scrittura; crea o svuota il file
"a"	aggiunta in fondo; crea il file se non esiste
"x"	creazione; errore se il file esiste già
"b" aggiunto ("rb", "wb")	modalità binaria: si leggono bytes, non str

Definizione (istruzione with)

with open("dati.txt", encoding="utf-8") as f:
    for riga in f:
        ...
# qui il file è già chiuso, anche se nel blocco è stata sollevata un'eccezione

with chiude il file automaticamente: è la forma da usare sempre.

Proprietà (scrittura con write e print)

with open("out.txt", "w", encoding="utf-8") as f:
    f.write("prima riga\n")          # write non aggiunge "\n" e accetta solo str
    f.write(str(42) + "\n")
    print("con print", 3.5, file=f)  # print aggiunge spazi e "\n" e converte da solo

Eccezioni in Python

Definizione (eccezione). Un'eccezione è un oggetto che segnala un errore a tempo di esecuzione. Quando viene sollevata, l'esecuzione normale si interrompe e l'eccezione risale lo stack delle chiamate finché qualcuno la gestisce; se nessuno la gestisce il programma termina stampando il traceback (sequenza delle chiamate, dalla più esterna alla riga dell'errore, e in fondo tipo e messaggio).

Definizione (eccezioni comuni)

Eccezione	Causa tipica
NameError	nome non definito (refuso, variabile non ancora assegnata)
TypeError	operazione su un tipo sbagliato ("a" + 1, None + 1, numero di argomenti errato)
ValueError	tipo giusto, valore inammissibile (int("abc"))
IndexError	indice fuori dalla sequenza
KeyError	chiave assente in un dizionario
ZeroDivisionError	divisione o modulo per zero
AttributeError	metodo o attributo inesistente (lista.push(1))
FileNotFoundError	file da leggere inesistente
RecursionError	ricorsione troppo profonda (vedi RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →)

Proprietà (ordine dei rami except)

• I rami except vengono provati in ordine: il primo compatibile vince.
• Nel try mettere solo le istruzioni che possono sollevare l'eccezione attesa.

Definizione (raise). Una funzione che riceve argomenti non validi non deve stampare un messaggio e proseguire: deve segnalare l'errore al chiamante.

File di record e controllo degli errori riga per riga

Proprietà (controllo di ogni riga di un file di record)

• enumerate(f, start=1) dà il numero di riga senza contatore a mano.
• strip() toglie il '\n' finale e gli spazi; senza, "12\n" è accettato da int ma "Rossi\n" finisce nei dati.
• Una sola try può coprire più conversioni; se serve distinguere il tipo di errore si usano più except: split con troppi o pochi campi e int("abc") sollevano entrambi ValueError, mentre riga.split()[1] su una riga con un solo campo solleva IndexError.
• I messaggi vanno su sys.stderr, i risultati su sys.stdout: così si possono separare con le ridirezioni della shell (2> errori.txt).
• int("3.5") è un errore, float("3.5") no: scegliere la conversione dal tipo del campo; float("") e float("1,5") sono ValueError (la virgola decimale non esiste).

Proprietà (file inesistente: FileNotFoundError). Un file che non esiste solleva FileNotFoundError: va gestita attorno all'open, non dentro il ciclo.

Proprietà (in C si controllano i valori restituiti)

• fgets restituisce NULL a fine file; legge al più n - 1 caratteri e tiene il '\n'.
• strtol(s, &fine, 10) converte e mette in fine il primo carattere non convertito: fine == s significa nessuna cifra, *fine != '\0' significa caratteri in più ("12abc"). atoi non segnala errori e restituisce 0 per "abc": da evitare per dati non fidati.
• sscanf(riga, "%31[^:]:%d", nome, &costo) è più corto ma non distingue "Rossi:12abc" da "Rossi:12"; restituisce il numero di campi letti, da confrontare con quelli attesi (== 2).
• Con fscanf(f, "%d", &x) si legge un numero alla volta: il ciclo è while (fscanf(...) == 1), mai while (!feof(f)).
• fopen restituisce NULL se il file non si apre: controllare sempre, e stampare perror.

VII. Pattern algoritmici e complessità

Pattern algoritmici iterativi

Definizione (schema dell'accumulatore). Variabile inizializzata all'elemento neutro dell'operazione e aggiornata a ogni elemento.

somma = 0                      # neutro della somma
prodotto = 1                   # neutro del prodotto
testo = ""                     # neutro della concatenazione
for x in valori:
    somma += x
    prodotto *= x

Invariante: dopo $k$ iterazioni somma è la somma dei primi $k$ elementi.

Definizione (schema del contatore)

conta = 0
for x in valori:
    if x > soglia:
        conta += 1
# equivalente: conta = sum(1 for x in valori if x > soglia)

Definizione (schema del massimo e del minimo). Si inizializza con il primo elemento, non con 0 (i valori potrebbero essere tutti negativi).

def indice_massimo(v):
    """Indice del massimo di una lista non vuota."""
    im = 0
    for i in range(1, len(v)):
        if v[i] > v[im]:
            im = i
    return im

> restituisce la prima occorrenza del massimo, >= l'ultima.

Definizione (ricerca con uscita anticipata)

def contiene_negativo(v):
    for x in v:
        if x < 0:
            return True        # basta un esempio: esco subito
    return False               # solo dopo aver visto tutto

Definizione (verifica universale)

def tutti_positivi(v):
    for x in v:
        if x <= 0:
            return False       # basta un controesempio
    return True

Equivalenti predefiniti: any(x < 0 for x in v), all(x > 0 for x in v). Errore classico: mettere return True dentro il ciclo nel ramo else, decidendo dopo il primo elemento.

Definizione (finestra scorrevole). Somma di ogni blocco di k elementi consecutivi aggiornando invece di ricalcolare ($O(n)$ invece di $O(nk)$):

def max_somma_finestra(v, k):
    s = sum(v[:k])
    migliore = s
    for i in range(k, len(v)):
        s += v[i] - v[i - k]       # entra v[i], esce v[i-k]
        migliore = max(migliore, s)
    return migliore

Ricorsione

Definizione (funzione ricorsiva). Una funzione è ricorsiva se chiama se stessa. Si scrive come una dimostrazione per induzione:

• caso base: input abbastanza piccolo da risolvere direttamente;
• passo ricorsivo: si riduce il problema a uno (o più) problemi dello stesso tipo più piccoli e si combina il risultato.

def fattoriale(n):
    """n! per n >= 0."""
    if n == 0:                 # caso base
        return 1
    return n * fattoriale(n - 1)   # passo: problema di taglia n-1

Per essere corretta: ogni chiamata deve avvicinarsi al caso base e il caso base deve essere sempre raggiunto.

Proprietà (limite della profondità di ricorsione). Lo stack ha dimensione limitata: in Python il limite predefinito è circa 1000 chiamate annidate (sys.getrecursionlimit()), oltre si ottiene RecursionError. Senza caso base (o con un caso base mai raggiunto, es. fattoriale(-1)) la ricorsione è infinita. In C lo stack esaurito provoca un stack overflow (vedi Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Proprietà (ricorsione multipla: chiamate di fib)

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

L'albero delle chiamate ricalcola gli stessi valori moltissime volte: il numero di chiamate cresce come $\varphi^n$ con $\varphi \approx 1{,}618$ (esponenziale). Rimedi: versione iterativa, oppure memoizzazione (salvare i risultati già calcolati):

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # ora O(n) chiamate

Definizione (divide et impera). Schema: dividere il problema in sottoproblemi indipendenti, risolverli ricorsivamente, combinare. Esempi: ricerca binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria → (un sottoproblema di metà taglia) e merge sort (due sottoproblemi di metà taglia, vedi Algoritmi di ordinamentoSelection sort, insertion sort e bubble sort (quadratici), merge sort (n log n, divide et impera); stabilità, ordinamento sul posto, costo nei vari casi; sort e sorted con key.Algoritmi di ordinamento →).

def massimo(v, lo, hi):
    """Massimo di v[lo:hi], hi > lo."""
    if hi - lo == 1:
        return v[lo]
    m = (lo + hi) // 2
    return max(massimo(v, lo, m), massimo(v, m, hi))

Complessità computazionale

Definizione (caso peggiore, migliore e medio). Si misura il numero di operazioni elementari (assegnamenti, confronti, operazioni aritmetiche, accessi per indice) in funzione della dimensione dell'input $n$ (lunghezza della lista, numero di cifre...). Il tempo in secondi dipende dalla macchina; la crescita al crescere di $n$ no.

• Caso peggiore: massimo numero di operazioni tra gli input di dimensione $n$ (è quello che si dà di solito: è una garanzia).
• Caso migliore: minimo.
• Caso medio: media su una distribuzione degli input.

Definizione (notazione O-grande). $f(n) = O(g(n))$ se esistono $c > 0$ e $n_0$ tali che $f(n) \le c \cdot g(n)$ per ogni $n \ge n_0$: $f$ cresce al più come $g$, a meno di costanti.

Regole pratiche:

• si tiene solo il termine dominante e si tolgono le costanti: $3n^2 + 10n + 7 = O(n^2)$;
• passi in sequenza: si sommano (vince il maggiore);
• cicli annidati: si moltiplicano.

Definizione (classi di crescita)

Classe	Nome	Esempio
$O(1)$	costante	accesso v[i], append
$O(\log n)$	logaritmica	ricerca binaria
$O(n)$	lineare	ricerca lineare, somma, massimo
$O(n \log n)$	quasi lineare	merge sort, sorted
$O(n^2)$	quadratica	selection sort, insertion sort, tutte le coppie
$O(2^n)$	esponenziale	fib ricorsivo ingenuo, tutti i sottoinsiemi

Proprietà (equazioni di ricorrenza del costo). Ricorsione: si scrive l'equazione di ricorrenza del costo $T(n)$.

• fattoriale: $T(n) = T(n-1) + c$ → $O(n)$.
• ricerca binaria: $T(n) = T(n/2) + c$ → $O(\log n)$.
• merge sort: $T(n) = 2T(n/2) + cn$ → $O(n \log n)$.
• fib ingenuo: $T(n) = T(n-1) + T(n-2) + c$ → esponenziale.

Proprietà (effetto del raddoppio di n sul tempo). Raddoppiando $n$: un algoritmo lineare raddoppia il tempo, uno quadratico lo quadruplica.

Ricerca lineare e binaria

Definizione (ricerca lineare). Funziona su qualunque sequenza, anche non ordinata.

def ricerca_lineare(v, x):
    for i in range(len(v)):
        if v[i] == x:
            return i
    return -1

• Caso migliore $O(1)$, caso peggiore $O(n)$ (elemento assente).
• Restituisce la prima occorrenza.
• È ciò che fanno x in v e v.index(x).

Definizione (ricerca binaria). Richiede v ordinata. Si confronta x con l'elemento centrale e si scarta metà dell'intervallo a ogni passo.

def ricerca_binaria(v, x):
    lo, hi = 0, len(v) - 1          # intervallo di ricerca [lo, hi], estremi inclusi
    while lo <= hi:
        m = (lo + hi) // 2
        if v[m] == x:
            return m
        elif v[m] < x:
            lo = m + 1              # x, se c'è, sta a destra di m
        else:
            hi = m - 1              # x, se c'è, sta a sinistra di m
    return -1

Invariante: se x è in v, allora si trova in v[lo..hi]. Il ciclo termina perché a ogni giro l'intervallo si riduce di almeno un elemento (m + 1, m - 1); quando lo > hi l'intervallo è vuoto e x non c'è.

Costo: dopo $k$ iterazioni restano circa $n / 2^k$ elementi, quindi al più $\lfloor \log_2 n \rfloor + 1$ iterazioni: $O(\log n)$. Con $n = 10^6$ bastano 20 confronti.

Definizione (modulo bisect)

import bisect
v = [2, 5, 8, 8, 12]
bisect.bisect_left(v, 8)     # 2: primo indice dove inserire 8 mantenendo l'ordine
bisect.bisect_right(v, 8)    # 4
bisect.insort(v, 7)          # inserimento ordinato: [2, 5, 7, 8, 8, 12]

bisect_left(v, x) restituisce un indice i con v[i] == x se x c'è (e i < len(v)).

Algoritmi di ordinamento

Definizione (proprietà degli algoritmi di ordinamento)

• costo nel caso peggiore, migliore, medio (vedi Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →);
• sul posto (in place): usa solo $O(1)$ memoria aggiuntiva;
• stabile: elementi uguali restano nell'ordine relativo di partenza (conta quando si ordina per una chiave, es. studenti per voto).

Proprietà (selection sort)

• Invariante: v[:i] contiene gli i elementi più piccoli, in ordine.
• Confronti: $n(n-1)/2$ sempre → $O(n^2)$ in tutti i casi. Al più $n - 1$ scambi.
• Sul posto, non stabile.

Proprietà (insertion sort)

• Invariante: v[:i] è ordinata (ma contiene gli elementi originali di v[:i], non i più piccoli).
• Caso peggiore (lista al contrario) $O(n^2)$; caso migliore (già ordinata) $O(n)$: molto buono su liste quasi ordinate.
• Sul posto, stabile (grazie a > stretto nel while).

Proprietà (bubble sort). $O(n^2)$ nel caso peggiore, $O(n)$ se già ordinata; sul posto e stabile. Più lento di insertion sort in pratica.

Proprietà (merge sort: costo e memoria)

• Costo $T(n) = 2T(n/2) + O(n)$ → $O(n \log n)$ in tutti i casi: $\log_2 n$ livelli di ricorsione, ciascuno con lavoro complessivo $O(n)$ per le fusioni.
• Memoria aggiuntiva $O(n)$ (non sul posto); stabile.
• Questa versione restituisce una lista nuova: v = merge_sort(v).

Teorema (limite inferiore per l'ordinamento per confronti). Nessun ordinamento per confronti può fare meglio di $O(n \log n)$ nel caso peggiore.

Definizione (sort e sorted in Python). Nella pratica si usa l'ordinamento predefinito (Timsort: $O(n \log n)$, stabile, $O(n)$ su dati già ordinati).

v.sort()                                  # sul posto, restituisce None
w = sorted(v)                             # nuova lista
sorted(v, reverse=True)                   # decrescente
sorted(parole, key=str.lower)             # ignorando maiuscole/minuscole
sorted(studenti, key=lambda s: (-s[1], s[0]))   # voto decrescente, poi nome

VIII. Il linguaggio C

Dal Python al C

Definizione (struttura di un programma C)

• Il programma inizia sempre da main. Il valore restituito arriva al sistema operativo: 0 = terminato correttamente.
• Le istruzioni finiscono con ;, i blocchi stanno tra { }; l'indentazione serve solo alla leggibilità.
• Commenti: // fino a fine riga e /* su più righe */.
• #include <stdio.h> inserisce le dichiarazioni della libreria di input/output (printf, scanf, ...).

Definizione (dal sorgente all'eseguibile)

1. Preprocessore: esegue le direttive # (#include copia il file indicato, #define sostituisce testo). Lavora sul testo, non conosce il C.
2. Compilatore: traduce ogni file .c in codice macchina (file oggetto .o) e controlla sintassi e tipi.
3. Linker: unisce i file oggetto e le librerie in un unico eseguibile.

Definizione (differenze fondamentali tra Python e C)

	Python	C
Variabile	nome legato a un oggetto	cella di memoria di tipo fisso, contiene direttamente il valore
Dichiarazione	nessuna	obbligatoria prima dell'uso: int x;
Valore iniziale	assegnamento obbligatorio	variabile locale non inizializzata contiene un valore indeterminato
Controlli a run-time	indici, tipi, overflow: eccezioni	quasi nessuno: errori silenziosi o crash (comportamento indefinito)
Stringhe	tipo str	array di char terminato da '\0'
Booleani	bool	int (0 falso, diverso da 0 vero); bool con <stdbool.h>
Liste	list dinamica	array di dimensione fissa
Output	print(x)	printf("%d\n", x) con formato esplicito
Memoria	automatica	stack automatico; heap con malloc/free

Definizione (printf e specificatori di formato). printf(formato, valori...): il formato contiene testo e specificatori che devono corrispondere, per numero e tipo, ai valori passati.

Specificatore	Tipo
%d	int
%ld	long
%u	unsigned int
%f (%.2f)	double (anche float, promosso)
%c	char
%s	stringa (char *)
%p	puntatore
%x	intero in esadecimale
%%	il carattere %

Tipi, operatori e controllo del flusso in C

Definizione (tipi fondamentali del C)

Tipo	Dimensione tipica	Intervallo tipico
char	1 byte	−128…127 (o 0…255)
short	2 byte	−32 768…32 767
int	4 byte	circa ±2,1 miliardi ($-2^{31} \dots 2^{31}-1$)
long	4 o 8 byte
long long	8 byte	circa $\pm 9{,}2 \cdot 10^{18}$
float	4 byte	7 cifre significative
double	8 byte	15–16 cifre significative

• Le dimensioni dipendono dalla piattaforma: sizeof(tipo) le dà in byte; i limiti sono in <limits.h> (INT_MAX, INT_MIN).
• unsigned davanti a un tipo intero: solo valori non negativi, intervallo doppio ($0 \dots 2^{32}-1$ per unsigned int).

Definizione (divisione intera e reale in C)

• Tra due interi / è divisione intera, troncata verso zero: 7 / 2 == 3, -7 / 2 == -3, -7 % 2 == -1.
• Basta un operando reale per avere la divisione reale: 7 / 2.0 == 3.5, (double)a / b.

Definizione (conversioni implicite ed esplicite)

• Implicite: negli operatori aritmetici il tipo "più piccolo" viene promosso al più grande (int → long → float → double); char e short diventano int. Nell'assegnamento il valore si converte al tipo della variabile, con possibile perdita (int i = 3.99; → 3).
• Esplicite (cast): (tipo)espressione.
• Mescolare int e unsigned nei confronti dà sorprese: -1 < 0u è falso perché -1 diventa un unsigned enorme.

Definizione (incremento e decremento)

i++;        /* i = i + 1 */
x = i++;    /* x prende il valore VECCHIO di i, poi i aumenta */
x = ++i;    /* prima i aumenta, poi x prende il nuovo valore */

Definizione (operatori bit a bit). & (and), | (or), ^ (xor), ~ (not), <<, >> (spostamenti): x << k vale $x \cdot 2^k$ per valori non negativi senza overflow; x & 1 è il bit meno significativo (pari/dispari). Non confondere & con &&.

Proprietà (fall-through dello switch). Senza break l'esecuzione prosegue nel case successivo (fall-through).

Funzioni in C

Definizione (funzione C, tipo di ritorno e prototipo)

• Ogni funzione ha un tipo di ritorno e parametri con tipo. void come tipo di ritorno: non restituisce niente; (void) come parametri: nessun parametro.
• Una funzione va dichiarata prima dell'uso: o la si definisce sopra main, o si scrive prima il prototipo (intestazione seguita da ;).
• Gli argomenti vengono convertiti al tipo dei parametri (media(3.9, 4) passa 3).
• Si restituisce un solo valore. Per "restituire" più risultati si usano parametri puntatore (vedi Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →) o una struct (vedi Strutture (struct) in Cstruct per raggruppare campi di tipo diverso, typedef, accesso con punto e freccia, struct come parametri e valori di ritorno, array di struct, struct allocate dinamicamente e struct autoreferenziali.Strutture (struct) in C →).

Definizione (passaggio per valore in C). In C gli argomenti sono sempre copiati nei parametri: modificare un parametro non modifica la variabile del chiamante.

Definizione (ambito e durata delle variabili in C)

Tipo di variabile	Dove si dichiara	Visibilità	Durata
locale (automatica)	dentro un blocco { }	dal punto di dichiarazione alla fine del blocco	dall'ingresso all'uscita del blocco (sullo stack)
parametro	intestazione	corpo della funzione	come le locali
globale	fuori da ogni funzione	tutto il file (dal punto di dichiarazione)	intero programma
locale static	dentro una funzione con static	la funzione	intero programma: conserva il valore tra le chiamate

Array e stringhe in C

Definizione (array in C)

• Indici da 0 a N - 1; v[i] si trova all'indirizzo v + i * sizeof(int), per questo l'accesso è $O(1)$.
• Nessun controllo degli indici: v[N] o v[-1] leggono/scrivono memoria altrui (comportamento indefinito: valori casuali, crash, variabili vicine modificate).
• Non si può assegnare un array a un altro (w = v; è un errore) né confrontarli con ==: si copia elemento per elemento.
• sizeof(w) / sizeof(w[0]) dà il numero di elementi, ma solo dove l'array è dichiarato, non dentro una funzione che lo riceve.

Proprietà (array passato a una funzione). Il nome di un array, in quasi tutte le espressioni, vale l'indirizzo del primo elemento (vedi Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →). Passandolo a una funzione si passa quell'indirizzo:

int somma(const int v[], int n) {    /* equivalente a: const int *v */
    int s = 0;
    for (int i = 0; i < n; i++)
        s += v[i];
    return s;
}

void azzera(int v[], int n) {        /* modifica l'array del chiamante */
    for (int i = 0; i < n; i++)
        v[i] = 0;
}

/* chiamate: somma(w, 5); azzera(w, 5); */

Definizione (stringa C). Una stringa C è un array di char che termina con il carattere nullo '\0' (valore 0). La lunghezza non è memorizzata: si conta fino a '\0'.

Definizione (funzioni di string.h)

Funzione	Effetto
strlen(s)	numero di caratteri prima di '\0' ($O(n)$)
strcpy(dst, src)	copia src in dst (dst deve essere abbastanza grande)
strncpy(dst, src, n)	copia al più n caratteri (può non aggiungere '\0')
strcat(dst, src)	accoda src a dst
strcmp(a, b)	< 0, 0, > 0 se a precede, è uguale, segue b (ordine dei codici)
strchr(s, c), strstr(s, sub)	puntatore alla prima occorrenza, o NULL

Input e output in C

Definizione (formato di printf). Forma generale %[flag][larghezza][.precisione]tipo: - allinea a sinistra, 0 riempie con zeri. Specificatori principali in Dal Python al CStruttura di un programma C, compilazione con gcc (preprocessore, compilatore, linker), main e valore di ritorno, dichiarazioni con tipo statico, printf di base; corrispondenze con Python.Dal Python al C →.

Proprietà (scanf: spazi bianchi, %s e valore di ritorno)

• scanf salta gli spazi bianchi prima di %d, %lf, %s (non prima di %c: per saltarli si scrive " %c").
• %s legge una parola (si ferma al primo spazio); la larghezza (%31s) evita di scrivere oltre l'array, lasciando posto a '\0'.
• Valore di ritorno: numero di valori letti con successo, oppure EOF a fine input. Va controllato:

int a, b;
if (scanf("%d %d", &a, &b) != 2) {
    fprintf(stderr, "input non valido\n");
    return 1;
}

/* somma di interi fino a fine input */
int x, somma = 0;
while (scanf("%d", &x) == 1)
    somma += x;

Definizione (fgets). fgets(buf, n, flusso) legge al più n - 1 caratteri fino a '\n' incluso e aggiunge '\0'; restituisce NULL a fine file o in caso di errore. Non usare mai gets (eliminata dallo standard: non controlla la dimensione). Da una riga letta si estraggono i valori con sscanf(riga, "%d %d", &a, &b).

IX. Puntatori e memoria in C

Puntatori in C

Definizione (puntatore, operatori di indirizzo e dereferenziazione). Ogni variabile occupa celle di memoria con un indirizzo (vedi Struttura di un elaboratoreModello di von Neumann: CPU, memoria centrale, bus e periferiche; ciclo fetch-decode-execute e gerarchia di memoria.Struttura di un elaboratore →). Un puntatore è una variabile che contiene un indirizzo; il suo tipo dice a quale tipo di dato punta.

Proprietà (aritmetica dei puntatori). Se p punta a un elemento di un array, p + k punta al k-esimo elemento successivo: l'indirizzo aumenta di k * sizeof(*p) byte, non di k.

Proprietà (const e puntatori)

const int *p;        /* puntatore a int costante: *p = 1 vietato, p = &y permesso */
int *const q = &x;   /* puntatore costante: q non può cambiare, *q sì */

Nei parametri const T * documenta (e fa verificare al compilatore) che la funzione non modifica i dati puntati.

Gestione della memoria in C

Definizione (segmenti di memoria di un processo)

Segmento	Contenuto	Gestione	Durata
Codice (text)	istruzioni macchina	caricato dal sistema operativo	intero programma
Dati statici	variabili globali e static, letterali stringa	allocati all'avvio, inizializzati a zero se non indicato	intero programma
Stack	record di attivazione: parametri, variabili locali, indirizzo di ritorno	automatica: cresce a ogni chiamata, si libera al ritorno	fino alla fine della funzione/blocco
Heap	memoria allocata dinamicamente	manuale: malloc / free	finché non si chiama free

Definizione (malloc, calloc, realloc e free)

Funzione	Effetto
malloc(byte)	alloca byte byte non inizializzati; restituisce void * o NULL
calloc(n, dim)	alloca n elementi di dim byte, azzerati
realloc(p, nuovi_byte)	ridimensiona il blocco; può spostarlo e restituire un nuovo indirizzo (copiando il contenuto); NULL se fallisce, nel qual caso il vecchio blocco resta valido
free(p)	libera un blocco ottenuto da malloc/calloc/realloc; free(NULL) non fa niente

Proprietà (array che cresce raddoppiando la capacità). Raddoppiando la capacità, il costo totale delle copie su n inserimenti è $O(n)$: è lo stesso meccanismo delle Liste in Pythonlist come sequenza mutabile (array dinamico); indici, slicing e assegnamento a fette; metodi e loro costo; aliasing, copia superficiale e profonda; list comprehension; liste annidate e matrici.Liste in Python →.

Strutture (struct) in C

Definizione (struct). Una struct raggruppa in un unico tipo più campi di tipo anche diverso (come una tupla con nomi o un semplice oggetto Python con soli attributi).

Proprietà (assegnazione e dimensione di una struct)

• Una struct si può assegnare (q = p; copia tutti i campi, anche gli array interni) ma non confrontare con ==.
• sizeof(Studente) può essere maggiore della somma dei campi per l'allineamento in memoria (padding).

Definizione (struct passate a funzioni). Una struct passata per valore viene copiata per intero; per modificarla o per evitare la copia di strutture grandi si passa un puntatore. Con un puntatore i campi si raggiungono con ->: ps->media equivale a (*ps).media.

Definizione (struct autoreferenziale). Una struct non può contenere se stessa, ma può contenere un puntatore al proprio tipo. È la base delle strutture collegate:

typedef struct nodo {
    int valore;
    struct nodo *succ;     /* serve il nome "struct nodo": il typedef non è ancora completo */
} Nodo;

Ordinare e cercare in C - qsort, bsearch e puntatori a funzione

Definizione (puntatore a funzione). Il nome di una funzione, senza parentesi, è il suo indirizzo. Un puntatore a funzione si dichiara indicando firma e nome tra parentesi tonde con *:

#include <stdio.h>

int somma(int a, int b) { return a + b; }
int prodotto(int a, int b) { return a * b; }

int applica(int (*f)(int, int), int x, int y) {   /* f: puntatore a funzione */
    return f(x, y);                                /* chiamata tramite il puntatore */
}

int main(void) {
    printf("%d %d\n", applica(somma, 3, 4), applica(prodotto, 3, 4));   /* 7 12 */
    return 0;
}

Definizione (qsort e funzione di confronto)

• base: indirizzo del primo elemento; n: numero di elementi; dim: dimensione in byte di un elemento (sizeof v[0]).
• cmp(a, b) riceve puntatori agli elementi (come const void *) e restituisce un numero < 0, 0 o > 0 se *a va prima, pari o dopo *b. Si converte il puntatore al tipo vero dell'elemento.

Definizione (bsearch). Ricerca binaria (Ricerca lineare e binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria →) in $O(\log n)$: restituisce il puntatore all'elemento trovato o NULL. L'array deve essere già ordinato con lo stesso cmp. La chiave è un puntatore a un elemento "di prova" (anche un Voce con solo il campo chiave riempito); l'indice si ricava con la differenza di puntatori.

X. Tipi di dato astratti

Tipi di dato astratti

Definizione (tipo di dato astratto). Un tipo di dato astratto (ADT, abstract data type) è un insieme di valori più un insieme di operazioni su di essi, descritto solo da che cosa fanno le operazioni, non da come sono realizzate.

• Interfaccia: nomi, parametri, risultati e comportamento atteso (con precondizioni) delle operazioni.
• Implementazione: rappresentazione concreta dei dati (array, struct, lista collegata...) e codice delle operazioni.
• Incapsulamento: chi usa l'ADT accede ai dati solo tramite le operazioni. Si può cambiare l'implementazione senza toccare il codice che la usa.

Definizione (classe, costruttore e metodi speciali)

• Frazione(1, 2) crea l'oggetto e chiama __init__ con self = il nuovo oggetto.
• a.numeratore() equivale a Frazione.numeratore(a).
• I metodi "speciali" con doppio trattino basso (__add__, __eq__, __str__, __len__, __lt__, ...) collegano l'ADT agli operatori e alle funzioni predefinite.
• Python non impedisce l'accesso agli attributi: il prefisso _ è una convenzione di incapsulamento.
• L'invariante della classe (qui: frazione ridotta, den > 0) è stabilito dal costruttore e mantenuto da ogni operazione; per questo i dati non vanno modificati dall'esterno.

Classi ed ereditarietà in Python

Definizione (attributi di classe e di istanza, metodi di classe e statici)

• Un attributo di classe è l'analogo di un attributo static di altri linguaggi: si legge anche da un'istanza, ma a.n_conti = 7 crea un attributo di istanza che oscura quello di classe senza modificarlo.
• @staticmethod è una funzione "dentro" la classe solo per raggruppamento; @classmethod serve per costruttori alternativi, che con l'ereditarietà creano la sottoclasse giusta.
• Un metodo di istanza ha sempre un parametro implicito, self; se manca nella definizione, la chiamata a.versa(5) fallisce con TypeError.

Definizione (proprietà con @property). @property fa sembrare un attributo un metodo con controllo:

class Cerchio:
    def __init__(self, r):
        self.raggio = r               # passa dal setter

    @property
    def raggio(self):
        return self._r

    @raggio.setter
    def raggio(self, r):
        if r < 0:
            raise ValueError("raggio negativo")
        self._r = r

    @property
    def area(self):                   # sola lettura: calcolata ogni volta
        return 3.14159 * self._r ** 2

Definizione (ereditarietà e override). class Sotto(Sopra): la sottoclasse eredita attributi e metodi, può aggiungerne e ridefinirli (override: stesso nome, stessa interfaccia). super() raggiunge la versione della superclasse.

Definizione (polimorfismo). Lo stesso messaggio, comportamenti diversi: il metodo eseguito dipende dalla classe effettiva dell'oggetto, scelta a tempo di esecuzione.

Pila e coda

Definizione (pila, LIFO). Last In, First Out: esce per primo l'ultimo elemento inserito.

Operazione	Effetto
push(x)	inserisce x in cima
pop()	toglie e restituisce l'elemento in cima (errore se vuota)
top() / peek()	restituisce l'elemento in cima senza toglierlo
is_empty(), size()

Tutte $O(1)$ con una buona implementazione.

Definizione (controllo delle parentesi bilanciate con una pila)

def bilanciata(s):
    coppie = {")": "(", "]": "[", "}": "{"}
    pila = []
    for c in s:
        if c in "([{":
            pila.append(c)
        elif c in coppie:
            if not pila or pila.pop() != coppie[c]:
                return False
    return not pila           # alla fine non devono restare aperte

bilanciata("a[(b)+c]")        # True
bilanciata("(]")              # False

Definizione (coda, FIFO). First In, First Out: esce per primo l'elemento inserito da più tempo.

Operazione	Effetto
enqueue(x)	inserisce in fondo
dequeue()	toglie e restituisce il primo (errore se vuota)
first()	restituisce il primo senza toglierlo
is_empty(), size()

Definizione (coda circolare su array). Due indici, testa (primo elemento) e numero di elementi n; le posizioni "girano" con il modulo, così non serve spostare elementi.

Liste concatenate

Definizione (lista concatenata). Una lista concatenata (linked list) è una sequenza di nodi; ogni nodo contiene un valore e il puntatore al nodo successivo. Il primo nodo è indicato da un puntatore testa; l'ultimo ha successivo NULL.

Proprietà (liste concatenate e array: costi a confronto)

Operazione	Array (o lista Python)	Lista concatenata
accesso al k-esimo elemento	$O(1)$	$O(k)$: bisogna scorrere
inserimento/rimozione in testa	$O(n)$ (spostamenti)	$O(1)$
inserimento/rimozione dopo un nodo noto	$O(n)$	$O(1)$
inserimento in fondo	$O(1)$ ammortizzato	$O(n)$, oppure $O(1)$ tenendo un puntatore alla coda
ricerca	$O(n)$ ($O(\log n)$ se ordinato)	$O(n)$, anche se ordinata
memoria	contigua, compatta	un puntatore in più per elemento

Definizione (inserimento in testa). La funzione deve modificare il puntatore testa del chiamante: o lo restituisce, o riceve un puntatore a puntatore (Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →).

/* versione che restituisce la nuova testa */
Nodo *inserisci_testa(Nodo *testa, int x) {
    Nodo *n = malloc(sizeof *n);
    if (n == NULL) return testa;      /* allocazione fallita: lista invariata */
    n->valore = x;
    n->succ = testa;
    return n;
}

/* versione con puntatore a puntatore */
void inserisci_testa2(Nodo **pt, int x) {
    Nodo *n = malloc(sizeof *n);
    if (n == NULL) return;
    n->valore = x;
    n->succ = *pt;
    *pt = n;
}

Definizione (rimozione di un nodo da una lista).

/* rimuove la prima occorrenza di x; restituisce la nuova testa */
Nodo *rimuovi(Nodo *testa, int x) {
    Nodo *prec = NULL, *cur = testa;
    while (cur != NULL && cur->valore != x) {
        prec = cur;
        cur = cur->succ;
    }
    if (cur == NULL) return testa;         /* non trovato */
    if (prec == NULL) testa = cur->succ;   /* era il primo */
    else prec->succ = cur->succ;           /* scavalca cur */
    free(cur);
    return testa;
}

Dizionari e insiemi in Python

Definizione (ADT mappa e insieme)

• Mappa (dizionario): associa a ogni chiave un valore; operazioni: inserire/aggiornare una coppia, cercare il valore di una chiave, togliere una chiave, scorrere le coppie.
• Insieme: collezione senza duplicati e senza ordine; operazioni: aggiungere, togliere, verificare l'appartenenza, unione, intersezione, differenza.

Definizione (dict: operazioni principali)

voti = {"Ada": 30, "Alan": 27}
vuoto = {}                            # dizionario vuoto (NON un insieme)
d = dict(a=1, b=2)
quadrati = {x: x * x for x in range(5)}   # dict comprehension

voti["Grace"] = 29        # inserisce
voti["Ada"] = 28          # aggiorna: una chiave compare una volta sola
voti["Ada"]               # 28
voti["Bob"]               # KeyError
voti.get("Bob")           # None
voti.get("Bob", 0)        # 0: valore di default
"Ada" in voti             # True: cerca tra le CHIAVI
del voti["Alan"]
voti.pop("Grace")         # toglie e restituisce 29
len(voti)

Proprietà (chiavi hashable). Le chiavi devono essere hashable (immutabili): int, float, str, tuple di immutabili. Una list non può essere chiave (TypeError: unhashable type); i valori invece possono essere qualsiasi cosa.

Definizione (schemi tipici con i dizionari)

# conteggio delle frequenze
freq = {}
for parola in testo.split():
    freq[parola] = freq.get(parola, 0) + 1

# raggruppamento
per_iniziale = {}
for nome in nomi:
    per_iniziale.setdefault(nome[0], []).append(nome)

# chiave con valore massimo
piu_frequente = max(freq, key=freq.get)

# inversione (valori distinti)
inverso = {v: k for k, v in d.items()}

Definizione (operazioni sugli insiemi)

Operazione	Operatore	Metodo
unione	a | b	a.union(b)
intersezione	a & b	a.intersection(b)
differenza	a - b	a.difference(b)
differenza simmetrica	a ^ b	a.symmetric_difference(b)
sottoinsieme	a <= b	a.issubset(b)

Proprietà (dict e set come tabelle hash). dict e set sono tabelle hash: un array di celle in cui la posizione di una chiave è calcolata da hash(chiave) modulo la dimensione dell'array. Ricerca, inserimento e rimozione costano quindi $O(1)$ in media, indipendentemente dal numero di elementi; due chiavi nella stessa cella (collisione) vengono gestite cercando un'altra cella. Quando la tabella si riempie viene ingrandita e le chiavi ridistribuite (costo ammortizzato, come l'append delle liste).

Per questo le chiavi devono essere immutabili: se una chiave cambiasse dopo l'inserimento, il suo hash cambierebbe e non verrebbe più trovata.

	list	set / dict
x in ...	$O(n)$	$O(1)$ medio
ordine e indici	sì	no (il dict mantiene l'ordine di inserimento)
duplicati	ammessi	no (chiavi uniche)

Realizzare contenitori su array e liste

Proprietà (raddoppio della capacità: costo ammortizzato). Costo: una append che ridimensiona costa $O(n)$, ma succede dopo $1, 2, 4, 8, \dots$ inserimenti; in $m$ inserimenti le copie totali sono $1 + 2 + 4 + \dots < 2m$, quindi $O(1)$ ammortizzato per inserimento. Con un incremento costante (capacità $+1$ o $+10$) le copie sono invece $O(m^2)$ in totale. È il meccanismo di list in Python e di realloc in C (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Proprietà (costi del dizionario su array ordinato). Costi: cerca $O(\log n)$; inserisci e cancella $O(n)$ per gli spostamenti (la ricerca del posto è comunque $O(\log n)$). Su un array non ordinato la ricerca è $O(n)$, e anche l'inserimento lo è, perché prima bisogna verificare che la chiave non ci sia già. La tabella hash di dict (Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →) dà $O(1)$ medio per tutte le operazioni ma non mantiene l'ordine delle chiavi.

Proprietà (coda doppia su array circolare). Tutte le operazioni sono $O(1)$ tranne il raddoppio, ammortizzato $O(1)$. In C la formula è identica, ma attenzione: (t - 1) % cap con t = 0 dà $-1$ in C (il resto ha il segno del dividendo); si scrive (t + cap - 1) % cap. L'alternativa è la lista doppiamente concatenata (Liste concatenateLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate →) con puntatori a testa e coda: $O(1)$ senza raddoppi, ma un puntatore in più per elemento. collections.deque è già una coda doppia.

Proprietà (coda con priorità a livelli). A parità di priorità l'ordine è FIFO. Con priorità arbitrarie si usa uno heap (heapq): inserimento ed estrazione $O(\log n)$.

XI. Debugging e testing

Debugging e testing

Definizione (tipi di errore)

Tipo	Quando emerge	Esempio
sintattico	prima dell'esecuzione (Python) / in compilazione (C)	: mancante, ; mancante
di tipo	a run-time in Python, in compilazione in C (in parte)	"a" + 1
a run-time	durante l'esecuzione	divisione per zero, indice fuori intervallo, NULL dereferenziato
logico	mai segnalato: risultato sbagliato	< invece di <=, accumulatore inizializzato male

Definizione (assert). assert condizione, "messaggio" interrompe il programma se la condizione è falsa. Serve a verificare ipotesi interne (precondizioni, invarianti di ciclo), non a validare l'input dell'utente.

def media(v):
    assert len(v) > 0, "lista vuota"
    return sum(v) / len(v)

Definizione (test). Un test esegue il codice su un input con risultato noto e confronta. I test mostrano la presenza di errori, non ne dimostrano l'assenza: vanno scelti bene.

Definizione (doctest). Con doctest gli esempi nella docstring diventano test (python -m doctest modulo.py -v):

def quadrato(x):
    """
    >>> quadrato(3)
    9
    >>> quadrato(-2)
    4
    """
    return x * x