Algoritmi e Principi dell'Informatica: esercizi risolti e commentati

di Alessandro Barenghi, Davide Martinenghi, Matteo Pradella, Matteo Rossi

Errata corrige (aggiornato al 3/8/2023)

Capitolo 1

Esercizio 1.14, punto 2 (segnalato l'11/3/2023): il linguaggio indicato si può ovviamente riconoscere anche con un automa a pila deterministico, come mostrato qui.
Esercizio 1.15 (segnalato il 26/3/2023): le prime tre produzioni della prima grammatica mostrata (S → A | B | C) non sono formalmente consentite in una grammatica regolare. Basta sostituirle con S → tB | dD | dL (e a questo punto si può eliminare la produzione C → dL, dal momento che C non è più usato).
Esercizio 1.24 (segnalato il 18/3/2023): l'automa mostrato non accetta la stringa c. Occorre aggiungere un altro stato (di accettazione), come mostrato qui.
Esercizio 1.29 (segnalato il 15/4/2023): nella soluzione del punto 4, la quantificazione universale di y è un refuso e può essere eliminata.
Esercizio 1.32 (segnalato il 15/4/2023): nel testo del primo punto sostituire "modelli a potenza minima" con "modelli di automa a potenza minima". Infatti il linguaggio L₂ può anche essere caratterizzato da una formula MFO.

Capitolo 2

Esercizio 2.4 (segnalato il 31/3/2023): nella macchina M' tutte le occorrenze del simbolo blank vanno sostituite con il simbolo a, come mostrato qui.
Esercizio 2.5 (segnalato il 2/4/2023): nella macchina M' la transizione dallo stato iniziale a quello finale deve avvenire anche in corrispondenza del simbolo blank, come mostrato qui.
Esercizio 2.16 (segnalato il 15/4/2023): nella soluzione, sostituire "se lo sono, ne restituisce il valore" con "se lo sono, calcola f_y(x) e ne restituisce il valore".
Esercizio 2.24 (segnalato il 16/4/2023): nel testo del punto 1 vanno eliminate le parole "dell'insieme considerato".
Esercizio 2.26 (segnalato il 12/4/2023): la soluzione proposta per il punto 3 assume implicitamente che siano totali sia la funzione del generatore di test, sia la funzione del generico studente. Senza quest'assunzione ci troviamo di fatto di fronte al problema dell'equivalenza tra funzioni, che comunque non è semidecidibile (ma nemmeno il suo complemento lo è).
Esercizio 2.30 (segnalato il 12/4/2023): nella soluzione del punto 3, le parole "non appartenessero all'insieme di definizione delle rispettive funzioni o" sono un refuso e vanno rimosse.
Esercizio 2.30 (segnalato il 19/4/2023): nella soluzione del punto 3, nella formula di d(x,y) il "+1" va sostituito con "+x".
Esercizio 2.32 (segnalato il 15/4/2023): nella soluzione del punto 1, sostituire "che infatti associa ad ogni stringa in ingresso un 1 o uno 0 a seconda che la stringa venga accettata o meno" con "che infatti associa ad ogni stringa in ingresso un 1 oppure non termina a seconda che la stringa venga accettata o meno".
Esercizio 2.37 (segnalato il 16/4/2023): nel testo del punto 2 va sostituito M₂ con M².

Capitolo 3

Esercizio 3.1 (segnalato il 28/4/2023): nel testo dell'esercizio, nelle funzioni P1, P2 e P3, dopo l'istruzione Stampa(n) va inserita anche una return:
```
if n < 1
    Stampa(n)
    return
...
```
Esercizio 3.2 (segnalato il 17/5/2023): nella soluzione, nella seconda riga dell'espansione di T(n), il termine -32 va sostituito con -32b. Il resto dei calcoli va corretto di conseguenza.
Esercizio 3.2: Alla fine della soluzione, aggiungere la frase "Si possono effettuare verifiche analoghe per i casi n=17, 18, 19."
Esercizio 3.5 (segnalato il 15/5/2023): nella prima riga del codice, sostituire: if (n<5) con if (n<3).
Esercizio 3.7 (segnalato l'1/5/2023): nella soluzione, sostituire: "verificata già per c=1" con "verificata ad esempio per c=9/10 e n≥3".
Esercizio 3.11 (segnalato il 9/5/2023): nella soluzione, nel paragrafo che inizia con "Si noti che" sotto l'albero di ricorsione, tutte le sommatorie devono avere indice i (e non k) e gli esponenti di 4, 8 e 16 devono essere i (e non k).
Esercizio 3.11 (segnalato il 18/5/2023): nella soluzione, nell'albero di ricorsione, il terzo livello dev'essere popolato dai termini n²/4², n²/4³, n²/4⁴, ..., n²/4^k+1 al posto di n²/8, n²/8², n²/8³, ..., n²/8^k.
Esercizio 3.13 (segnalato il 22/4/2023): nel primo frammento di codice del punto 2, l'istruzione sum := sum + j dev'essere soggetta a if j mod i = 0. Complessivamente, il codice di tale frammento è:
```
for i := 1 to n
    j := i
    while j <= i * i
        if j mod i = 0
            sum := sum + j
        j := j + 1
```
Esercizio 3.13 (segnalato il 7/5/2023): nella soluzione del punto 2 a pagina 90, sostituire "che ha complessità" con "Il valore di cui viene incrementata la variabile sum alla fine di ogni esecuzione del ciclo interno è" e sostituire "come già calcolato in (3.1)" con "applicando la formula (3.1)".
Esercizio 3.16 (segnalato il 19/5/2023): nella soluzione del punto 3, nella terzultima riga, dopo "equivalentemente," aggiungere "assumendo che nella scrittura log(n) la base dei logaritmi sia 2".

Capitolo 4

Esercizio 4.2 (segnalato il 23/4/2023): nel secondo paragrafo della soluzione, sostituire "una a se in ingresso legge una b, e una b se in ingresso legge una a" con "il simbolo letto dall'ingresso".
Esercizio 4.3 (segnalato l'11/6/2023): è possibile ottenere una complessità spaziale di Θ(log n) se si utilizza un contatore binario al posto di un contatore unario.
Esercizio 4.4 (segnalato l'11/5/2023): nella penultima frase del testo, sostituire "se ne studino le complessità spaziali e temporali" con "se ne studino le complessità spaziali e temporali nel caso di accettazione della stringa in ingresso".
Esercizio 4.4 (segnalato il 15/6/2023): è possibile ottenere una complessità spaziale di Θ(log n) se si utilizzano dei contatori binari al posto di contatori unari.
Esercizio 4.5 (segnalato il 29/4/2023): nella prima frase dell'ultimo paragrafo della soluzione, sostituire "riducendo di un quinto" con "riducendo a un quinto".
Esercizio 4.9 (segnalato il 29/4/2023): nella prima frase della soluzione, sostituire "cifre meno significative a sinistra" con "cifre meno significative a destra".
Esercizio 4.10 (segnalato il 29/4/2023): nella seconda riga di pagina 105, nella produttoria, sostituire il pedice "i=j" con "j=0".
Esercizio 4.10 (segnalato il 20/6/2023): la complessità temporale complessiva, a costo logaritmico, ottenuta con il secondo metodo è comunque Θ(n²), se si assume che il costo della moltiplicazione sia proporzionale al prodotto del numero di cifre degli operandi.
Esercizio 4.12 (segnalato il 30/4/2023): nella prima frase della soluzione, sostituire "2 nastri" con "1 nastro".
Esercizio 4.12 (segnalato il 30/4/2023): alla fine del primo paragrafo del punto 1 della soluzione, sostituire "ha costo Θ(log₂(n))" con "ha costo Θ(log₂(2ⁿ))=Θ(n)".
Esercizio 4.13 (segnalato il 19/5/2023): nella soluzione, sostituire "un automa a stati finiti per accettare il linguaggio, che si fermerà al più dopo 36 mosse" con "un automa a stati finiti per accettare il linguaggio. La MT si fermerà al più dopo 36 mosse".
Esercizio 4.19 (segnalato il 2/5/2023): nella soluzione, alla fine della prima frase sotto la prima macchina di Turing, sostituire "la lunghezza di y sia dispari" con "la lunghezza di y sia pari".
Esercizio 4.19 (segnalato il 2/5/2023): nella soluzione, seconda frase sotto la seconda macchina di Turing, sostituire "il primo simbolo di y che non è X" con "il simbolo più a destra in y che non è X".
Esercizio 4.19 (segnalato il 6/6/2023): con la macchina di Turing a k nastri e senza il vincolo (ii) si può ottenere una complessità spaziale di Θ(log n) facendo uso di un contatore binario nel nastro di memoria, incrementandolo durante la lettura di x e decrementandolo durante la lettura di y.
Esercizio 4.21 (segnalato il 18/5/2023): con una diversa strategia rispetto a quella presentata nella soluzione, nel punto 1 si può ottenere una complessità spaziale di O(n^1/2 log n) e temporale di O(n log n).
Esercizio 4.21 (segnalato il 30/6/2023): con una diversa strategia rispetto a quella presentata nella soluzione, nel punto 1 si può ottenere una complessità spaziale e temporale di O(n).

Capitolo 5

Esercizio 5.1: nelle righe 2 e 3 di SottoArray(A), sostituire 0 con 1 e nella riga 11 sostituire < con ≤.
Esercizio 5.1 (segnalato il 13/5/2023): con un algoritmo più complesso, è in realtà possibile abbassare la complessità a O(n).
Esercizio 5.2 (segnalato il 5/5/2023): con un algoritmo più complesso, è in realtà possibile abbassare la complessità a O(n² log n).
Esercizio 5.2 (segnalato il 7/6/2023): nel primo paragrafo della soluzione, sostituire n² con Θ(n²), per quanto riguarda il numero di sottoarray.
Esercizio 5.3 (segnalato il 31/5/2023): nel codice della soluzione, si assume che l'allocazione dei vettori li inizializzi con elementi posti a 0.
Esercizio 5.4 (segnalato il 23/5/2023): nella soluzione, alla riga 3 dell'algoritmo CERCACOPPIA-LINEARE, sostituire (j < A.length) con (j ≤ A.length)
Esercizio 5.7 (segnalato il 20/5/2023): nella soluzione, alla riga 9 di FINDSUM, occorre aggiungere una if che controlli che j sia diverso da NIL prima di accedere a j.key.
Esercizio 5.8 (segnalato il 20/5/2023): nella soluzione, alla riga 1 dell'algoritmo sostituire d:=0 con d:=1, alla riga 3 sostituire il + con un * e alla riga 4 sostituire il false con d.
Esercizio 5.8 (segnalazioni varie): nella soluzione, la complessità con il criterio di costo logaritmico è O(n²), poiché il ciclo alla riga 2 viene eseguito n volte e la moltiplicazione più onerosa, quella nell'ultima iterazione, effettua il prodotto di un numero di O(n) cifre per uno con un numero costante di cifre.
Esercizio 5.10 (segnalato il 10/5/2023): nei primi due paragrafi del testo, sostituire "tra 0 e n-1" con "tra 1 e n" (due volte).
Esercizio 5.11 (segnalato il 9/5/2023): nella riga 7 dello pseudocodice, sostituire "n" con "S.length+1".
Esercizio 5.11 (segnalato il 20/6/2023): nella seconda frase della soluzione, sostituire "dall'inizio se l'indice è pari e dalla fine se è dispari" con "dall'inizio se l'indice è dispari e dalla fine se è pari". Nella dimostrazione, sostituire "possiamo costruire una procedura che ordina S in ordine decrescente come segue" con "possiamo costruire una procedura che ordina S in ordine crescente come segue".
Esercizio 5.13 (segnalato il 15/6/2023): nel punto 1 della soluzione, per usare il nuovo pivot A[(r+p)/2] occorre semplicemente effettuare una swap(A[(r+p)/2],A[r]) prima della riga 1 di Partition.
Esercizio 5.18: nella soluzione, alla riga 2 di TrovaSottoAlberi, il primo parametro passato a VisitaERiconosci deve essere T.root anziché T.
Esercizio 5.18: nel testo, nella terza frase, sostituire "i sottoalberi più grandi" con "i sottoalberi più grandi (con almeno un nodo)".
Esercizio 5.18 (segnalato il 27/5/2023): nella soluzione, la condizione alla riga 6 di VisitaERiconosci è incompleta e va sostituita con la negazione di ta, che dev'essere quindi definito prima, come mostrato qui.
Esercizio 5.23 (segnalato il 24/5/2023): nelle righe 1 e 2 di TREE-MINIMUM, sostituire right con left.
Esercizio 5.28 (segnalato il 30/5/2023): il codice dev'essere come mostrato qui, ovvero alla riga 9 occorre tenere conto dei valori di ok_l e ok_r; inoltre, per poter usare T.nil, va passato l'albero T.
Esercizio 5.30 (segnalazioni varie): l'albero del punto 1.a dev'essere come mostrato qui.
Esercizio 5.30 (segnalato il 31/5/2023): nella soluzione del punto 2.a, il codice dev'essere come mostrato qui. La modifica consiste quindi nell'aggiunta delle righe 5 e 6.
Esercizio 5.32 (segnalato il 30/5/2023): nel testo del punto 2, sostituire "determina un percorso" con "determina un percorso non vuoto". Nella soluzione del punto 2, alla fine della seconda frase, aggiungere "purché si attraversino almeno due incroci oltre a quello iniziale". Sostituire poi "v coincide con il nodo di partenza s" con "v coincide con il nodo di partenza s e la lunghezza del percorso è maggiore di 2".
Esercizio 5.37 (segnalato il 30/5/2023): con una diversa soluzione, che gestisce l'insieme A come un min-heap a cui viene applicato HeapSort solo per k iterazioni, si ottiene una complessità di O(n + k log(n)).
Esercizio 5.37 (segnalato il 24/6/2023): con una diversa soluzione, che sfrutta un noto algoritmo per selezionare la k-esima statistica d'ordine in tempo lineare, è possibile portare la complessità a O(n + k log(k)).