Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
10 set
in corso

Introduzione al corso e algoritmi

Lezione 01 di Programmazione 1, 10 settembre 2026. Slide: 1.1 Algoritmi, slide 1-95. 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

1Definizioni

Informatica (slide 2-3). Le slide partono da due definizioni:

Nessuna delle due nomina il computer, e la slide lo sottolinea: “le definizioni non implicano necessariamente l’uso di un calcolatore”. Si può elaborare informazione con carta e penna, per esempio facendo una divisione in colonna seguendo regole precise (slide 20). 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.

Algoritmo (slide 5).

A parole: una ricetta così precisa che chi la segue non deve mai decidere niente di testa sua, e che prima o poi finisce con il compito fatto. Ogni pezzo della frase ha un ruolo:

PezzoCosa esclude
sequenza precisaistruzioni vaghe come “cuoci un po‘“
comprensibili dall’esecutorepassi che chi esegue non sa fare
finitaprocedimenti che non terminano mai
realizzazione di un compitoliste di passi che non risolvono niente
sequenza (ordinata)l’ordine dei passi conta, spostarli cambia il risultato

Esempio: le istruzioni della divisione in colonna sono un algoritmo per chi sa fare le tabelline e le sottrazioni. Controesempio: “aggiungi sale quanto basta” non è un passo di un algoritmo, perché “quanto basta” non è preciso, e due esecutori diversi farebbero due cose diverse. Un secondo controesempio, sulla finitezza: “scrivi tutti i numeri pari” è preciso e comprensibile, ma non finisce mai.

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.

Programma (slide 17-19). La descrizione (codifica) di un algoritmo deve essere comprensibile al suo esecutore. 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.

Correttezza ed efficienza (slide 63).

Servono entrambe. 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.

Top-down (slide 58).

Pseudocodice. Passi numerati in italiano, precisi come un programma ma senza la sintassi di un linguaggio vero. È il linguaggio LA delle slide (sotto, Tre livelli di linguaggio).

2Concetti

2.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:

ParteContenuto
1°algoritmi e linguaggio di programmazione (C)
2°strutture dati

2.2Algoritmi e programmi

È essenziale che un algoritmo sia comprensibile al suo esecutore, e per un calcolatore lo si descrive con un programma, cioè una sequenza di istruzioni in un linguaggio che il calcolatore capisce. 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.

2.3Prima il problema, poi la soluzione

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

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, con problemi semplici che portano a programmi di dimensioni contenute.

Definire un problema vuol dire dire quattro cose, come per una ricetta (slide 36-37, cucinare i canederli):

VoceNella ricettaIn un problema di calcolo
descrizionecanederli alla tiroleseconversione di temperature
condizioni di partenzagli ingredientii dati di ingresso (input) e cosa vale per loro
compito da eseguirecucinarei passi
risultato finale aspettatoil piattoi dati di uscita (output)

Esempio 1, un problema ben definito: input una temperatura CC in gradi Celsius, output la stessa in Fahrenheit, F=95C+32F = \frac{9}{5} C + 32. Con C=100C = 100: 95⋅100=180\frac{9}{5} \cdot 100 = 180, 180+32=212180 + 32 = 212. Con C=−40C = -40: 95⋅(−40)=−72\frac{9}{5} \cdot (-40) = -72, −72+32=−40-72 + 32 = -40.

Esempio 2, lo stesso problema detto male: “converti le temperature”. Mancano l’unità di partenza, quella di arrivo e quante temperature sono. Prima di scrivere un passo bisogna chiederlo.

2.4Categorie di problemi

(slide 42)

CategoriaCosa chiedeEsempi
Calcolo e conversioneprodurre un valore a partire dai datimedia di un campione audio, Celsius in Fahrenheit, trasformata di Fourier
Decisionedire sì o no: una proprietà vale per i dati?15237 è primo? “anna” è palindroma? una travatura è stabile?
Ricercatrovare in un insieme un elemento con certe caratteristicheil più piccolo primo con 44 cifre, i cognomi palindromi nell’elenco, la segretaria con un certo profilo

Altri esempi tecnici (slide 29-32): il massimo comune divisore di più numeri (calcolo), stabilire se due grafi sono isomorfi, cioè uguali a meno dei nomi dei nodi (decisione). L’esempio dei grafi è svolto sotto, in Esempi svolti a lezione.

Come si riconosce la categoria: si guarda la forma della risposta. Un numero o un valore trasformato è calcolo; un sì o un no è decisione; un elemento preso da un insieme (o “non c’è”) è ricerca.

2.5Tre livelli di linguaggio

(slide 43-45)

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: abbastanza preciso da seguirlo a mano senza dubbi, abbastanza libero da non perdersi nella sintassi.

2.6Le strutture di controllo

L’esempio del risveglio (slide 46-54, svolto sotto) 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.

2. Selezione (se … allora … altrimenti). Un passo si esegue solo se vale una condizione. Dei due rami se ne esegue uno solo, poi le strade si riuniscono.

3. Iterazione (mentre … fai). Un passo si ripete finché vale una condizione. Dopo ogni giro si torna alla domanda; quando la risposta è no si esce.

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

Esempio 1, le tre insieme: il massimo fra tre numeri aa, bb, cc.

1. leggi a, b, c
2. max ← a
3. se b > max, max ← b
4. se c > max, max ← c
5. stampa max

È una sequenza di cinque passi, e i passi 3 e 4 sono selezioni senza “altrimenti”. Tracing con a=3a = 3, b=7b = 7, c=5c = 5:

passocondizionemax
2. max ← a3
3. b > max?7 > 3 vero7
4. c > max?5 > 7 falso7
5. stampastampa 7

Esempio 2, iterazione: contare quante volte si può togliere 3 da un numero n≥0n \geq 0 senza andare sotto zero (cioè la divisione intera per 3).

1. leggi n
2. q ← 0
3. mentre n ≥ 3
   3.1 n ← n − 3
   3.2 q ← q + 1
4. stampa q

Tracing con n=10n = 10:

passocondizionenq
1-2100
3. n ≥ 3?10 ≥ 3 vero71
3. n ≥ 3?7 ≥ 3 vero42
3. n ≥ 3?4 ≥ 3 vero13
3. n ≥ 3?1 ≥ 3 falso, esco13
4. stampastampa 3

Controllo: 10=3⋅3+110 = 3 \cdot 3 + 1, quindi quoziente 3 e resto 1, che è proprio il valore finale di n. Il ciclo termina perché n cala di 3 a ogni giro e prima o poi scende sotto 3.

2.7Top-down

Il procedimento si vede nella ricerca in biblioteca (svolta sotto): il primo livello ha sei passi, e il passo “cerca la scheda” è troppo grosso, quindi diventa un sotto-algoritmo. Le slide ne danno due versioni, sequenziale e dicotomica.

Esempio, raffinare “trova il massimo” in una lista di numeri. Primo livello:

1. leggi la lista
2. trova il massimo
3. stampa il massimo

Il passo 2 non è eseguibile da chi sa solo confrontare due numeri. Si raffina:

2.1 max ← primo elemento
2.2 per ogni elemento x successivo
    2.2.1 se x > max, max ← x

Ora ogni passo usa solo confronti e assegnazioni. Il raffinamento si ferma quando tutti i passi sono eseguibili dall’esecutore: per un umano basta il primo livello, per un calcolatore serve il secondo.

2.8Efficienza: contare i passi

Due algoritmi corretti per lo stesso problema si confrontano contando le operazioni importanti nel caso peggiore, cioè con i dati più sfavorevoli. Per le ricerche l’operazione importante è il confronto con un elemento.

schede NNsequenziale, al massimodicotomica, al massimo
884
16165
1000100010
1 000 0001 000 00020

Da dove vengono i numeri della dicotomica: ogni confronto dimezza la parte ancora da consultare, quindi dopo kk confronti resta circa N/2kN / 2^k. Ci si ferma quando resta una scheda sola, cioè dopo circa log⁡2N\log_2 N dimezzamenti, più il confronto con quell’ultima scheda: il numero esatto è ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1. Con N=1000N = 1000: 29=512≤1000<1024=2102^9 = 512 \leq 1000 < 1024 = 2^{10}, quindi ⌊log⁡21000⌋=9\lfloor \log_2 1000 \rfloor = 9 e i confronti sono al massimo 10.

Un esempio di efficienza dalle slide (slide 94): moltiplicare due interi di nn cifre. Il metodo delle elementari fa circa n2n^2 operazioni, l’algoritmo più veloce conosciuto circa nlog⁡nn \log n. Con numeri di un milione di cifre la differenza è enorme: n2=1012n^2 = 10^{12}, mentre nlog⁡2n≈106⋅20=2⋅107n \log_2 n \approx 10^6 \cdot 20 = 2 \cdot 10^7. La slide rimanda all’articolo “Multiplication hits the speed limit”.

3Metodo

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, Δ=0\Delta = 0, NN pari e dispari) e chiediti se c’è un modo con meno passi.

Seguire a mano un algoritmo (tracing).

  1. Fai una tabella con una colonna per ogni variabile, più una per il passo e una per la condizione.
  2. Una riga per ogni passo eseguito, nell’ordine in cui viene eseguito (non nell’ordine in cui è scritto: un ciclo ripete le sue righe).
  3. A ogni condizione scrivi il calcolo per esteso (“7 > 3 vero”).
  4. Alla fine controlla il risultato con un ragionamento diverso (un conto a mano, un caso noto).

Confrontare due algoritmi. Scegli l’operazione che conta (il confronto, la moltiplicazione), contala nel caso peggiore in funzione della dimensione dei dati NN, e confronta le due funzioni per NN grande.

4Esempi svolti a lezione

Somma con il pallottoliere (slide 6-9). Riga 1 contiene a=4a = 4 dischi a sinistra, riga 2 contiene b=7b = 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=11a + 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.

Tracing: si contano i dischi a sinistra in ogni riga.

passoriga 1riga 2riga 3
inizio470
1 (primo giro)371
1272
1173
1, riga 1 vuota: passo 2 finito074
3 (primo giro)065
3056
3047
3038
3029
30110
3, riga 2 vuota: passo 4 finito0011

Controllo: a ogni spostamento la somma riga 1 + riga 2 + riga 3 resta 1111, e alla fine è tutta nella riga 3. L’algoritmo termina perché ogni giro toglie un disco da una riga che ne ha un numero finito.

Il robot che cammina (slide 10-12).

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. Tracing con un blocco lungo 4 passi: sinistro (1 passo fatto), destro (2), alla fine? no, torna a 1; sinistro (3), destro (4), alla fine? sì, termina.

Due difetti si vedono provando i casi limite. Se il robot parte già alla fine del blocco, fa comunque due passi, perché il controllo viene dopo. Se il blocco è lungo 3 passi, dopo il terzo passo (sinistro) il robot ne fa un quarto (destro) prima di controllare, e va oltre la fine. Il controllo va messo prima di ogni passo.

La slide dopo chiede di gestire anche gli ostacoli: serve un’altra condizione dentro il ciclo. Le slide non danno la soluzione; una possibile, che corregge anche i due difetti:

1. se sei alla fine del blocco, vai a 6
2. se davanti c'è un ostacolo, aggiralo e vai a 1
3. fai un passo con il piede sinistro
4. se sei alla fine del blocco, vai a 6
5. fai un passo con il piede destro e vai a 1
6. termina

Stirare una camicia, montare un mobile (slide 13-16). Altri due compiti da descrivere come algoritmo. Le slide mostrano il robot TEO del New Scientist che stira una camicia: per un robot “stira” va spezzato in misure della piega, movimenti del ferro, controlli. È l’idea dell’esecutore: lo stesso compito, descritto per un umano, sta in una riga.

Il problema della segretaria (slide 21-28). 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? L’esempio della slide: scegliere un compagno di appartamento fra 100 che ti contattano.

Sotto certe ipotesi è la strategia che massimizza la probabilità di scegliere il migliore in assoluto. Il 37% viene da 1/e≈0,3681/e \approx 0{,}368. Con 100 candidati la slide dice: non fermarti prima del 37°, e dal 38° in poi scegli il primo che va in cima alla classifica.

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%37\% di 5050 è 18,518{,}5.

La slide 27 chiede “altri problemi simili?”: sono simili tutti quelli in cui i candidati arrivano uno alla volta e un rifiuto è definitivo (un parcheggio lungo una strada a senso unico, un’offerta di lavoro con scadenza). La slide 28 chiede di descriverne uno proprio, in linguaggio naturale, con il problema e i passi.

Grafi isomorfi (slide 30-32). Due grafi sono isomorfi se hanno le stesse caratteristiche in termini di nodi e archi: si possono rinominare i nodi del primo in modo da ottenere esattamente il secondo. È un problema di decisione. Nella slide, a sinistra il grafo degli utenti Facebook (amicizia = arco, id = nodo), a destra quello degli utenti WhatsApp:

grafo 1: nodi a, b, c, d     archi a-b, b-d, d-c, c-a      (le due diagonali della slide sono a-c e b-d)
grafo 2: nodi 1, 2, 3, 4     archi 1-2, 2-3, 3-4, 4-1

rinomina a→1, b→2, d→3, c→4
  a-b → 1-2  c'è     b-d → 2-3  c'è     d-c → 3-4  c'è     c-a → 4-1  c'è

Tutti e quattro gli archi vanno in archi del secondo grafo, e i grafi hanno lo stesso numero di archi: la risposta è sì. L’esempio della slide 32 è più grande (due grafi da 8 nodi), stessa risposta. A colpo d’occhio i due disegni sembrano diversi (uno ha le diagonali incrociate, l’altro è un quadrato): conta solo chi è collegato a chi.

Il risveglio (slide 46-54). Problema in linguaggio naturale: “cosa devo fare dal momento in cui ci si sveglia per arrivare all’università”. Algoritmo in pseudocodice, solo sequenza:

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

La slide chiede “posso invertire i passi 3 e 4?” e mostra la versione con i passi scambiati: ci si fa la doccia vestiti. Ogni passo resta eseguibile, ma il risultato è sbagliato. “I passi sono eseguiti in sequenza e l’ordine delle istruzioni è essenziale per la correttezza dell’algoritmo.”

La sequenza non basta. Prima versione con una scelta senza alternativa (slide 52):

6. se piove
   6.1 prendere l'ombrello
7. prendere l'autobus

Poi con l’alternativa (slide 53):

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

E scegliere può non bastare (slide 54):

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

Tracing dell’ultima versione con “piove alle 8:00 e alle 8:30, smette alle 9:00” (un controllo ogni mezz’ora): alle 8:00 piove? sì, resto; alle 8:30 piove? sì, resto; alle 9:00 piove? no, esco dal ciclo e prendo l’autobus. Se piovesse sempre il ciclo non finirebbe.

Ricerca in biblioteca (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 (la scheda della slide: Alan Moore, David Lloyd, V for Vendetta, 1988, scaffale 35, posizione 21). 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 la slide chiede: “che succede se l’autore cercato è Manzoni Alessandro o Zac Zucker?”. Manzoni sta a metà schedario, Zucker in fondo: bisogna scorrerlo tutto. 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é 210=10242^{10} = 1024. Stesso problema, stessa correttezza, efficienza molto diversa.

Le due ricerche seguite a mano, su uno schedario di 16 schede con numeri al posto dei nomi (posizioni da 0 a 15). La scheda centrale fra le posizioni inizio e fine è quella in posizione (inizio+fine)/2(\text{inizio} + \text{fine}) / 2, arrotondato per difetto.

Cerco 37 con la dicotomica:

passoiniziofinecentraleschedaconfronto
101573137 > 31: tengo la destra, inizio ← 8
2815115137 < 51: tengo la sinistra, fine ← 10
381094037 < 40: tengo la sinistra, fine ← 8
488837trovato

4 confronti. La sequenziale guarda le posizioni 0, 1, …, 8: 9 confronti.

Cerco 30, che non c’è:

passoiniziofinecentraleschedaconfronto
101573130 < 31: fine ← 6
20631230 > 12: inizio ← 4
34652330 > 23: inizio ← 6
46662930 > 29: inizio ← 7
576inizio > fine: parte vuota, il libro non esiste

Qui si vede perché serve la seconda condizione di arresto: senza, al passo 5 non ci sarebbe una scheda centrale da guardare. La sequenziale, per dire “non c’è”, deve guardare tutte le 16 schede (o fermarsi a 31, se sfrutta l’ordine).

Radici di un’equazione di secondo grado (slide 64-69). Problema: calcolare le radici reali di ax2+bx+c=0ax^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”.

Tracing sulle tre strade (radici verificate):

a,b,ca, b, cpasso 2stradarisultato
1,−3,21, -3, 2Δ=9−8=1\Delta = 9 - 8 = 13 no, 4 no, 5 sìx1=3+12=2x_1 = \frac{3 + 1}{2} = 2, x2=3−12=1x_2 = \frac{3 - 1}{2} = 1, poi 6 e 7
1,2,11, 2, 1Δ=4−4=0\Delta = 4 - 4 = 03 no, 4 sì, salto a 6x1=x2=−22=−1x_1 = x_2 = \frac{-2}{2} = -1
1,0,11, 0, 1Δ=0−4=−4\Delta = 0 - 4 = -43 sì, salto a 7nessuna stampa di radici

Controllo della prima riga: 22−3⋅2+2=02^2 - 3 \cdot 2 + 2 = 0 e 1−3+2=01 - 3 + 2 = 0. Un caso che l’algoritmo non gestisce: a=0a = 0. Allora l’equazione è di primo grado e al passo 4 o 5 si dividerebbe per zero. Un algoritmo corretto controlla a≠0a \neq 0 dopo il passo 1.

Mediana (slide 70-74). La mediana mm di n1,…,nNn_1, \dots, n_N separa i valori in due metà con lo stesso numero di elementi ≤m\leq m e ≥m\geq m.

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.

Il passo 4 raffinato, con le posizioni numerate da 1 a NN:

4.1 se N è dispari, m ← a[(N + 1) / 2]
4.2 altrimenti m ← (a[N / 2] + a[N / 2 + 1]) / 2

Controllo sui due esempi: con N=7N = 7 la posizione è (7+1)/2=4(7 + 1)/2 = 4, e il quarto elemento ordinato è 6. Con N=6N = 6 le posizioni sono 33 e 44, cioè 5 e 7, media 6. La slide 75 suggerisce di chiedere lo stesso algoritmo a ChatGPT e confrontarlo.

Mazzo di carte (slide 76-77). Ordinare un mazzo di 52 carte in modo che le picche precedano i fiori, i fiori i quadri, i quadri i cuori (P-F-Q-C), descrivendolo in linguaggio naturale. Una soluzione, senza ordinare i valori dentro un seme (la slide non lo chiede):

1. prepara quattro mucchi vuoti: P, F, Q, C
2. mentre il mazzo non è vuoto
   2.1 prendi la carta in cima
   2.2 mettila sul mucchio del suo seme
3. impila i mucchi in ordine: P sopra, poi F, poi Q, poi C

Ogni carta si guarda una volta sola: 52 passi del ciclo. L’alternativa di cercare ogni volta “la prossima picca” nel mazzo farebbe molti più confronti.

Tavoletta di cioccolato (slide 78-81). Una tavoletta di h×kh \times k quadratini (hh righe, kk colonne) va divisa in quadratini singoli, spezzando sempre una porzione lungo una riga o una colonna. Esempio della slide: una porzione 5×25 \times 2 spezzata lungo la terza riga dà due porzioni, 3×23 \times 2 e 2×22 \times 2. Domande: quanti spezzamenti servono? Esistono strategie migliori di altre? La risposta (svolta negli esercizi) è che ne servono sempre h⋅k−1h \cdot k - 1, qualunque strategia.

Percorso più breve (slide 82-88, esempio 1.3 del libro). Una carta geografica è un grafo: le città sono nodi, le strade archi con una distanza. Le slide disegnano le città USA e cercano il percorso da Houston a Chicago. Assumendo che un percorso esista, per andare da CpC_p a CaC_a:

  1. trova tutte le sequenze di città C0,…,CkC_0, \dots, C_k con C0=CpC_0 = C_p, Ck=CaC_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.

Scala (slide 89-90, esercizio d’esame 2016/17). Una scala di NN gradini si sale con passi da 1, 2 o 3 scalini: in quanti modi? La slide imposta la soluzione provando a mano N=1,2,3,4N = 1, 2, 3, 4 e contando i passi di ogni tipo; la soluzione completa è in Ciclo while ed esempi. Le prove a mano:

NNmodiquanti
111
21+1, 22
31+1+1, 1+2, 2+1, 34
4vedi esercizio 11 della pagina esercizi7

Riparazione di uno pneumatico (slide 91-93). La slide mostra le istruzioni grafiche del kit di riparazione Continental (ContiMobilityKit), dieci riquadri numerati: è un “algoritmo in pseudocodice grafico”, da trasformare in pseudocodice testuale. I riquadri contengono anche condizioni (la lancetta del manometro nella zona verde o rossa) e limiti (velocità massima 80 km/h, 200 km), cioè selezioni e vincoli, non solo una sequenza.

Moltiplicazione (slide 94). Descrivere l’algoritmo di moltiplicazione di due interi di nn cifre e contare le operazioni: n2n^2 con il metodo delle elementari (ogni cifra del primo per ogni cifra del secondo), nlog⁡nn \log n con il più veloce noto. Con n=3n = 3, 123×456123 \times 456: 9 prodotti di cifre, 3⋅33 \cdot 3.

Esercizi lasciati aperti dalle slide, e dove sono svolti:

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Introduzione al corso e algoritmi (esercizi).

6Errori tipici

7Domande

Dai la definizione informale di algoritmo.

Una sequenza precisa di operazioni, comprensibili da un esecutore (non per forza un calcolatore), che in un numero finito di passi porta alla realizzazione di un compito.

Perché “comprensibili all’esecutore” è una parte necessaria della definizione di algoritmo?

Se anche un solo passo non è comprensibile, l’esecutore non può eseguire l’algoritmo. Per questo lo stesso compito va descritto in modo diverso a seconda dell’esecutore (persona o robot).

Che differenza c’è fra un algoritmo e un programma?

Un algoritmo è una sequenza di passi per un esecutore qualsiasi; un programma è un algoritmo scritto in un linguaggio di programmazione, così che lo esegua un calcolatore.

Quali sono le due proprietà fondamentali di un algoritmo e cosa significa ciascuna?

Correttezza: arriva alla soluzione senza errori. Efficienza: ci arriva usando meno risorse possibile, cioè tempo e memoria, non solo velocità.

Quali sono le tre categorie di problemi viste a lezione? Dai un esempio per ognuna.

Calcolo e conversione: produce un valore (Celsius in Fahrenheit). Decisione: risponde sì o no (“anna” è palindroma?). Ricerca: restituisce un elemento dell’insieme con certe caratteristiche (scegliere la segretaria o il coinquilino).

Quali linguaggi corrispondono a problema, algoritmo e programma?

Problema: linguaggio naturale (LP). Algoritmo: pseudocodice (LA). Programma: linguaggio di programmazione, nel corso il C (LT).

Quali sono le tre strutture di controllo con cui si costruisce un algoritmo?

Sequenza, selezione (se … altrimenti), iterazione (mentre … fai).

Cosa vuol dire procedere top-down (stepwise refinement)?

Si parte da un algoritmo generale e ogni passo non comprensibile o non eseguibile dall’esecutore diventa un sotto-algoritmo. Si ripete, dal generale al particolare, finché tutti i passi sono eseguibili.

Enuncia la regola del 37% del problema della segretaria.

Con N candidati: guarda il primo 37% senza scegliere e costruisci una classifica. Dopo, fermati sul primo candidato migliore di tutti quelli visti. Se non arriva, prendi il primo della classifica.

Perché la ricerca dicotomica nello schedario ha bisogno di due condizioni di terminazione?

Le uscite sono due: libro trovato, oppure parte da consultare vuota (libro non esiste). Senza la seconda, se il libro non c’è l’algoritmo non termina.

Perché la ricerca dicotomica funziona solo se lo schedario è ordinato?

Scarta metà schedario in base a “prima o dopo” la scheda centrale. Se non è ordinato, la metà scartata può contenere il libro e l’algoritmo risponde “non esiste” sbagliando.

Nell’algoritmo dell’equazione di secondo grado, perché dopo il caso Δ<0\Delta < 0 si salta direttamente alla fine?

Proseguendo, i passi 4 e 5 non scattano e si arriva al 6, che stamperebbe x1x_1 e x2x_2 mai calcolati. Il salto al 7 evita la stampa.