Introduzione al corso e algoritmi

Lezione 01 di Programmazione 1, 10 settembre 2026. Slide: 1.1 Algoritmi. Lezione successiva: Architettura hardware e software di un calcolatore.

Il filo della lezione, in ordine:

informatica          studio degli algoritmi, anche senza computer
      |
      v
algoritmo            passi precisi, finiti, comprensibili all'esecutore
      |
      v
problema             prima si definisce bene, poi si risolve
      |              (calcolo, decisione, ricerca)
      v
tre linguaggi        naturale  ->  pseudocodice  ->  C
      |
      v
strutture            sequenza, scelta (se), ripetizione (mentre)
      |
      v
top-down             un passo troppo grosso diventa un sotto-algoritmo
      |
      v
proprietà            correttezza ed efficienza

1Concetti

1.1Il corso

Obiettivi. Tre filoni:

1. Programmare con un linguaggio imperativo (C, C++, Java). Imperativo vuol dire che il programma è una lista di azioni esplicite da eseguire in ordine: “leggi”, “somma”, “scrivi in questa variabile”.
2. Strutture dati astratte: liste, pile, alberi e simili. Sono astratte perché non dipendono dal linguaggio, le stesse idee si usano in tutti.
3. Analisi degli algoritmi: capire quanto costa un algoritmo in tempo e memoria, cioè la sua complessità.

Programma. Il corso è diviso in due parti:

1.2Cos’è l’informatica

Le slide partono da due definizioni (slide 3):

• ACM: “lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione: la loro teoria, analisi, progetto, efficienza, realizzazione e applicazione”.
• Ceri, Mandrioli, Sbattella: “la scienza della rappresentazione e dell’elaborazione dell’informazione”.

Nessuna delle due nomina il computer. Si può elaborare informazione con carta e penna, per esempio facendo una divisione in colonna seguendo regole precise. Il computer è uno strumento: molto veloce (tante operazioni per unità di tempo) e autonomo, quindi rende trattabili quantità di informazione che a mano non si gestirebbero mai.

1.3Algoritmo

Ogni pezzo della frase ha un ruolo:

Esecutore. Chi esegue i passi: una persona, un robot, un computer. Lo stesso compito richiede descrizioni diverse a seconda dell’esecutore. “Fai la doccia” va bene per una persona, per un robot va spezzato in decine di movimenti.

Esempio: somma con il pallottoliere (slide 7-9). Riga 1 contiene $a = 4$ dischi a sinistra, riga 2 contiene $b = 7$ dischi a sinistra, riga 3 è piena a destra.

1. Nella riga 1 sposta un disco da sinistra a destra e, insieme, nella riga 3 sposta un disco da destra a sinistra.
2. Ripeti finché la parte sinistra della riga 1 è vuota.
3. Fai la stessa cosa fra riga 2 e riga 3.
4. Ripeti finché la parte sinistra della riga 2 è vuota.
5. I dischi a sinistra nella riga 3 sono il risultato: $a + b = 11$.

L’esecutore non deve sapere cos’è una somma, deve solo saper spostare un disco e controllare se una riga è vuota. È questo che rende la descrizione un algoritmo.

Esempio: il robot che cammina (slide 11).

1. fai un passo con il piede sinistro, poi vai a 2
2. fai un passo con il piede destro, poi vai a 3
3. se sei alla fine del blocco vai a 4, altrimenti vai a 1
4. termina

Il passo 3 fa due cose che serviranno sempre: decide in base a una condizione e torna indietro per ripetere. La slide dopo chiede di gestire anche gli ostacoli: serve un’altra condizione dentro il ciclo.

1.4Algoritmi e programmi

La descrizione di un algoritmo deve essere comprensibile a chi lo esegue. Se l’esecutore è un calcolatore, serve un linguaggio di programmazione (nel corso il C, con cenni di C++). Un algoritmo scritto in un linguaggio di programmazione si chiama programma.

Il lavoro del programmatore ha due metà (slide 38):

1. progettare l’algoritmo, cioè la sequenza di passi che risolve il problema;
2. codificarlo in un programma che il calcolatore capisce ed esegue.

Chi progetta l’algoritmo non è per forza chi scrive il programma.

1.5Proprietà di un algoritmo

• Correttezza. Arriva alla soluzione del compito senza errori in nessun passo fondamentale.
• Efficienza. Ci arriva usando la minima quantità di risorse. Per un computer le risorse sono soprattutto tempo di esecuzione e memoria.

Servono entrambe (slide 63). Un algoritmo corretto ma così lento da non poterlo usare non serve. Un algoritmo velocissimo che dà risultati approssimati o sbagliati non serve nemmeno lui.

Un esempio di efficienza (slide 94): moltiplicare due interi di $n$ cifre. Il metodo delle elementari fa circa $n^2$ operazioni, l’algoritmo più veloce conosciuto circa $n \log n$. Con numeri di un milione di cifre la differenza è enorme.

1.6Esempio di task: il problema della segretaria

Molti problemi di tutti i giorni sono di ricerca con un criterio di arresto: scegliere un appartamento, un piano tariffario, un compagno di stanza. Vedi un candidato alla volta, e una volta scartato non torni indietro. Quando ti fermi?

Sotto certe ipotesi è la strategia che massimizza la probabilità di scegliere il migliore in assoluto.

Esercizio fatto a lezione: il compagno di squadra dal ranking online.

1. cerca online i ranking
2. prendi i primi 50
3. analizza i primi 18 e costruisci la tua classifica      <- look-and-rank
4. dal 19° in poi scegli il primo migliore di tutti i precedenti   <- leap

Il 18 viene dalla regola: il $37\%$ di $50$ è $18{,}5$.

1.7Prima il problema, poi la soluzione

Prima di cercare una soluzione bisogna definire esattamente il problema (slide 40-41). Alcuni problemi sono già chiari, altri no:

• ordinare $[2, 0, 1, 10, 3]$ in $[0, 1, 2, 3, 10]$ è definito senza ambiguità;
• “decidere quali azioni comprare domani” o “contare i semafori di Trento” richiedono prima di stabilire cosa conta come risposta;
• “progettare la biblioteca online dell’università” è quasi tutto definizione.

Nel mondo reale definire il problema può essere più difficile che risolverlo, e se ne occupa la requirement engineering. Nel corso il problema sarà sempre dato e chiaro, e ci si concentra sulla soluzione.

1.8Categorie di problemi

Altri esempi tecnici: il massimo comune divisore di più numeri (calcolo), stabilire se due grafi sono isomorfi, cioè uguali a meno dei nomi dei nodi (decisione).

1.9Tre livelli di linguaggio

Problema    ->  linguaggio LP  =  linguaggio naturale     "calcola le radici di ax²+bx+c"
    |
Algoritmo   ->  linguaggio LA  =  pseudocodice            "1. leggi a, b, c  2. ..."
    |
Programma   ->  linguaggio LT  =  C / C++                 scanf("%d", &a); ...

Si scende di un livello alla volta. Il pseudocodice è una via di mezzo: passi numerati in italiano, precisi come un programma ma senza la sintassi di un linguaggio vero.

1.10Le strutture di controllo

L’esempio del risveglio (slide 47-54) mostra i tre modi di combinare i passi. Ogni algoritmo si costruisce solo con questi tre.

1. Sequenza. I passi si eseguono uno dopo l’altro, e l’ordine è essenziale per la correttezza.

1. alzarsi dal letto
2. togliersi il pigiama
3. fare la doccia
4. vestirsi
5. fare colazione
6. prendere il bus per l'università

Scambiando 3 e 4 ci si fa la doccia vestiti: ogni passo resta eseguibile, ma il risultato è sbagliato.

2. Selezione (se … allora … altrimenti). Un passo si esegue solo se vale una condizione.

6. se piove
   6.1 prendere la macchina
   altrimenti
   6.2 prendere l'autobus

3. Iterazione (mentre … fai). Un passo si ripete finché vale una condizione.

6. mentre piove
   6.1 restare in casa
7. prendere l'autobus

Attenzione: se la condizione non smette mai di valere, il ciclo non termina e la sequenza non è più finita.

1.11Top-down: la ricerca in biblioteca

Contesto (slide 55-62). Ogni libro ha una posizione fissa (numero di scaffale e posizione nello scaffale). Lo schedario è ordinato per autore e titolo, e ogni scheda riporta autore, titolo, anno, scaffale e posizione. Input: il libro da cercare. Output: il libro prelevato.

Primo livello.

1. acquisisci il libro da richiedere
2. cerca la scheda del libro richiesto
3. segnati numero di scaffale e posizione
4. cerca lo scaffale indicato
5. accedi alla posizione e preleva il libro
6. scrivi i tuoi dati sulla scheda prestito

Il passo 2 è troppo grosso, quindi si raffina.

Raffinamento 1: ricerca sequenziale.

2.1 prendi la prima scheda
2.2 se titolo e autore sono quelli cercati, termina con successo;
    altrimenti passa alla scheda successiva e ripeti
2.3 se finiscono le schede, il libro non esiste

Funziona, ma se l’autore è “Zac Zucker” bisogna scorrere tutto lo schedario. Non sfrutta il fatto che è ordinato.

Raffinamento 2: ricerca dicotomica.

2.1 esamina la scheda centrale della parte di schedario da consultare
2.2 se corrisponde al libro cercato, oppure la parte da consultare è vuota, termina
2.3 altrimenti prosegui allo stesso modo nella metà superiore o inferiore,
    a seconda che il libro cercato venga prima o dopo la scheda centrale

schedario ordinato:  [A ........................ M ........................ Z]
cerco "Zucker":                                  ^ centrale: M < Z, tengo la metà destra
                                                 [M ........... S ........... Z]
                                                                ^ S < Z, metà destra
                                                                [S .... V .... Z]
                                                                      ...
ogni confronto dimezza le schede rimaste

La prima versione della slide dimenticava la condizione “la parte da consultare è vuota”: senza, se il libro non esiste l’algoritmo non termina. Ogni ricerca ha due uscite, trovato e non trovato.

Con 1000 schede la ricerca sequenziale può fare 1000 confronti, la dicotomica al massimo 10, perché $2^{10} = 1024$. Stesso problema, stessa correttezza, efficienza molto diversa.

1.12Esempio completo: le radici di un’equazione di secondo grado

Problema (slide 64-69): calcolare le radici reali di $ax^2 + bx + c = 0$ e stamparle.

1. acquisisci i coefficienti a, b, c
2. calcola Δ = b² − 4ac
3. se Δ < 0, non esistono radici reali. vai a 7
4. se Δ = 0, x1 = x2 = −b / 2a. vai a 6
5. se Δ > 0, x1 = (−b + √Δ) / 2a,  x2 = (−b − √Δ) / 2a
6. visualizza x1 e x2
7. fine

Il diagramma di flusso disegna lo stesso algoritmo: rettangoli per le azioni, rombi per le domande sì/no, frecce per l’ordine. Si vede subito che ci sono tre strade e che tutte arrivano a “fine”.

1.13Altri esempi dalle slide

Mediana (slide 70-74). La mediana $m$ di $n_1, \dots, n_N$ separa i valori in due metà con lo stesso numero di elementi $\leq m$ e $\geq m$.

• $N$ dispari: $7, 5, 1, 9, 3, 6, 10$ ordinati diventano $1, 3, 5, \mathbf{6}, 7, 9, 10$, quindi $m = 6$, l’elemento centrale.
• $N$ pari: $1, 3, 5, 7, 9, 10$ ha due elementi centrali, $m = \frac{5 + 7}{2} = 6$.

1. leggi n1, ..., nN                      \
2. memorizza i valori in un vettore a     /  input
3. ordina gli elementi di a               \
4. calcola m da a, distinguendo N pari    /  calcolo
   e N dispari
5. stampa m                                  output

Lo schema input, calcolo, output tornerà in quasi tutti i programmi.

Percorso più breve (slide 86-88). Una carta geografica è un grafo: le città sono nodi, le strade archi con una distanza. Per andare da $C_p$ a $C_a$:

1. trova tutte le sequenze di città $C_0, \dots, C_k$ con $C_0 = C_p$, $C_k = C_a$, nessuna città ripetuta, e una strada diretta fra città consecutive;
2. per ogni sequenza calcola la somma delle distanze;
3. scegli la sequenza con somma minima (a parità, una qualsiasi).

È corretto ma poco efficiente: le sequenze possibili crescono in modo esplosivo con il numero di città. Esistono algoritmi molto migliori, che arriveranno più avanti.

Esercizi lasciati aperti dalle slide:

• descrivere un proprio algoritmo simile al problema della segretaria, in linguaggio naturale;
• ordinare un mazzo di 52 carte in picche, fiori, quadri, cuori (slide 76);
• tavoletta di cioccolato $h \times k$: quanti spezzamenti servono per ottenere tutti i quadratini, e conta la strategia? (slide 78-81);
• scala di $N$ gradini salita con passi da 1, 2 o 3: in quanti modi? Prova a mano con $N = 1, 2, 3, 4$ (slide 89-90, esercizio d’esame 2016/17, risolto in Ciclo while ed esempi);
• trasformare in pseudocodice le istruzioni grafiche di montaggio di un mobile (slide 92-93).

2Metodo

Scrivere un algoritmo per un problema.

1. Definisci il problema: quali sono i dati di ingresso, cosa deve uscire, quali condizioni di partenza valgono.
2. Scrivi i passi grossi in linguaggio naturale, numerati, nell’ordine giusto.
3. Raffina top-down ogni passo che l’esecutore non sa fare direttamente.
4. Usa solo le tre strutture: sequenza, se/altrimenti, mentre.
5. Controlla la terminazione: ogni ciclo deve avere una condizione che prima o poi diventa falsa, e ogni ricerca deve gestire anche il caso “non trovato”.
6. Controlla la correttezza sui casi limite (lista vuota, $\Delta = 0$, $N$ pari e dispari) e chiediti se c’è un modo con meno passi.

3Esercizi tipo esame

Esercizio 1. Scrivi in pseudocodice un algoritmo che legge numeri interi positivi finché non arriva 0 e stampa il più grande. Cosa stampa se il primo numero è 0?

1. leggi x
2. se x = 0, stampa "nessun numero" e termina
3. max ← x
4. leggi x
5. mentre x ≠ 0
   5.1 se x > max, max ← x
   5.2 leggi x
6. stampa max

Esercizio 2. Uno schedario ordinato ha 1 000 000 di schede. Quanti confronti fa al massimo la ricerca sequenziale? E la dicotomica?

Esercizio 3. Questo algoritmo termina? Perché?

1. x ← 10
2. mentre x ≠ 0
   2.1 x ← x − 3
3. stampa x

Esercizio 4. In quanti modi si sale una scala di 4 gradini con passi da 1, 2 o 3? Elencali.

Esercizio 5. Tavoletta di cioccolato $h \times k$: ogni spezzamento divide un pezzo in due lungo una riga. Quanti spezzamenti servono per avere tutti i quadratini separati? La strategia conta?

Esercizio 6. Regola del 37% con 100 candidati: quanti ne guardi senza scegliere? Cosa fai se nessuno dei successivi è migliore di tutti quelli visti?

4Errori tipici

• Scrivere passi che l’esecutore non sa fare (“trova il massimo” come passo unico, senza raffinarlo).
• Dimenticare il caso “non trovato” in una ricerca, o il caso “sequenza vuota”.
• Cicli con una condizione che può non diventare mai falsa.
• Confondere correttezza ed efficienza: un algoritmo lento ma giusto è corretto, uno veloce ma sbagliato no.
• Applicare la ricerca dicotomica a dati non ordinati.

5Domande