Formulario - fondamenti di informatica

Il calcolatore e i linguaggi

Note: 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 → · 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 → · Paradigmi di programmazione e linguaggiAlgoritmo e programma; paradigmi imperativo, procedurale, a oggetti, funzionale e dichiarativo; compilazione e interpretazione; confronto tra Python e C.Paradigmi di programmazione e linguaggi →

• Ciclo fetch-decode-execute: il PC contiene l'indirizzo della prossima istruzione, il fetch la copia nell'IR e incrementa il PC; un salto scrive un nuovo valore nel PC. Con $k$ bit si indirizzano $2^k$ celle da 1 byte.

• Base $b$: $\sum_{i=0}^{n-1}c_ib^i$; prefissi 0b, 0o (Python) o 0 (C), 0x; $45=\texttt{0b101101}=\texttt{0o55}=\texttt{0x2D}$. Decimale $\to$ binario con divisioni per 2 e resti letti dal basso; binario $\leftrightarrow$ esadecimale a gruppi di 4 bit. Con $n$ bit: $2^n$ configurazioni.
• Senza segno $0\ldots2^n-1$ (overflow = troncamento modulo $2^n$). Complemento a 2: $x=-c_{n-1}2^{n-1}+\sum_{i=0}^{n-2}c_i2^i$, intervallo $[-2^{n-1},2^{n-1}-1]$ (8 bit: $-128\ldots127$), opposto = inverti i bit e somma 1; overflow se due operandi dello stesso segno danno un risultato di segno opposto.

• $x=(-1)^s\cdot1.m\cdot2^{e-\text{bias}}$. Esatti solo i numeri $\frac k{2^j}$ ($0.1$ è approssimato): mai == tra float, usare math.isclose. Valori speciali inf, -inf, nan (nan != nan). ASCII 7 bit ('A'=65, 'a'=97, '0'=48); UTF-8 1-4 byte.
• Python: interpretato (bytecode), tipi dinamici ma forti, memoria con garbage collection, blocchi per indentazione, interi a precisione arbitraria. C: compilato, tipi statici, memoria manuale (malloc/free), blocchi tra graffe, interi di dimensione fissa. Paradigmi: imperativo, procedurale, a oggetti, funzionale, dichiarativo.

Python: variabili, tipi ed espressioni

Note: Eseguire un programma PythonInterprete interattivo e script .py, struttura di un file Python, indentazione, commenti, istruzioni ed espressioni, errori di sintassi.Eseguire un programma Python → · Variabili, oggetti e riferimentiIn Python una variabile è un nome legato a un oggetto; tipo, identità e valore; assegnamento, aliasing, oggetti mutabili e immutabili, None.Variabili, oggetti e riferimenti → · Tipi numerici ed espressioniint, float, complex e bool; operatori aritmetici con divisione intera e modulo; precedenza; conversioni di tipo; modulo math e arrotondamenti.Tipi numerici ed espressioni →

• Un nome si riferisce a un oggetto con tipo, identità (id) e valore. Immutabili: int, float, bool, complex, str, tuple, frozenset, None; mutabili: list, dict, set. b = a con una lista crea un alias; copia superficiale a[:], a.copy(), list(a); annidata copy.deepcopy. a == b confronta i valori, a is b l'identità (quasi solo con None).

• Sempre a == (a // b) * b + a % b. Precedenza: ** (associativo a destra), +x/-x, * / // %, + -, confronti, not, and, or. n % 10 ultima cifra, n // 10 senza l'ultima, divmod(135, 60) $\to$ (2, 15). int(3.99) $\to$ 3; round(2.5) $\to$ 2 (arrotonda al pari); math.floor(-2.5) $=-3$, ceil $=-2$, trunc $=-2$. ^ è lo XOR, non la potenza.
• Errori: sintassi (SyntaxError, file non eseguito), a tempo di esecuzione (eccezione con traceback), logici. input() restituisce sempre str.

Decisioni e cicli

Note: Logica booleana e istruzione ifValori di verità, operatori di confronto e logici con valutazione a corto circuito, leggi di De Morgan, truthiness; if/elif/else, espressione condizionale e match.Logica booleana e istruzione if → · Ciclo whileCiclo while, cicli controllati da contatore, da sentinella e da condizione; break, continue, else; terminazione e invariante di ciclo.Ciclo while → · Ciclo for e rangefor scorre gli elementi di un iterabile; range per gli indici; enumerate, zip, reversed, sorted; cicli annidati; quando usare for e quando while.Ciclo for e range →

• De Morgan: $\lnot(A\land B)=\lnot A\lor\lnot B$, $\lnot(A\lor B)=\lnot A\land\lnot B$. Corto circuito: A and B non valuta B se A è falso, A or B non valuta B se A è vero. Falsi: False, None, 0, 0.0, "", [], (), {}, set(). Confronti concatenabili 0 <= x < 10.

if cond1:
    ...
elif cond2:
    ...
else:
    ...
r = vero if cond else falso      # espressione condizionale

while condizione:                # condizione valutata prima di ogni iterazione
    ...
for elemento in iterabile:       # range(start, stop, step): stop escluso
    ...

• break esce dal ciclo più interno, continue salta al controllo, else del ciclo se non c'è stato break. range(5) $\to0..4$, range(2,6) $\to2..5$, range(5,0,-1) $\to5..1$; enumerate, zip, reversed, sorted. Euclide: while b != 0: a, b = b, a % b. Terminazione: una quantità intera non negativa che decresce; invariante di ciclo vera prima e dopo ogni iterazione.

Funzioni e moduli

Note: Funzioni in Pythondef e return, parametri posizionali, con nome e con valore predefinito, *args e **kwargs; passaggio per riferimento a oggetto; ambito delle variabili LEGB; docstring, type hint, lambda.Funzioni in Python → · Moduli e libreria standardOgni file .py è un modulo; forme di import; il blocco if name == "main"; moduli della libreria standard più usati (math, random, sys, os, time, collections).Moduli e libreria standard →

• Passaggio per riferimento a oggetto: riassegnare il parametro non tocca il chiamante, modificare un oggetto mutabile sì. Moduli utili: math (isclose, gcd), random (randint(a, b) estremi inclusi, choice, shuffle), sys (argv, exit), time.perf_counter(), collections (deque, Counter, defaultdict), csv, copy, unittest.

Stringhe, liste e tuple

Note: 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 → · 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 → · 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 →

• Stringhe immutabili: s[i:j] ha lunghezza j - i e non dà mai errore, s[::-1] rovesciata. Metodi: upper, lower, strip, split(sep), sep.join(seq), find (-1 se manca) e index (ValueError), count, replace, startswith, endswith, isdigit, isalpha. f-string: f"{x:.2f}", f"{42:05d}", f"{0.25:.1%}", f"{nome:<10}". Costruire con "".join(pezzi), non con += in un ciclo.
• Liste: [x*x for x in range(10) if cond]; matrice corretta [[0] * c for _ in range(r)] (con [[0] * c] * r le righe sono la stessa). l.sort() e l.reverse() agiscono sul posto e restituiscono None.

• Tuple: (5,) per un elemento; unpacking x, y = p, a, b = b, a, primo, *resto = [1, 2, 3, 4], _ per ignorare; chiavi di dizionario.

Input/Output ed eccezioni

Note: Input e output da consoleinput() restituisce sempre una stringa da convertire; lettura di più valori su una riga; print con sep, end e file; flussi standard stdin, stdout, stderr e reindirizzamento.Input e output da console → · 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 → · Eccezioni in PythonEccezioni e traceback, eccezioni predefinite più comuni, try/except/else/finally, raise per segnalare errori, propagazione lungo le chiamate.Eccezioni in Python → · File di record e controllo degli errori riga per rigaSchema per leggere un file (o lo standard input) di record, uno per riga: formati con separatore, controllo di ogni riga, messaggi di errore con il numero di riga su standard error, righe da saltare, fine dell'input su riga vuota; versione in Python con split, int, float e eccezioni; versione in C con fgets, sscanf e strtol.File di record e controllo degli errori riga per riga →

• n = int(input()), a, b = map(int, input().split()), for riga in sys.stdin:; print(*oggetti, sep=" ", end="\n", file=sys.stderr). Reindirizzamento python prog.py < dati.txt > risultati.txt.
• File: with open(nome, "r", encoding="utf-8") as f:; modi "r", "w" (crea o svuota), "a", "x", "b"; f.read(), f.readline(), f.readlines(), for riga in f; f.write("testo\n") non aggiunge \n. CSV: csv.reader(f), csv.writer(f).writerow([...]) con newline="".

try:
    f = open(nome, encoding="utf-8")
except FileNotFoundError as e:
    print("Impossibile aprire:", e)
else:
    dati = f.read()          # solo se non c'è stata eccezione
finally:
    print("fine")            # sempre
raise ValueError("media di una lista vuota")

• LBYL (controllo preventivo) contro EAFP (prova e gestisci). Riga per riga: for n, riga in enumerate(f, start=1), riga vuota $\to$ continue, errori su sys.stderr con il numero di riga. In C: fgets restituisce NULL a fine file, strtol(s, &fine, 10) segnala fine == s o *fine != '\0', sscanf restituisce i campi letti.

Pattern algoritmici e complessità

Note: Pattern algoritmici iterativiSchemi ricorrenti nei cicli: accumulatore, contatore, massimo e minimo, ricerca con uscita anticipata, verifica universale, filtro e trasformazione, finestra scorrevole, due indici, elaborazione di coppie.Pattern algoritmici iterativi → · 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 → · 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 → · 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 → · Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →

• Pattern: accumulatore (inizializzato all'elemento neutro), contatore, massimo e minimo (inizializzati al primo elemento, non a 0), ricerca return True al primo riscontro, verifica universale return False al primo controesempio (any, all), finestra scorrevole, due indici, tutte le coppie con $i<j$ ($\frac{n(n-1)}2$).
• Ricorsione: caso base e passo su input più piccolo, un record di attivazione per chiamata. fattoriale: n * fattoriale(n - 1). fib(n) ricorsivo: chiamate esponenziali ($\sim\varphi^n$, $\varphi\approx1{,}618$); con memoizzazione (functools.cache) $O(n)$.

• $f(n)=O(g(n))$ se $f(n)\le c\,g(n)$ per $n\ge n_0$; si tiene il termine dominante; passi in sequenza si sommano, cicli annidati si moltiplicano. Ricorrenze: $T(n)=T(n-1)+c\to O(n)$; $T(n)=T(n/2)+c\to O(\log n)$; $T(n)=2T(n/2)+cn\to O(n\log n)$; $T(n)=T(n-1)+T(n-2)+c\to$ esponenziale.

• Ricerca lineare: migliore $O(1)$, peggiore $O(n)$. Ricerca binaria (lista ordinata): $O(\log n)$, al più $\lfloor\log_2n\rfloor+1$ iterazioni, invariante "se x c'è, sta in v[lo..hi]", m = (lo + hi) // 2, aggiornamenti lo = m + 1 o hi = m - 1; bisect.bisect_left(v, x), bisect.insort(v, x).

• Selection sort: $\frac{n(n-1)}2$ confronti sempre. Merge sort: $T(n)=2T(n/2)+O(n)$, memoria $O(n)$. Timsort (sort, sorted): $O(n\log n)$, stabile, $O(n)$ su dati già ordinati; sorted(v, key=..., reverse=True). Nessun ordinamento per confronti supera $O(n\log n)$ al caso peggiore.
• Costi nascosti: slicing, v.copy(), s + t proporzionali al risultato; x in lista $O(n)$; x in insieme, d[k] $O(1)$ medio.

Il linguaggio C

Note: 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 → · 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 → · Funzioni in CDefinizione e prototipo di una funzione C, tipo di ritorno e void, passaggio dei parametri sempre per valore, variabili locali, globali e static, file header e compilazione separata, funzioni ricorsive.Funzioni in C → · Array e stringhe in CArray di dimensione fissa in memoria contigua, inizializzazione, nessun controllo sugli indici, passaggio a funzioni con la lunghezza, matrici; stringhe come array di char terminati da '\0' e funzioni di string.h.Array e stringhe in C → · Input e output in Cprintf con larghezza e precisione, scanf con indirizzi e valore di ritorno, lettura di righe con fgets, file con FILE*, fopen, fclose, fprintf, fscanf, controllo degli errori e della fine del file.Input e output in C →

• Compilazione: preprocessore (#include, #define), compilatore (.c $\to$ .o), linker; gcc -Wall -Wextra -o prog main.c (-lm per <math.h>). Variabili locali non inizializzate: valore indeterminato. Overflow di int = comportamento indefinito, di unsigned = modulo $2^n$. Booleani: 0 falso, altro vero (<stdbool.h>).
• Tra interi / tronca verso zero: 7 / 2 == 3, -7 / 2 == -3, -7 % 2 == -1; reale con (double)a / b. i++ restituisce il vecchio valore, ++i il nuovo. Logici &&, ||, ! con corto circuito; bit a bit &, |, ^, ~, <<, >>; condizionale max = (a > b) ? a : b;. switch senza break prosegue (fall-through); do { ... } while (cond);.
• Funzioni: argomenti sempre copiati; per modificare una variabile si passa &x; prototipo prima dell'uso; header .h con include guard #ifndef / #define / #endif; locale static conserva il valore. Mai restituire l'indirizzo di una variabile locale.

• Lettura corretta: while (fscanf(f, "%d", &x) == 1) e while ((c = fgetc(f)) != EOF), mai while (!feof(f)).

Puntatori e memoria in C

Note: 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 → · 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 → · 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 → · Ordinare e cercare in C - qsort, bsearch e puntatori a funzionePuntatori a funzione e funzioni di confronto; qsort per ordinare array di interi, stringhe e struct; bsearch per la ricerca binaria; dizionario ordinato su array dinamico di struct con inserimento (memmove e realloc) e ricerca in O(log n).Ordinare e cercare in C - qsort, bsearch e puntatori a funzione →

• Puntatore: int *p = &x; *p = 20; modifica x; in int *p, q; solo p è un puntatore. Aritmetica: p + k sposta di $k\cdot\texttt{sizeof(*p)}$ byte; v[i] $\equiv$ *(v + i); il nome di un array decade a puntatore. const int *p (dato costante), int *const q (puntatore costante), int **pp per modificare un puntatore passato a funzione, p->campo $\equiv$ (*p).campo.

• Errori classici: memory leak, dangling pointer, double free, buffer overflow, memoria non inizializzata. Strumenti: valgrind --leak-check=full ./prog, -fsanitize=address. Array che cresce: a n == cap si raddoppia con realloc, costo totale delle copie $O(n)$.
• Struct: typedef struct { char nome[32]; int matricola; double media; } Studente; campo con ., con puntatore ->; si assegnano ma non si confrontano con ==; sizeof include il padding. Autoreferenziale: typedef struct nodo { int valore; struct nodo *succ; } Nodo;.
• int (*f)(int, int) è un puntatore a funzione. qsort(base, n, sizeof base[0], cmp) con cmp(const void *a, const void *b) che restituisce <0, 0, >0 (mai x - y: (x > y) - (x < y)), non stabile, $O(n\log n)$. bsearch(&chiave, base, n, sizeof base[0], cmp) $O(\log n)$ su array ordinato con lo stesso cmp.

Tipi di dato astratti

Note: Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti → · Classi ed ereditarietà in PythonAttributi di istanza e di classe, metodi di istanza, di classe e statici; confronto e ordinamento con eq e lt; proprietà; ereditarietà, super(), override e polimorfismo; classi astratte come interfacce; eccezioni personalizzate; overloading e shadowing in Python.Classi ed ereditarietà in Python → · 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 → · 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 → · 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 → · Realizzare contenitori su array e listeCome si realizza un ADT contenitore partendo da un array: lunghezza logica e capacità con raddoppio (costo ammortizzato), dizionario su array ordinato con ricerca binaria, coda doppia su array circolare, coda con priorità a livelli, ADT costruiti sopra altri ADT (pila di code, pila reversibile); tabella dei costi.Realizzare contenitori su array e liste →

• ADT = interfaccia (cosa) e implementazione (come e a che costo); incapsulamento e invariante stabilito dal costruttore. Python: classi con self, __init__, __eq__, __lt__, __str__, @property; super().__init__(...); ereditarietà per is-a; classi astratte con ABC e @abstractmethod. C: header con tipo opaco typedef struct frazione *Frazione; e funzioni di creazione e distruzione.
• Pila (LIFO): push, pop, top, tutte $O(1)$; in Python list con append e pop(). Coda (FIFO): enqueue, dequeue, first, $O(1)$; in Python collections.deque (append, popleft(), perché list.pop(0) è $O(n)$); in C array circolare con indici % CAP e conteggio $n$.

• Lista concatenata in C: inserimento in testa n->succ = *pt; *pt = n; con Nodo **pt; cerca finché p != NULL && p->valore != x; rimozione con prec->succ = cur->succ e free(cur); deallocazione salvando il successivo prima di free.
• dict: d[k] = v, d.get(k, 0), k in d, d.pop(k), d.items(), chiavi hashable; frequenze freq[p] = freq.get(p, 0) + 1, Counter, defaultdict(list). set: {} crea un dizionario, set() l'insieme vuoto; unione a | b, intersezione a & b, differenza a - b, simmetrica a ^ b. Array che raddoppia: $O(1)$ ammortizzato per inserimento, copie totali $<2m$; con incremento costante $O(m^2)$.

• Dizionario su array ordinato: bisect_left $O(\log n)$, cerca $O(\log n)$, inserisci e cancella $O(n)$. Coda doppia su array circolare: elemento i in a[(t + i) % cap]. Coda con priorità a pochi livelli fissi: inserisci $O(1)$, estrai $O(L)$; con priorità arbitrarie, heap $O(\log n)$.

Debugging e testing

Note: 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 →

• Metodo: riprodurre con l'input minimo, leggere il messaggio (traceback dal fondo in Python, primo errore in C), formulare un'ipotesi, restringere, correggere la causa e aggiungere un test. assert condizione, "messaggio" verifica ipotesi interne, non l'input utente (in C si disattiva con -DNDEBUG). Test: casi normali, limite, partizioni, input non validi; unittest (assertEqual, assertRaises), doctest, in C funzioni di test con assert.