Fondamenti di Informatica

Informazione, algoritmi e computer

In breve

Prima di scrivere una sola riga di codice, occorre capire di cosa parla l'informatica: due concetti fondamentali, l'informazione (i dati) e l'algoritmo (il procedimento che li elabora). Un computer, per quanto potente, è una macchina che esegue algoritmi su dati, nient'altro. Programmare significa saper descrivere un procedimento in modo così preciso e non ambiguo che una macchina possa eseguirlo. Questo capitolo introduce cos'è un algoritmo e le sue proprietà, come è fatto un computer (il modello di von Neumann), la differenza tra hardware e software, e il percorso che porta da un'idea a un programma eseguibile. È la mappa concettuale su cui poggia tutto il corso.

🎯 Alla fine di questo capitolo saprai: cosa sono informazione e algoritmo e le proprietà di un algoritmo; l'architettura di un computer (von Neumann); la differenza tra hardware e software; cosa sono linguaggi di programmazione, compilatore e codice eseguibile.

Che cos'è un algoritmo

Perché conta: l'algoritmo è il concetto centrale dell'informatica; programmare è tradurre algoritmi in istruzioni per la macchina.

L'informatica è la scienza dell'elaborazione automatica dell'informazione. Il suo cuore concettuale non è il computer (che è solo lo strumento), ma l'algoritmo: una sequenza finita di passi ben definiti che, a partire da certi dati di ingresso (input), produce un risultato (output) risolvendo un problema. Una ricetta di cucina, le istruzioni di montaggio di un mobile, il procedimento per fare una divisione in colonna: sono tutti algoritmi. L'idea è antichissima (il nome deriva dal matematico persiano al-Khwārizmī), ma l'informatica la rende rigorosa.

Perché un procedimento sia un vero algoritmo (eseguibile da una macchina) deve avere alcune proprietà irrinunciabili:

finitezza: deve terminare dopo un numero finito di passi (non può andare avanti all'infinito);
non ambiguità (determinismo): ogni passo deve essere definito con precisione, senza interpretazioni possibili — una macchina non può "capire cosa intendevi";
eseguibilità: ogni passo deve essere realizzabile concretamente;
generalità: deve risolvere un'intera classe di problemi, non un solo caso (l'algoritmo della divisione funziona per qualsiasi coppia di numeri, non solo per 12÷3).

Programmare significa progettare algoritmi e poi tradurli in un linguaggio comprensibile alla macchina. La parte difficile e creativa è la prima: pensare come risolvere il problema passo dopo passo. La scrittura del codice (la sintassi) viene dopo. Per questo il corso insegna prima a ragionare algoritmicamente, poi a scrivere in un linguaggio specifico.

🔗 Analogia. Un algoritmo è come uno spartito musicale. Descrive con precisione assoluta una sequenza di azioni (le note, i tempi) che chiunque — o qualunque strumento automatico — può eseguire ottenendo sempre lo stesso risultato, senza dover "interpretare" cosa volesse dire il compositore. La musica (il risultato) nasce solo quando lo spartito viene eseguito; ma lo spartito, in sé, è l'algoritmo: il piano preciso e ripetibile.

L'architettura del computer

Perché conta: capire come è fatto un computer chiarisce cosa succede quando un programma viene eseguito e perché la programmazione ha certe caratteristiche.

Un computer (elaboratore) è una macchina che esegue algoritmi automaticamente. Quasi tutti i computer seguono lo stesso schema fondamentale, il modello di von Neumann (1945), con poche componenti essenziali:

la CPU (unità di elaborazione centrale, il "cervello"): esegue le istruzioni, una dopo l'altra, e fa i calcoli. Contiene l'unità aritmetico-logica (ALU) e l'unità di controllo;
la memoria (RAM): conserva sia i dati sia le istruzioni del programma in esecuzione. È l'intuizione geniale di von Neumann — programmi e dati stanno nello stesso posto, il che rende il computer flessibile (può eseguire qualsiasi programma caricato in memoria);
i dispositivi di input/output (tastiera, schermo, disco...): permettono al computer di comunicare con l'esterno (ricevere dati e restituire risultati).

Il funzionamento è un ciclo incessante e velocissimo: la CPU preleva un'istruzione dalla memoria, la interpreta, la esegue, e passa alla successiva (ciclo fetch-decode-execute), miliardi di volte al secondo. Un punto fondamentale: il computer, a livello fisico, capisce solo due stati — acceso/spento, che rappresentiamo con 0 e 1 (il sistema binario, cap. 2). Ogni dato, ogni istruzione, ogni immagine o suono, dentro il computer è in ultima analisi una sequenza di 0 e 1. La programmazione consiste nel costruire, sopra questa base binaria, livelli di astrazione sempre più comodi per l'uomo.

Hardware, software e linguaggi

Perché conta: la distinzione hardware/software e la catena dei linguaggi spiegano come un'idea diventa un programma eseguibile dalla macchina.

Un sistema informatico ha due componenti complementari:

l'hardware: la parte fisica, tangibile (CPU, memoria, schede, cavi, periferiche);
il software: la parte logica, immateriale — i programmi, cioè le sequenze di istruzioni che dicono all'hardware cosa fare. Senza software, l'hardware è inerte; senza hardware, il software non può girare.

Ma c'è un problema: il computer "capisce" solo il linguaggio macchina (sequenze di 0 e 1), impossibile da usare per un umano. Per questo si usano i linguaggi di programmazione: linguaggi artificiali con regole precise (sintassi), abbastanza vicini al pensiero umano da essere scrivibili, ma abbastanza rigorosi da essere traducibili in linguaggio macchina. Si distinguono in livelli: i linguaggi di basso livello (assembly) sono vicini alla macchina; quelli di alto livello (C, Java, Python) sono più vicini al ragionamento umano e più comodi. Questo corso usa il C, un linguaggio di riferimento per l'ingegneria: abbastanza vicino alla macchina da insegnare come funziona davvero, ma strutturato e leggibile.

Come si passa dal codice scritto dal programmatore (il codice sorgente) al programma eseguibile dalla macchina? Attraverso una traduzione. Per linguaggi come il C si usa un compilatore: un programma che traduce tutto il codice sorgente in linguaggio macchina, producendo un file eseguibile che poi la CPU può lanciare. (In alternativa, alcuni linguaggi usano un interprete, che traduce ed esegue le istruzioni una per una, al volo.) Il processo completo — scrivere il sorgente, compilarlo, correggere gli errori (debugging), eseguire — è il ciclo di lavoro quotidiano del programmatore.

🧩 Esempio. Vogliamo un algoritmo che trovi il massimo tra due numeri A e B. In pseudocodice (descrizione a parole, indipendente dal linguaggio): "1. Leggi A e B. 2. Se A è maggiore di B, allora il massimo è A. 3. Altrimenti, il massimo è B. 4. Comunica il massimo." Nota le proprietà: è finito (4 passi), non ambiguo (ogni passo è chiaro), generale (funziona per qualsiasi A e B). Questo pseudocodice si tradurrà poi in C con un'istruzione di selezione (cap. 4). L'algoritmo viene prima del codice.

⚠️ Attenzione. Non confondere algoritmo (il procedimento astratto, indipendente dal linguaggio) e programma (l'algoritmo scritto in un linguaggio specifico): lo stesso algoritmo si può scrivere in C, Java o Python. E non confondere compilatore (traduce tutto in anticipo, producendo un eseguibile) e interprete (traduce ed esegue al volo, riga per riga). Infine: il computer non "capisce" nulla in senso umano — esegue meccanicamente istruzioni non ambigue; ogni imprecisione è un errore.

🗺️ Come si collega il tutto

Questo capitolo pone le fondamenta concettuali. L'algoritmo (sequenza finita, non ambigua, generale di passi) è il vero oggetto dell'informatica; programmare è progettarne uno e tradurlo per la macchina. Il computer (modello di von Neumann: CPU, memoria condivisa per dati e istruzioni, I/O) lo esegue meccanicamente, lavorando alla base con soli 0 e 1 — la rappresentazione binaria che sarà il tema del cap. 2. La distinzione hardware/software e la catena dei linguaggi (dal C, di alto livello, al linguaggio macchina, via compilatore) mostrano come un'idea diventa eseguibile. Da qui il corso costruisce, mattone su mattone: prima come si rappresentano i dati (cap. 2-3), poi come si controlla il flusso di un algoritmo (selezione e iterazione, cap. 4-5), fino alle strutture dati e agli algoritmi avanzati.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Algoritmo	Sequenza finita, non ambigua, generale di passi che risolve un problema	Programma (algoritmo in un linguaggio specifico)
Proprietà	Finitezza, non ambiguità, eseguibilità, generalità	(mancano una → non è un algoritmo valido)
Modello di von Neumann	CPU + memoria (dati e istruzioni insieme) + I/O	(base di quasi tutti i computer)
Hardware / software	Parte fisica / programmi (istruzioni logiche)	(l'una inerte senza l'altra)
Linguaggio di alto livello	Vicino all'uomo (C, Java); va tradotto in linguaggio macchina	Linguaggio macchina (0 e 1, per la CPU)
Compilatore	Traduce tutto il sorgente in un eseguibile	Interprete (traduce ed esegue al volo)

📝 Riepilogo

L'informatica elabora informazione tramite algoritmi: sequenze finite di passi ben definiti che da un input producono un output. Proprietà irrinunciabili: finitezza, non ambiguità (determinismo), eseguibilità, generalità. Programmare = progettare algoritmi (parte creativa) e tradurli (parte tecnica).
Un computer segue il modello di von Neumann: CPU (esegue le istruzioni), memoria (contiene dati e istruzioni insieme), I/O. Cicla velocissimo fetch-decode-execute e lavora alla base con soli 0 e 1 (binario, cap. 2).
Hardware (fisico) e software (programmi) sono complementari. Si programma in linguaggi (di alto livello come il C, vicini all'uomo) che vanno tradotti in linguaggio macchina: un compilatore traduce tutto in un eseguibile (un interprete traduce ed esegue al volo). Il ciclo: scrivere → compilare → debug → eseguire.
Distinzioni chiave: algoritmo (astratto) ≠ programma (in un linguaggio); compilatore ≠ interprete. Il computer esegue meccanicamente, senza "capire": ogni ambiguità è un errore. Prossimo passo: come si rappresentano i dati in binario (cap. 2).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

La rappresentazione dell'informazione (numeri binari)

In breve

Dentro un computer tutto — numeri, testo, immagini, suoni — è rappresentato con soli due simboli: 0 e 1. Non è un capriccio, ma una necessità fisica: i circuiti elettronici distinguono affidabilmente solo due stati (corrente sì/no, tensione alta/bassa). Capire come da questi due simboli si costruisca ogni tipo di informazione è il primo passo per capire come funziona davvero un calcolatore. Questo capitolo spiega il sistema binario e la sua aritmetica, il concetto di bit e byte, come si rappresentano i numeri (interi e con segno) e i caratteri (codice ASCII), e perché a volte i calcoli in virgola mobile danno risultati inaspettati. È il ponte tra l'informazione astratta e la sua realizzazione fisica.

🎯 Alla fine di questo capitolo saprai: cos'è il sistema binario e come convertire da/verso il decimale; bit, byte e i multipli; la rappresentazione dei numeri interi (con e senza segno); la codifica dei caratteri (ASCII); un cenno alla virgola mobile e ai suoi limiti.

Il sistema binario

Perché conta: il binario è il linguaggio nativo del computer; comprenderlo è indispensabile per capire come vengono trattati tutti i dati.

Nella vita quotidiana usiamo il sistema decimale (base 10): dieci cifre (0–9) e il valore di ogni cifra dipende dalla sua posizione (nel numero 253, il 2 vale 200, il 5 vale 50, il 3 vale 3 — potenze di 10). Il computer usa invece il sistema binario (base 2): solo due cifre, 0 e 1, con lo stesso principio posizionale, ma basato sulle potenze di 2. Ogni cifra binaria si chiama bit (da binary digit).

La ragione è fisica: i componenti elettronici (transistor) sono affidabili nel distinguere solo due stati (acceso/spento, tensione alta/bassa, magnetizzato/no). Associando questi stati a 0 e 1, il computer può memorizzare ed elaborare informazione in modo robusto: un sistema a dieci livelli di tensione sarebbe fragile e soggetto a errori, due livelli no. Tutta la potenza del calcolatore nasce da questa scelta minimalista.

Convertire da binario a decimale è semplice: si sommano le potenze di 2 corrispondenti agli 1. Per esempio, il binario $1011$ vale $1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 8 + 0 + 2 + 1 = 11$ in decimale. Al contrario, per convertire da decimale a binario si divide ripetutamente per 2 raccogliendo i resti. L'aritmetica binaria funziona con le stesse regole di quella decimale, ma con i riporti a 2: $1+1 = 10$ (cioè 0 con riporto di 1). Si usano spesso anche i sistemi ottale (base 8) ed esadecimale (base 16, cifre 0–9 e A–F), come "scorciatoie" compatte per scrivere lunghe sequenze di bit.

🔗 Analogia. Il binario è come un linguaggio a interruttori. Immagina una fila di lampadine, ciascuna accesa (1) o spenta (0): con abbastanza lampadine puoi codificare qualsiasi messaggio concordando un codice. Non serve che ogni lampadina abbia mille livelli di luminosità (difficili da distinguere): bastano due stati netti, moltiplicati per tante lampadine. È esattamente ciò che fa il computer con i suoi miliardi di "interruttori" (transistor).

Bit, byte e la rappresentazione dei numeri

Perché conta: bit e byte sono le unità di misura dell'informazione; la rappresentazione degli interi ne mostra i limiti pratici (overflow).

Il bit è l'unità elementare di informazione: un singolo 0 o 1, che distingue tra due possibilità. Ma un solo bit dice poco; si raggruppano quindi in blocchi. Il raggruppamento fondamentale è il byte: 8 bit. Con 8 bit si possono rappresentare $2^8 = 256$ combinazioni diverse (da 00000000 a 11111111), sufficienti per esempio a codificare tutti i caratteri di base. In generale, con $n$ bit si rappresentano $2^n$ valori distinti — una crescita esponenziale: 8 bit → 256, 16 bit → 65.536, 32 bit → oltre 4 miliardi. I multipli del byte (kilobyte, megabyte, gigabyte...) misurano le quantità di dati.

Come si rappresentano i numeri interi? Per gli interi senza segno (solo positivi) si usa direttamente il binario: con $n$ bit si va da 0 a $2^n - 1$ . Per gli interi con segno (anche negativi) la tecnica standard è il complemento a due, un'ingegnosa convenzione che permette di rappresentare i negativi e — vantaggio cruciale — di fare le sottrazioni come addizioni, semplificando enormemente i circuiti. Il dettaglio tecnico non è essenziale; conta l'idea: con un numero fisso di bit si rappresenta un intervallo limitato di interi.

E qui emerge una conseguenza pratica importante: l'overflow. Poiché ogni tipo di numero ha un numero fisso di bit, esiste un valore massimo rappresentabile. Se un calcolo produce un risultato troppo grande per i bit disponibili, il valore "trabocca" e si ottiene un risultato errato (spesso un numero che "gira" e diventa negativo). È un problema reale della programmazione: bisogna scegliere tipi di dato con abbastanza bit per i valori attesi (cap. 3). L'overflow ha causato bug famosi e persino incidenti (razzi, sistemi bancari): il computer non "segnala" sempre di aver sforato, semplicemente dà il numero sbagliato.

Caratteri e numeri reali

Perché conta: testo e numeri decimali sono onnipresenti; capire come sono codificati spiega comportamenti altrimenti misteriosi (caratteri strani, errori di arrotondamento).

Il computer non rappresenta solo numeri. I caratteri (lettere, cifre, simboli, punteggiatura) si codificano associando a ciascuno un numero, secondo una tabella di corrispondenza. Lo standard storico è il codice ASCII, che assegna a ogni carattere un numero da 0 a 127 (rappresentabile in 7 bit): per esempio 'A' = 65, 'a' = 97, '0' = 48, lo spazio = 32. Così una parola o un testo diventa una sequenza di byte (un byte per carattere). Le codifiche moderne come Unicode/UTF-8 estendono l'idea per includere tutti gli alfabeti del mondo (accenti, ideogrammi, emoji), usando più byte per carattere. Un fatto importante: il carattere '5' (codice ASCII 53) è diverso dal numero 5 — sono due cose distinte, un errore tipico dei principianti.

I numeri reali (con la virgola: 3,14; 0,5) sono più delicati. Si rappresentano in virgola mobile (floating point), una notazione simile a quella scientifica ( $m \times 2^e$ , con una mantissa e un esponente) che permette di coprire un enorme intervallo di valori, dai piccolissimi ai grandissimi, con un numero fisso di bit. Ma c'è un prezzo: la maggior parte dei numeri reali non si può rappresentare esattamente con bit finiti (come $1/3 = 0{,}333...$ non ha rappresentazione decimale finita, molti numeri non ne hanno una binaria finita). Il risultato sono piccoli errori di arrotondamento: il classico caso in cui $0{,}1 + 0{,}2$ in un programma non dà esattamente $0{,}3$ ma $0{,}30000000000000004$ . Non è un bug del computer: è la conseguenza inevitabile di rappresentare infiniti numeri reali con bit finiti. Il programmatore deve esserne consapevole (per esempio, non confrontare mai due numeri in virgola mobile con l'uguaglianza esatta).

🧩 Esempio. La parola "Ciao" in ASCII: 'C' = 67, 'i' = 105, 'a' = 97, 'o' = 111. In memoria è la sequenza di quattro byte 67, 105, 97, 111 (ciascuno in binario: 01000011, 01101001, 01100001, 01101111). Per il computer "Ciao" è questa sequenza di 32 bit. Cambiare un solo bit può trasformare un carattere in un altro — ecco perché un file corrotto mostra simboli strani.

⚠️ Attenzione. Il carattere '5' ≠ il numero 5 (uno è il codice ASCII 53, l'altro il valore numerico). Un tipo intero ha un intervallo limitato: superarlo causa overflow (risultato errato, spesso senza avviso). I numeri in virgola mobile sono approssimati: non confrontarli mai con == (uguaglianza esatta), ma verificare se la differenza è minore di una piccola soglia. Questi non sono difetti del computer, ma conseguenze della rappresentazione a bit finiti.

🗺️ Come si collega il tutto

La rappresentazione binaria è il fondamento fisico su cui poggia tutto: il computer (von Neumann, cap. 1) lavora con soli 0 e 1 perché i circuiti distinguono due stati. Il sistema binario (base 2) e la sua aritmetica codificano ogni informazione; bit e byte ne sono le unità. I numeri interi (con segno, in complemento a due) hanno un intervallo limitato → rischio di overflow; i caratteri si codificano con tabelle (ASCII/Unicode); i reali in virgola mobile sono approssimati (errori di arrotondamento). Questi limiti spiegano perché, quando si programma, bisogna scegliere con cura il tipo di dato giusto per ogni variabile — l'argomento diretto del prossimo capitolo (variabili e tipi, cap. 3), dove questi concetti diventano strumenti concreti del linguaggio C.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Sistema binario	Base 2, cifre 0 e 1 (posizionale, potenze di 2)	Decimale (base 10, uso umano)
Bit / byte	Bit = 0 o 1; byte = 8 bit (256 valori)	(con $n$ bit → $2^n$ valori)
Complemento a due	Rappresentazione degli interi con segno; sottrazioni come addizioni	(permette i negativi)
Overflow	Risultato troppo grande per i bit disponibili → valore errato	(spesso senza segnalazione!)
ASCII	Tabella carattere↔numero (es. 'A' = 65)	(Unicode/UTF-8 = versione estesa)
Virgola mobile	Rappresentazione dei reali ( $m\times2^e$ ); approssimata	Interi (esatti ma con range limitato)

📝 Riepilogo

Il computer rappresenta tutto in binario (base 2, cifre 0 e 1) perché i circuiti distinguono affidabilmente solo due stati. Il binario è posizionale (potenze di 2): es. $1011_2 = 8+2+1 = 11_{10}$ . Aritmetica come in decimale, ma con riporti a 2.
Il bit (0/1) è l'unità elementare; il byte = 8 bit (256 valori). Con $n$ bit → $2^n$ valori (crescita esponenziale). I numeri interi usano il binario (senza segno) o il complemento a due (con segno): intervallo limitato → rischio di overflow (risultato errato se si sfora, spesso senza avviso).
I caratteri si codificano con tabelle numeriche: ASCII (0–127, es. 'A'=65), estesa da Unicode/UTF-8. Il carattere '5' ≠ numero 5. I numeri reali usano la virgola mobile ( $m\times2^e$ ): coprono un ampio range ma sono approssimati (errori di arrotondamento: $0{,}1+0{,}2\neq0{,}3$ esatto).
Conseguenze pratiche: scegliere tipi con abbastanza bit (overflow), non confrontare i float con ==. Questi limiti nascono dai bit finiti, non da difetti. Prossimo passo: variabili, tipi e operatori in C (cap. 3).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Variabili, tipi e operatori

In breve

Un programma manipola dati, e i dati vanno messi da qualche parte: nelle variabili. Una variabile è una "scatola" con un nome, in cui il programma conserva un valore che può cambiare durante l'esecuzione. Ma non tutte le scatole sono uguali: ogni variabile ha un tipo (intero, reale, carattere...) che ne stabilisce la natura, lo spazio occupato in memoria e le operazioni possibili. Comprendere variabili, tipi e operatori significa imparare l'alfabeto con cui si scrivono i programmi: come conservare i dati, come combinarli con calcoli e confronti. Questo capitolo introduce questi elementi fondamentali nel linguaggio C, i mattoni con cui costruiremo tutto il resto.

🎯 Alla fine di questo capitolo saprai: cos'è una variabile e cosa significa dichiararla; i principali tipi di dato in C; l'assegnazione; gli operatori (aritmetici, relazionali, logici); l'input/output di base; il concetto di espressione.

Variabili e tipi di dato

Perché conta: le variabili sono il modo in cui un programma conserva e manipola i dati; il tipo ne determina comportamento e limiti.

Una variabile è uno spazio di memoria, identificato da un nome, in cui il programma conserva un valore che può variare nel corso dell'esecuzione. È il concetto più basilare della programmazione: senza variabili, un programma non potrebbe ricordare nulla. Ogni variabile ha tre aspetti: un nome (con cui la richiamiamo, es. eta, somma), un valore (il dato che contiene in un dato momento) e un tipo (la natura del dato).

Il tipo è cruciale, specialmente in un linguaggio come il C, che è tipizzato staticamente: ogni variabile deve essere dichiarata con il suo tipo prima di essere usata. La dichiarazione (es. int eta;) riserva lo spazio in memoria e stabilisce cosa quella variabile può contenere. I tipi fondamentali del C:

int: numeri interi (con segno), es. −5, 0, 42. Occupa tipicamente 4 byte (con i limiti di range visti nel cap. 2);
float e double: numeri reali in virgola mobile (double con maggior precisione), es. 3.14, −0.5;
char: un singolo carattere, es. 'A', '7' (memorizzato come il suo codice ASCII, cap. 2);
(il C non ha un tipo booleano nativo classico: usa gli int, dove 0 = falso e diverso da 0 = vero).

Perché tutta questa attenzione ai tipi? Perché il tipo dice al computer quanti bit usare, come interpretarli (i bit di un int e di un float si leggono diversamente) e quali operazioni sono lecite. Scegliere il tipo giusto è la prima decisione di ogni programma: un int per contare persone, un double per una misura, un char per una lettera. Usare il tipo sbagliato porta a errori (overflow, perdita di precisione, cap. 2).

🔗 Analogia. Una variabile è come un contenitore etichettato in un magazzino. L'etichetta è il nome (eta), il contenuto è il valore (25), e la forma del contenitore è il tipo: una bottiglia per i liquidi (double), una scatola per oggetti interi (int), un porta-singolo per una lettera (char). Non metteresti un liquido in una scatola di cartone: allo stesso modo, il tipo garantisce che il dato "giusto" vada nel contenitore adatto.

Assegnazione ed espressioni

Perché conta: l'assegnazione e le espressioni sono il modo in cui i valori entrano nelle variabili e vengono calcolati; sono il "verbo" di ogni programma.

Come si mette un valore in una variabile? Con l'assegnazione, l'operazione più frequente della programmazione, indicata in C con il simbolo =:

eta = 25;

Questo non è l'uguaglianza matematica! È un comando: "prendi il valore a destra e mettilo nella variabile a sinistra". La distinzione è fondamentale, e lo si vede in un'istruzione come x = x + 1;, che in matematica sarebbe assurda (x = x+1?), ma in programmazione ha perfettamente senso: "prendi il valore attuale di x, aggiungi 1, e rimetti il risultato in x" (incrementa x). L'assegnazione ha una direzione: da destra (il valore da calcolare) a sinistra (la variabile che lo riceve).

A destra dell'assegnazione c'è in generale un'espressione: una combinazione di valori, variabili e operatori che, una volta valutata (calcolata), produce un risultato. 3 + 4, eta * 2, (a + b) / 2 sono espressioni. Il computer le valuta rispettando le regole di precedenza degli operatori (prima moltiplicazioni e divisioni, poi somme e sottrazioni, come in matematica; le parentesi forzano l'ordine). Il risultato dell'espressione viene poi assegnato, stampato, o usato in un'altra espressione.

Un programma comunica anche con l'esterno tramite input/output. In C, printf stampa a schermo (output) e scanf legge dati dalla tastiera (input), permettendo all'utente di fornire valori. Un tipico programma legge dei dati (scanf), li elabora con espressioni e assegnazioni, e stampa il risultato (printf) — la struttura input → elaborazione → output vista nel cap. 1.

Gli operatori

Perché conta: gli operatori sono gli strumenti per calcolare, confrontare e combinare i dati; senza di essi le variabili sarebbero inerti.

Gli operatori sono i simboli che combinano i valori per produrne di nuovi. Si dividono in categorie, ciascuna con uno scopo:

Operatori aritmetici: eseguono i calcoli. + (somma), - (sottrazione), * (moltiplicazione), / (divisione) e % (modulo, il resto della divisione intera). Un'insidia classica: in C, la divisione tra due int è una divisione intera (scarta la parte decimale): 7 / 2 dà 3, non 3.5! Per ottenere 3.5 bisogna usare i tipi reali. Il modulo % è utilissimo: 7 % 2 dà 1 (il resto), e serve per esempio a verificare se un numero è pari (n % 2 == 0).

Operatori relazionali (di confronto): confrontano due valori e producono un risultato vero/falso (in C, 1 o 0). Sono == (uguale a), != (diverso da), <, >, <=, >=. Attenzione all'errore più insidioso per i principianti: == (confronto) è diverso da = (assegnazione)! Scrivere if (x = 5) invece di if (x == 5) è un bug classico.

Operatori logici: combinano condizioni vero/falso. && (AND, vero se entrambe le condizioni sono vere), || (OR, vero se almeno una è vera), ! (NOT, inverte). Servono a costruire condizioni composte: "se l'età è ≥ 18 e ha la patente" si scrive eta >= 18 && haPatente. Questi operatori saranno il cuore delle decisioni (cap. 4).

🧩 Esempio. Un programma che calcola la media di due numeri interi:

int a = 7, b = 4;
double media;
media = (a + b) / 2.0;   // (7+4)/2.0 = 11/2.0 = 5.5
printf("La media e %f", media);

Nota il dettaglio cruciale: si divide per 2.0 (reale) e non per 2 (intero). Se avessimo scritto (a + b) / 2, la divisione intera avrebbe dato 5 (perdendo il .5)! Il tipo degli operandi cambia il risultato: è una delle prime trappole da conoscere.

⚠️ Attenzione. Tre errori classici da evitare. (1) = è assegnazione ("metti dentro"), == è confronto ("sono uguali?"): confonderli è il bug più comune. (2) La divisione tra interi scarta i decimali (7/2 = 3): usa i reali se ti servono. (3) Una variabile non inizializzata (dichiarata ma senza valore assegnato) contiene un valore casuale/imprevedibile: assegna sempre un valore prima di usarla. Questi errori non danno errori di compilazione, ma risultati sbagliati a runtime.

🗺️ Come si collega il tutto

Variabili, tipi e operatori sono l'alfabeto della programmazione. Le variabili (scatole con nome) conservano i dati; il tipo (int, double, char) ne stabilisce natura, bit e operazioni — applicando concretamente la rappresentazione binaria del cap. 2 (overflow degli int, approssimazione dei double). L'assegnazione (=, un comando, non un'uguaglianza) mette valori nelle variabili; le espressioni li calcolano con gli operatori (aritmetici, relazionali, logici). L'I/O (scanf/printf) realizza lo schema input→elaborazione→output (cap. 1). Con questi mattoni si possono scrivere programmi "lineari" (una sequenza di istruzioni), ma un algoritmo interessante deve decidere e ripetere: servono le strutture di controllo. Gli operatori relazionali e logici visti qui saranno la base delle decisioni (selezione, cap. 4) e dei cicli (iterazione, cap. 5).

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Variabile	Spazio di memoria con nome che conserva un valore modificabile	Costante (valore fisso)
Tipo	Natura del dato (`int`, `double`, `char`): bit e operazioni ammesse	(in C va dichiarato prima dell'uso)
Assegnazione `=`	Comando: "metti il valore a destra nella variabile a sinistra"	Confronto `==` (verifica uguaglianza)
Espressione	Combinazione di valori/operatori che produce un risultato	Istruzione (comando completo)
Divisione intera	Tra `int` scarta i decimali (`7/2=3`)	Divisione reale (`7/2.0=3.5`)
Operatori logici	`&&` (AND), `

📝 Riepilogo

Una variabile è uno spazio di memoria con un nome che conserva un valore modificabile. In C ogni variabile ha un tipo e va dichiarata: int (interi), float/double (reali), char (carattere). Il tipo stabilisce quanti bit usare, come interpretarli e quali operazioni sono lecite.
L'assegnazione = è un comando ("metti il valore a destra nella variabile a sinistra"), non un'uguaglianza: x = x + 1 incrementa x. A destra c'è un'espressione (valori + operatori) che viene valutata rispettando la precedenza. L'I/O usa printf (stampa) e scanf (legge).
Operatori: aritmetici (+ - * / %; attenzione: divisione tra interi scarta i decimali, % dà il resto); relazionali (== != < > <= >=, danno vero/falso); logici (&& AND, || OR, ! NOT, combinano condizioni).
Errori classici: = (assegnazione) ≠ == (confronto); 7/2 = 3 (divisione intera); variabili non inizializzate contengono valori casuali. Non danno errori di compilazione, ma risultati sbagliati. Prossimo passo: le decisioni — la selezione (cap. 4).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Le strutture di controllo: selezione

In breve

Un programma che esegue sempre le stesse istruzioni nello stesso ordine sarebbe inutile: la potenza nasce dalla capacità di prendere decisioni, di comportarsi diversamente a seconda dei dati. È la selezione (o istruzione condizionale): "se questa condizione è vera, allora fai questo, altrimenti fai quello". È la prima delle strutture di controllo che rendono un programma "intelligente", capace di reagire alle situazioni. Questo capitolo introduce l'istruzione if-else e le sue varianti nel linguaggio C, il concetto di condizione (booleana), i blocchi di istruzioni e la selezione multipla. Insieme all'iterazione (cap. 5), la selezione è ciò che trasforma una lista di comandi in un vero algoritmo.

🎯 Alla fine di questo capitolo saprai: cos'è la selezione e l'istruzione if-else; come si scrive una condizione (espressione booleana); i blocchi di istruzioni; la selezione annidata e a cascata; l'istruzione switch; e la logica del diagramma di flusso.

L'istruzione condizionale if-else

Perché conta: la selezione è la struttura che permette a un programma di comportarsi diversamente secondo i dati; senza di essa non c'è vera logica.

Fin qui i programmi eseguivano le istruzioni una dopo l'altra, in sequenza. Ma un algoritmo reale deve scegliere: fare una cosa in un caso, un'altra in un caso diverso. Questa capacità è la selezione, realizzata dall'istruzione if ("se"). La forma base:

if (condizione) {
    // istruzioni eseguite SE la condizione è vera
}

Il programma valuta la condizione: se è vera, esegue le istruzioni nel blocco; se è falsa, le salta e prosegue. Spesso si vuole anche un'alternativa: l'istruzione if-else ("se... altrimenti"):

if (condizione) {
    // ramo VERO
} else {
    // ramo FALSO
}

Ora il programma esegue uno dei due rami, mai entrambi: se la condizione è vera il primo, se è falsa il secondo. È un bivio nel flusso di esecuzione. La condizione è un'espressione booleana (vero/falso), costruita con gli operatori relazionali e logici del cap. 3 (x > 0, eta >= 18 && haPatente). In C, ricordiamo, "vero" è qualsiasi valore diverso da zero, "falso" è zero.

Le istruzioni raggruppate tra parentesi graffe { } formano un blocco: un insieme di istruzioni trattate come una sola unità. Il blocco permette di eseguire più istruzioni in un ramo. L'indentazione (rientro del testo) non è obbligatoria per il C ma è essenziale per la leggibilità: mostra a colpo d'occhio quali istruzioni appartengono a quale ramo. Un codice ben indentato è un codice comprensibile.

🔗 Analogia. La selezione è un bivio stradale con un cartello. Arrivi a un incrocio (l'if), leggi il cartello (la condizione): "pioggia?". Se sì, prendi la strada a sinistra (prendi l'ombrello); se no, quella a destra (esci senza). Percorri una sola delle due strade, mai entrambe, e poi le due strade si ricongiungono e prosegui. Il programma "sceglie il percorso" in base alla condizione, esattamente come tu scegli la strada in base al cartello.

Selezione multipla e annidata

Perché conta: i problemi reali hanno spesso più di due casi; saper strutturare decisioni multiple è essenziale per algoritmi realistici.

Molti problemi non hanno solo due casi, ma molti. Come gestirli? Si possono annidare (nidificare) le selezioni: mettere un if dentro il ramo di un altro if, creando decisioni a più livelli. La forma più usata è la cascata if-else if-else, che verifica una serie di condizioni in ordine:

if (voto >= 90) {
    printf("Ottimo");
} else if (voto >= 60) {
    printf("Sufficiente");
} else {
    printf("Insufficiente");
}

Il programma controlla le condizioni dall'alto in basso e esegue il blocco della prima che risulta vera, saltando tutte le altre; se nessuna è vera, esegue l'else finale (il caso "di default"). L'ordine conta: le condizioni vanno messe in modo che i casi non si sovrappongano ambiguamente. Questa struttura è la spina dorsale di ogni algoritmo che classifica o smista dati in categorie.

Quando le decisioni multiple dipendono tutte dal valore di una singola variabile, il C offre un'alternativa più leggibile: l'istruzione switch. Essa confronta una variabile con una serie di valori (case) ed esegue il blocco corrispondente:

switch (giorno) {
    case 1: printf("Lunedi"); break;
    case 2: printf("Martedi"); break;
    // ...
    default: printf("Giorno non valido");
}

Il switch è più chiaro di una lunga cascata di if quando si confronta la stessa variabile con valori discreti (un menu, un giorno della settimana, un codice). Attenzione all'istruzione break: senza di essa l'esecuzione "cade" nel caso successivo (comportamento raramente voluto, altra insidia classica).

Il flusso di controllo e i diagrammi

Perché conta: visualizzare il flusso di esecuzione aiuta a progettare e verificare la logica di un algoritmo prima di scriverlo.

Con la selezione, l'esecuzione di un programma non è più una linea retta: si ramifica. Il concetto di flusso di controllo (l'ordine in cui le istruzioni vengono eseguite) diventa centrale. La programmazione strutturata (un principio fondamentale) stabilisce che ogni algoritmo si può costruire con sole tre strutture di controllo: la sequenza (istruzioni una dopo l'altra), la selezione (questo capitolo) e l'iterazione (cap. 5). Con questi tre soli mattoni si può esprimere qualsiasi algoritmo, per quanto complesso — un risultato teorico profondo (teorema di Böhm-Jacopini) che è alla base del buon stile di programmazione.

Per progettare e visualizzare il flusso di un algoritmo si usa spesso il diagramma di flusso (flowchart): una rappresentazione grafica con simboli standard — rettangoli per le istruzioni (azioni), rombi per le decisioni (le condizioni, da cui escono due frecce, "vero" e "falso"), frecce per il flusso. Un rombo con due uscite è esattamente una selezione. Disegnare il diagramma di flusso prima di scrivere il codice aiuta a chiarire la logica, individuare i casi da gestire ed evitare errori. È un modo di "pensare l'algoritmo" (cap. 1) prima di tradurlo in C.

🧩 Esempio. Algoritmo per stabilire se un numero è pari o dispari:

int n;
scanf("%d", &n);
if (n % 2 == 0) {
    printf("%d e pari", n);
} else {
    printf("%d e dispari", n);
}

La condizione n % 2 == 0 usa il modulo (cap. 3): se il resto della divisione per 2 è zero, il numero è pari. Il flusso si biforca: un ramo per i pari, uno per i dispari, e si stampa il messaggio giusto. Un problema del mondo reale ("è pari?") tradotto in una decisione binaria — l'essenza della selezione.

⚠️ Attenzione. Ricorda la trappola del cap. 3: nella condizione si usa == (confronto), non = (assegnazione) — if (n = 0) è un bug che assegna invece di confrontare. Nel switch, non dimenticare il break alla fine di ogni case (senza, l'esecuzione prosegue nei casi seguenti). E attento all'ambiguità dell'else annidato ("dangling else"): un else si lega sempre all'if più vicino — l'indentazione può ingannare, le graffe { } chiariscono.

🗺️ Come si collega il tutto

La selezione è la prima struttura di controllo che rende un algoritmo capace di decidere. L'istruzione if-else biforca il flusso di controllo in base a una condizione booleana, costruita con gli operatori relazionali e logici del cap. 3. La cascata else if e lo switch gestiscono casi multipli; i blocchi { } raggruppano istruzioni. La programmazione strutturata poggia su tre soli mattoni — sequenza, selezione, iterazione — con cui si esprime ogni algoritmo (cap. 1), visualizzabili con i diagrammi di flusso. La selezione da sola permette di scegliere, ma non di ripetere: molti problemi richiedono di eseguire azioni più volte (elaborare tutti i dati, cercare, sommare). Serve la seconda grande struttura: l'iterazione (cap. 5), i cicli, che insieme alla selezione completa il potere espressivo della programmazione.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Selezione (`if`)	Esegue istruzioni se una condizione è vera	Iterazione (ripete, cap. 5)
`if`-`else`	Bivio: un ramo se vero, l'altro se falso (mai entrambi)	(esegue uno solo dei due rami)
Condizione	Espressione booleana (vero/falso), con operatori relazionali/logici	(in C: 0 = falso, ≠0 = vero)
Blocco `{ }`	Gruppo di istruzioni trattate come una unità	(indentazione = leggibilità, non obbligo)
Cascata `else if`	Serie di condizioni: esegue la prima vera	`switch` (confronta una sola variabile)
Diagramma di flusso	Grafico del flusso; rombo = decisione	(progetta prima di codificare)

📝 Riepilogo

La selezione permette a un programma di decidere. L'istruzione if (condizione) { ... } esegue il blocco solo se la condizione è vera; if-else sceglie tra due rami (ne esegue uno solo). La condizione è un'espressione booleana (operatori relazionali/logici, cap. 3; in C 0 = falso, ≠0 = vero). Le graffe { } formano un blocco.
Per casi multipli: la cascata if-else if-else verifica le condizioni dall'alto e esegue la prima vera (o l'else di default). Lo switch è più chiaro quando si confronta una sola variabile con valori discreti (ricorda il break).
La selezione ramifica il flusso di controllo. La programmazione strutturata costruisce ogni algoritmo con tre mattoni: sequenza, selezione, iterazione (cap. 5). I diagrammi di flusso (rombo = decisione) aiutano a progettare la logica prima di scrivere il codice.
Trappole: == (confronto) ≠ = (assegnazione) nelle condizioni; il break nello switch; l'else si lega all'if più vicino (usa le graffe). Prossimo passo: ripetere le azioni — l'iterazione (cap. 5).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Le strutture di controllo: iterazione

In breve

Molti problemi richiedono di ripetere un'azione tante volte: sommare cento numeri, cercare un nome in una lista, contare fino a mille. Scrivere l'istruzione cento volte sarebbe assurdo (e impossibile se il numero di ripetizioni non è noto in anticipo). La soluzione è l'iterazione (o ciclo): una struttura che ripete un blocco di istruzioni finché una condizione lo richiede. È la seconda grande struttura di controllo, e forse quella che dà ai programmi il loro vero potere: fare in un istante ciò che a mano richiederebbe una vita. Questo capitolo presenta i cicli del C (while, do-while, for), spiega il pericoloso ciclo infinito, e mostra i pattern classici (contatori, accumulatori) che ricorrono in ogni programma.

🎯 Alla fine di questo capitolo saprai: cos'è l'iterazione e perché è potente; i cicli while, do-while e for; la differenza tra ciclo a condizione e a contatore; il pericolo del ciclo infinito; i pattern di contatore e accumulatore.

Il ciclo while

Perché conta: il while è la forma fondamentale di iterazione; comprenderlo bene è la base per tutti gli altri cicli.

L'iterazione è la capacità di ripetere un blocco di istruzioni. La forma fondamentale è il ciclo while ("mentre"):

while (condizione) {
    // istruzioni ripetute FINCHÉ la condizione è vera
}

Il funzionamento: il programma valuta la condizione; se è vera, esegue il blocco, poi torna a valutare la condizione; se è ancora vera, riesegue; e così via, finché la condizione diventa falsa, momento in cui il ciclo termina e il programma prosegue. Il blocco ripetuto si chiama corpo del ciclo; ogni singola esecuzione è un'iterazione.

Perché l'iterazione è così potente? Perché permette di eseguire un numero enorme — o variabile, non noto in anticipo — di ripetizioni con poche righe di codice. Un ciclo di tre righe può elaborare tre dati o tre miliardi: la differenza è solo nella condizione. È ciò che rende i computer capaci di macinare grandi quantità di dati.

Il punto cruciale di ogni while è che qualcosa nel corpo deve modificare la condizione, avvicinandola a diventare falsa: altrimenti il ciclo non finirebbe mai. Tipicamente c'è una variabile (un contatore) che cambia a ogni iterazione. Se ci si dimentica di aggiornarla, o la si aggiorna nel verso sbagliato, si crea un ciclo infinito: il programma si blocca, ripetendo all'infinito le stesse istruzioni senza mai uscire. È uno degli errori più comuni e frustranti (il programma "si pianta"). Ogni volta che si scrive un ciclo, bisogna chiedersi: "questa condizione, prima o poi, diventerà falsa?".

🔗 Analogia. Un ciclo while è come salire una scala contando i gradini: "finché non sei arrivato all'ultimo gradino, sali di uno e conta". A ogni passo controlli la condizione (sei arrivato?) e, se no, fai un altro passo — avvicinandoti alla fine. Se però dimenticassi di salire (non aggiorni il contatore), continueresti a chiederti "sono arrivato?" restando fermo sullo stesso gradino per sempre: è il ciclo infinito.

Il ciclo for e il do-while

Perché conta: for e do-while sono varianti che si adattano a situazioni diverse; scegliere il ciclo giusto rende il codice più chiaro e sicuro.

Il C offre tre forme di ciclo, adatte a esigenze diverse.

Il ciclo for è la forma ideale quando si sa quante volte ripetere (iterazione a contatore). Concentra in una riga i tre elementi tipici di un ciclo controllato da contatore: inizializzazione, condizione e aggiornamento:

for (i = 0; i < 10; i++) {
    // ripetuto 10 volte, con i che va da 0 a 9
}

Qui i = 0 inizializza il contatore, i < 10 è la condizione di continuazione, i++ incrementa i a ogni giro. Il for è compatto e sicuro: avendo tutto in vista (inizio, fine, passo), è più difficile dimenticare l'aggiornamento e cadere nel ciclo infinito. È il ciclo di elezione per scorrere un intervallo noto o gli elementi di un array (cap. 7).

Il ciclo do-while è simile al while, ma con una differenza chiave: controlla la condizione alla fine, dopo aver eseguito il corpo:

do {
    // istruzioni
} while (condizione);

Questo garantisce che il corpo venga eseguito almeno una volta, anche se la condizione è subito falsa (nel while, invece, se la condizione è falsa dall'inizio, il corpo non viene eseguito mai). Il do-while è utile quando un'azione va fatta almeno una volta prima di poter verificare se ripeterla — tipicamente la lettura di un input con validazione ("chiedi un numero; finché non è valido, richiedilo").

In sintesi: while per ripetere finché una condizione vale (0 o più volte, controllo iniziale); do-while per ripetere almeno una volta (controllo finale); for per ripetere un numero determinato di volte (contatore). Sono equivalenti in potenza (ogni ciclo si può riscrivere con gli altri), ma sceglierne quello adatto rende il codice più leggibile e meno soggetto a errori.

I pattern dell'iterazione

Perché conta: contatori e accumulatori sono schemi ricorrenti che compaiono in quasi ogni programma; riconoscerli accelera enormemente la scrittura del codice.

L'iterazione dà origine ad alcuni pattern (schemi ricorrenti) che si ritrovano ovunque, tanto da diventare automatismi per il programmatore:

il contatore: una variabile che si incrementa a ogni iterazione, per contare quante volte accade qualcosa (quanti numeri positivi ci sono, quante volte una lettera compare in un testo). Si inizializza a 0 e si fa contatore++ quando la condizione di conteggio è soddisfatta;
l'accumulatore (o totalizzatore): una variabile che accumula un risultato progressivo, tipicamente una somma o un prodotto. Si inizializza (a 0 per una somma, a 1 per un prodotto) e a ogni iterazione si aggiorna: somma = somma + valore. È il modo di sommare una serie di numeri, calcolare una media, un massimo, ecc.

Questi pattern spesso si combinano: per calcolare una media, si usa un accumulatore (per la somma) e un contatore (per quanti numeri), e alla fine si divide. Altri pattern comuni: la ricerca (scorrere dati finché si trova ciò che si cerca), il filtraggio (processare solo gli elementi che soddisfano una condizione), la ricerca del massimo/minimo (tenere traccia del miglior valore visto finora). Riconoscere quale pattern serve è metà del lavoro di scrivere un algoritmo iterativo.

Due istruzioni speciali modificano il flusso di un ciclo: break (esce immediatamente dal ciclo, anche se la condizione sarebbe ancora vera — utile per interrompere una ricerca appena trovato il risultato) e continue (salta il resto dell'iterazione corrente e passa direttamente alla successiva). Vanno usate con parsimonia, per non rendere il flusso confuso.

🧩 Esempio. Sommare i numeri da 1 a 100 (un accumulatore in un ciclo for):

int somma = 0;              // inizializza l'accumulatore
for (int i = 1; i <= 100; i++) {
    somma = somma + i;      // accumula: aggiunge i alla somma
}
printf("La somma e %d", somma);   // stampa 5050

L'accumulatore somma parte da 0 e, a ogni iterazione, ingloba il valore di i (1, poi 2, poi 3...). Dopo 100 giri contiene 1+2+...+100 = 5050. Un compito che a mano richiederebbe minuti, il ciclo lo esegue in un lampo — e cambiando 100 in 1000000 funzionerebbe identico. Questa è la potenza dell'iterazione.

⚠️ Attenzione. Il pericolo numero uno è il ciclo infinito: assicurati che la condizione, prima o poi, diventi falsa (qualcosa nel corpo deve modificarla verso l'uscita). Ricorda: while può eseguire il corpo zero volte (condizione subito falsa), do-while almeno una. Attento agli errori di conteggio ("off-by-one"): i < 10 fa 10 iterazioni (0–9), i <= 10 ne fa 11 — sbagliare l'estremo è un classico. E inizializza sempre contatori e accumulatori prima del ciclo (a 0 o 1 secondo il caso).

🗺️ Come si collega il tutto

L'iterazione completa, insieme alla selezione (cap. 4), le strutture di controllo della programmazione strutturata (cap. 1): con sequenza, selezione e iterazione si esprime ogni algoritmo. I cicli while (controllo iniziale, 0+ volte), do-while (controllo finale, 1+ volte) e for (a contatore, numero noto) ripetono un blocco finché una condizione (cap. 3) lo richiede — con il rischio del ciclo infinito se la condizione non evolve. I pattern (contatore, accumulatore, ricerca, massimo) sono schemi ricorrenti. L'iterazione dà finalmente ai programmi il potere di elaborare grandi quantità di dati; ma i programmi crescono, e ripetere blocchi di codice diventa ingestibile. Serve un modo di organizzare e riusare il codice: le funzioni (cap. 6), che scompongono un programma in parti gestibili. E i cicli saranno lo strumento naturale per scorrere gli array (cap. 7).

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Iterazione	Ripetere un blocco finché una condizione lo richiede	Selezione (decide una volta, cap. 4)
`while`	Ripete finché la condizione è vera; controllo iniziale (0+ volte)	`do-while` (controllo finale, 1+ volte)
`for`	Ciclo a contatore: init, condizione, aggiornamento in una riga	`while` (a condizione generica)
Ciclo infinito	La condizione non diventa mai falsa → il programma si blocca	(errore: dimenticato l'aggiornamento)
Accumulatore	Variabile che somma/moltiplica progressivamente	Contatore (conta le occorrenze)
`break` / `continue`	Esce dal ciclo / salta all'iterazione successiva	(modificano il flusso del ciclo)

📝 Riepilogo

L'iterazione (ciclo) ripete un blocco di istruzioni, dando ai programmi il potere di elaborare grandi quantità di dati con poche righe. Il while (condizione) { } esegue il corpo finché la condizione è vera (controllo iniziale: può eseguirlo zero volte).
Varianti: il for (init, condizione, aggiornamento) è ideale quando si sa quante volte ripetere (contatore); il do-while controlla la condizione alla fine, quindi esegue il corpo almeno una volta (utile per validare input). Equivalenti in potenza, ma il ciclo giusto rende il codice più chiaro.
Il pericolo principale è il ciclo infinito: qualcosa nel corpo deve far evolvere la condizione verso il falso. Pattern ricorrenti: contatore (conta occorrenze), accumulatore (somma/prodotto progressivo, es. 1+...+100 = 5050), ricerca, massimo/minimo. break esce dal ciclo, continue salta all'iterazione seguente.
Trappole: ciclo infinito, errori "off-by-one" (i < 10 = 10 giri, i <= 10 = 11), inizializzare accumulatori/contatori prima del ciclo. Prossimo passo: organizzare il codice con le funzioni (cap. 6).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Le funzioni e la modularità

In breve

Man mano che i programmi crescono, scrivere tutto in un unico blocco diventa ingestibile: codice ripetuto, difficile da leggere e da correggere. La soluzione è la modularità: scomporre il programma in funzioni, piccoli "sotto-programmi" ciascuno con un compito preciso, riutilizzabili e verificabili separatamente. Le funzioni sono uno dei concetti più importanti dell'informatica: permettono di gestire la complessità con la strategia del "divide et impera", di riusare il codice invece di riscriverlo, e di ragionare su un problema alla volta. Questo capitolo spiega cos'è una funzione, come si definisce e si chiama, il passaggio dei parametri, il valore di ritorno, e il concetto delicato di visibilità delle variabili (scope).

🎯 Alla fine di questo capitolo saprai: cos'è una funzione e perché serve la modularità; parametri e valore di ritorno; la differenza tra definizione e chiamata; il passaggio dei parametri per valore; il concetto di variabile locale e scope; l'idea di divide et impera.

Che cos'è una funzione

Perché conta: la funzione è l'unità di organizzazione e riuso del codice; senza di essa i programmi complessi sarebbero ingestibili.

Una funzione è un blocco di codice con un nome, che svolge un compito specifico e può essere richiamato (eseguito) ogni volta che serve, da qualunque punto del programma. È l'equivalente informatico di una "procedura" o "sottoprogramma". Invece di scrivere le stesse istruzioni molte volte, le si racchiude in una funzione e la si chiama dove serve — scrivendola una volta, usandola infinite. Abbiamo già usato funzioni (printf, scanf): ora impariamo a crearne di nostre.

Una funzione, come una piccola macchina, riceve degli ingressi (i parametri, o argomenti: i dati su cui lavora), esegue il suo compito, e restituisce un risultato (il valore di ritorno). Per esempio, una funzione massimo(a, b) riceve due numeri e restituisce il maggiore. Questa struttura input→elaborazione→output (cap. 1) si ripete a ogni livello: un programma è fatto di funzioni, ciascuna un mini-programma.

I vantaggi della modularità sono enormi e giustificano l'intera esistenza delle funzioni:

riuso: scrivi il codice una volta, lo usi ovunque (niente duplicazioni);
leggibilità: un programma diviso in funzioni con nomi chiari (leggiDati, calcolaMedia, stampaRisultato) si legge come una descrizione del suo scopo;
manutenibilità: se c'è un errore in un calcolo, lo correggi in un solo posto (la funzione), non in mille copie sparse;
verificabilità: puoi testare ogni funzione separatamente, isolando i problemi;
astrazione: usi una funzione sapendo cosa fa, senza doverti preoccupare di come lo fa (come guidi l'auto senza conoscere il motore).

🔗 Analogia. Una funzione è come un elettrodomestico specializzato. Il frullatore (frulla) riceve degli ingredienti (parametri), fa il suo lavoro (elabora) e restituisce un frullato (valore di ritorno). Non ti interessa come funziona il motore interno: sai cosa mettere e cosa ottieni. E puoi usarlo ogni volta che vuoi, riutilizzandolo. Costruire un programma per funzioni è come attrezzare una cucina con tanti apparecchi specializzati, ciascuno che fa bene una cosa, invece di un unico marchingegno confuso.

Definizione, chiamata e parametri

Perché conta: capire il meccanismo di chiamata e passaggio dei parametri è essenziale per usare correttamente le funzioni ed evitare errori sottili.

Con le funzioni bisogna distinguere due momenti. La definizione è dove si scrive la funzione: le si dà un nome, si specificano i parametri (con i loro tipi) e il tipo del valore restituito, e si scrive il corpo (le istruzioni). La chiamata (o invocazione) è dove la si usa: si scrive il suo nome passandole i valori concreti (gli argomenti). Definire una funzione non la esegue; solo la chiamata la mette in azione. In C, una funzione tipica ha questa forma:

int massimo(int a, int b) {   // definizione: tipo di ritorno, nome, parametri
    if (a > b)
        return a;             // return: restituisce il valore ed esce
    else
        return b;
}

Il tipo davanti al nome (int) è quello del valore di ritorno; l'istruzione return restituisce quel valore al chiamante e termina la funzione. Se una funzione non deve restituire nulla (fa solo un'azione, es. stampare), il suo tipo è void.

Quando si chiama una funzione (m = massimo(5, 3);), succede questo: il flusso di esecuzione "salta" dentro la funzione, i parametri ricevono i valori degli argomenti passati (a diventa 5, b diventa 3), la funzione esegue e con return restituisce un valore (qui 5), che sostituisce la chiamata nell'espressione (m diventa 5); poi il controllo torna al punto dopo la chiamata. È come una piccola deviazione: vai nella funzione, fai il lavoro, torni con il risultato.

Un punto delicato è come i parametri vengono passati. In C il passaggio è per valore: la funzione riceve una copia dei valori degli argomenti, non gli originali. Conseguenza importante: se la funzione modifica un parametro, modifica solo la sua copia locale — la variabile originale del chiamante resta invariata. Questo protegge i dati del chiamante da modifiche accidentali, ma significa anche che una funzione non può (di norma) cambiare le variabili di chi la chiama. Per farlo servono i puntatori (cap. 8), che permettono il passaggio "per riferimento".

Variabili locali e scope

Perché conta: capire dove "vivono" e "sono visibili" le variabili previene una vasta classe di errori e chiarisce l'indipendenza delle funzioni.

Le variabili dichiarate dentro una funzione (inclusi i suoi parametri) sono locali a quella funzione: esistono solo mentre la funzione è in esecuzione e sono visibili solo al suo interno. Fuori dalla funzione non esistono. Questo concetto — la visibilità o scope (ambito) di una variabile — è fondamentale: stabilisce dove nel codice una variabile può essere usata.

La conseguenza più importante è l'indipendenza delle funzioni. Due funzioni diverse possono usare variabili con lo stesso nome senza interferire, perché sono variabili distinte, ciascuna nel proprio scope. La variabile i di un ciclo in una funzione non ha nulla a che vedere con la i di un'altra funzione. Questo isolamento è ciò che rende le funzioni davvero "moduli" separati: puoi scrivere e capire una funzione senza preoccuparti delle altre, perché le sue variabili locali sono "private". È l'incarnazione dell'astrazione: ogni funzione è un mondo a sé.

Esistono anche variabili globali (dichiarate fuori da ogni funzione, visibili a tutte), ma il loro uso è sconsigliato nella maggior parte dei casi: rompono l'isolamento, creano dipendenze nascoste tra funzioni e rendono il codice difficile da capire e correggere (una funzione può modificare una globale usata da un'altra, con effetti imprevedibili). La buona pratica è: le funzioni comunicano tramite parametri e valori di ritorno (canali espliciti e controllati), non tramite variabili globali. Questo mantiene ogni funzione indipendente e prevedibile.

Il tutto realizza la strategia del divide et impera ("dividi e conquista"): affrontare un problema complesso scomponendolo in sotto-problemi più semplici, ciascuno risolto da una funzione. Si risolve ogni pezzo separatamente e poi si combinano. È il principio-guida della progettazione di programmi (e ritornerà negli algoritmi, cap. 10-11): la complessità si domina dividendola.

🧩 Esempio. Un programma modulare che usa una funzione per calcolare l'area di un cerchio:

double area_cerchio(double raggio) {
    return 3.14159 * raggio * raggio;
}

int main() {
    double r = 5.0;
    double a = area_cerchio(r);   // chiamata: passa una copia di r
    printf("Area: %f", a);        // Area: 78.53975
    return 0;
}

La funzione area_cerchio è definita una volta e può essere chiamata ovunque, con qualsiasi raggio. raggio è locale: è una copia di r, e la funzione non può alterare r (passaggio per valore). Il main stesso è una funzione — quella da cui parte l'esecuzione. Il programma è ora modulare: il calcolo dell'area è isolato, riusabile e testabile.

⚠️ Attenzione. Non confondere definizione (scrivere la funzione, una volta) e chiamata (usarla, quante volte vuoi): definire non esegue. In C il passaggio è per valore: la funzione riceve copie, quindi non può modificare le variabili del chiamante (per farlo servono i puntatori, cap. 8). Le variabili locali esistono solo dentro la funzione: usarne una fuori dal suo scope è un errore. Evita le variabili globali: comunica tramite parametri e return.

🗺️ Come si collega il tutto

Le funzioni portano ordine e riuso nei programmi, che con sequenza, selezione e iterazione (cap. 4-5) potevano già esprimere ogni algoritmo ma diventavano ingestibili se grandi. Una funzione riceve parametri (per valore: copie), elabora, e restituisce un valore di ritorno (return) — struttura input→elaborazione→output (cap. 1). Le variabili locali e lo scope garantiscono l'indipendenza dei moduli, realizzando l'astrazione e il divide et impera. Il passaggio per valore protegge i dati ma impedisce a una funzione di modificare le variabili del chiamante: il ponte verso il capitolo successivo, i puntatori (cap. 8), che superano questo limite. Prima però servono le strutture per raggruppare più dati: gli array (cap. 7), che, combinati con cicli e funzioni, permettono di elaborare collezioni di valori — il passo verso programmi realmente utili. Il divide et impera tornerà nella ricorsione (cap. 10) e negli algoritmi (cap. 11).

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Funzione	Blocco di codice con nome, riusabile, che svolge un compito	(main è la funzione di partenza)
Parametro / argomento	Ingresso della funzione (definizione) / valore passato (chiamata)	Valore di ritorno (l'output)
Valore di ritorno (`return`)	Il risultato restituito al chiamante; `void` = nessuno	Parametri (gli ingressi)
Definizione / chiamata	Scrivere la funzione / eseguirla	(definire non esegue)
Passaggio per valore	La funzione riceve copie; non altera gli originali	Per riferimento (puntatori, cap. 8)
Variabile locale / scope	Esiste e si vede solo dentro la funzione	Variabile globale (visibile a tutte, sconsigliata)

📝 Riepilogo

Una funzione è un blocco di codice con nome, con un compito preciso, richiamabile ovunque. Realizza la modularità: riuso (scrivi una volta), leggibilità, manutenibilità (correggi in un solo posto), verificabilità, astrazione (sai cosa fa, non come).
Riceve parametri (ingressi), elabora e restituisce un valore di ritorno con return (void se nessuno). Distingui definizione (scrivere la funzione) e chiamata (eseguirla). In C il passaggio è per valore: la funzione riceve copie, quindi non modifica le variabili del chiamante (servono i puntatori, cap. 8).
Le variabili dichiarate in una funzione sono locali: esistono e sono visibili solo al suo interno (scope). Questo rende le funzioni indipendenti (stessi nomi non interferiscono). Le variabili globali sono sconsigliate: si comunica tramite parametri e return.
Le funzioni realizzano il divide et impera: scomporre un problema complesso in sotto-problemi risolti separatamente. Prossimo passo: raggruppare più dati con gli array (cap. 7), poi i puntatori (cap. 8).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Array e stringhe

In breve

Finora ogni variabile conteneva un solo valore. Ma molti problemi riguardano collezioni di dati: i voti di una classe, le temperature di un mese, i caratteri di una parola. Dichiarare cento variabili separate sarebbe assurdo. La soluzione è l'array (vettore): una struttura che raggruppa molti valori dello stesso tipo sotto un unico nome, accessibili tramite un indice numerico. Gli array, combinati con i cicli (cap. 5), sono lo strumento naturale per elaborare grandi quantità di dati con poche righe. Un caso particolare e importantissimo sono le stringhe, cioè gli array di caratteri con cui si rappresenta il testo. Questo capitolo spiega array monodimensionali e multidimensionali, il ruolo dell'indice e le stringhe in C.

🎯 Alla fine di questo capitolo saprai: cos'è un array e come si dichiara e si accede con l'indice; perché gli array si scorrono con i cicli; gli array multidimensionali (matrici); cosa sono le stringhe in C e il carattere terminatore; gli errori comuni (indici fuori range).

L'array: una collezione di dati

Perché conta: l'array è la struttura dati fondamentale per gestire collezioni; senza di esso ogni programma con molti dati sarebbe impraticabile.

Un array (o vettore) è una collezione ordinata di elementi, tutti dello stesso tipo, memorizzati in posizioni contigue di memoria e accessibili tramite un unico nome più un indice (la posizione). Invece di dichiarare voto1, voto2, ..., voto30, si dichiara un solo array voti di 30 elementi:

int voti[30];   // array di 30 interi: voti[0], voti[1], ..., voti[29]

Si accede a ciascun elemento con il suo indice tra parentesi quadre: voti[0] è il primo, voti[1] il secondo, voti[29] l'ultimo. Un dettaglio cruciale e fonte di infiniti errori: in C (come in quasi tutti i linguaggi) gli indici partono da zero, non da uno. Un array di $N$ elementi ha indici da 0 a N-1. Il primo elemento è voti[0], e l'ultimo è voti[N-1], non voti[N].

La potenza degli array emerge dalla combinazione con i cicli (cap. 5). Poiché gli elementi sono numerati da 0 a N-1, un ciclo for con contatore che va da 0 a N-1 può scorrere l'intero array, elaborando ogni elemento con le stesse istruzioni:

for (int i = 0; i < 30; i++) {
    somma = somma + voti[i];   // accumula tutti i voti
}

Con tre righe si elaborano 30 elementi (o 30 milioni, cambiando solo la dimensione). L'indice i del ciclo fa da "puntatore mobile" che scorre le posizioni. Questa sinergia array + ciclo è uno dei pattern più importanti della programmazione: ogni volta che si tratta una collezione, c'è un ciclo che la scorre.

🔗 Analogia. Un array è come una fila di caselle postali numerate in un condominio. C'è un unico "indirizzo" (il nome dell'array), e ogni casella ha un numero (l'indice) che la identifica: casella 0, casella 1, ecc. Per consegnare la posta (accedere a un dato) usi il numero della casella. E il postino, per svuotarle tutte, passa in ordine dalla prima all'ultima (il ciclo). Le caselle sono tutte uguali (stesso tipo) e affiancate (memoria contigua).

Array multidimensionali

Perché conta: molti dati reali sono organizzati in tabelle o griglie; gli array multidimensionali li rappresentano naturalmente.

Un array "normale" è monodimensionale: una singola fila di elementi. Ma molti dati hanno una struttura a griglia o tabella: una scacchiera, i pixel di un'immagine, i voti di più studenti in più materie, una matrice matematica (cap. di geometria). Per questi si usano gli array multidimensionali, in particolare quelli bidimensionali (matrici), che si immaginano come una tabella con righe e colonne:

int matrice[3][4];   // 3 righe, 4 colonne: 12 elementi

Si accede a un elemento con due indici: matrice[i][j] è l'elemento nella riga i, colonna j (entrambi partendo da 0). Per scorrere una matrice servono due cicli annidati (cap. 4-5): uno esterno per le righe, uno interno per le colonne:

for (int i = 0; i < 3; i++)         // per ogni riga
    for (int j = 0; j < 4; j++)     // per ogni colonna
        printf("%d ", matrice[i][j]);

Il ciclo interno scorre tutta una riga; quello esterno passa alla riga successiva. Questo pattern (due cicli annidati) è tipico di ogni elaborazione su tabelle: sommare gli elementi di una matrice, moltiplicare matrici, elaborare un'immagine pixel per pixel. Si possono avere anche array a tre o più dimensioni (per dati ancora più strutturati, come un cubo di dati), ma quelli mono- e bidimensionali coprono la maggior parte dei casi.

Le stringhe

Perché conta: le stringhe rappresentano il testo, onnipresente in ogni programma; in C hanno peculiarità che è essenziale conoscere.

Come si rappresenta il testo (una parola, una frase, un nome) in un programma? Con una stringa: una sequenza di caratteri. In C — e qui sta una peculiarità del linguaggio — una stringa non è un tipo a sé, ma semplicemente un array di char (caratteri, cap. 3), con una convenzione speciale. La parola "Ciao" è memorizzata come un array contenente i caratteri 'C', 'i', 'a', 'o'.

La convenzione fondamentale del C è il carattere terminatore: ogni stringa termina con un carattere speciale, il carattere nullo '\0' (il byte con valore zero), che segnala "qui finisce la stringa". Serve perché il programma, scorrendo l'array carattere per carattere, deve sapere dove fermarsi (l'array potrebbe essere più lungo del testo che contiene). Conseguenza pratica: una stringa di $N$ caratteri richiede un array di almeno $N+1$ elementi (uno spazio in più per il '\0'). Dimenticare questo spazio è un errore classico e insidioso.

char nome[10] = "Mario";   // 5 caratteri + '\0' = 6 usati (dei 10)

Le stringhe si elaborano scorrendole con un ciclo fino a incontrare '\0'. Poiché la manipolazione manuale è laboriosa e soggetta a errori, il C fornisce una libreria di funzioni dedicate (string.h): strlen (lunghezza), strcpy (copia), strcat (concatena), strcmp (confronta). Un'avvertenza importante: le stringhe non si confrontano con == (che confronterebbe indirizzi, non contenuti) né si copiano con =: bisogna usare le funzioni apposite (strcmp, strcpy). È una delle trappole più comuni per chi arriva da altri linguaggi.

🧩 Esempio. Contare le vocali in una stringa, scorrendola fino al terminatore:

char parola[] = "programmazione";
int vocali = 0;
for (int i = 0; parola[i] != '\0'; i++) {   // scorre fino a '\0'
    char c = parola[i];
    if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
        vocali++;
}
printf("Vocali: %d", vocali);   // Vocali: 6

La condizione del ciclo parola[i] != '\0' scorre carattere per carattere finché non trova il terminatore: non serve conoscere in anticipo la lunghezza, è il '\0' a dire "stop". Un contatore (cap. 5) conta le vocali. Array di caratteri, ciclo e terminatore lavorano insieme — l'essenza dell'elaborazione del testo in C.

⚠️ Attenzione. Gli indici partono da 0: un array di $N$ elementi va da 0 a N-1. Accedere fuori da questo intervallo (es. voti[30] in un array di 30) è un grave errore — il C non controlla i limiti e legge/scrive memoria non sua (buffer overflow), causando comportamenti imprevedibili o crash (e vulnerabilità di sicurezza!). Per le stringhe: prevedi sempre lo spazio per il '\0' (N+1 caratteri), e usa le funzioni di string.h (strcmp, strcpy), non == o =.

🗺️ Come si collega il tutto

Gli array superano il limite "una variabile = un valore": raggruppano collezioni di dati dello stesso tipo, accessibili per indice (da 0 a N-1). La loro potenza si sprigiona coi cicli (cap. 5): un for scorre l'array elaborando ogni elemento — il pattern collezione+ciclo. Gli array multidimensionali (matrici) rappresentano tabelle e griglie, scorse con cicli annidati (cap. 4-5). Le stringhe sono array di char (cap. 3) con il terminatore '\0', elaborate con cicli e la libreria string.h. Gli array sono memorizzati in modo contiguo in memoria: questo li lega intimamente ai puntatori (cap. 8), che ne svelano il funzionamento interno (il nome di un array è, di fatto, l'indirizzo del primo elemento). Combinati con le funzioni (cap. 6), gli array permettono di scrivere algoritmi realistici — come l'ordinamento e la ricerca (cap. 11), che operano proprio su array.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Array	Collezione di elementi dello stesso tipo, accessibili per indice	Struct (dati di tipi diversi, cap. 9)
Indice	Posizione dell'elemento; parte da 0 (fino a N-1)	(l'ultimo è N-1, non N!)
Array + ciclo	Un `for` scorre tutti gli elementi (pattern fondamentale)	(l'indice del ciclo scorre le posizioni)
Matrice	Array bidimensionale (righe × colonne); due indici	Array monodimensionale (una fila)
Stringa	Array di `char` terminato da `'\0'`	(in C non è un tipo a sé)
Terminatore `'\0'`	Segna la fine della stringa; richiede uno spazio in più	(N caratteri → array di N+1)

📝 Riepilogo

Un array raggruppa molti elementi dello stesso tipo in memoria contigua, sotto un unico nome, accessibili per indice: voti[i]. Gli indici partono da 0 (un array di N elementi va da 0 a N-1). La potenza emerge coi cicli: un for scorre l'array elaborando ogni elemento — pattern fondamentale.
Gli array multidimensionali (matrici, matrice[i][j]) rappresentano tabelle/griglie e si scorrono con cicli annidati (esterno = righe, interno = colonne). Utili per immagini, matrici, dati tabellari.
Le stringhe sono, in C, array di char terminati dal carattere nullo '\0', che segna la fine (serve uno spazio in più: N caratteri → array di N+1). Si elaborano scorrendo fino a '\0'; la libreria string.h offre strlen, strcpy, strcat, strcmp. Non confrontarle con == né copiarle con =.
Errore grave: indice fuori range (il C non controlla i limiti → buffer overflow, crash, vulnerabilità). Gli array sono legati ai puntatori (memoria contigua, cap. 8) e sono la base di ordinamento e ricerca (cap. 11). Prossimo passo: i puntatori (cap. 8).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Puntatori e gestione della memoria

In breve

I puntatori sono il concetto più temuto — e più potente — del linguaggio C. Un puntatore è una variabile che, invece di contenere un valore, contiene un indirizzo di memoria: "punta" a dove un dato si trova. Sembra un dettaglio tecnico, ma è la chiave che sblocca le capacità più profonde del C: permettere alle funzioni di modificare i dati del chiamante, gestire la memoria dinamicamente, costruire strutture dati flessibili. Capire i puntatori significa capire come funziona davvero la memoria di un computer. Questo capitolo li spiega dalle fondamenta: cos'è un indirizzo, cosa fanno gli operatori & e *, il legame tra puntatori e array, e un'introduzione alla memoria dinamica.

🎯 Alla fine di questo capitolo saprai: cos'è un indirizzo di memoria e un puntatore; gli operatori & (indirizzo di) e * (dereferenziazione); come i puntatori permettono il passaggio per riferimento; il legame tra puntatori e array; un cenno alla memoria dinamica (malloc/free).

Indirizzi e puntatori

Perché conta: il puntatore è la porta d'accesso al funzionamento reale della memoria; è indispensabile per le funzionalità avanzate del C.

Per capire i puntatori, bisogna prima capire come è organizzata la memoria (RAM, cap. 1). La memoria è una lunghissima sequenza di celle, ciascuna con un indirizzo numerico univoco (come le case lungo una strada, ciascuna col suo numero civico). Quando si dichiara una variabile, il computer le assegna una o più celle di memoria a un certo indirizzo, e lì conserva il suo valore. Finora abbiamo lavorato con i valori delle variabili, ignorando dove fossero. I puntatori portano in primo piano gli indirizzi.

Un puntatore è una variabile speciale il cui valore è un indirizzo di memoria: non contiene un dato, ma dice dove si trova un dato. Si dice che il puntatore "punta a" quella locazione. In C si dichiara con un asterisco: int *p; dichiara p come "puntatore a un intero" — una variabile che conterrà l'indirizzo di un int. Il tipo è importante: un puntatore "sa" a che tipo di dato punta (un puntatore a int è diverso da uno a char), perché deve sapere come interpretare i byte a quell'indirizzo.

Due operatori fondamentali collegano valori e indirizzi:

l'operatore & ("indirizzo di"): applicato a una variabile, ne restituisce l'indirizzo. &x è "dove si trova x in memoria". (È lo stesso & che usiamo in scanf("%d", &x) — passiamo l'indirizzo di x perché scanf possa scrivervi dentro!);
l'operatore * ("dereferenziazione", o "contenuto di"): applicato a un puntatore, accede al valore presente all'indirizzo puntato. Se p punta a x, allora *p è il valore di x, e si può anche modificare (*p = 5 cambia x).

🔗 Analogia. Un puntatore è come un bigliettino con scritto un indirizzo. Il bigliettino non contiene la casa (il valore), ma dice dove si trova la casa (&casa = "prendi l'indirizzo"). Per andare fisicamente alla casa e vedere/cambiare cosa c'è dentro, segui l'indirizzo scritto sul bigliettino (*p = "vai lì e guarda dentro"). Puoi anche fotocopiare il bigliettino (copiare il puntatore): ora due persone conoscono l'indirizzo della stessa casa, e se una cambia l'arredamento, l'altra lo vede.

Puntatori e funzioni: il passaggio per riferimento

Perché conta: i puntatori risolvono il limite del passaggio per valore, permettendo alle funzioni di modificare i dati del chiamante — un'esigenza costante.

Ricordiamo il limite visto nel cap. 6: in C il passaggio dei parametri è per valore (la funzione riceve copie), quindi una funzione non può modificare le variabili del chiamante. Ma spesso è proprio ciò che serve: una funzione scambia(a, b) che scambi i valori di due variabili, o una che restituisca più di un risultato. I puntatori risolvono elegantemente il problema.

L'idea: invece di passare alla funzione il valore di una variabile, le si passa il suo indirizzo (con &). La funzione riceve così un puntatore che le dice dove si trova la variabile originale; usando * può allora accedere e modificare direttamente il dato originale del chiamante. Questo si chiama passaggio per riferimento (simulato tramite puntatori):

void raddoppia(int *p) {
    *p = *p * 2;        // modifica il valore ALL'INDIRIZZO puntato
}
int main() {
    int x = 5;
    raddoppia(&x);      // passa l'INDIRIZZO di x
    printf("%d", x);    // stampa 10: x È stato modificato!
}

Passando &x (l'indirizzo) invece di x (il valore), la funzione può raggiungere la vera x e cambiarla. È così che scanf scrive nelle nostre variabili (per questo vuole &x), e come una funzione può "restituire" più valori (modificando più variabili tramite puntatori). Il passaggio per riferimento è uno degli usi più importanti dei puntatori.

Puntatori, array e memoria dinamica

Perché conta: il legame puntatori-array e la memoria dinamica sono alla base delle strutture dati flessibili e dell'uso efficiente della memoria.

C'è un legame profondo tra puntatori e array (cap. 7). In C, il nome di un array è, di fatto, l'indirizzo del suo primo elemento: un array "è" essenzialmente un puntatore alla sua prima cella. Ecco perché gli elementi sono in memoria contigua e perché array[i] funziona: significa "vai all'indirizzo dell'array, spostati di i posizioni, e prendi il valore lì". Questa aritmetica dei puntatori (sommare a un puntatore per spostarsi tra elementi adiacenti) è ciò che sta sotto l'accesso per indice. Di conseguenza, quando si passa un array a una funzione, si passa in realtà il suo indirizzo: la funzione può modificare l'array originale (a differenza delle variabili semplici) — perché di fatto riceve un puntatore.

I puntatori abilitano anche la memoria dinamica, cioè la possibilità di richiedere memoria durante l'esecuzione, quando serve e quanta serve. Finora le variabili e gli array avevano dimensione fissa, decisa alla scrittura del programma. Ma spesso non si sa in anticipo quanti dati arriveranno (quanti nomi inserirà l'utente?). Con la memoria dinamica si chiede al sistema un blocco di memoria a runtime, tramite la funzione malloc (memory allocation), che restituisce un puntatore all'area riservata:

int *v = malloc(n * sizeof(int));   // riserva spazio per n interi a runtime

Ora v si può usare come un array di n elementi, con n deciso durante l'esecuzione. Regola d'oro: la memoria richiesta con malloc va restituita quando non serve più, con la funzione free. Dimenticarlo causa il memory leak (perdita di memoria): il programma accumula memoria mai liberata, fino a esaurirla. La gestione manuale della memoria è potente ma delicata, e una delle principali fonti di bug nel C. È anche il fondamento delle strutture dati dinamiche (liste, alberi), che crescono e si riducono durante l'esecuzione (cap. 9).

🧩 Esempio. La funzione scambia, impossibile senza puntatori:

void scambia(int *a, int *b) {
    int temp = *a;      // salva il valore puntato da a
    *a = *b;            // metti in *a il valore di *b
    *b = temp;          // metti in *b il valore salvato
}
int main() {
    int x = 3, y = 7;
    scambia(&x, &y);    // passa gli INDIRIZZI
    printf("%d %d", x, y);   // 7 3: scambiati davvero!
}

Passando gli indirizzi &x e &y, la funzione raggiunge le variabili originali e le scambia tramite *. Con il passaggio per valore (senza puntatori) scambierebbe solo le copie, e x e y resterebbero 3 e 7. I puntatori rendono possibile ciò che altrimenti sarebbe impossibile.

⚠️ Attenzione. Non confondere p (l'indirizzo, dove punta), *p (il valore puntato, il contenuto) e &x (l'indirizzo di x). Il pericolo maggiore sono i puntatori non validi: un puntatore non inizializzato, o che punta a memoria liberata/inesistente (puntatore penzolante), causa crash o corruzione (il temuto segmentation fault). Regole: inizializza sempre i puntatori; per ogni malloc ci sia un free (evita memory leak); non usare memoria dopo averla liberata. I puntatori sono potentissimi ma non perdonano errori.

🗺️ Come si collega il tutto

I puntatori rivelano il funzionamento reale della memoria (celle con indirizzi, cap. 1): un puntatore contiene un indirizzo, & lo ottiene, * accede al valore puntato. Risolvono il limite del passaggio per valore delle funzioni (cap. 6): passando indirizzi (&x) si realizza il passaggio per riferimento, con cui una funzione modifica i dati del chiamante (è come opera scanf). Svelano il legame con gli array (cap. 7): il nome di un array è l'indirizzo del primo elemento, e l'accesso per indice è aritmetica dei puntatori. Abilitano la memoria dinamica (malloc/free) per gestire dati di dimensione variabile a runtime — il fondamento delle strutture dati dinamiche (liste, alberi) che, insieme alle struct (cap. 9), permettono di costruire modelli di dati complessi e flessibili. I puntatori sono la chiave del "potere di basso livello" del C.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Indirizzo	Numero che identifica una cella di memoria	Valore (il contenuto della cella)
Puntatore	Variabile che contiene un indirizzo ("punta a" un dato)	Variabile normale (contiene un valore)
`&` (indirizzo di)	`&x` = l'indirizzo dove si trova x	`*` (accede al contenuto puntato)
*`` (dereferenziazione)**	`*p` = il valore all'indirizzo puntato da p	`&` (ottiene l'indirizzo)
Passaggio per riferimento	Passare `&x` così la funzione modifica l'originale	Per valore (copie, non modifica, cap. 6)
`malloc` / `free`	Richiede / restituisce memoria a runtime	(ogni malloc → un free, o memory leak)

📝 Riepilogo

La memoria è fatta di celle con indirizzi univoci. Un puntatore è una variabile che contiene un indirizzo ("punta a" un dato). Operatori: & ("indirizzo di", &x) ottiene dove si trova una variabile; * ("dereferenziazione", *p) accede al valore all'indirizzo puntato (e lo può modificare).
I puntatori superano il limite del passaggio per valore (cap. 6): passando l'indirizzo (&x), una funzione riceve un puntatore e con * modifica direttamente la variabile originale del chiamante (passaggio per riferimento). È così che scanf scrive nelle variabili e come una funzione "restituisce" più valori.
Puntatori e array: il nome di un array è l'indirizzo del primo elemento; l'accesso array[i] è aritmetica dei puntatori. Passare un array = passare il suo indirizzo. La memoria dinamica (malloc/free) richiede memoria a runtime (dimensione variabile): ogni malloc va bilanciato da un free (altrimenti memory leak).
Distingui p (indirizzo), *p (valore puntato), &x (indirizzo di x). Pericoli: puntatori non inizializzati/penzolanti (crash, segfault), memory leak, uso dopo free. Prossimo passo: raggruppare dati eterogenei con le strutture (cap. 9).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Strutture dati e tipi definiti dall'utente

In breve

Un array raggruppa dati tutti dello stesso tipo. Ma un'entità del mondo reale — uno studente, un punto nello spazio, una data — è fatta di attributi di tipi diversi: uno studente ha un nome (stringa), una matricola (intero), una media (reale). Per rappresentarla serve uno strumento che unisca dati eterogenei in un unico oggetto coerente: la struttura (struct). Le struct permettono di creare nuovi tipi su misura del problema, avvicinando il programma al modo in cui pensiamo il mondo. Combinate con array e puntatori, sono la base delle strutture dati più sofisticate (liste, alberi) che organizzano l'informazione in modi flessibili e potenti. Questo capitolo introduce le struct, i tipi definiti dall'utente e un'idea delle strutture dati dinamiche.

🎯 Alla fine di questo capitolo saprai: cos'è una struttura (struct) e come raggruppa dati eterogenei; come si definisce un tipo su misura; l'accesso ai campi; la combinazione con array e puntatori; un'introduzione alle strutture dati dinamiche (liste, alberi) e alla scelta della struttura giusta.

Le strutture (struct)

Perché conta: le struct permettono di modellare entità del mondo reale unendo attributi eterogenei; sono il ponte tra i dati grezzi e i concetti del problema.

Un array ha un limite: tutti i suoi elementi devono essere dello stesso tipo. Ma le entità reali sono composte da attributi diversi. Uno studente ha: un nome (testo), una matricola (numero intero), una media dei voti (numero reale). Tenere questi dati in tre variabili separate (o tre array paralleli) è scomodo e fragile. La struttura (in C, struct) risolve il problema: raggruppa in un unico oggetto più variabili, anche di tipi diversi, chiamate campi (o membri).

Si definisce una struttura descrivendone i campi:

struct Studente {
    char nome[30];      // campo di tipo stringa
    int matricola;      // campo di tipo intero
    float media;        // campo di tipo reale
};

Questo crea un nuovo "stampo" (un tipo) chiamato struct Studente. Da esso si possono dichiarare variabili, ciascuna un pacchetto completo con i suoi tre campi:

struct Studente s;

Si accede ai singoli campi con l'operatore punto (.): s.nome, s.matricola, s.media. Ogni campo si usa come una normale variabile del suo tipo (s.matricola = 12345;). La struttura tiene insieme, in modo ordinato e coerente, tutti i dati di un'entità: manipolare "uno studente" diventa naturale come manipolare un singolo oggetto, anziché giostrare tra variabili sparse.

🔗 Analogia. Una struct è come una scheda anagrafica (o una carta d'identità). Invece di tenere il nome su un foglietto, la data di nascita su un altro, l'indirizzo su un terzo (rischiando di mescolarli), metti tutto su un'unica scheda con campi etichettati: Nome, Data, Indirizzo. La scheda è un singolo oggetto che porti in giro tutto insieme, e ogni campo lo leggi guardando l'etichetta giusta. La struct fa esattamente questo con i dati eterogenei di un'entità.

Tipi definiti dall'utente e combinazioni

Perché conta: creare tipi su misura e combinarli con array e puntatori è ciò che permette di modellare dati complessi in modo naturale.

Le struct sono un esempio di tipi definiti dall'utente: il programmatore non è limitato ai tipi predefiniti (int, float...), ma può creare i propri tipi su misura del problema. In C, la parola chiave typedef permette di dare un nome più breve e comodo a un tipo (per esempio Studente invece di struct Studente), migliorando la leggibilità. Questa capacità di definire nuovi tipi è un passo importante verso l'astrazione dei dati: si modella il programma nei termini del dominio (studenti, conti bancari, punti geometrici) invece che in termini di dati grezzi.

La vera potenza emerge combinando le struct con gli strumenti precedenti:

array di struct: un array di Studente rappresenta un'intera classe (struct Studente classe[100];). Scorrendolo con un ciclo (cap. 5) si elaborano tutti gli studenti — la lista dei dipendenti di un'azienda, i prodotti di un magazzino;
struct annidate: un campo di una struct può essere a sua volta una struct (uno Studente può contenere una struct Data per la data di nascita), costruendo modelli gerarchici;
puntatori a struct: si può puntare a una struct (cap. 8); per accedere ai campi tramite un puntatore si usa l'operatore freccia -> (p->matricola, abbreviazione di (*p).matricola). Questo è essenziale per passare struct alle funzioni in modo efficiente (senza copiarle) e per costruire le strutture dinamiche.

Queste combinazioni permettono di rappresentare dati arbitrariamente complessi: un'azienda (struct) con un array di reparti (struct), ciascuno con un array di dipendenti (struct), ciascuno con una data di assunzione (struct). Il programma rispecchia la struttura del problema reale.

Le strutture dati dinamiche

Perché conta: liste, alberi e altre strutture dinamiche sono strumenti fondamentali dell'informatica; scegliere la struttura giusta determina l'efficienza di un programma.

Combinando struct e puntatori con la memoria dinamica (cap. 8) si costruiscono le strutture dati dinamiche: organizzazioni di dati che crescono e si riducono durante l'esecuzione, superando la rigidità degli array a dimensione fissa. L'idea-chiave: una struct contiene, oltre ai dati, uno o più puntatori ad altre struct dello stesso tipo, creando catene o reti di elementi collegati. Le principali:

la lista concatenata (linked list): una catena di nodi, ciascuno contenente un dato e un puntatore al nodo successivo. A differenza dell'array, cresce dinamicamente (si aggiungono nodi a runtime) e l'inserimento/eliminazione in mezzo è efficiente (basta ridirigere i puntatori), ma non si può accedere direttamente all'i-esimo elemento (bisogna scorrere dal primo). Utile quando la dimensione varia molto e si inserisce/rimuove spesso;
l'albero (tree): una struttura gerarchica in cui ogni nodo può avere più "figli". Rappresenta naturalmente gerarchie (file system, organigrammi) e, in forme particolari (alberi di ricerca), permette ricerche molto efficienti;
altre: pile (stack, "ultimo entrato primo uscito"), code (queue, "primo entrato primo uscito"), grafi (reti di nodi collegati, per mappe e social network).

Il messaggio profondo è che la scelta della struttura dati è cruciale quanto quella dell'algoritmo. Struttura dati e algoritmo sono due facce dello stesso problema: la struttura giusta rende un'operazione facile ed efficiente, quella sbagliata la rende lenta o complicata. Un array è ottimo per l'accesso diretto per indice ma rigido nelle dimensioni; una lista è flessibile ma lenta nell'accesso casuale; un albero è ideale per ricerche ordinate. Scegliere bene è arte e scienza insieme — un tema centrale del corso successivo, Algoritmi e Strutture Dati.

🧩 Esempio. Una struct per rappresentare un punto nel piano e usarla:

struct Punto {
    double x;
    double y;
};

struct Punto p;
p.x = 3.0;              // accesso ai campi con il punto
p.y = 4.0;
double distanza = sqrt(p.x*p.x + p.y*p.y);   // distanza dall'origine: 5.0

La struct Punto unisce le due coordinate in un singolo oggetto coerente (come un vettore, cap. di geometria): invece di gestire due double scollegati, si manipola "un punto". Si potrebbe passare p a una funzione distanza(struct Punto), creare un array di punti (un poligono), ecc. La struct avvicina il codice al concetto matematico.

⚠️ Attenzione. Si accede ai campi con il punto (.) su una struct, con la freccia (->) su un puntatore a struct (p->x = (*p).x): confonderli è un errore comune. Una struct raggruppa dati eterogenei (a differenza dell'array, omogeneo). Le strutture dinamiche (liste, alberi) usano malloc/free (cap. 8): valgono le stesse cautele (memory leak, puntatori penzolanti). E ricorda: non esiste "la struttura migliore" in assoluto — dipende dalle operazioni che dovrai fare più spesso.

🗺️ Come si collega il tutto

Le struct superano il limite dell'omogeneità degli array (cap. 7): raggruppano dati eterogenei (campi di tipi diversi) in un oggetto coerente, accessibile col punto (.). Sono tipi definiti dall'utente (typedef), un passo verso l'astrazione dei dati: modellare il problema nei suoi termini. Combinate con array (array di struct = collezioni di entità), struct annidate e puntatori (accesso con ->, cap. 8), rappresentano dati complessi. Con la memoria dinamica (cap. 8) nascono le strutture dati dinamiche (liste, alberi, pile, code, grafi), che crescono a runtime e la cui scelta determina l'efficienza — legando struttura dati e algoritmo. Questo prepara i temi finali del corso: gli algoritmi che operano su queste strutture (ordinamento, ricerca, cap. 11) e la loro complessità (cap. 12), oltre alla tecnica della ricorsione (cap. 10), naturale per le strutture gerarchiche come gli alberi.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
struct	Raggruppa dati eterogenei (campi di tipi diversi) in un oggetto	Array (elementi dello stesso tipo)
Campo (membro)	Un attributo della struct, accessibile col punto `.`	(ogni campo ha il suo tipo)
Tipo definito dall'utente	Nuovo tipo creato dal programmatore (`typedef`)	Tipo predefinito (`int`, `float`)
`.` vs `->`	Punto su una struct / freccia su un puntatore a struct	(`p->x` = `(*p).x`)
Lista concatenata	Nodi collegati da puntatori; cresce dinamicamente	Array (dimensione fissa, accesso diretto)
Albero	Struttura gerarchica (nodi con figli)	Lista (lineare) / grafo (rete generica)

📝 Riepilogo

La struttura (struct) raggruppa dati eterogenei (campi di tipi diversi) in un unico oggetto coerente, superando l'omogeneità dell'array. Modella entità reali (studente, punto, data). Si accede ai campi con l'operatore punto (.): s.matricola.
Le struct sono tipi definiti dall'utente (con typedef si abbreviano), un passo verso l'astrazione dei dati. Si combinano con: array di struct (collezioni di entità), struct annidate (modelli gerarchici), puntatori a struct (accesso con la freccia ->, efficienza, base delle strutture dinamiche).
Unendo struct, puntatori e memoria dinamica (cap. 8) nascono le strutture dati dinamiche: liste concatenate (catene di nodi, flessibili, crescono a runtime), alberi (gerarchie, ricerche efficienti), pile, code, grafi. Crescono e si riducono durante l'esecuzione.
La scelta della struttura dati è cruciale quanto l'algoritmo: non esiste "la migliore", dipende dalle operazioni frequenti (array = accesso per indice; lista = inserimenti; albero = ricerca ordinata). Distingui . (struct) e -> (puntatore). Prossimo passo: la ricorsione (cap. 10).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

La ricorsione

In breve

La ricorsione è una delle idee più eleganti e potenti dell'informatica: una funzione che, per risolvere un problema, chiama sé stessa su una versione più piccola dello stesso problema. Sembra un paradosso (come può una cosa definirsi in termini di sé stessa senza avvitarsi all'infinito?), ma è invece un modo naturalissimo di pensare — molti problemi hanno una struttura intrinsecamente ricorsiva. La ricorsione permette di esprimere soluzioni complesse in poche righe cristalline, dove un approccio iterativo sarebbe contorto. Questo capitolo spiega il meccanismo della ricorsione, i suoi due ingredienti indispensabili (caso base e caso ricorsivo), come funziona in memoria, e quando conviene usarla.

🎯 Alla fine di questo capitolo saprai: cos'è la ricorsione e come una funzione chiama sé stessa; i due ingredienti essenziali (caso base e caso ricorsivo); come funziona la ricorsione in memoria (stack); il legame con il divide et impera; quando conviene la ricorsione rispetto all'iterazione.

L'idea di ricorsione

Perché conta: la ricorsione è un modo di pensare fondamentale, che risolve elegantemente problemi con struttura auto-simile.

La ricorsione si ha quando una funzione, nel suo corpo, chiama sé stessa. Detta così sembra un cortocircuito, ma è un'idea profonda: molti problemi si possono risolvere riducendoli a una versione più piccola dello stesso problema, finché non si arriva a un caso talmente semplice da essere risolto direttamente. Invece di dire "come faccio tutto?", si dice "come riduco il problema a uno leggermente più piccolo, dello stesso tipo?".

Un esempio classico è il fattoriale di un numero ( $n! = n \times (n-1) \times \dots \times 1$ ). Lo si può definire ricorsivamente osservando che $n! = n \times (n-1)!$ : il fattoriale di $n$ è $n$ moltiplicato per il fattoriale di $n-1$ (un problema più piccolo, dello stesso tipo). E $(n-1)!$ a sua volta è $(n-1) \times (n-2)!$ , e così via, fino a $1! = 1$ (il caso semplice). La definizione si "appoggia su sé stessa", ma su input sempre più piccoli, fino a fermarsi.

Molti concetti sono per natura ricorsivi: le definizioni matematiche (successioni), le strutture dati gerarchiche (un albero è un nodo con dei sotto-alberi — cap. 9), i frattali, l'esplorazione di cartelle (una cartella contiene file e altre cartelle). Per questi, la soluzione ricorsiva è la più naturale e leggibile: rispecchia la struttura del problema. Pensare ricorsivamente — "assumo di saper risolvere il caso più piccolo, e costruisco su quello" — è una competenza chiave del programmatore.

🔗 Analogia. La ricorsione è come le bambole russe (matrioske): per aprire la bambola più grande, la apri e trovi dentro una bambola più piccola, identica ma minore; la apri e ne trovi un'altra ancora più piccola... finché arrivi alla bambolina più piccola che non si apre (il caso base). Ogni passo è "la stessa azione su una versione ridotta", e il processo si ferma perché c'è una bambola finale. Senza quella bambolina piena (il caso base), continueresti ad aprire all'infinito.

Caso base e caso ricorsivo

Perché conta: senza i due ingredienti corretti, la ricorsione non funziona (loop infinito); capirli è la chiave per scrivere funzioni ricorsive corrette.

Ogni funzione ricorsiva ben fatta ha due ingredienti irrinunciabili, che devono coesistere:

il caso base (o condizione di arresto): il caso più semplice, che si risolve direttamente, senza ulteriori chiamate ricorsive. È ciò che ferma la ricorsione. Per il fattoriale: $1! = 1$ (o $0! = 1$ );
il caso ricorsivo: la regola che risolve il problema generale chiamando la funzione su un caso più piccolo, avvicinandosi al caso base. Per il fattoriale: $n! = n \times (n-1)!$ .

La condizione cruciale è che ogni chiamata ricorsiva si avvicini al caso base (il problema deve rimpicciolire): così, prima o poi, si raggiunge il caso base e la catena di chiamate si ferma, "tornando indietro" con i risultati. Se manca il caso base, o se il caso ricorsivo non si avvicina ad esso, si ha una ricorsione infinita — l'equivalente del ciclo infinito (cap. 5), che qui esaurisce la memoria e fa crashare il programma (stack overflow). Scrivere una funzione ricorsiva significa sempre chiedersi: "qual è il caso base? e il caso ricorsivo si avvicina ad esso?".

In C, il fattoriale ricorsivo è limpido:

int fattoriale(int n) {
    if (n <= 1)                    // CASO BASE: si risolve direttamente
        return 1;
    else                           // CASO RICORSIVO: chiama sé stessa su n-1
        return n * fattoriale(n - 1);
}

Cinque righe che catturano l'intera definizione matematica. La chiamata fattoriale(4) genera 4 * fattoriale(3), che genera 3 * fattoriale(2), poi 2 * fattoriale(1), che è il caso base e vale 1; poi i risultati "risalgono": 2*1=2, 3*2=6, 4*6=24.

La ricorsione in memoria e quando usarla

Perché conta: capire come la ricorsione usa la memoria (stack) e i suoi costi permette di scegliere consapevolmente tra ricorsione e iterazione.

Come fa il computer a gestire una funzione che chiama sé stessa più volte, tenendo traccia di tutte le chiamate "in sospeso"? Usa una struttura chiamata stack di chiamata (call stack, una pila — cap. 9). Ogni volta che una funzione viene chiamata (anche ricorsivamente), il sistema crea un record di attivazione (un "foglietto") con le sue variabili locali e il punto a cui tornare, e lo mette in cima alla pila. Le chiamate ricorsive impilano questi record: fattoriale(4) in attesa sopra ci mette fattoriale(3), sopra fattoriale(2), ecc. Quando si raggiunge il caso base, i record si svuotano dalla cima verso il basso, ciascuno restituendo il suo risultato al precedente. È come una pila di piatti: metti in cima, togli dalla cima.

Questo spiega un costo della ricorsione: ogni chiamata in sospeso occupa memoria sullo stack. Una ricorsione troppo profonda (o infinita) esaurisce lo stack → stack overflow (crash). Inoltre, la ricorsione ha un piccolo sovraccarico (gestire le chiamate). Per questo si pone la scelta ricorsione vs iterazione (cap. 5):

teoricamente equivalenti: ogni problema risolubile ricorsivamente lo è anche iterativamente (con cicli) e viceversa;
l'iterazione è di solito più efficiente (meno memoria e sovraccarico): per problemi semplici come il fattoriale o la somma, un ciclo è preferibile in pratica;
la ricorsione è più elegante e naturale quando il problema è intrinsecamente ricorsivo: attraversare un albero (cap. 9), il divide et impera (dividere un problema in due metà — la base degli algoritmi di ordinamento veloci, cap. 11), problemi come le Torri di Hanoi, l'esplorazione di labirinti. In questi casi la versione iterativa sarebbe molto più contorta.

La ricorsione è la realizzazione più pura del divide et impera (cap. 6): un problema si divide in sotto-problemi identici ma più piccoli, si risolvono ricorsivamente e si combinano le soluzioni. Sapere quando usarla — eleganza contro efficienza — è segno di maturità nel programmare.

🧩 Esempio. La successione di Fibonacci (ogni numero è la somma dei due precedenti: 0, 1, 1, 2, 3, 5, 8...) ha una definizione ricorsiva naturale: $F(n) = F(n-1) + F(n-2)$ , con casi base $F(0)=0$ , $F(1)=1$ .

int fib(int n) {
    if (n <= 1) return n;              // casi base: F(0)=0, F(1)=1
    return fib(n-1) + fib(n-2);        // caso ricorsivo
}

Elegantissima e fedele alla definizione. Ma attenzione: questa versione è inefficiente (ricalcola gli stessi valori molte volte — fib(5) calcola fib(2) più volte), un esempio perfetto di come la ricorsione, per quanto pulita, non sia sempre la scelta migliore in termini di prestazioni (cap. 12). Un ciclo o la "memoizzazione" sarebbero molto più veloci.

⚠️ Attenzione. Una funzione ricorsiva deve avere un caso base raggiungibile, e ogni chiamata deve avvicinarsi ad esso: senza, si ha ricorsione infinita → stack overflow (crash per esaurimento memoria), l'analogo del ciclo infinito. La ricorsione è elegante ma non gratis: consuma stack e può essere inefficiente (Fibonacci naïf). Regola pratica: usala quando il problema è intrinsecamente ricorsivo (alberi, divide et impera); preferisci l'iterazione per problemi lineari semplici.

🗺️ Come si collega il tutto

La ricorsione è una funzione (cap. 6) che chiama sé stessa su un problema più piccolo, fino a un caso base che la ferma. È l'incarnazione più pura del divide et impera (cap. 6): dividere in sotto-problemi identici e combinarne le soluzioni. Richiede sempre due ingredienti — caso base (arresto) e caso ricorsivo (che si avvicina alla base) — pena la ricorsione infinita (analoga al ciclo infinito, cap. 5). In memoria usa lo stack di chiamata (una pila, cap. 9), con un costo che la rende talvolta meno efficiente dell'iterazione (cap. 5), a cui è comunque teoricamente equivalente. La ricorsione brilla sulle strutture intrinsecamente ricorsive: gli alberi (cap. 9) e, soprattutto, gli algoritmi divide et impera di ordinamento (merge sort, quick sort) e ricerca (ricerca binaria) — il tema del prossimo capitolo (cap. 11). La sua efficienza si valuterà con la complessità (cap. 12).

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Ricorsione	Una funzione che chiama sé stessa su un problema più piccolo	Iterazione (ripete con un ciclo, cap. 5)
Caso base	Il caso semplice risolto direttamente: ferma la ricorsione	Caso ricorsivo (richiama la funzione)
Caso ricorsivo	Risolve il problema chiamando sé stessa su input più piccolo	(deve avvicinarsi al caso base)
Ricorsione infinita	Manca il caso base o non ci si avvicina → stack overflow	Ciclo infinito (l'analogo iterativo)
Stack di chiamata	Pila dei record delle chiamate in sospeso	(una ricorsione profonda lo riempie)
Divide et impera	Dividere in sotto-problemi identici e combinare	(la ricorsione ne è la realizzazione naturale)

📝 Riepilogo

La ricorsione è una funzione (cap. 6) che chiama sé stessa su una versione più piccola dello stesso problema, finché non raggiunge un caso semplice. Rispecchia la struttura di problemi auto-simili (fattoriale $n!=n\times(n-1)!$ , alberi, frattali) in modo elegante e leggibile.
Ogni ricorsione ha due ingredienti: il caso base (risolto direttamente, ferma la ricorsione) e il caso ricorsivo (richiama la funzione su input più piccolo, avvicinandosi al caso base). Senza caso base raggiungibile → ricorsione infinita → stack overflow (crash).
In memoria usa lo stack di chiamata (una pila): le chiamate in sospeso si impilano e si svuotano dalla cima quando i risultati "risalgono". Questo comporta un costo (memoria, sovraccarico). Ricorsione e iterazione sono teoricamente equivalenti.
Quando usarla: l'iterazione è più efficiente per problemi lineari; la ricorsione è più naturale per problemi intrinsecamente ricorsivi (alberi, divide et impera). Attenzione all'inefficienza (Fibonacci naïf ricalcola valori). Prossimo passo: gli algoritmi di ordinamento e ricerca (cap. 11), molti dei quali ricorsivi.

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Algoritmi di ordinamento e ricerca

In breve

Ordinare e cercare sono due tra le operazioni più comuni e importanti dell'informatica: ordinare una lista di nomi, cercare un prodotto in un catalogo, disporre dei numeri in sequenza. Non a caso sono anche i problemi su cui si è studiato di più, e per i quali esistono algoritmi diversi con prestazioni molto diverse. Studiarli non serve solo a saperli usare, ma insegna qualcosa di più profondo: che per lo stesso problema esistono soluzioni migliori e peggiori, e che scegliere l'algoritmo giusto può fare la differenza tra un programma istantaneo e uno inutilizzabile. Questo capitolo presenta i principali algoritmi di ordinamento (dai semplici ai veloci) e di ricerca (lineare e binaria), preparando il terreno per il concetto di complessità (cap. 12).

🎯 Alla fine di questo capitolo saprai: perché ordinamento e ricerca sono problemi fondamentali; alcuni algoritmi di ordinamento (bubble sort, selection sort, e i più veloci merge/quick sort); la ricerca lineare e la ricerca binaria; perché l'ordinamento abilita ricerche più veloci; l'idea che algoritmi diversi hanno efficienze diverse.

Il problema dell'ordinamento

Perché conta: ordinare è un'operazione onnipresente e il banco di prova classico per confrontare l'efficienza degli algoritmi.

Ordinare significa disporre gli elementi di una collezione (tipicamente un array, cap. 7) secondo un criterio: numeri in ordine crescente, nomi in ordine alfabetico, date cronologicamente. È un'operazione richiestissima (elenchi, classifiche, database) e, come vedremo, è anche la premessa per cercare in modo efficiente. Esistono molti algoritmi di ordinamento, il che introduce un'idea centrale: lo stesso problema si può risolvere in modi diversi, con costi diversi.

Gli algoritmi di ordinamento semplici (intuitivi ma lenti):

Bubble sort (ordinamento a bolle): confronta ripetutamente coppie di elementi adiacenti e li scambia se sono nell'ordine sbagliato, scorrendo l'array più volte. Gli elementi più grandi "risalgono" come bolle verso la fine. Semplicissimo da capire, ma lento: fa moltissimi confronti.
Selection sort (ordinamento per selezione): a ogni passo cerca il minimo tra gli elementi non ancora ordinati e lo mette al suo posto. Intuitivo ma anch'esso lento.
Insertion sort (per inserimento): costruisce la parte ordinata inserendo ogni nuovo elemento nella posizione giusta (come si ordinano le carte in mano). Efficiente su array piccoli o quasi ordinati.

Questi algoritmi hanno tutti un difetto: su collezioni grandi diventano troppo lenti, perché il numero di operazioni cresce col quadrato del numero di elementi (raddoppiando i dati, il tempo quadruplica). Per grandi quantità servono algoritmi migliori.

🔗 Analogia. Ordinare un mazzo di carte fa capire i due approcci. Il selection sort è: "scorro tutte le carte, prendo la più bassa, la metto per prima; scorro le rimanenti, prendo la più bassa, la metto seconda..." — sicuro ma laborioso. L'insertion sort è come raccogliere le carte una a una infilando ciascuna al posto giusto tra quelle già in mano. Il merge sort (sotto) è: "divido il mazzo in due, faccio ordinare le due metà (magari da due amici), poi fondo i due mazzetti ordinati" — molto più veloce con tante carte.

Algoritmi di ordinamento efficienti

Perché conta: gli algoritmi divide et impera mostrano come un'idea più intelligente riduca drasticamente il tempo, un principio centrale dell'informatica.

Per ordinare grandi quantità di dati si usano algoritmi più sofisticati, basati sul divide et impera (cap. 6, 10) e tipicamente ricorsivi:

il merge sort (ordinamento per fusione): divide l'array a metà, ordina ricorsivamente ciascuna metà (dividendo ancora, fino a pezzi di un solo elemento, già ordinati), e poi fonde (merge) le due metà ordinate in un'unica sequenza ordinata. La fusione di due liste già ordinate è veloce (si confrontano solo i primi elementi). Il merge sort è molto più rapido dei metodi semplici e ha prestazioni garantite in ogni caso;
il quick sort (ordinamento rapido): sceglie un elemento pivot e partiziona l'array in due gruppi — quelli minori del pivot e quelli maggiori — poi ordina ricorsivamente i due gruppi. In pratica è spesso il più veloce, ed è largamente usato (anche se nel caso peggiore può degradare).

L'idea comune è potente: invece di ordinare tutto in blocco (tanti confronti), si divide il problema in metà sempre più piccole, facili da gestire, e si combinano le soluzioni. Questa strategia riduce il numero di operazioni da proporzionale a $n^2$ (metodi semplici) a proporzionale a $n \log n$ (metodi efficienti) — una differenza enorme su grandi dati: per un milione di elementi, si passa da mille miliardi di operazioni a circa venti milioni. È l'esempio perfetto di come un'idea algoritmica migliore batta la pura forza bruta. Il "quanto più veloce" si misura con la complessità (cap. 12).

La ricerca: lineare e binaria

Perché conta: la ricerca binaria mostra concretamente come l'ordinamento e un'idea intelligente trasformino un problema lento in uno velocissimo.

Cercare significa determinare se (e dove) un certo elemento è presente in una collezione. Ci sono due approcci fondamentali, con efficienze drammaticamente diverse.

La ricerca lineare (sequenziale) è la più semplice: si scorre la collezione dall'inizio, confrontando ogni elemento con quello cercato, finché lo si trova (o si arriva alla fine). Funziona sempre, su qualsiasi array (anche disordinato), ma è lenta su grandi collezioni: nel caso peggiore bisogna controllare tutti gli elementi (se cerco un nome in un elenco di un milione, potrei doverli guardare tutti). Il tempo cresce linearmente col numero di elementi.

La ricerca binaria (o dicotomica) è molto più veloce, ma richiede che la collezione sia già ordinata (ecco perché l'ordinamento è così importante!). L'idea, geniale nella sua semplicità: si guarda l'elemento centrale; se è quello cercato, fatto; se il cercato è minore, si cerca solo nella metà sinistra (scartando l'altra metà); se è maggiore, solo nella metà destra. A ogni passo si dimezza lo spazio di ricerca. È lo stesso metodo con cui si cerca una parola nel dizionario (si apre a metà, si capisce se andare avanti o indietro) o si indovina un numero con la strategia ottimale.

La differenza è stupefacente: per cercare in un milione di elementi, la ricerca lineare può richiedere fino a un milione di confronti; la ricerca binaria ne richiede al massimo venti (perché dimezzando un milione venti volte si arriva a 1). Dimezzare a ogni passo dà una crescita logaritmica, incredibilmente più efficiente. Questo illustra due lezioni fondamentali: (1) investire nell'ordinare i dati ripaga enormemente nelle ricerche successive; (2) un'idea algoritmica intelligente (dimezzare invece di scorrere) può trasformare un problema da lento a istantaneo.

🧩 Esempio. Cerchiamo il numero 7 nell'array ordinato [1, 3, 5, 7, 9, 11, 13] con la ricerca binaria. (1) Elemento centrale: 7 (posizione centrale). È proprio quello cercato → trovato al primo colpo! Proviamo a cercare 3: (1) centrale = 7; 3 < 7, cerco a sinistra [1, 3, 5]. (2) centrale = 3 → trovato, in 2 passi invece di scorrere. Su 7 elementi la differenza è piccola, ma su un milione la ricerca binaria fa ~20 passi contro il milione della lineare. La chiave è che l'array è ordinato: senza, la ricerca binaria non funzionerebbe.

⚠️ Attenzione. La ricerca binaria funziona solo su collezioni ordinate: applicarla a dati disordinati dà risultati sbagliati. Quindi conviene solo se si cerca molte volte (l'ordinamento iniziale si "ammortizza" sulle tante ricerche veloci); per una singola ricerca su dati disordinati, la lineare è più diretta. E ricorda: gli algoritmi di ordinamento semplici (bubble, selection) vanno bene per pochi dati o a scopo didattico, ma su grandi collezioni servono quelli efficienti (merge, quick sort) — la differenza è drammatica.

🗺️ Come si collega il tutto

Ordinamento e ricerca applicano tutto ciò che si è costruito — array (cap. 7), cicli (cap. 5), funzioni (cap. 6), ricorsione (cap. 10) — a due problemi fondamentali. Gli algoritmi di ordinamento semplici (bubble, selection, insertion) sono intuitivi ma lenti ( $\sim n^2$ ); quelli efficienti (merge, quick sort) usano il divide et impera ricorsivo per scendere a $\sim n\log n$ . La ricerca lineare scorre tutto (lenta); la ricerca binaria dimezza a ogni passo (velocissima, $\sim\log n$ ) ma richiede dati ordinati — ecco perché ordinare abilita ricerche efficienti. La lezione centrale — algoritmi diversi per lo stesso problema hanno costi drasticamente diversi — chiede uno strumento per misurare e confrontare rigorosamente questa efficienza: è la complessità computazionale (cap. 12), che chiude il corso formalizzando il "quanto veloce" incontrato qui in modo intuitivo.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Ordinamento	Disporre gli elementi secondo un criterio	Ricerca (trovare un elemento)
Bubble/selection sort	Ordinamenti semplici ma lenti ( $\sim n^2$ )	Merge/quick sort (efficienti, $\sim n\log n$ )
Merge/quick sort	Ordinamenti efficienti divide-et-impera (ricorsivi)	Ordinamenti semplici (quadratici)
Ricerca lineare	Scorre tutto; funziona su dati disordinati; lenta	Ricerca binaria (richiede ordinamento)
Ricerca binaria	Dimezza a ogni passo; velocissima ( $\sim\log n$ ); serve ordinamento	Lineare (scorre; su dati qualsiasi)
Idea algoritmica	Un'idea migliore (dividere/dimezzare) batte la forza bruta	(stesso problema, costi diversissimi)

📝 Riepilogo

Ordinare (disporre secondo un criterio) e cercare (trovare un elemento) sono problemi fondamentali. Lezione centrale: lo stesso problema ha soluzioni con costi molto diversi.
Ordinamenti semplici (bubble sort: scambia adiacenti; selection sort: cerca il minimo; insertion sort: inserisce al posto giusto): intuitivi ma lenti ( $\sim n^2$ , il tempo quadruplica se i dati raddoppiano). Ordinamenti efficienti (merge sort: divide, ordina le metà, fonde; quick sort: partiziona attorno a un pivot): usano il divide et impera ricorsivo, scendendo a $\sim n\log n$ (enormemente più veloci su grandi dati).
Ricerca lineare: scorre dall'inizio; funziona su dati disordinati ma è lenta (fino a $n$ confronti). Ricerca binaria: guarda il centro e dimezza lo spazio a ogni passo; velocissima ( $\sim\log n$ : ~20 passi per un milione) ma richiede dati ordinati.
Due lezioni: ordinare ripaga nelle ricerche successive; un'idea intelligente (dimezzare) batte la forza bruta. La ricerca binaria funziona solo su dati ordinati. Serve un modo rigoroso di misurare l'efficienza: la complessità (cap. 12).

Fondamenti di Informatica

Hai letto. Ora impara.

L'AI trasforma questo modulo in strumenti di studio personalizzati.

Complessità computazionale

In breve

Abbiamo visto (cap. 11) che per lo stesso problema esistono algoritmi più veloci e più lenti. Ma "più veloce" misurato come? Non col cronometro (dipende dal computer, dal linguaggio, dal momento), bensì con uno strumento matematico e universale: la complessità computazionale, che misura come cresce il tempo (o la memoria) al crescere della dimensione dei dati. È forse il concetto più importante dell'informatica teorica, perché permette di prevedere se un algoritmo reggerà su grandi quantità di dati o collasserà, e di confrontare algoritmi in modo oggettivo, indipendente dalla macchina. Questo capitolo chiude il corso introducendo la notazione O-grande, le classi di complessità fondamentali, e il loro significato pratico.

🎯 Alla fine di questo capitolo saprai: cos'è la complessità computazionale e perché non si misura col cronometro; la notazione O-grande (big-O); le principali classi di complessità (costante, logaritmica, lineare, $n\log n$ , quadratica, esponenziale); come confrontare algoritmi e riconoscere quelli inefficienti.

Perché misurare la complessità

Perché conta: valutare l'efficienza in modo indipendente dalla macchina è essenziale per prevedere se un algoritmo funzionerà nella pratica.

Come si stabilisce se un algoritmo è "efficiente"? L'idea ingenua sarebbe misurarne il tempo di esecuzione col cronometro. Ma questo approccio è inaffidabile: il tempo dipende dal computer usato (uno veloce, uno lento), dal linguaggio, dal carico del sistema, dalla giornata. Un algoritmo cattivo su un supercomputer può sembrare più veloce di uno buono su un portatile. Serve una misura oggettiva e universale, indipendente dall'hardware.

La soluzione dell'informatica è geniale: invece del tempo assoluto, si misura come il numero di operazioni cresce al crescere della dimensione dei dati (indicata con $n$ ). Questa è la complessità computazionale. Non chiediamo "quanti secondi impiega?", ma "se raddoppio i dati, il lavoro raddoppia, quadruplica, o esplode?". Questa domanda ha una risposta che dipende solo dall'algoritmo, non dalla macchina: è una proprietà intrinseca del procedimento.

Il motivo per cui questo conta enormemente è la scalabilità. Su pochi dati, qualsiasi algoritmo è veloce (anche uno pessimo ordina 10 numeri in un lampo). La differenza emerge — drammaticamente — su grandi quantità di dati, che sono la norma nel mondo reale (milioni di utenti, miliardi di record). Un algoritmo che "esplode" su grandi dati è inutilizzabile, per quanto veloce sia il computer. La complessità ci dice, prima di eseguire, se un algoritmo reggerà la scala o crollerà — un'informazione preziosissima. Si distingue anche la complessità temporale (numero di operazioni) da quella spaziale (memoria usata), entrambe importanti.

🔗 Analogia. La complessità è come chiedere "come cresce lo sforzo?" invece di "quanto ci metti ora?". Se devi cercare un amico in una fila, e con 10 persone ci metti un minuto: cosa succede con 1000 persone? Se il tempo cresce in proporzione (100 minuti) è un conto; se cresce col quadrato (10.000 minuti) è tutt'altra storia; se dimezzi ogni volta (pochi secondi in più) è ottimo. Non conta quanto sei veloce oggi, ma come peggiora man mano che il problema cresce: è questo che decide se il metodo regge alla realtà.

La notazione O-grande

Perché conta: la notazione O-grande è il linguaggio standard per esprimere e confrontare la complessità degli algoritmi.

Per esprimere la complessità in modo conciso si usa la notazione O-grande (big-O, $O(\cdot)$ ). Essa descrive l'andamento asintotico del numero di operazioni al crescere di $n$ , cioè come cresce il costo per grandi valori di $n$ , ignorando i dettagli irrilevanti. La filosofia dell'O-grande è "guardare la foresta, non gli alberi": si tiene solo il termine dominante (quello che cresce più in fretta) e si ignorano le costanti moltiplicative e i termini di ordine inferiore.

Perché ignorarli? Perché per grandi $n$ contano solo gli ordini di grandezza. Un algoritmo che fa $3n^2 + 5n + 100$ operazioni si scrive $O(n^2)$ : per $n$ grande, il termine $n^2$ domina totalmente (il $5n$ e il $100$ diventano trascurabili, e il fattore 3 non cambia la "categoria"). Ciò che conta è la forma della crescita ( $n^2$ ), non i coefficienti. Questo rende l'O-grande una misura pulita e universale della "categoria di efficienza" di un algoritmo, che permette confronti immediati: $O(n)$ è meglio di $O(n^2)$ , $O(\log n)$ è meglio di $O(n)$ , indipendentemente dai dettagli.

Di solito si considera il caso peggiore (worst case): il massimo numero di operazioni che l'algoritmo può richiedere, che dà una garanzia ("non impiegherà mai più di così"). A volte si analizza anche il caso medio. L'O-grande è diventato il linguaggio universale con cui informatici e programmatori parlano di efficienza: dire che un algoritmo è " $O(n \log n)$ " comunica istantaneamente la sua scalabilità a chiunque.

Le classi di complessità

Perché conta: riconoscere la classe di complessità di un algoritmo permette di prevederne il comportamento e scegliere il migliore per il problema.

Gli algoritmi si raggruppano in classi di complessità, ordinate dalla migliore alla peggiore. Ecco le fondamentali, con il loro significato pratico:

$O(1)$ — costante: il tempo non dipende dalla dimensione dei dati. Ottimo. Esempio: accedere a un elemento di un array per indice (array[i]), che è immediato qualunque sia la dimensione;
$O(\log n)$ — logaritmica: il tempo cresce lentissimamente (raddoppiando i dati, aggiunge una sola operazione). Eccellente. Esempio: la ricerca binaria (cap. 11), che dimezza a ogni passo;
$O(n)$ — lineare: il tempo cresce in proporzione ai dati (doppi dati, doppio tempo). Buona, spesso inevitabile (bisogna almeno guardare ogni dato). Esempio: la ricerca lineare, scorrere un array;
$O(n \log n)$ — quasi-lineare: poco più che lineare. È la complessità degli ordinamenti efficienti (merge sort, quick sort, cap. 11), considerata ottima per l'ordinamento;
$O(n^2)$ — quadratica: il tempo cresce col quadrato (doppi dati, tempo quadruplo). Accettabile solo per dati piccoli. Esempio: gli ordinamenti semplici (bubble sort) e i cicli annidati su un array;
$O(2^n)$ — esponenziale: il tempo raddoppia a ogni dato aggiunto. Disastrosa: diventa impraticabile già per $n$ modesti (con $n=60$ le operazioni superano l'età dell'universo). Esempio: alcuni problemi combinatori "forza bruta", il Fibonacci ricorsivo naïf (cap. 10).

Per capire l'impatto: su un milione di dati, un algoritmo $O(n)$ fa un milione di operazioni (istantaneo), uno $O(n^2)$ ne fa mille miliardi (ore o giorni), uno $O(2^n)$ è semplicemente impossibile. La classe di complessità è quindi ciò che separa un programma utilizzabile da uno inservibile su dati reali. Ridurre la complessità (trovare un algoritmo di classe migliore) è spesso molto più efficace di qualsiasi ottimizzazione tecnica o hardware più potente: passare da $O(n^2)$ a $O(n\log n)$ vale più di un computer dieci volte più veloce.

🧩 Esempio. Confrontiamo la ricerca lineare $O(n)$ e binaria $O(\log n)$ (cap. 11) su collezioni crescenti (operazioni nel caso peggiore):

Elementi ( $n$ )	Lineare $O(n)$	Binaria $O(\log n)$
100	100	~7
1.000	1.000	~10
1.000.000	1.000.000	~20
1.000.000.000	1 miliardo	~30

La ricerca lineare peggiora in proporzione ai dati; la binaria a malapena cambia (da 7 a 30 mentre i dati esplodono da 100 a un miliardo). Questa è la potenza della complessità logaritmica — e la ragione per cui la classe di complessità, non la velocità del computer, decide cosa è fattibile.

⚠️ Attenzione. La complessità riguarda la crescita al crescere di $n$ , non il tempo su dati piccoli: per pochi dati anche un algoritmo $O(n^2)$ va benissimo (e può battere uno $O(n\log n)$ per via delle costanti nascoste). L'O-grande ignora le costanti: $O(n)$ e $O(100n)$ sono la stessa classe (ma nella pratica la costante può contare). Non confondere complessità temporale (tempo) e spaziale (memoria). E " $O(2^n)$ " è un campanello d'allarme: un algoritmo esponenziale è inutilizzabile su dati non minuscoli — spesso segnala che serve un approccio del tutto diverso.

🗺️ Come si collega il tutto

La complessità computazionale formalizza e chiude ciò che il corso ha costruito. Dà lo strumento oggettivo (indipendente dalla macchina) per misurare l'efficienza intravista con ordinamento e ricerca (cap. 11): la notazione O-grande esprime come cresce il costo al crescere di $n$ , e le classi ( $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n\log n)$ , $O(n^2)$ , $O(2^n)$ ) ordinano gli algoritmi per scalabilità. Ora si spiega rigorosamente perché la ricerca binaria ( $O(\log n)$ ) batte la lineare ( $O(n)$ ), perché il merge sort ( $O(n\log n)$ ) batte il bubble sort ( $O(n^2)$ ), perché il Fibonacci ricorsivo naïf ( $O(2^n)$ , cap. 10) è impraticabile. La complessità unisce tutti i fili — algoritmi (cap. 1), cicli (cap. 5), ricorsione (cap. 10), strutture dati (cap. 9) — nella domanda ultima dell'informatica: quanto costa risolvere un problema? È il ponte verso il corso di Algoritmi e Strutture Dati, e la conclusione di Fondamenti di Informatica: dal singolo bit (cap. 2) alla teoria dell'efficienza, l'intero cammino del pensiero computazionale.

🔑 Concetti chiave

Termine	In una frase	Da non confondere con
Complessità	Come cresce il costo al crescere della dimensione $n$ dei dati	Tempo col cronometro (dipende dalla macchina)
Notazione O-grande	Andamento asintotico; tiene il termine dominante, ignora costanti	(misura la classe, non il tempo esatto)
$O(1)$ / $O(\log n)$	Costante / logaritmica: eccellenti (accesso array / ricerca binaria)	$O(n)$ (lineare)
$O(n)$ / $O(n\log n)$	Lineare (ricerca lineare) / quasi-lineare (ordinamenti efficienti)	$O(n^2)$ (quadratica)
$O(n^2)$ / $O(2^n)$	Quadratica (ordinamenti semplici) / esponenziale (disastrosa)	(classi da evitare su grandi dati)
Caso peggiore	Il massimo costo possibile: dà una garanzia	Caso medio (comportamento tipico)

📝 Riepilogo

La complessità computazionale misura l'efficienza in modo oggettivo (indipendente dalla macchina): non il tempo col cronometro, ma come cresce il numero di operazioni al crescere della dimensione $n$ dei dati. Conta la scalabilità su grandi dati, dove le differenze diventano drammatiche.
La notazione O-grande ( $O(\cdot)$ ) esprime l'andamento asintotico: si tiene solo il termine dominante e si ignorano costanti e termini minori ( $3n^2+5n+100 \to O(n^2)$ ). Di solito si considera il caso peggiore. È il linguaggio universale dell'efficienza.
Classi (dalla migliore alla peggiore): $O(1)$ costante (accesso array), $O(\log n)$ logaritmica (ricerca binaria), $O(n)$ lineare (ricerca lineare), $O(n\log n)$ quasi-lineare (ordinamenti efficienti), $O(n^2)$ quadratica (ordinamenti semplici), $O(2^n)$ esponenziale (disastrosa, impraticabile).
La classe di complessità separa un programma utilizzabile da uno inservibile su dati reali: ridurre la complessità vale più di un hardware più potente. Attenzione: riguarda la crescita, non i dati piccoli; ignora le costanti; distingui temporale e spaziale. Fine di Fondamenti di Informatica — dal bit al pensiero computazionale.

Fondamenti di Informatica

Hai finito il corso. Ora studia davvero.

Usa l'AI per consolidare tutto quello che hai studiato.