Programmazione I · Teoria · Canale B · Lezione 01A
Dal concetto di algoritmo alla moltiplicazione per somme ripetute, attraverso sette riscritture successive, fino al diagramma di flusso. Appunti ricostruiti dalle 30 slide della lezione, con esempi svolti, un simulatore passo-passo, esercizi e domande di ripasso.
m × n (con n ≥ 0) con una macchina che sa solo sommare, assegnare e confrontare: somme ripetute a partire dall'elemento neutro 0.s (la somma parziale) e un contatore i (le addizioni già fatte).i = n dopo aver sommato, con n = 0 l'algoritmo non termina mai.← assegna, = confronta. Dai salti a righe numerate si passa ai blocchi annidati (Inizio/Fine) resi visibili dall'indentazione.Sei del canale A o C?
Canale A (Fiandrotti): deck molto simile "01A_primo_algoritmo" (40 slide), con le stesse versioni V1–V6 e lo stesso bug del caso n = 0. Rispetto al canale B mancano la slide "In informatica tutto è numero", la slide "Progettare un algoritmo" (input, output, passi, terminazione), il riquadro su dati, procedure e Wirth ("Programma = Algoritmi + Strutture Dati"), la versione V7 senza numeri di riga e il confronto tra flow-chart e rappresentazione strutturata; nella slide sul caso iniziale manca "anche in sede d'esame". Nella stessa settimana c'è anche "01B_architettura".
Canale C (Mazzei): l'argomento è la sezione "Il Primo Algoritmo" (slide 20–42) della lezione 01. Parte dall'addizione in colonna, chiama "dita" il contatore e salta le versioni sbagliate e il caso n = 0, arrivando subito allo pseudocodice corretto e al diagramma di flusso; poi prosegue con Von Neumann, assembly e FORTRAN.
L'esame è unico per i tre canali: caso iniziale e "prima verificare, poi eseguire" (§8) valgono per tutti.
La parola ha cambiato significato nel tempo:
L'informatica non è la scienza dei calcolatori. Non più di quanto l'astronomia sia la scienza dei telescopi o la chirurgia la scienza dei bisturi.
Il messaggio: l'informatica studia gli algoritmi, non i dispositivi. Il computer è solo lo strumento con cui gli algoritmi vengono eseguiti.
Definizione · slide 4
Informatica = lo studio degli algoritmi, che comprende:
| Aspetto | Che cosa si studia | Dove lo ritroverai |
|---|---|---|
| Proprietà formali e matematiche | Algoritmi corretti ed efficienti | Algoritmi e Strutture Dati, corsi di matematica e logica |
| Realizzazione fisica | Progettare e costruire computer che eseguono gli algoritmi | Architettura degli Elaboratori |
| Realizzazione linguistica | Progettare linguaggi di programmazione per scrivere ed eseguire gli algoritmi | Programmazione I e II, Linguaggi Formali e Traduttori |
| Applicazioni | Progettare software (algoritmi implementati) per problemi importanti | Basi di Dati, Reti, Sistemi Operativi e gran parte degli anni successivi |
La colonna "Dove lo ritroverai" è un collegamento aggiunto negli appunti, non è nelle slide.
La slide dà due definizioni. La prima è intuitiva, la seconda è quella precisa da saper ripetere.
Definizione intuitiva
Un procedimento di calcolo ben definito, eseguibile meccanicamente da un essere umano o da una macchina, per ottenere un dato risultato (output) a partire da certi dati di partenza (input).
Definizione precisa · da memorizzare
Un insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in un tempo finito.
Ogni parola chiave è un requisito. Se ne manca uno, non è un algoritmo:
| Proprietà | Significato | Controesempio |
|---|---|---|
| Ordinato | Le operazioni hanno una sequenza precisa: dopo ogni passo si sa quale viene dopo. | Una lista di istruzioni senza ordine ("scola la pasta", "fai bollire l'acqua"…) |
| Non ambiguo | Ogni operazione ha una sola interpretazione possibile. | "Aggiungi sale q.b." |
| Effettivamente computabile | Ogni operazione si può davvero eseguire, con i mezzi che l'esecutore ha a disposizione. | "Calcola m × n" per una macchina che sa solo sommare; "dividi per 0" |
| Produce un risultato | Alla fine c'è un output. | Una procedura che non restituisce né comunica nulla |
| Si arresta in tempo finito | Termina dopo un numero finito di passi, per ogni input ammesso. | La seconda formulazione della moltiplicazione con n = 0 (§8) |
"Eseguibile meccanicamente" significa che per eseguirlo non servono intuito o creatività: basta seguire le istruzioni. È proprio questo che permette di affidarlo a una macchina.
Dal matematico persiano Muḥammad ibn Mūsā al-Khwārizmī, vissuto intorno all'anno 800. Il suo libro sui calcoli con i numerali indiani (le cifre 0–9 con la notazione posizionale che usiamo oggi) descrive procedure per le operazioni aritmetiche. Nella traduzione latina del XII secolo il testo si apre con le parole "Dixit Algorizmi" ("così disse al-Khwārizmī"); l'opera è nota con il titolo "Algoritmi de numero Indorum", che le fu dato nell'edizione a stampa del 1857. Dal nome latinizzato dell'autore deriva "algoritmo". Curiosità: da un altro suo libro (al-jabr) deriva la parola "algebra".
Oltre le slide · esempi
La lettera A è memorizzata come il numero 65 (codice ASCII), cioè 01000001 in binario. Un pixel rosso è la terna di numeri (255, 0, 0). In C lo vedrai presto: un carattere è un piccolo intero.
Una variabile è un contenitore con un nome (s, i, m…) che contiene un valore, e quel valore può cambiare durante l'esecuzione. L'insieme dei valori delle variabili è lo stato.
Problema: calcolare la moltiplicazione fra due numeri interi m e n, con n ≥ 0. Prima di scrivere qualsiasi passo bisogna fissare quattro cose:
m e nm × nIpotesi sulla macchina: non sa moltiplicare direttamente, ma sa eseguire operazioni elementari: somma, assegnamento e confronto.
L'idea chiave
Progettare l'algoritmo significa costruire il risultato richiesto usando soltanto le operazioni disponibili. Si riconduce un'operazione che la macchina non ha (la moltiplicazione) a una che ha (l'addizione).
Oltre le slide · precondizione
Il vincolo n ≥ 0 si chiama precondizione: è ciò che deve valere sull'input perché l'algoritmo funzioni. Nota che su m non c'è vincolo: può essere anche negativo (vedi esercizio 3).
Per n ≥ 0 vale:
m × n = m + m + … + m ▷ n addendi: sommo m a sé stesso n−1 volte
s = 0 + m + m + … + m ▷ parto dall'elemento neutro 0: sommo m esattamente n volteLa seconda scrittura parte dall'elemento neutro della somma (0, perché a + 0 = a). Conviene per tre motivi:
n = 0 è gestito da solo: zero addizioni, e il risultato resta 0 = m × 0.Resta da stabilire come eseguire meccanicamente esattamente n addizioni e poi fermarsi. Serve qualcosa che conti.
0 + 4 = ───── 4 + ← 1° parziale 4 = ───── 8 + ← 2° parziale 4 = ───── 12 ← 3° parziale e totale
| Dita alzate | s |
|---|---|
| nessuna | 0 |
| una | 4 |
| due | 8 |
| tre → mi fermo | 12 |
Le slide 10–13 mostrano la stessa cosa: si parte dal "parziale iniziale" s = 0 con il pugno chiuso, e a ogni addizione si alza un dito. Quando le dita alzate sono tre (cioè n), ci si ferma.
La moltiplicazione si realizza sommando ripetutamente m a una somma parziale s, inizialmente 0, per n volte. Per farlo meccanicamente servono due strumenti:
| Strumento | Variabile | A cosa serve | Nell'esempio a mano |
|---|---|---|---|
| Accumulatore | s | tiene traccia della somma parziale | il foglio di carta su cui faccio le addizioni |
| Contatore | i | tiene traccia del numero di addizioni fatte | le dita della mano usate per contare |
Da qui due concetti essenziali della programmazione, su cui il corso tornerà spesso:
Niklaus Wirth
Programma = Algoritmi + Strutture Dati
Un programma è la combinazione di come rappresentiamo i dati e di come definiamo le operazioni che li elaborano. Wirth, creatore del linguaggio Pascal, intitolò così un suo libro del 1976 (Algorithms + Data Structures = Programs).
Oltre le slide · due schemi che rivedrai ovunque
Accumulatore: una variabile inizializzata all'elemento neutro dell'operazione (0 per somme e conteggi, 1 per prodotti) e aggiornata a ogni passo. Ciclo controllato da contatore: una variabile che parte da un valore iniziale, avanza di 1 a ogni ripetizione e decide quando fermarsi. Quasi ogni esercizio sui cicli ne usa almeno uno.
Il cuore della lezione è il modo in cui l'algoritmo viene raffinato un passo alla volta: ogni versione corregge un difetto della precedente. Sapere perché si passa da una versione all'altra conta quanto sapere la versione finale.
1. Preliminarmente, imposta al valore neutro 0 l'accumulatore s,
e imposta a 0 il contatore i.
2. Somma m a s esattamente n volte, aggiornando il contatore i
(addizioni fatte) e contemporaneamente l'accumulatore s
(risultato parziale).Difetto: il punto 2 è semanticamente complesso. Nasconde al suo interno la ripetizione e il controllo, quindi non è un passo elementare che la macchina sappia eseguire.
1. imposta s a 0 (valore neutro) e i a 0
2. somma m all'accumulatore s
3. somma 1 al contatore i
4. se i = n: le addizioni sono finite e s è il totale,
altrimenti ripeti dal punto 2Difetto: funziona con m = 4, n = 3, ma il controllo arriva dopo la somma. Con n = 0 esegue comunque una addizione, poi i = 1 e la condizione i = n non sarà mai vera: non termina (§8).
[1] imposta l'accumulatore s a 0 e il contatore i a 0
[2] se i = n le addizioni sono finite e s è il totale:
terminiamo. Altrimenti continuiamo.
[3] somma m all'accumulatore s
[4] somma 1 al contatore i
[5] ritorna alla riga 2Cosa cambia: la verifica viene prima delle operazioni. Con n = 0 termina subito con s = 0. Le righe sono numerate perché servono come destinazione dei salti.
[1] s ← 0, i ← 0
[2] se i = n l'algoritmo termina, altrimenti
[3] s ← s + m ▷ somma m ad s
[4] i ← i + 1 ▷ incrementa di 1 il contatore i
[5] ritorna alla riga 2Cosa cambia: ← è l'assegnamento ("il valore a destra va nella variabile a sinistra"), = è il confronto. Il testo dopo ▷ è un commento. Il rientro (indentazione) di [3]–[5] è voluto: indica che quelle operazioni dipendono dalla condizione della riga [2].
[1] s ← 0, i ← 0
[2] se i = n allora salta alla riga 6, altrimenti
[3] s ← s + m
[4] i ← i + 1
[5] salta alla riga 2
[6] FineCosa cambia: dire che "l'algoritmo termina" è troppo forte, perché dopo la moltiplicazione potremmo voler eseguire altre istruzioni. Si introduce l'istruzione speciale Fine e si usa il salto verso un'istruzione numerata sia per ripetere sia per uscire.
[1] Inizio Algoritmo
[2] s ← 0, i ← 0
[3] Inizio Ripetizione Condizionata
se i = n allora salta alla riga 7, altrimenti ▷ salto condizionato
[4] s ← s + m
[5] i ← i + 1
[6] salta alla riga 3 ▷ salto non condizionato
[7] Fine Ripetizione Condizionata
[8] Fine AlgoritmoCosa cambia: per uniformità i blocchi sono delimitati da coppie di istruzioni speciali Inizio/Fine. Si distinguono il salto condizionato (riga 3 → 7, avviene solo se i = n) e il salto non condizionato (riga 6 → 3, avviene sempre).
Inizio Algoritmo
s ← 0, i ← 0
Inizio Ripetizione Condizionata
se i = n salta alla Fine Ripetizione Condizionata, altrimenti
s ← s + m
i ← i + 1
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoCosa cambia: la struttura permette di eliminare i numeri di riga: i salti puntano all'inizio o alla fine di un blocco. I linguaggi di programmazione strutturati organizzano le istruzioni in blocchi annidabili, e l'indentazione rende visibile la gerarchia e l'appartenenza di ogni istruzione al proprio blocco. È esattamente la forma che avrà il ciclo while in C (§11).
L'algoritmo V2 è stato costruito a partire da valori "di prova" (m = 4, n = 3). Ma funziona anche per input diversi? La slide prova un caso particolare: n = 0, dove il risultato atteso è 0 (perché m × 0 = 0).
| Passo | Istruzione | s | i | Verifica i = n |
|---|---|---|---|---|
| 1 | s ← 0, i ← 0 | 0 | 0 | non ancora controllata |
| 2 | s ← s + m | 4 | 0 | — |
| 3 | i ← i + 1 | 4 | 1 | — |
| 4 | se i = n … | 4 | 1 | 1 = 0? NO → ripeti |
| 7 | se i = n … | 8 | 2 | 2 = 0? NO → ripeti |
| … | … | … | … | i > n per sempre: non termina |
Il problema è l'ordine: V2 prima aggiorna s e i e dopo confronta i con n. Se n = 0, l'algoritmo non terminerà mai (sempre i > n). Inoltre, anche se si fermasse, s sarebbe già diverso da 0: il risultato sarebbe sbagliato.
Correzione: bisogna prima verificare che il contatore i sia inferiore a n, e solo dopo eventualmente eseguire l'addizione. Con V3 e m = 4, n = 0: s ← 0, i ← 0, poi 0 = 0? SÌ → fine con s = 0. Corretto.
Il principio di progetto del corso · slide 20
Prima verificare le condizioni, e solo dopo eseguire (la prima di una serie di) operazioni.
"Ci accompagnerà nel resto di questo insegnamento."
Conta all'esame · slide 20
Testuale dalla slide: "La gestione del caso iniziale è una tipica fonte di errori, anche in sede d'esame." Quando scrivi un ciclo chiediti sempre: che cosa succede se il ciclo non deve essere eseguito neanche una volta?
Oltre le slide · come si verifica un algoritmo
Oltre al caso "normale" usato per progettarlo, prova sempre i casi limite: n = 0 (nessuna ripetizione), n = 1 (una sola), m = 0, m negativo, e cosa succede se la precondizione è violata (n < 0). Puoi farlo nel simulatore qui sotto.
Prima di passare a un vero linguaggio di programmazione, la lezione introduce una rappresentazione intermedia: il diagramma di flusso.
Nel diagramma della moltiplicazione i due salti si vedono bene: l'uscita SÌ del rombo verso Fine è il salto condizionato (avviene solo se i = n), la freccia che dal blocco delle somme torna al rombo è il salto non condizionato (avviene sempre).
Caricamento…
| # | Riga | Istruzione | s | i | Che cosa succede |
|---|
Terminologia · slide 27
Programma: descrizione di un algoritmo attraverso un linguaggio di programmazione.
Linguaggio di programmazione: insieme di parole e di regole, definite in modo formale, per consentire la programmazione di un calcolatore affinché esegua compiti predeterminati.
| Linguaggi | Caratteristica | Esempi |
|---|---|---|
| Di basso livello | vicini alla macchina | linguaggio macchina, assembly |
| Di alto livello | vicini al linguaggio naturale | FORTRAN, C, Java, Python |
Ora abbiamo un'idea di come implementare l'algoritmo di moltiplicazione su un vero computer. Lo scopo del corso è imparare a implementare algoritmi elementari (molto semplici) nel linguaggio C, cioè a tradurre in C algoritmi specificati in italiano.
| Termine | Significato (note della slide 30) |
|---|---|
| Implementare | realizzare concretamente una procedura usando un linguaggio di programmazione, partendo dalla sua definizione logica |
| Tradurre | è l'obiettivo di Programmazione I. Nell'esame di Algoritmi lo scopo sarà invece analizzare e progettare nuovi algoritmi |
Per farlo serve un modello di calcolo che possa essere eseguito da un calcolatore meccanico o elettronico: la macchina di Von Neumann, argomento della prossima parte.
Oltre le slide · anteprima di Von Neumann
Nella macchina di Von Neumann una memoria contiene sia i dati sia le istruzioni del programma. La CPU ripete sempre lo stesso ciclo: preleva l'istruzione successiva, la decodifica, la esegue. Un registro (il program counter) indica quale istruzione eseguire: normalmente passa alla successiva ("riga n+1", slide 7). Un salto non fa altro che cambiarne il valore. Il nostro pseudocodice con i numeri di riga è quindi molto vicino a come lavora davvero la macchina.
Il C arriverà nelle prossime lezioni, ma vedere adesso dove porta la versione V7 aiuta a capire perché la lezione insiste tanto su blocchi e condizioni.
#include <stdio.h>
#include <assert.h>
int main(void) {
int m = 4, n = 3; // input (per ora fissati nel codice)
assert(n >= 0); // precondizione
int s = 0; // accumulatore: parte dall'elemento neutro
int i = 0; // contatore delle addizioni fatte
while (i != n) { // prima verifico la condizione...
assert(s == m * i);// invariante (§12): vale a ogni controllo
s = s + m; // ...poi eseguo: s ← s + m
i = i + 1; // i ← i + 1
} // fine blocco: si torna al controllo del while
assert(s == m * n); // postcondizione
printf("%d x %d = %d\n", m, n, s);
return 0;
}Verificato con gcc -Wall -Werror (le opzioni usate all'esame negli anni scorsi): stampa 4 x 3 = 12, e funziona anche con 5 × 0, 0 × 7, −2 × 3. assert(cond), da <assert.h>, ferma il programma con un errore se la condizione è falsa: nel corso si usa per scrivere pre e postcondizioni direttamente nel codice.
| Pseudocodice (V7) | C | Attenzione |
|---|---|---|
| s ← 0 | s = 0; | in C = è l'assegnamento |
| i = n (confronto) | i == n | il confronto è == (doppio uguale) |
| Inizio … Fine | { … } | le graffe delimitano un blocco |
| Inizio Ripetizione Condizionata se i = n salta alla Fine… | while (i != n) { | il while ripete finché la condizione è vera: la condizione di uscita (i = n) va negata (i != n) |
| salta all'Inizio Ripetizione… | } | il salto non condizionato è implicito nella fine del blocco |
| ▷ commento | // commento | ignorato dal compilatore |
Trappola classica del C
Scrivere if (i = n) invece di if (i == n): il primo assegna n a i, non li confronta. Senza opzioni il compilatore lo accetta in silenzio (è C valido); con -Wall gcc avvisa ("suggest parentheses around assignment used as truth value") e con -Wall -Werror, le opzioni usate all'esame negli anni scorsi, il programma non compila. La distinzione ← / = vista nella slide 22 serve proprio a non confondere le due cose.
Spesso si scrive while (i < n) invece di while (i != n). Con n ≥ 0 le due versioni fanno esattamente le stesse cose. Con n negativo, i < n è falso subito e il ciclo termina (con un risultato sbagliato), mentre i != n non termina mai. In entrambi i casi la precondizione va rispettata.
La versione V2 (controllo dopo) corrisponde invece al ciclo do { … } while (…); del C, che esegue il corpo almeno una volta. Con i do-while il caso iniziale richiede sempre un'attenzione in più.
Le slide verificano l'algoritmo provando dei casi. Si può anche ragionare sul perché funziona sempre. Sono concetti che torneranno quando parlerete di correttezza dei cicli.
Ogni volta che si arriva alla verifica i = n ? vale s = m × i:
s = 0 e i = 0, e infatti 0 = m × 0.s = m × i, dopo s ← s + m e i ← i + 1 vale s + m = m × i + m = m × (i + 1). La proprietà si conserva.i = n, quindi s = m × n. È esattamente il risultato voluto.La quantità n − i parte da n ≥ 0 e diminuisce di 1 a ogni giro: dopo esattamente n giri vale 0 e il ciclo si ferma. Qui serve la precondizione: con n < 0 la quantità parte negativa, i cresce e non raggiungerà mai n (provalo nel simulatore con il preset "4 × −2").
Con input n: la condizione viene valutata n + 1 volte (n volte "NO", una volta "SÌ"), il corpo viene eseguito n volte, cioè n addizioni su s e n incrementi di i. Il tempo cresce in proporzione a n. Questo tipo di conto sarà centrale in Algoritmi e Strutture Dati.
Da evitare
static partono da 0.m + m + … + m ha n addendi ma n − 1 addizioni. Partendo da 0 le addizioni sono esattamente n.← contro = nello pseudocodice, = contro == in C.Questa lezione non è "teoria da ripetere e basta": i suoi concetti sono la base di tutte le tipologie d'esame. Ecco come si collegano.
Che cosa dice la scheda ufficiale · Programmazione I, MFN0582, 2026/27
"L'esame è essenzialmente uno scritto che si svolge al calcolatore o su carta." Verifica la capacità di progettare semplici algoritmi iterativi e ricorsivi, di codificarli in C, di rispondere a domande su correttezza e terminazione e di simulare il funzionamento del linguaggio durante l'esecuzione. Il voto è la somma dei punteggi degli esercizi, fino a 30 e lode. Niente orale, progetto o esoneri.
La slide "Tipico esame di Programmazione 1" della presentazione del canale B precisa: esercizi in laboratorio su Moodle, al PC, di programmazione iterativa e ricorsiva, di teoria (correttezza, tipi) e sullo stato della memoria. I dettagli arrivano a fine corso, con esercizi simili a quelli d'esame.
| Appello 2026/27 | Iscrizioni su MyUniTo | Dove |
|---|---|---|
| lun 25/01/2027, ore 9:00 | 05/01 – 18/01/2027 | laboratori Turing, Dijkstra e Von Neumann |
| gio 11/02/2027, ore 9:00 | 22/01 – 04/02/2027 | laboratori Turing, Dijkstra e Von Neumann |
L'appello è unico per i canali A, B e C. Con circa 400 iscritti e 118 posti nei tre laboratori, negli anni scorsi è stato diviso in turni su più giorni: la convocazione arriva per email all'indirizzo @edu.unito.it. Allo stesso esame ci si può presentare al massimo 3 volte per anno accademico. Per iscriversi servono tasse in regola, piano carriera approvato e la valutazione del corso su Edumeter, tutto entro il 18/01 per il primo appello. Gli altri appelli non sono ancora pubblicati: oltre alla sessione estiva (07/06–30/07/2027) e a quella autunnale (da settembre 2027), il calendario 2026/27 del corso di laurea prevede, in via sperimentale, un 3° appello per gli insegnamenti del 1° semestre il 31/03 e l'1–2/04/2027 (dettagli non ancora pubblicati).
| Tipologia | Che cosa chiede | Che cosa c'entra la lezione 01A |
|---|---|---|
| Funzione iterativa | Scrivere una funzione con cicli che verifica una proprietà su array o matrici ("per ogni…", "esiste…"), spesso calcolando anche una somma o un conteggio. | Accumulatori, contatori, e soprattutto il caso iniziale: da che valore parte la variabile che raccoglie il risultato? |
| Funzione ricorsiva | Scrivere una funzione ricorsiva (con una funzione "involucro" che la avvia) del tipo richiesto dal testo, senza usare cicli. | Il caso base della ricorsione è il caso iniziale di questa lezione (n = 0), e la terminazione va garantita. |
| Modello della memoria | Simulare a mano l'esecuzione di un programma e rispondere a domande sui valori delle variabili in punti precisi. | È una traccia di esecuzione, come quella del simulatore (§9) e dell'esercizio 1, applicata al C. |
| Correttezza | Scegliere o scrivere le asserzioni (pre e postcondizioni) ragionando all'indietro sul codice. | Precondizione n ≥ 0, postcondizione s = m × n, invariante s = m × i (§12). |
| Heap | Scrivere una funzione che crea un nuovo array con malloc e lo restituisce (un puntatore int*), scrivendo la sua lunghezza in un parametro di uscita (per esempio *out_len). | Anche qui il caso iniziale: che cosa succede se non c'è nessun elemento da copiare? |
Fonti: esercizi Moodle 2023/24 e riepilogo d'esame 2025/26 del canale C (5 esercizi su Moodle con CodeRunner: correttezza, memoria, iterativa, ricorsiva, heap), fac-simili 2016–2019. Esame e commissione sono unici per i tre canali, ma il formato preciso del 2026/27 sarà spiegato a fine corso.
return; usare variabili sentinella per combinare le condizioni; vietati break, switch, case e static, e in generale i costrutti non visti a lezione.for e while; attenzione al tipo di ricorsione richiesto.-Wall -Werror, quindi anche un solo warning impedisce la compilazione.Il collegamento con la programmazione strutturata
Queste regole applicano l'idea della §7. break e i return multipli sono salti che escono da un blocco "dal fianco". Nella V7 invece dalla ripetizione si esce solo attraverso la sua condizione. All'esame il ciclo deve fermarsi grazie alla condizione (per esempio i < n && !trovato), non grazie a un salto.
Oltre le slide · anteprima di un esercizio d'esame
Ecco dove porta il principio "prima verifica, poi esegui", applicato a un array (argomento delle prossime settimane): esiste un elemento negativo tra i primi aLen elementi di a?
bool esiste = false; // caso iniziale: in un array vuoto non esiste nulla
size_t i = 0; // contatore
while (i < aLen && !esiste) { // prima verifico, poi eseguo; niente break
esiste = (a[i] < 0);
i = i + 1;
}
return esiste; // una sola returnPer "tutti gli elementi sono positivi" la sentinella parte invece da true, perché in un array vuoto la proprietà vale. Sbagliare questo valore iniziale è l'errore del caso iniziale.
Cosa fare già da questa settimana
gcc -Wall -Werror file.c -o file, così ti alleni nelle condizioni d'esame. All'esame si scrive in un editor di testo semplice, senza IDE né autocompletamento: esercitati anche così.Prova a risolverli su carta prima di aprire la soluzione. Usa la notazione della V7 (o la V6 con i numeri di riga).
Esegui la versione V6 (slide 25) con m = 5, n = 2. Scrivi una tabella con riga eseguita, s, i ed esito del controllo. Quante volte viene valutata la condizione? Quante addizioni su s?
| # | Riga | s | i | Nota |
|---|---|---|---|---|
| 1 | [1] Inizio | — | — | |
| 2 | [2] s ← 0, i ← 0 | 0 | 0 | |
| 3 | [3] i = n? | 0 | 0 | 0 = 2? NO |
| 4 | [4] s ← s + m | 5 | 0 | |
| 5 | [5] i ← i + 1 | 5 | 1 | |
| 6 | [6] salta a 3 | 5 | 1 | |
| 7 | [3] i = n? | 5 | 1 | 1 = 2? NO |
| 8 | [4] s ← s + m | 10 | 1 | |
| 9 | [5] i ← i + 1 | 10 | 2 | |
| 10 | [6] salta a 3 | 10 | 2 | |
| 11 | [3] i = n? | 10 | 2 | 2 = 2? SÌ → riga 7 |
| 12 | [7] Fine Rip. | 10 | 2 | |
| 13 | [8] Fine | 10 | 2 | s = 10 = 5 × 2 |
Condizione valutata 3 volte (n + 1), addizioni su s: 2 (n). Controlla con il simulatore.
Esegui la V2 (controllo dopo) con m = 3, n = 1 e poi con m = 3, n = 0. In quale caso funziona? Perché la V2 "sembra" corretta se si prova solo con n ≥ 1?
Con n = 1: s ← 0, i ← 0; s ← 3; i ← 1; 1 = 1? SÌ → s = 3. Corretto.
Con n = 0: s ← 3, i ← 1, 1 = 0? NO, poi s = 6, i = 2… non termina.
La V2 esegue il corpo almeno una volta. Questo è giusto solo se servono almeno una addizione, cioè n ≥ 1. Il caso n = 0 è l'unico caso ammesso (n ≥ 0) in cui il corpo non deve essere eseguito, ed è proprio lì che sbaglia. Morale: il caso iniziale va sempre provato.
(a) L'algoritmo funziona con m = −2, n = 3? (b) E con m = 2, n = −3? (c) Modificalo perché funzioni per qualsiasi intero n, sapendo che la macchina sa anche calcolare l'opposto di un numero (x ← −x).
(a) Sì: s vale 0, −2, −4, −6 e −6 = −2 × 3. Su m non c'è nessun vincolo.
(b) No: i vale 0, 1, 2, … e non sarà mai uguale a −3. La precondizione n ≥ 0 è violata e l'algoritmo non termina.
(c) Si usa l'identità m × n = (−m) × (−n): se n è negativo si cambiano di segno entrambi, e ci si riconduce al caso n ≥ 0.
Inizio Algoritmo
se n < 0 allora m ← −m, n ← −n ▷ ora n ≥ 0
s ← 0, i ← 0
Inizio Ripetizione Condizionata
se i = n salta alla Fine Ripetizione Condizionata, altrimenti
s ← s + m
i ← i + 1
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoEsempio: 2 × (−3) diventa (−2) × 3 = −6. Corretto.
Scrivi un algoritmo che, dati m ≥ 0 e n > 0, calcoli quoziente q e resto r della divisione intera m ÷ n usando solo addizione, sottrazione, assegnamento e confronto. Eseguilo con m = 14, n = 4. Che cosa succede se n = 0?
Inizio Algoritmo
q ← 0, r ← m ▷ r è "quello che resta da dividere"
Inizio Ripetizione Condizionata
se r < n salta alla Fine Ripetizione Condizionata, altrimenti
r ← r − n ▷ tolgo un n
q ← q + 1 ▷ conto quanti n ho tolto
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoTraccia (q, r): (0, 14) → (1, 10) → (2, 6) → (3, 2), poi 2 < 4 → fine: q = 3, r = 2, infatti 14 = 3 × 4 + 2.
Il controllo è prima del corpo: se m < n esce subito con q = 0, r = m (per esempio 3 ÷ 5 → q = 0, r = 3). Stesso principio della slide 20.
Se n = 0, r non diminuisce mai e il ciclo non termina: è la "divisione per zero". Per questo la precondizione richiede n > 0. Qui q fa da contatore, ma a differenza della moltiplicazione non sai in anticipo quante ripetizioni farai.
(a) Calcola p = mⁿ (n ≥ 0) supponendo che la macchina sappia moltiplicare. Da che valore parte p? (b) Sfida: e se la macchina sapesse solo sommare (con m ≥ 0)?
(a) Stesso schema della moltiplicazione, ma l'accumulatore parte dall'elemento neutro del prodotto, cioè 1. Se partisse da 0 il risultato sarebbe sempre 0.
Inizio Algoritmo
p ← 1, i ← 0
Inizio Ripetizione Condizionata
se i = n salta alla Fine Ripetizione Condizionata, altrimenti
p ← p × m
i ← i + 1
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoCon m = 2, n = 3: p vale 1, 2, 4, 8. Con n = 0 dà 1 (per convenzione m⁰ = 1).
(b) Si sostituisce p ← p × m con l'algoritmo di moltiplicazione: una ripetizione dentro l'altra (cicli annidati). Qui si vede perché blocchi e indentazione sono indispensabili.
Inizio Algoritmo
p ← 1, i ← 0
Inizio Ripetizione Condizionata ▷ esterna: n volte
se i = n salta alla Fine Ripetizione Condizionata, altrimenti
s ← 0, j ← 0 ▷ calcolo p × m con somme
Inizio Ripetizione Condizionata ▷ interna: m volte
se j = m salta alla Fine Ripetizione Condizionata, altrimenti
s ← s + p
j ← j + 1
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
p ← s
i ← i + 1
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoOgni "salta" si riferisce al blocco di cui fa parte: l'indentazione è ciò che rende questa lettura non ambigua. Serve un secondo contatore (j) e un secondo accumulatore (s), azzerati a ogni giro esterno.
Scrivi un algoritmo che calcoli 1 + 2 + … + n (n ≥ 0). Poi rispondi: che cosa calcola se nel corpo si scambiano le due istruzioni?
Inizio Algoritmo
s ← 0, i ← 0
Inizio Ripetizione Condizionata
se i = n salta alla Fine Ripetizione Condizionata, altrimenti
i ← i + 1 ▷ prima avanzo il contatore...
s ← s + i ▷ ...poi lo sommo: aggiungo 1, 2, …, n
salta all'Inizio Ripetizione Condizionata
Fine Ripetizione Condizionata
Fine AlgoritmoCon n = 4, (i, s): (0, 0) → (1, 1) → (2, 3) → (3, 6) → (4, 10). Infatti 1 + 2 + 3 + 4 = 10 = 4 × 5 / 2.
Se si scambiano (s ← s + i e poi i ← i + 1) si sommano 0, 1, 2, 3 = 6: è la somma dei numeri da 0 a n − 1, un classico errore "di uno". Qui il contatore viene anche usato come dato, quindi l'ordine conta.
Disegna il diagramma di flusso dell'esercizio 4 (divisione). Indica quale freccia è il salto condizionato e quale il salto non condizionato.
Inizio → rettangolo q ← 0, r ← m → rombo r < n ?. Dal rombo: uscita SÌ → Fine (salto condizionato); uscita NO → rettangolo r ← r − n, q ← q + 1 → freccia che torna al rombo (salto non condizionato).
È lo stesso disegno della moltiplicazione: cambiano solo il contenuto dei blocchi e la condizione. Molti algoritmi con un ciclo hanno questa forma.
Con m, n ≥ 0 l'algoritmo fa n addizioni: per 3 × 1000 ne fa mille. Modificalo in modo che ne faccia min(m, n). Serve scambiare il contenuto di due variabili: perché m ← n, n ← m non funziona?
Poiché m × n = n × m, se n > m conviene scambiare m e n prima del ciclo. Lo scambio richiede una variabile d'appoggio t:
se n > m allora
t ← m ▷ salvo m
m ← n
n ← t
▷ ...poi l'algoritmo di moltiplicazione come primaCon m ← n, n ← m il primo assegnamento sovrascrive m, e il secondo copia in n il valore che n aveva già: alla fine entrambe valgono il vecchio n. Lo scambio con variabile d'appoggio è uno degli esercizi dei primi laboratori.
Un insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in un tempo finito. Ordinato: sequenza precisa. Non ambiguo: una sola interpretazione. Effettivamente computabile: eseguibile davvero dall'esecutore. Produce un risultato: c'è un output. Termina: numero finito di passi per ogni input ammesso.
Che l'informatica non è la scienza dei computer, così come l'astronomia non è la scienza dei telescopi: il computer è lo strumento. L'informatica studia gli algoritmi: le loro proprietà (correttezza, efficienza), la loro realizzazione fisica (i computer), quella linguistica (i linguaggi di programmazione) e le applicazioni (il software).
Dal nome del matematico persiano al-Khwārizmī (intorno all'800), autore di un libro sui calcoli con i numerali indiani che descrive procedure per le operazioni aritmetiche.
Perché ogni informazione (testo, immagine, suono, istruzione) nella memoria del computer è codificata come numero, cioè come sequenza di bit. Un programma imperativo lavora modificando valori numerici nello stato della macchina; programmare significa descrivere come trasformarli passo dopo passo.
Il programma è una sequenza ordinata di istruzioni, una per riga. Finita la riga n si esegue la n+1, salvo diversa indicazione (salti). Istruzioni tipiche: assegnare un valore a una variabile, sommare due variabili mettendo il risultato in una terza, confrontare due variabili, saltare a un'altra riga (eventualmente sotto condizione).
Input (i dati di partenza), output (il risultato), passi (una sequenza non ambigua di operazioni che la macchina sa eseguire) e terminazione (si raggiunge l'output e ci si ferma dopo un numero finito di passi). Bisogna anche sapere quali operazioni ha a disposizione la macchina.
Perché 0 è l'elemento neutro della somma: s = 0 + m + … + m richiede esattamente n addizioni tutte uguali, e il caso n = 0 dà subito il risultato giusto (0) senza trattamenti speciali. Scrivendo m + m + … + m le addizioni sarebbero n − 1 e il caso n = 0 non avrebbe senso.
L'accumulatore s tiene la somma parziale, come il foglio di carta su cui si fanno le addizioni. Il contatore i tiene il numero di addizioni già fatte, come le dita della mano, e serve a decidere quando fermarsi.
Niklaus Wirth. Un programma combina il modo in cui rappresentiamo e organizziamo i dati con le procedure (algoritmi) che li trasformano.
Perché aggiorna s e i e solo dopo controlla se i = n. Con n = 0 esegue comunque un'addizione, i diventa 1 e la condizione i = n non sarà mai vera: l'algoritmo non termina. Principio: prima verificare le condizioni, e solo dopo eseguire le operazioni. La gestione del caso iniziale è una tipica fonte di errori, anche all'esame.
Il salto condizionato avviene solo se una condizione è vera: "se i = n salta alla riga 7" (V6, riga 3). Nel diagramma è l'uscita SÌ del rombo verso Fine. Il salto non condizionato avviene sempre: "salta alla riga 3" (V6, riga 6). Nel diagramma è la freccia che dal blocco delle somme torna al rombo.
Perché la moltiplicazione potrebbe essere solo una parte di un algoritmo più grande, dopo la quale vogliamo eseguire altre istruzioni. Invece di "l'algoritmo termina" si salta alla fine del blocco (istruzione Fine) e l'esecuzione prosegue.
Delimitano i blocchi, che possono essere annidati uno dentro l'altro. Grazie alla struttura i salti possono riferirsi all'inizio o alla fine di un blocco, così i numeri di riga non servono più. L'indentazione rende visibile la gerarchia dei blocchi e a quale blocco appartiene ogni istruzione. È l'idea dei linguaggi strutturati.
Il diagramma di flusso mostra graficamente il flusso di controllo (le possibili sequenze di esecuzione) seguendo i collegamenti tra le istruzioni, ma non rende esplicito l'annidamento dei blocchi. La rappresentazione strutturata organizza le istruzioni in blocchi annidati. I linguaggi moderni preferiscono la seconda.
Quelli di basso livello sono vicini alla macchina (linguaggio macchina, assembly). Quelli di alto livello sono più vicini al linguaggio naturale (FORTRAN, C, Java, Python).
In Programmazione I si impara a implementare algoritmi elementari in C, cioè a tradurre in C algoritmi specificati in italiano. Nell'esame di Algoritmi lo scopo sarà analizzare e progettare nuovi algoritmi. Il modello di calcolo di riferimento è la macchina di Von Neumann.
s ← s + m. In C si scrive =.i = n. In C si scrive ==.s).i).Spunta quando sai fare la cosa senza guardare gli appunti. Le spunte restano salvate in questo browser.