Esercizi · Algoritmi numerici

Esercizi · Capitolo 5 · ogni soluzione si apre con un clic · Capitolo 5: Algoritmi numerici · Eserciziario, volume 1 (PDF)

Gli esercizi di questo capitolo applicano i quattro algoritmi del capitolo «Algoritmi numerici»: ChangeOfBase, BasicPrimalityTest e PrimalityTest, SieveOfEratosthenes, EuclideanAlgorithm. Nelle soluzioni si usano i seguenti fatti del capitolo.

Divisione con resto. Per ogni numero naturale \(n\) e ogni numero naturale \(b \ge 1\):

\[ n = \lfloor n/b \rfloor \; b + (n \bmod b) \qquad \text{con} \qquad 0 \le n \bmod b < b . \]

Cambio di base. Se \(n = (d_{k-1} \dots d_1 d_0)_b\), allora \(n \bmod b = d_0\) e \(\lfloor n/b \rfloor = (d_{k-1} \dots d_1)_b\); il numero di cifre è \(\lfloor \log_b n \rfloor + 1\). ChangeOfBase memorizza la cifra \(d_{k-1}\) nell'elemento \(d[k]\).

Primalità. Un numero naturale \(n \ge 2\) è primo se e solo se nessun numero naturale in \(\{2, 3, \dots, \lfloor \sqrt{n} \rfloor\}\) è un divisore di \(n\).

Crivello. La marcatura dei multipli di un primo \(p\) parte da \(p^2\), e il ciclo esterno si ferma a \(\lfloor \sqrt{n} \rfloor\). Nelle tabelle di esecuzione le celle blu sono gli elementi appena posti a \(0\) e le celle rosse il valore corrente di \(p\).

Massimo comun divisore. Per ogni coppia di numeri naturali \(n, m \ge 1\):

\[ \gcd(n, m) = \gcd(m,\ n \bmod m) \qquad \text{e} \qquad \gcd(n, 0) = n . \]

Due numeri naturali sono coprimi se e solo se il loro massimo comun divisore è \(1\).

Esercizio 5.1: Algoritmi numerici (E1)

Consideriamo il seguente numero naturale, scritto come sequenza di cifre in base dieci:

\[ (16)_{10} \]

Domande

1. Convertire il numero in base \(b=2\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

2. Convertire il numero in base \(b=3\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

3. Convertire il numero in base \(b=4\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

4. Convertire il numero in base \(b=5\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

5. Convertire il numero in base \(b=6\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

Soluzione

1. Conversione di \(16\) in base \(b=2\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(16\)	\(16/2\)	\(8\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(8\)	\(8/2\)	\(4\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/2\)	\(2\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(2\)	\(2/2\)	\(1\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (più significativa)

   Quindi \(16\) in base \(2\) è \((10000)_{2}\), con \(nd = \lfloor \log_{2} 16 \rfloor + 1 = 5\) cifre.

2. Conversione di \(16\) in base \(b=3\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(16\)	\(16/3\)	\(5\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(5\)	\(5/3\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(16\) in base \(3\) è \((121)_{3}\), con \(nd = \lfloor \log_{3} 16 \rfloor + 1 = 3\) cifre.

3. Conversione di \(16\) in base \(b=4\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(16\)	\(16/4\)	\(4\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(4\)	\(4/4\)	\(1\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/4\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(16\) in base \(4\) è \((100)_{4}\), con \(nd = \lfloor \log_{4} 16 \rfloor + 1 = 3\) cifre.

4. Conversione di \(16\) in base \(b=5\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(16\)	\(16/5\)	\(3\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(3\)	\(3/5\)	\(0\)	\(3\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(16\) in base \(5\) è \((31)_{5}\), con \(nd = \lfloor \log_{5} 16 \rfloor + 1 = 2\) cifre.

5. Conversione di \(16\) in base \(b=6\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(16\)	\(16/6\)	\(2\)	\(4\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(2\)	\(2/6\)	\(0\)	\(2\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(16\) in base \(6\) è \((24)_{6}\), con \(nd = \lfloor \log_{6} 16 \rfloor + 1 = 2\) cifre.

Esercizio 5.2: Algoritmi numerici (E2)

Consideriamo il seguente numero naturale, scritto come sequenza di cifre in base dieci:

\[ (25)_{10} \]

Domande

1. Convertire il numero in base \(b=2\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

2. Convertire il numero in base \(b=3\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

3. Convertire il numero in base \(b=4\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

4. Convertire il numero in base \(b=5\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

5. Convertire il numero in base \(b=7\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

Soluzione

1. Conversione di \(25\) in base \(b=2\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(25\)	\(25/2\)	\(12\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(12\)	\(12/2\)	\(6\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(6\)	\(6/2\)	\(3\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (più significativa)

   Quindi \(25\) in base \(2\) è \((11001)_{2}\), con \(nd = \lfloor \log_{2} 25 \rfloor + 1 = 5\) cifre.

2. Conversione di \(25\) in base \(b=3\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(25\)	\(25/3\)	\(8\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(8\)	\(8/3\)	\(2\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(2\)	\(2/3\)	\(0\)	\(2\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(25\) in base \(3\) è \((221)_{3}\), con \(nd = \lfloor \log_{3} 25 \rfloor + 1 = 3\) cifre.

3. Conversione di \(25\) in base \(b=4\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(25\)	\(25/4\)	\(6\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(6\)	\(6/4\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/4\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(25\) in base \(4\) è \((121)_{4}\), con \(nd = \lfloor \log_{4} 25 \rfloor + 1 = 3\) cifre.

4. Conversione di \(25\) in base \(b=5\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(25\)	\(25/5\)	\(5\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(5\)	\(5/5\)	\(1\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/5\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(25\) in base \(5\) è \((100)_{5}\), con \(nd = \lfloor \log_{5} 25 \rfloor + 1 = 3\) cifre.

5. Conversione di \(25\) in base \(b=7\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(25\)	\(25/7\)	\(3\)	\(4\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(3\)	\(3/7\)	\(0\)	\(3\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(25\) in base \(7\) è \((34)_{7}\), con \(nd = \lfloor \log_{7} 25 \rfloor + 1 = 2\) cifre.

Esercizio 5.3: Algoritmi numerici (E3)

Consideriamo il seguente numero naturale, scritto come sequenza di cifre in base dieci:

\[ (42)_{10} \]

Domande

1. Convertire il numero in base \(b=2\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

2. Convertire il numero in base \(b=3\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

3. Convertire il numero in base \(b=5\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

4. Convertire il numero in base \(b=6\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

5. Convertire il numero in base \(b=8\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

Soluzione

1. Conversione di \(42\) in base \(b=2\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(42\)	\(42/2\)	\(21\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(21\)	\(21/2\)	\(10\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(10\)	\(10/2\)	\(5\)	\(0\)	\(d[3] = d_{2}\)
   \(4\)	\(5\)	\(5/2\)	\(2\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(2\)	\(2/2\)	\(1\)	\(0\)	\(d[5] = d_{4}\)
   \(6\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[6] = d_{5}\) (più significativa)

   Quindi \(42\) in base \(2\) è \((101010)_{2}\), con \(nd = \lfloor \log_{2} 42 \rfloor + 1 = 6\) cifre.

2. Conversione di \(42\) in base \(b=3\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(42\)	\(42/3\)	\(14\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(14\)	\(14/3\)	\(4\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/3\)	\(1\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[4] = d_{3}\) (più significativa)

   Quindi \(42\) in base \(3\) è \((1120)_{3}\), con \(nd = \lfloor \log_{3} 42 \rfloor + 1 = 4\) cifre.

3. Conversione di \(42\) in base \(b=5\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(42\)	\(42/5\)	\(8\)	\(2\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(8\)	\(8/5\)	\(1\)	\(3\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/5\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(42\) in base \(5\) è \((132)_{5}\), con \(nd = \lfloor \log_{5} 42 \rfloor + 1 = 3\) cifre.

4. Conversione di \(42\) in base \(b=6\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(42\)	\(42/6\)	\(7\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(7\)	\(7/6\)	\(1\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/6\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(42\) in base \(6\) è \((110)_{6}\), con \(nd = \lfloor \log_{6} 42 \rfloor + 1 = 3\) cifre.

5. Conversione di \(42\) in base \(b=8\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(42\)	\(42/8\)	\(5\)	\(2\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(5\)	\(5/8\)	\(0\)	\(5\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(42\) in base \(8\) è \((52)_{8}\), con \(nd = \lfloor \log_{8} 42 \rfloor + 1 = 2\) cifre.

Esercizio 5.4: Algoritmi numerici (E4)

Consideriamo il seguente numero naturale, scritto come sequenza di cifre in base dieci:

\[ (63)_{10} \]

Domande

1. Convertire il numero in base \(b=2\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

2. Convertire il numero in base \(b=4\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

3. Convertire il numero in base \(b=7\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

4. Convertire il numero in base \(b=8\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

5. Convertire il numero in base \(b=9\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

Soluzione

1. Conversione di \(63\) in base \(b=2\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(63\)	\(63/2\)	\(31\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(31\)	\(31/2\)	\(15\)	\(1\)	\(d[2] = d_{1}\)
   \(3\)	\(15\)	\(15/2\)	\(7\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(7\)	\(7/2\)	\(3\)	\(1\)	\(d[4] = d_{3}\)
   \(5\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[5] = d_{4}\)
   \(6\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[6] = d_{5}\) (più significativa)

   Quindi \(63\) in base \(2\) è \((111111)_{2}\), con \(nd = \lfloor \log_{2} 63 \rfloor + 1 = 6\) cifre.

2. Conversione di \(63\) in base \(b=4\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(63\)	\(63/4\)	\(15\)	\(3\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(15\)	\(15/4\)	\(3\)	\(3\)	\(d[2] = d_{1}\)
   \(3\)	\(3\)	\(3/4\)	\(0\)	\(3\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(63\) in base \(4\) è \((333)_{4}\), con \(nd = \lfloor \log_{4} 63 \rfloor + 1 = 3\) cifre.

3. Conversione di \(63\) in base \(b=7\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(63\)	\(63/7\)	\(9\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(9\)	\(9/7\)	\(1\)	\(2\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/7\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(63\) in base \(7\) è \((120)_{7}\), con \(nd = \lfloor \log_{7} 63 \rfloor + 1 = 3\) cifre.

4. Conversione di \(63\) in base \(b=8\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(63\)	\(63/8\)	\(7\)	\(7\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(7\)	\(7/8\)	\(0\)	\(7\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(63\) in base \(8\) è \((77)_{8}\), con \(nd = \lfloor \log_{8} 63 \rfloor + 1 = 2\) cifre.

5. Conversione di \(63\) in base \(b=9\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(63\)	\(63/9\)	\(7\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(7\)	\(7/9\)	\(0\)	\(7\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(63\) in base \(9\) è \((70)_{9}\), con \(nd = \lfloor \log_{9} 63 \rfloor + 1 = 2\) cifre.

Esercizio 5.5: Algoritmi numerici (E5)

Consideriamo il seguente numero naturale, scritto come sequenza di cifre in base dieci:

\[ (100)_{10} \]

Domande

1. Convertire il numero in base \(b=2\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

2. Convertire il numero in base \(b=3\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

3. Convertire il numero in base \(b=5\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

4. Convertire il numero in base \(b=8\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

5. Convertire il numero in base \(b=16\) con l'algoritmo ChangeOfBase, mostrando il quoziente e il resto di ogni divisione.

Soluzione

1. Conversione di \(100\) in base \(b=2\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(100\)	\(100/2\)	\(50\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(50\)	\(50/2\)	\(25\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(25\)	\(25/2\)	\(12\)	\(1\)	\(d[3] = d_{2}\)
   \(4\)	\(12\)	\(12/2\)	\(6\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(6\)	\(6/2\)	\(3\)	\(0\)	\(d[5] = d_{4}\)
   \(6\)	\(3\)	\(3/2\)	\(1\)	\(1\)	\(d[6] = d_{5}\)
   \(7\)	\(1\)	\(1/2\)	\(0\)	\(1\)	\(d[7] = d_{6}\) (più significativa)

   Quindi \(100\) in base \(2\) è \((1100100)_{2}\), con \(nd = \lfloor \log_{2} 100 \rfloor + 1 = 7\) cifre.

2. Conversione di \(100\) in base \(b=3\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(100\)	\(100/3\)	\(33\)	\(1\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(33\)	\(33/3\)	\(11\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(11\)	\(11/3\)	\(3\)	\(2\)	\(d[3] = d_{2}\)
   \(4\)	\(3\)	\(3/3\)	\(1\)	\(0\)	\(d[4] = d_{3}\)
   \(5\)	\(1\)	\(1/3\)	\(0\)	\(1\)	\(d[5] = d_{4}\) (più significativa)

   Quindi \(100\) in base \(3\) è \((10201)_{3}\), con \(nd = \lfloor \log_{3} 100 \rfloor + 1 = 5\) cifre.

3. Conversione di \(100\) in base \(b=5\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(100\)	\(100/5\)	\(20\)	\(0\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(20\)	\(20/5\)	\(4\)	\(0\)	\(d[2] = d_{1}\)
   \(3\)	\(4\)	\(4/5\)	\(0\)	\(4\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(100\) in base \(5\) è \((400)_{5}\), con \(nd = \lfloor \log_{5} 100 \rfloor + 1 = 3\) cifre.

4. Conversione di \(100\) in base \(b=8\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(100\)	\(100/8\)	\(12\)	\(4\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(12\)	\(12/8\)	\(1\)	\(4\)	\(d[2] = d_{1}\)
   \(3\)	\(1\)	\(1/8\)	\(0\)	\(1\)	\(d[3] = d_{2}\) (più significativa)

   Quindi \(100\) in base \(8\) è \((144)_{8}\), con \(nd = \lfloor \log_{8} 100 \rfloor + 1 = 3\) cifre.

5. Conversione di \(100\) in base \(b=16\):

   iterazione \(k\)	\(n\)	\(n/b\)	\(q\)	\(r\)	cifra
   \(1\)	\(100\)	\(100/16\)	\(6\)	\(4\)	\(d[1] = d_{0}\) (meno significativa)
   \(2\)	\(6\)	\(6/16\)	\(0\)	\(6\)	\(d[2] = d_{1}\) (più significativa)

   Quindi \(100\) in base \(16\) è \((64)_{16}\), con \(nd = \lfloor \log_{16} 100 \rfloor + 1 = 2\) cifre.

Esercizio 5.6: Algoritmi numerici (E6)

Consideriamo i seguenti numeri naturali:

\[ n \in \{2,\ 7,\ 9,\ 11,\ 25\} \]

Domande

1. Applicare l'algoritmo PrimalityTest a ciascun numero della lista. Per ogni \(n\) mostrare l'esecuzione passo per passo, indicando il valore di \(\lfloor\sqrt{n}\rfloor\), i valori di \(d\) provati e il risultato di ciascun test \(n \bmod d = 0\).

Soluzione

1. Esecuzione di PrimalityTest su ciascun numero.

   Verifica \(n = 2\): \(\lfloor\sqrt{2}\rfloor = 1\).

   \(d\)	\(2 \bmod d\)	azione
   Il ciclo non viene eseguito, poiché \(2 > 1\).
   Restituisce true: 2 è primo.

   Verifica \(n = 7\): \(\lfloor\sqrt{7}\rfloor = 2\).

   \(d\)	\(7 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 7 è primo.

   Verifica \(n = 9\): \(\lfloor\sqrt{9}\rfloor = 3\).

   \(d\)	\(9 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(0\)	restituisce false
   9 non è primo (\(9 = 3 \cdot 3\)).

   Verifica \(n = 11\): \(\lfloor\sqrt{11}\rfloor = 3\).

   \(d\)	\(11 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 11 è primo.

   Verifica \(n = 25\): \(\lfloor\sqrt{25}\rfloor = 5\).

   \(d\)	\(25 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(0\)	restituisce false
   25 non è primo (\(25 = 5 \cdot 5\)).

Esercizio 5.7: Algoritmi numerici (E7)

Consideriamo i seguenti numeri naturali:

\[ n \in \{4,\ 13,\ 17,\ 49,\ 97\} \]

Domande

1. Applicare l'algoritmo PrimalityTest a ciascun numero della lista. Per ogni \(n\) mostrare l'esecuzione passo per passo, indicando il valore di \(\lfloor\sqrt{n}\rfloor\), i valori di \(d\) provati e il risultato di ciascun test \(n \bmod d = 0\).

Soluzione

1. Esecuzione di PrimalityTest su ciascun numero.

   Verifica \(n = 4\): \(\lfloor\sqrt{4}\rfloor = 2\).

   \(d\)	\(4 \bmod d\)	azione
   \(2\)	\(0\)	restituisce false
   4 non è primo (\(4 = 2 \cdot 2\)).

   Verifica \(n = 13\): \(\lfloor\sqrt{13}\rfloor = 3\).

   \(d\)	\(13 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 13 è primo.

   Verifica \(n = 17\): \(\lfloor\sqrt{17}\rfloor = 4\).

   \(d\)	\(17 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 17 è primo.

   Verifica \(n = 49\): \(\lfloor\sqrt{49}\rfloor = 7\).

   \(d\)	\(49 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(0\)	restituisce false
   49 non è primo (\(49 = 7 \cdot 7\)).

   Verifica \(n = 97\): \(\lfloor\sqrt{97}\rfloor = 9\).

   \(d\)	\(97 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(2 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(6 \ne 0\)	continua
   \(8\)	\(1 \ne 0\)	continua
   \(9\)	\(7 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 97 è primo.

Esercizio 5.8: Algoritmi numerici (E8)

Consideriamo i seguenti numeri naturali:

\[ n \in \{1,\ 3,\ 15,\ 23,\ 36\} \]

Domande

1. Applicare l'algoritmo PrimalityTest a ciascun numero della lista. Per ogni \(n\) mostrare l'esecuzione passo per passo, indicando il valore di \(\lfloor\sqrt{n}\rfloor\), i valori di \(d\) provati e il risultato di ciascun test \(n \bmod d = 0\).

Soluzione

1. Esecuzione di PrimalityTest su ciascun numero.

   Verifica \(n = 1\): \(n < 2\).

   \(d\)	\(1 \bmod d\)	azione
   \(n = 1 < 2\): restituisce false immediately.
   1 non è primo.

   Verifica \(n = 3\): \(\lfloor\sqrt{3}\rfloor = 1\).

   \(d\)	\(3 \bmod d\)	azione
   Il ciclo non viene eseguito, poiché \(2 > 1\).
   Restituisce true: 3 è primo.

   Verifica \(n = 15\): \(\lfloor\sqrt{15}\rfloor = 3\).

   \(d\)	\(15 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(0\)	restituisce false
   15 non è primo (\(15 = 3 \cdot 5\)).

   Verifica \(n = 23\): \(\lfloor\sqrt{23}\rfloor = 4\).

   \(d\)	\(23 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   \(4\)	\(3 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 23 è primo.

   Verifica \(n = 36\): \(\lfloor\sqrt{36}\rfloor = 6\).

   \(d\)	\(36 \bmod d\)	azione
   \(2\)	\(0\)	restituisce false
   36 non è primo (\(36 = 2 \cdot 18\)).

Esercizio 5.9: Algoritmi numerici (E9)

Consideriamo i numeri naturali \(n = 29\) e \(n = 49\).

Domande

1. Per ciascun numero \(n\), applicare sia l'algoritmo BasicPrimalityTest (ciclo fino a \(\lfloor n/2 \rfloor\)) sia l'algoritmo PrimalityTest (ciclo fino a \(\lfloor\sqrt{n}\rfloor\)). Mostrare l'esecuzione passo per passo di ciascun algoritmo.

2. Per ciascun numero, contare il numero di iterazioni eseguite da ciascun algoritmo e confrontarle.

Soluzione

1. Esecuzione passo per passo.

   Caso \(n = 29\).

   BasicPrimalityTest (\(\lfloor 29/2 \rfloor = 14\)):

   \(d\)	\(29 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   \(6\)	\(5 \ne 0\)	continua
   \(7\)	\(1 \ne 0\)	continua
   \(8\)	\(5 \ne 0\)	continua
   \(9\)	\(2 \ne 0\)	continua
   \(10\)	\(9 \ne 0\)	continua
   \(11\)	\(7 \ne 0\)	continua
   \(12\)	\(5 \ne 0\)	continua
   \(13\)	\(3 \ne 0\)	continua
   \(14\)	\(1 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 29 è primo. (13 iterazioni)

   PrimalityTest (\(\lfloor\sqrt{29}\rfloor = 5\)):

   \(d\)	\(29 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 29 è primo. (4 iterazioni)

   Caso \(n = 49\).

   BasicPrimalityTest (\(\lfloor 49/2 \rfloor = 24\)):

   \(d\)	\(49 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(0\)	restituisce false
   49 non è primo (\(49 = 7 \cdot 7\)). (6 iterazioni)

   PrimalityTest (\(\lfloor\sqrt{49}\rfloor = 7\)):

   \(d\)	\(49 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(0\)	restituisce false
   49 non è primo (\(49 = 7 \cdot 7\)). (6 iterazioni)

2. Confronto delle iterazioni:

   \(n\)	\(\lfloor n/2 \rfloor\)	\(\lfloor\sqrt{n}\rfloor\)	BasicPrimalityTest	PrimalityTest
   \(29\)	\(14\)	\(5\)	\(13\)	\(4\)
   \(49\)	\(24\)	\(7\)	\(6\)	\(6\)

   Per \(n = 29\) (primo), PrimalityTest esegue solo \(4\) iterazioni invece di \(13\): entrambi gli algoritmi devono provare tutti i loro candidati, e PrimalityTest ne ha molti meno. Per \(n = 49\) (composto, con il più piccolo divisore \(7 = \sqrt{49}\)), entrambi gli algoritmi si fermano allo stesso divisore \(d = 7\), quindi il numero di iterazioni è lo stesso.

Esercizio 5.10: Algoritmi numerici (E10)

Consideriamo i numeri naturali \(n \in \{2, 3, 4, \dots, 30\}\).

Domande

1. Applicare l'algoritmo PrimalityTest a ciascun numero naturale \(n \in \{2, 3, \dots, 30\}\) e determinare quali numeri sono primi. Per ogni \(n\) riportare il valore di \(\lfloor\sqrt{n}\rfloor\), se è stato trovato un divisore (e quale) e il risultato.

2. Elencare tutti i numeri primi in \(\{2, 3, \dots, 30\}\) e contarli.

Soluzione

1. Riepilogo delle esecuzioni di PrimalityTest (il divisore riportato è il primo trovato, cioè il valore di \(d\) per cui la funzione restituisce false):

   \(n\)	\(\lfloor\sqrt{n}\rfloor\)	primo divisore trovato	risultato
   \(2\)	\(1\)	nessuno (ciclo non eseguito)	primo
   \(3\)	\(1\)	nessuno (ciclo non eseguito)	primo
   \(4\)	\(2\)	\(d = 2\)	non primo (\(4 = 2 \cdot 2\))
   \(5\)	\(2\)	nessuno	primo
   \(6\)	\(2\)	\(d = 2\)	non primo (\(6 = 2 \cdot 3\))
   \(7\)	\(2\)	nessuno	primo
   \(8\)	\(2\)	\(d = 2\)	non primo (\(8 = 2 \cdot 4\))
   \(9\)	\(3\)	\(d = 3\)	non primo (\(9 = 3 \cdot 3\))
   \(10\)	\(3\)	\(d = 2\)	non primo (\(10 = 2 \cdot 5\))
   \(11\)	\(3\)	nessuno	primo
   \(12\)	\(3\)	\(d = 2\)	non primo (\(12 = 2 \cdot 6\))
   \(13\)	\(3\)	nessuno	primo
   \(14\)	\(3\)	\(d = 2\)	non primo (\(14 = 2 \cdot 7\))
   \(15\)	\(3\)	\(d = 3\)	non primo (\(15 = 3 \cdot 5\))
   \(16\)	\(4\)	\(d = 2\)	non primo (\(16 = 2 \cdot 8\))
   \(17\)	\(4\)	nessuno	primo
   \(18\)	\(4\)	\(d = 2\)	non primo (\(18 = 2 \cdot 9\))
   \(19\)	\(4\)	nessuno	primo
   \(20\)	\(4\)	\(d = 2\)	non primo (\(20 = 2 \cdot 10\))
   \(21\)	\(4\)	\(d = 3\)	non primo (\(21 = 3 \cdot 7\))
   \(22\)	\(4\)	\(d = 2\)	non primo (\(22 = 2 \cdot 11\))
   \(23\)	\(4\)	nessuno	primo
   \(24\)	\(4\)	\(d = 2\)	non primo (\(24 = 2 \cdot 12\))
   \(25\)	\(5\)	\(d = 5\)	non primo (\(25 = 5 \cdot 5\))
   \(26\)	\(5\)	\(d = 2\)	non primo (\(26 = 2 \cdot 13\))
   \(27\)	\(5\)	\(d = 3\)	non primo (\(27 = 3 \cdot 9\))
   \(28\)	\(5\)	\(d = 2\)	non primo (\(28 = 2 \cdot 14\))
   \(29\)	\(5\)	nessuno	primo
   \(30\)	\(5\)	\(d = 2\)	non primo (\(30 = 2 \cdot 15\))

2. I numeri primi in \(\{2, 3, \dots, 30\}\) sono

   \[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 \]

   Ci sono \(10\) numeri primi in \(\{2, 3, \dots, 30\}\).

Esercizio 5.11: Algoritmi numerici (E11)

Consideriamo i seguenti numeri naturali:

\[ n \in \{6,\ 19,\ 49,\ 53,\ 91\} \]

Domande

1. Applicare l'algoritmo PrimalityTest a ciascun numero della lista. Per ogni \(n\) mostrare l'esecuzione passo per passo, indicando il valore di \(\lfloor\sqrt{n}\rfloor\), i valori di \(d\) provati e il risultato di ciascun test \(n \bmod d = 0\).

Soluzione

1. Esecuzione di PrimalityTest su ciascun numero.

   Verifica \(n = 6\): \(\lfloor\sqrt{6}\rfloor = 2\).

   \(d\)	\(6 \bmod d\)	azione
   \(2\)	\(0\)	restituisce false
   6 non è primo (\(6 = 2 \cdot 3\)).

   Verifica \(n = 19\): \(\lfloor\sqrt{19}\rfloor = 4\).

   \(d\)	\(19 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(3 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 19 è primo.

   Verifica \(n = 49\): \(\lfloor\sqrt{49}\rfloor = 7\).

   \(d\)	\(49 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(4 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(0\)	restituisce false
   49 non è primo (\(49 = 7 \cdot 7\)).

   Verifica \(n = 53\): \(\lfloor\sqrt{53}\rfloor = 7\).

   \(d\)	\(53 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(2 \ne 0\)	continua
   \(4\)	\(1 \ne 0\)	continua
   \(5\)	\(3 \ne 0\)	continua
   \(6\)	\(5 \ne 0\)	continua
   \(7\)	\(4 \ne 0\)	continua
   Il ciclo termina. Restituisce true: 53 è primo.

   Verifica \(n = 91\): \(\lfloor\sqrt{91}\rfloor = 9\).

   \(d\)	\(91 \bmod d\)	azione
   \(2\)	\(1 \ne 0\)	continua
   \(3\)	\(1 \ne 0\)	continua
   \(4\)	\(3 \ne 0\)	continua
   \(5\)	\(1 \ne 0\)	continua
   \(6\)	\(1 \ne 0\)	continua
   \(7\)	\(0\)	restituisce false
   91 non è primo (\(91 = 7 \cdot 13\)).

Esercizio 5.12: Algoritmi numerici (E12)

Consideriamo il numero naturale \(n = 15\).

Domande

1. Applicare l'algoritmo SieveOfEratosthenes con \(n = 15\). Mostrare l'esecuzione passo per passo: indicare il valore di \(\lfloor\sqrt{15}\rfloor\) e, per ogni primo \(p\) trovato, elencare i valori di \(j\) nel ciclo interno e i corrispondenti assegnamenti \(prime[j] \leftarrow 0\).

2. Elencare tutti i numeri primi \(\le 15\).

Soluzione

1. Si ha \(n = 15\) e \(\lfloor\sqrt{15}\rfloor = 3\). L'array \(prime[1..15]\) è inizializzato a \(1\) e poi \(prime[1] \leftarrow 0\). Ogni riga della tabella mostra lo stato dell'array dopo l'assegnamento \(prime[j] \leftarrow 0\) (blu: elemento appena posto a \(0\); rosso: valore corrente di \(p\)).

   		\(prime[1..15]\)
   \(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	azione
   \(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	inizializzazione
   2	4	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
   	6	0	1	1	0	1	0	1	1	1	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
   	8	0	1	1	0	1	0	1	0	1	1	1	1	1	1	1	\(prime[8] \leftarrow 0\)
   	10	0	1	1	0	1	0	1	0	1	0	1	1	1	1	1	\(prime[10] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	1	0	1	0	1	1	1	\(prime[12] \leftarrow 0\)
   	14	0	1	1	0	1	0	1	0	1	0	1	0	1	0	1	\(prime[14] \leftarrow 0\)
   	16																\(j = 16 > 15\): arresto
   3	9	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	\(prime[9] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	0	0	1	0	1	0	1	\(prime[12] \leftarrow 0\) (già \(0\))
   	15	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	\(prime[15] \leftarrow 0\)
   	18																\(j = 18 > 15\): arresto
   Il ciclo esterno termina: \(p = 4 > \lfloor\sqrt{15}\rfloor = 3\).

2. I numeri primi \(\le 15\) sono \(2,\ 3,\ 5,\ 7,\ 11,\ 13\).

Esercizio 5.13: Algoritmi numerici (E13)

Consideriamo il numero naturale \(n = 30\).

Domande

1. Applicare l'algoritmo SieveOfEratosthenes con \(n = 30\). Mostrare l'esecuzione passo per passo: indicare il valore di \(\lfloor\sqrt{30}\rfloor\) e, per ogni primo \(p\) trovato, elencare i valori di \(j\) nel ciclo interno e i corrispondenti assegnamenti \(prime[j] \leftarrow 0\).

2. Elencare tutti i numeri primi \(\le 30\).

Soluzione

1. Si ha \(n = 30\) e \(\lfloor\sqrt{30}\rfloor = 5\). L'array \(prime[1..30]\) è inizializzato a \(1\) e poi \(prime[1] \leftarrow 0\).

   • Iterazione \(p = 2\): \(prime[2] = 1\), quindi \(2\) è primo. Ciclo interno da \(j = p^2 = 4\) con passo \(2\):

     \(j\)	assegnamento	nota
     \(4\)	\(prime[4] \leftarrow 0\)
     \(6\)	\(prime[6] \leftarrow 0\)
     \(8\)	\(prime[8] \leftarrow 0\)
     \(10\)	\(prime[10] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)
     \(14\)	\(prime[14] \leftarrow 0\)
     \(16\)	\(prime[16] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)
     \(20\)	\(prime[20] \leftarrow 0\)
     \(22\)	\(prime[22] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)
     \(26\)	\(prime[26] \leftarrow 0\)
     \(28\)	\(prime[28] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)
     \(32\)		\(j = 32 > 30\): arresto

   • Iterazione \(p = 3\): \(prime[3] = 1\), quindi \(3\) è primo. Ciclo interno da \(j = p^2 = 9\) con passo \(3\):

     \(j\)	assegnamento	nota
     \(9\)	\(prime[9] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)	già \(0\)
     \(15\)	\(prime[15] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)	già \(0\)
     \(21\)	\(prime[21] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)	già \(0\)
     \(27\)	\(prime[27] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)	già \(0\)
     \(33\)		\(j = 33 > 30\): arresto

   • Iterazione \(p = 4\): \(prime[4] = 0\), quindi \(4\) non è primo: si salta.

   • Iterazione \(p = 5\): \(prime[5] = 1\), quindi \(5\) è primo. Ciclo interno da \(j = p^2 = 25\) con passo \(5\):

     \(j\)	assegnamento	nota
     \(25\)	\(prime[25] \leftarrow 0\)
     \(30\)	\(prime[30] \leftarrow 0\)	già \(0\)
     \(35\)		\(j = 35 > 30\): arresto

   • Il ciclo esterno termina: \(p = 6 > \lfloor\sqrt{30}\rfloor = 5\).

   Stato finale dell'array \(prime[1..30]\) (gli elementi uguali a \(1\) sono in blu):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0
   \(i\)	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
   \(prime[i]\)	0	1	0	1	0	0	0	1	0	0	0	0	0	1	0

2. I numeri primi \(\le 30\) sono \(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29\).

Esercizio 5.14: Algoritmi numerici (E14)

Consideriamo la seguente traccia di esecuzione dell'algoritmo SieveOfEratosthenes per \(n = 12\), in cui alcuni elementi sono stati sostituiti da un punto interrogativo.

		\(prime[1..12]\)
\(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	azione
\(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	inizializzazione
2	4	0	1	1	?	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
	6	0	1	1	0	1	?	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
	8	0	1	1	0	1	0	1	?	1	1	1	1	\(prime[8] \leftarrow 0\)
	10	0	1	1	0	1	0	1	0	1	?	1	1	\(prime[10] \leftarrow 0\)
	12	0	1	1	0	1	0	1	0	1	0	1	?	\(prime[12] \leftarrow 0\)
	14													\(j = 14 > 12\): arresto
3	9	0	1	1	0	1	0	1	0	?	0	1	0	\(prime[9] \leftarrow 0\)
	12	0	1	1	0	1	0	1	0	0	0	1	?	\(prime[12] \leftarrow 0\) (già \(0\))
	15													\(j = 15 > 12\): arresto
Il ciclo esterno termina: \(p = 4 > \lfloor\sqrt{12}\rfloor = ?\).

Domande

1. Completare tutti gli elementi contrassegnati da un punto interrogativo nella tabella.

2. Qual è il valore di \(\lfloor\sqrt{12}\rfloor\)? Perché il ciclo esterno può fermarsi quando \(p = 4\)?

3. Elencare tutti i numeri primi \(\le 12\).

Soluzione

1. Tabella completata:

   		\(prime[1..12]\)
   \(p\)	\(j\)	1	2	3	4	5	6	7	8	9	10	11	12	azione
   \(-\)	\(-\)	0	1	1	1	1	1	1	1	1	1	1	1	inizializzazione
   2	4	0	1	1	0	1	1	1	1	1	1	1	1	\(prime[4] \leftarrow 0\)
   	6	0	1	1	0	1	0	1	1	1	1	1	1	\(prime[6] \leftarrow 0\)
   	8	0	1	1	0	1	0	1	0	1	1	1	1	\(prime[8] \leftarrow 0\)
   	10	0	1	1	0	1	0	1	0	1	0	1	1	\(prime[10] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	1	0	1	0	\(prime[12] \leftarrow 0\)
   	14													\(j = 14 > 12\): arresto
   3	9	0	1	1	0	1	0	1	0	0	0	1	0	\(prime[9] \leftarrow 0\)
   	12	0	1	1	0	1	0	1	0	0	0	1	0	\(prime[12] \leftarrow 0\) (già \(0\))
   	15													\(j = 15 > 12\): arresto
   Il ciclo esterno termina: \(p = 4 > \lfloor\sqrt{12}\rfloor = 3\).

   Ogni punto interrogativo è l'elemento \(prime[j]\) della riga di indice \(j\): vale \(0\) dopo l'assegnamento \(prime[j] \leftarrow 0\) (nella riga \(p = 3\), \(j = 12\), l'elemento era già \(0\)).

2. \(\lfloor\sqrt{12}\rfloor = 3\). Il ciclo esterno viene eseguito per \(p = 2, 3\) e si ferma quando \(p = 4 > 3\). Ogni numero composto \(m \le 12\) ha un divisore primo non maggiore di \(\lfloor\sqrt{12}\rfloor = 3\) (capitolo «Algoritmi numerici», sezione «Crivello di Eratostene»), quindi tutti i numeri composti sono già stati marcati: \(4, 6, 8, 10, 12\) da \(p = 2\) e \(9\) da \(p = 3\).

3. I numeri primi \(\le 12\) sono \(2,\ 3,\ 5,\ 7,\ 11\).

Esercizio 5.15: Algoritmi numerici (E15)

Consideriamo l'algoritmo SieveOfEratosthenes applicato a \(n = 25\).

Domande

1. Applicare l'algoritmo SieveOfEratosthenes con \(n = 25\). Mostrare l'esecuzione passo per passo, indicando il valore di \(\lfloor\sqrt{25}\rfloor\) e, per ogni primo \(p\), i valori di \(j\) provati nel ciclo interno e i corrispondenti assegnamenti \(prime[j] \leftarrow 0\).

2. Per \(p = 5\): qual è il primo valore di \(j\) elaborato dal ciclo interno? Perché il punto di partenza è \(p^2 = 25\) e non \(2p = 10\)?

3. Elencare tutti i numeri primi \(\le 25\).

Soluzione

1. Si ha \(n = 25\) e \(\lfloor\sqrt{25}\rfloor = 5\). L'array \(prime[1..25]\) è inizializzato a \(1\) e poi \(prime[1] \leftarrow 0\).

   • Iterazione \(p = 2\): \(prime[2] = 1\), quindi \(2\) è primo. Ciclo interno da \(j = p^2 = 4\) con passo \(2\):

     \(j\)	assegnamento	nota
     \(4\)	\(prime[4] \leftarrow 0\)
     \(6\)	\(prime[6] \leftarrow 0\)
     \(8\)	\(prime[8] \leftarrow 0\)
     \(10\)	\(prime[10] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)
     \(14\)	\(prime[14] \leftarrow 0\)
     \(16\)	\(prime[16] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)
     \(20\)	\(prime[20] \leftarrow 0\)
     \(22\)	\(prime[22] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)
     \(26\)		\(j = 26 > 25\): arresto

   • Iterazione \(p = 3\): \(prime[3] = 1\), quindi \(3\) è primo. Ciclo interno da \(j = p^2 = 9\) con passo \(3\):

     \(j\)	assegnamento	nota
     \(9\)	\(prime[9] \leftarrow 0\)
     \(12\)	\(prime[12] \leftarrow 0\)	già \(0\)
     \(15\)	\(prime[15] \leftarrow 0\)
     \(18\)	\(prime[18] \leftarrow 0\)	già \(0\)
     \(21\)	\(prime[21] \leftarrow 0\)
     \(24\)	\(prime[24] \leftarrow 0\)	già \(0\)
     \(27\)		\(j = 27 > 25\): arresto

   • Iterazione \(p = 4\): \(prime[4] = 0\), quindi \(4\) non è primo: si salta.

   • Iterazione \(p = 5\): \(prime[5] = 1\), quindi \(5\) è primo. Ciclo interno da \(j = p^2 = 25\) con passo \(5\):

     \(j\)	assegnamento	nota
     \(25\)	\(prime[25] \leftarrow 0\)
     \(30\)		\(j = 30 > 25\): arresto

   • Il ciclo esterno termina: \(p = 6 > \lfloor\sqrt{25}\rfloor = 5\).

   Stato finale dell'array \(prime[1..25]\) (gli elementi uguali a \(1\) sono in blu):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1
   \(i\)	14	15	16	17	18	19	20	21	22	23	24	25
   \(prime[i]\)	0	0	0	1	0	1	0	0	0	1	0	0

2. Per \(p = 5\), il ciclo interno parte da \(j = p^2 = 25\). Tutti i multipli più piccoli di \(5\) maggiori di \(5\), cioè \(10, 15, 20\), sono già stati posti a \(0\): \(10 = 2 \cdot 5\) e \(20 = 2 \cdot 10\) quando \(p = 2\), e \(15 = 3 \cdot 5\) quando \(p = 3\). In generale, ogni multiplo \(m\) di \(p\) con \(p < m < p^2\) ha un divisore \(d\) con \(2 \le d < p\), quindi un divisore primo minore di \(p\), che lo ha già marcato.

3. I numeri primi \(\le 25\) sono \(2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23\).

Esercizio 5.16: Algoritmi numerici (E16)

Consideriamo il numero naturale \(n = 50\).

Domande

1. Applicare l'algoritmo SieveOfEratosthenes con \(n = 50\). Per ogni valore di \(p\) del ciclo esterno riportare il valore di \(prime[p]\) e, quando \(p\) è primo, tutti i valori di \(j\) elaborati dal ciclo interno (i multipli di \(p\) da \(p^2\) a \(50\)), distinguendo gli elementi posti a \(0\) per la prima volta da quelli già uguali a \(0\).

2. Elencare tutti i numeri primi \(\le 50\) e contarli.

Soluzione

1. Si ha \(n = 50\) e \(\lfloor\sqrt{50}\rfloor = 7\). L'array \(prime[1..50]\) è inizializzato a \(1\) e poi \(prime[1] \leftarrow 0\).

   \(p\)	\(prime[p]\)	valori di \(j\)	posti a \(0\) ora	già \(0\)
   \(2\)	\(1\) (primo)	\(4, 6, \dots, 50\)	4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50	—
   \(3\)	\(1\) (primo)	\(9, 12, \dots, 48\)	9, 15, 21, 27, 33, 39, 45	12, 18, 24, 30, 36, 42, 48
   \(4\)	\(0\) (salta)	—	—	—
   \(5\)	\(1\) (primo)	\(25, 30, \dots, 50\)	25, 35	30, 40, 45, 50
   \(6\)	\(0\) (salta)	—	—	—
   \(7\)	\(1\) (primo)	\(49\)	49	—
   Il ciclo esterno termina: \(p = 8 > \lfloor\sqrt{50}\rfloor = 7\).

   Stato finale dell'array \(prime[1..50]\) (gli elementi uguali a \(1\) sono in blu):

   \(i\)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
   \(prime[i]\)	0	1	1	0	1	0	1	0	0	0	1	0	1	0	0	0	1
   \(i\)	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34
   \(prime[i]\)	0	1	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0
   \(i\)	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
   \(prime[i]\)	0	0	1	0	0	0	1	0	1	0	0	0	1	0	0	0

2. I numeri primi \(\le 50\) sono

   \[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47 \]

   Ci sono \(15\) numeri primi \(\le 50\).

Esercizio 5.17: Algoritmi numerici (E17)

Consideriamo le seguenti coppie di numeri naturali \((n,m)\):

1. \((1071,\ 462)\)

2. \((100,\ 75)\)

3. \((17,\ 5)\)

4. \((89,\ 55)\)

5. \((30,\ 84)\)

Domande

1. Applicare l'algoritmo EuclideanAlgorithm per calcolare \(\gcd(n,m)\) per tutte le coppie. Per ogni coppia mostrare l'esecuzione passo per passo in una tabella, indicando a ogni passo i valori di \(n\), \(m\) e \(r=n\bmod m\), e dare il numero di iterazioni del ciclo while.

2. Quali coppie sono coprime?

3. Nella coppia 5 si ha \(n<m\). Che cosa accade nella prima iterazione?

Soluzione

1. Esecuzioni dell'algoritmo di Euclide.

   1. Calcoliamo \(\gcd(1071,462)\):

      passo	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(1071\)	\(462\)	\(1071 \bmod 462 = 147\)
      \(2\)	\(462\)	\(147\)	\(462 \bmod 147 = 21\)
      \(3\)	\(147\)	\(21\)	\(147 \bmod 21 = 0\)
      \(4\)	\(21\)	\(0\)	— (il ciclo termina)

      Risultato: \(\gcd(1071, 462) = 21\), con \(3\) iterazioni del ciclo while.

   2. Calcoliamo \(\gcd(100,75)\):

      passo	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(100\)	\(75\)	\(100 \bmod 75 = 25\)
      \(2\)	\(75\)	\(25\)	\(75 \bmod 25 = 0\)
      \(3\)	\(25\)	\(0\)	— (il ciclo termina)

      Risultato: \(\gcd(100, 75) = 25\), con \(2\) iterazioni del ciclo while.

   3. Calcoliamo \(\gcd(17,5)\):

      passo	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(17\)	\(5\)	\(17 \bmod 5 = 2\)
      \(2\)	\(5\)	\(2\)	\(5 \bmod 2 = 1\)
      \(3\)	\(2\)	\(1\)	\(2 \bmod 1 = 0\)
      \(4\)	\(1\)	\(0\)	— (il ciclo termina)

      Risultato: \(\gcd(17, 5) = 1\), con \(3\) iterazioni del ciclo while.

   4. Calcoliamo \(\gcd(89,55)\):

      passo	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(89\)	\(55\)	\(89 \bmod 55 = 34\)
      \(2\)	\(55\)	\(34\)	\(55 \bmod 34 = 21\)
      \(3\)	\(34\)	\(21\)	\(34 \bmod 21 = 13\)
      \(4\)	\(21\)	\(13\)	\(21 \bmod 13 = 8\)
      \(5\)	\(13\)	\(8\)	\(13 \bmod 8 = 5\)
      \(6\)	\(8\)	\(5\)	\(8 \bmod 5 = 3\)
      \(7\)	\(5\)	\(3\)	\(5 \bmod 3 = 2\)
      \(8\)	\(3\)	\(2\)	\(3 \bmod 2 = 1\)
      \(9\)	\(2\)	\(1\)	\(2 \bmod 1 = 0\)
      \(10\)	\(1\)	\(0\)	— (il ciclo termina)

      Risultato: \(\gcd(89, 55) = 1\), con \(9\) iterazioni del ciclo while.

      I numeri \(89, 55, 34, 21, 13, 8, 5, 3, 2, 1\) sono numeri di Fibonacci consecutivi: a ogni passo il quoziente è \(1\), e i resti decrescono più lentamente possibile.

   5. Calcoliamo \(\gcd(30,84)\):

      passo	\(n\)	\(m\)	\(r = n \bmod m\)
      \(1\)	\(30\)	\(84\)	\(30 \bmod 84 = 30\)
      \(2\)	\(84\)	\(30\)	\(84 \bmod 30 = 24\)
      \(3\)	\(30\)	\(24\)	\(30 \bmod 24 = 6\)
      \(4\)	\(24\)	\(6\)	\(24 \bmod 6 = 0\)
      \(5\)	\(6\)	\(0\)	— (il ciclo termina)

      Risultato: \(\gcd(30, 84) = 6\), con \(4\) iterazioni del ciclo while.

2. Due numeri sono coprimi se e solo se il loro massimo comun divisore è \(1\). Quindi le coppie coprime sono \((17,5)\) e \((89,55)\). Le coppie \((1071,462)\), \((100,75)\) e \((30,84)\) non sono coprime.

3. Poiché \(30<84\), si ha \(30\bmod 84=30\), quindi la prima iterazione sostituisce \((30,84)\) con \((84,30)\): scambia semplicemente i due numeri. Dalla seconda iterazione in poi l'esecuzione è la stessa che per \((84,30)\), che richiede \(3\) iterazioni. Dunque l'ipotesi \(n\ge m\) non serve per la correttezza: se \(n<m\), l'algoritmo esegue solo un'iterazione in più.

Esercizio 5.18: Algoritmi numerici (E18)

Consideriamo il seguente algoritmo naïf per il massimo comun divisore, che prova tutti i candidati divisori da \(\min\{n,m\}\) fino a \(1\).

Algoritmo: NaiveGCD

Input: Due numeri naturali \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function NaiveGCD(\(n\), \(m\))

2\(d := \min\{n,m\}\)

3while \(n \bmod d \ne 0\) or \(m \bmod d \ne 0\) do

4\(d \leftarrow d - 1\)

5end

6return \(d\)

7end

Domande

Le domande 2–4 usano le nozioni di invariante di ciclo, numero di passi e dimensione dell'input \(|I|\) (capitoli «Dimensione dell'input», «Tempo di esecuzione» e «Correttezza»).

1. Applicare NaiveGCD a \((48,18)\) e \((35,12)\). Quante iterazioni del ciclo while vengono eseguite? Confrontarle con il numero di iterazioni dell'algoritmo di Euclide sulle stesse coppie.

2. Dimostrare che NaiveGCD è corretto, usando un invariante di ciclo.

3. Calcolare il numero di passi \(S\) di NaiveGCD in funzione di \(n\), \(m\) e \(\gcd(n,m)\), contando un passo per ogni esecuzione di una riga. Quali input danno il caso peggiore? Confrontare i due algoritmi su \((1000,999)\).

4. Mostrare che NaiveGCD è esponenziale nella dimensione dell'input \(|I|\).

Soluzione

1. Per \((48,18)\): \(d\) parte da \(\min\{48,18\}=18\), e i candidati vengono controllati nell'ordine

   \[ 18,17,16,15,14,13,12,11,10,9,8,7,6. \]

   Il primo divisore comune è \(d=6\) (\(48=8\cdot 6\), \(18=3\cdot 6\)). Il corpo del ciclo while viene eseguito \(18-6=12\) volte. L'algoritmo di Euclide richiede solo \(3\) iterazioni (\(48\bmod 18=12\), \(18\bmod 12=6\), \(12\bmod 6=0\)).

   Per \((35,12)\): \(d\) scende da \(12\) a \(1\), poiché \(35\) e \(12\) sono coprimi: \(12-1=11\) iterazioni. L'algoritmo di Euclide richiede \(3\) iterazioni (\(35\bmod 12=11\), \(12\bmod 11=1\), \(11\bmod 1=0\)).

2. Invariante di ciclo:

   Ogni volta che la condizione alla riga 3 viene valutata, \(1\le \gcd(n,m)\le d\le\min\{n,m\}\), cioè nessun numero \(d'\) con \(d<d'\le\min\{n,m\}\) è un divisore comune di \(n\) e \(m\).

   • Inizializzazione. \(d=\min\{n,m\}\), e ogni divisore comune è al più \(\min\{n,m\}\).

   • Conservazione. Se la condizione è vera, \(d\) non è un divisore comune; poiché nessun numero più grande fino a \(\min\{n,m\}\) è un divisore comune, \(\gcd(n,m)<d\), cioè \(\gcd(n,m)\le d-1\). La riga 4 pone \(d\leftarrow d-1\), e l'invariante continua a valere.

   • Terminazione. \(d\) diminuisce di \(1\) a ogni iterazione e, per l'invariante, non può mai diventare minore di \(\gcd(n,m)\ge 1\); quando \(d=\gcd(n,m)\) la condizione è falsa. Quindi il ciclo termina, e quando termina \(d\) è un divisore comune con \(d\ge\gcd(n,m)\), dunque \(d=\gcd(n,m)\), che viene restituito.

3. Sia \(k=\min\{n,m\}-\gcd(n,m)\) il numero di iterazioni. Le righe 2 e 6 sono eseguite una volta, la riga 3 \(k+1\) volte, la riga 4 \(k\) volte:

   \[ S=1+(k+1)+k+1=2k+3=2\big(\min\{n,m\}-\gcd(n,m)\big)+3. \]

   Il caso peggiore si ha quando \(n\) e \(m\) sono coprimi: \(S=2\min\{n,m\}+1\). Per \((1000,999)\) (numeri consecutivi sono sempre coprimi) NaiveGCD esegue \(999-1=998\) iterazioni, mentre l'algoritmo di Euclide ne esegue solo \(2\) (\(1000\bmod 999=1\), \(999\bmod 1=0\)).

4. Consideriamo le coppie \((n,m)=(M,M-1)\), con \(M\ge 3\): sono coprime, quindi \(S=2(M-1)+1=2M-1=\Theta(M)\). L'input è formato da due numeri naturali, quindi \(|I|=\Theta(\log_2 M)\) con \(M=\max\{n,m\}\), cioè esistono \(c_1,c_2>0\) tali che

   \[ 2^{\frac{1}{c_2}|I|}\le M\le 2^{\frac{1}{c_1}|I|}. \]

   Quindi, su questi input, \(S=2^{\Theta(|I|)}\), e il tempo di esecuzione nel caso peggiore soddisfa \(T(|I|)=2^{\Theta(|I|)}\) (è anche al più \(2M+1\) su ogni input).

   NaiveGCD è esponenziale nella dimensione dell'input, mentre l'algoritmo di Euclide esegue \(O(\log_2 m)\) iterazioni (si veda l'esercizio successivo): per numeri con centinaia di cifre si può usare solo l'algoritmo di Euclide.

Esercizio 5.19: Algoritmi numerici (E19)

Consideriamo l'algoritmo di Euclide.

Algoritmo: EuclideanAlgorithm

Input: Due numeri naturali \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function EuclideanAlgorithm(\(n\), \(m\))

2while \(m \ne 0\) do

3\(r := n \bmod m\)

4\(n \leftarrow m\)

5\(m \leftarrow r\)

6end

7return \(n\)

8end

I numeri di Fibonacci sono \(F_1=F_2=1\) e \(F_{k}=F_{k-1}+F_{k-2}\) per \(k\ge 3\):

\[ 1,1,2,3,5,8,13,21,34,55,89,144,233,\dots \]

Domande

La domanda 4 usa le nozioni di tempo di esecuzione e dimensione dell'input \(|I|\) (capitoli «Dimensione dell'input» e «Tempo di esecuzione»).

1. Contare il numero di iterazioni del ciclo while per le coppie di numeri di Fibonacci consecutivi \((5,3)\), \((8,5)\), \((13,8)\), \((21,13)\), \((34,21)\), \((55,34)\), \((89,55)\), \((144,89)\), \((233,144)\).

2. Dimostrare che, per ogni \(n\ge m\ge 1\),

   \[ n\bmod m<\frac n2. \]

3. Usando il punto 2, dimostrare che il numero \(t\) di iterazioni del ciclo while sull'input \((n_0,m_0)\) soddisfa

   \[ t<2\log_2 m_0+2. \]

4. Assumendo che ogni operazione aritmetica sia un passo, determinare il tempo di esecuzione nel caso peggiore \(T(|I|)\) dell'algoritmo di Euclide. È polinomiale?

Soluzione

1. Per una coppia \((F_{k+1},F_k)\) con \(k\ge 3\) si ha \(F_k < F_{k+1} < 2F_k\), quindi \(F_{k+1}\bmod F_k=F_{k+1}-F_k=F_{k-1}\): a ogni iterazione si passa alla coppia precedente di numeri di Fibonacci consecutivi, fino a \((2,1)\to(1,0)\). Il numero di iterazioni è:

   \((n, m)\)	iterazioni \(t\)	\(2 \log_2 m + 2\)
   \((5, 3)\)	\(3\)	\(\approx 5.17\)
   \((8, 5)\)	\(4\)	\(\approx 6.64\)
   \((13, 8)\)	\(5\)	\(8\)
   \((21, 13)\)	\(6\)	\(\approx 9.40\)
   \((34, 21)\)	\(7\)	\(\approx 10.78\)
   \((55, 34)\)	\(8\)	\(\approx 12.17\)
   \((89, 55)\)	\(9\)	\(\approx 13.56\)
   \((144, 89)\)	\(10\)	\(\approx 14.95\)
   \((233, 144)\)	\(11\)	\(\approx 16.34\)

   Per esempio, \((89,55)\to(55,34)\to(34,21)\to(21,13)\to(13,8)\to(8,5)\to(5,3)\to(3,2)\to(2,1)\to(1,0)\): \(9\) iterazioni. Il numero di iterazioni cresce di \(1\) ogni volta che \(m\) viene moltiplicato per circa \(1.618\): cresce in modo logaritmico in \(m\). (I numeri di Fibonacci consecutivi sono, di fatto, il caso peggiore dell'algoritmo di Euclide.)

2. Sia \(n\ge m\ge 1\). Due casi:

   • se \(m\le\frac n2\), allora \(n\bmod m<m\le\frac n2\);

   • se \(m>\frac n2\), allora \(m\le n<2m\), quindi il quoziente di \(n\) diviso \(m\) è \(1\) e \(n\bmod m=n-m<n-\frac n2=\frac n2\).

3. Indichiamo con \(m_s\) il valore di \(m\) dopo \(s\) iterazioni (\(m_0\) è l'input). Nell'iterazione \(s+1\) la coppia \((n,m)\) diventa \((m,\ n\bmod m)\), quindi dopo l'iterazione \(s+1\) la variabile \(n\) è uguale a \(m_s\) e \(m_{s+1}<m_s\). Dunque, se l'iterazione \(s+2\) viene eseguita,

   \[ m_{s+2}=m_s\bmod m_{s+1} \quad\text{con}\quad m_s> m_{s+1}\ge 1, \]

   e per il punto 2, \(m_{s+2}<\dfrac{m_s}{2}\): ogni due iterazioni il valore di \(m\) almeno si dimezza. Per induzione su \(k\),

   \[ m_{2k}<\frac{m_0}{2^k}\qquad\text{ogni volta che l'iterazione }2k\text{ viene eseguita}, \ k\ge 1. \]

   Se \(t\le 2\) la limitazione vale: \(t=1<2\le 2\log_2 m_0+2\), e \(t=2\) è possibile solo se \(m_0\ge 2\) (per \(m_0=1\) il primo resto è \(0\)), quindi \(2<2\log_2 m_0+2\). Sia \(t\ge 3\) e sia \(k=\lfloor (t-1)/2\rfloor\ge 1\). Poiché \(2k\le t-1\), l'iterazione \(2k+1\) viene eseguita, quindi \(m_{2k}\ge 1\). Dunque

   \[ 1\le m_{2k}<\frac{m_0}{2^k} \quad\Longrightarrow\quad 2^k<m_0 \quad\Longrightarrow\quad k<\log_2 m_0 . \]

   Poiché \(k\ge\frac{t-2}{2}\), si ottiene \(\frac{t-2}{2}<\log_2 m_0\), cioè

   \[ t<2\log_2 m_0+2. \]

   I valori nella tabella del punto 1 rispettano questa limitazione.

4. Ogni iterazione esegue un numero costante di passi (righe 2–5), quindi il numero di passi soddisfa \(S=O(t)=O(\log_2 m_0)\). L'input è formato da due numeri naturali, quindi \(|I|=\Theta(\log_2 M)\) con \(M=\max\{n_0,m_0\}\ge m_0\): esiste \(c>0\) tale che \(\log_2 m_0\le\log_2 M\le\frac1c|I|\) per tutti gli input sufficientemente grandi. Quindi

   \[ T(|I|)=O(|I|). \]

   L'algoritmo di Euclide esegue \(O(\log_2 m)\) iterazioni, e il suo tempo di esecuzione nel caso peggiore è \(T(|I|)=O(|I|)\): è polinomiale (lineare) nella dimensione dell'input.

   Osservazione: se i numeri sono molto grandi, un'operazione \(n\bmod m\) non è un singolo passo, ma può essere eseguita in un numero di passi polinomiale in \(|I|\); quindi l'algoritmo rimane polinomiale.

Esercizio 5.20: Algoritmi numerici (E20)

Consideriamo la seguente variante dell'algoritmo di Euclide, che usa solo sottrazioni (è la versione descritta originariamente da Euclide).

Algoritmo: SubtractiveGCD

Input: Due numeri naturali \(n, m \ge 1\)

Output: \(\gcd(n, m)\)

1function SubtractiveGCD(\(n\), \(m\))

2while \(n \ne m\) do

3if \(n > m\) then

4\(n \leftarrow n - m\)

5end

6else

7\(m \leftarrow m - n\)

8end

9end

10return \(n\)

11end

Domande

Le domande 3 e 4 usano le nozioni di invariante di ciclo, tempo di esecuzione e dimensione dell'input \(|I|\) (capitoli «Dimensione dell'input», «Tempo di esecuzione» e «Correttezza»).

1. Applicare SubtractiveGCD a \((48,18)\), mostrando i valori di \(n\) e \(m\) a ogni iterazione. Confrontare con l'algoritmo di Euclide.

2. Dimostrare che, per ogni \(n>m\ge 1\), \(\gcd(n,m)=\gcd(n-m,m)\).

3. Dimostrare la correttezza di SubtractiveGCD usando un invariante di ciclo.

4. Quante iterazioni vengono eseguite sull'input \((n,1)\)? SubtractiveGCD è polinomiale nella dimensione dell'input?

Soluzione

1. Esecuzione su \((48,18)\):

   iterazione	\(n\)	\(m\)	azione
   \(1\)	\(48\)	\(18\)	\(n > m\): \(n \leftarrow 48 - 18 = 30\)
   \(2\)	\(30\)	\(18\)	\(n > m\): \(n \leftarrow 30 - 18 = 12\)
   \(3\)	\(12\)	\(18\)	\(n < m\): \(m \leftarrow 18 - 12 = 6\)
   \(4\)	\(12\)	\(6\)	\(n > m\): \(n \leftarrow 12 - 6 = 6\)
   —	\(6\)	\(6\)	\(n = m\): il ciclo termina, restituisce \(6\)

   Risultato: \(\gcd(48,18)=6\), con \(4\) iterazioni. L'algoritmo di Euclide calcola \(48\bmod 18=12\) in un solo passo: sottrarre \(18\) da \(48\) finché possibile (iterazioni 1–2) dà esattamente il resto \(12\). In generale, una sequenza di sottrazioni consecutive dello stesso numero è un solo passo dell'algoritmo di Euclide.

2. Sia \(n>m\ge 1\). Se \(d\) è un divisore comune di \(n\) e \(m\), allora \(n=k_1d\) e \(m=k_2d\), quindi \(n-m=(k_1-k_2)d\), con \(k_1-k_2\ge 1\) poiché \(n>m\): \(d\) è un divisore comune di \(n-m\) e \(m\). Viceversa, se \(n-m=k_1d\) e \(m=k_2d\), allora \(n=(n-m)+m=(k_1+k_2)d\): \(d\) è un divisore comune di \(n\) e \(m\). Le due coppie hanno gli stessi divisori comuni, quindi lo stesso massimo comun divisore.

3. Indichiamo con \(n_0,m_0\) i valori in input. Invariante di ciclo:

   Ogni volta che la condizione alla riga 2 viene valutata, \(n\ge 1\), \(m\ge 1\) e \(\gcd(n,m)=\gcd(n_0,m_0)\).

   • Inizializzazione. \(n=n_0\ge 1\), \(m=m_0\ge 1\).

   • Conservazione. Supponiamo che valga l'invariante e che \(n\neq m\). Se \(n>m\), la riga 4 sostituisce \(n\) con \(n-m\ge 1\) e, per il punto 2, \(\gcd(n-m,m)=\gcd(n,m)\). Se \(n<m\), la riga 7 sostituisce \(m\) con \(m-n\ge 1\) e, per il punto 2 con i ruoli scambiati, \(\gcd(n,m-n)=\gcd(n,m)\). In entrambi i casi l'invariante continua a valere.

   • Terminazione. Il numero naturale \(n+m\) diminuisce di almeno \(1\) a ogni iterazione (si sottrae un numero \(\ge 1\)), ed è sempre almeno \(2\). Quindi il ciclo termina, e termina quando \(n=m\). Allora

     \[ \gcd(n_0,m_0)=\gcd(n,n)=n, \]

     che viene restituito alla riga 10.

4. Su \((n,1)\) con \(n\ge 2\), ogni iterazione esegue \(n\leftarrow n-1\), fino a \(n=1\): il ciclo esegue \(n-1\) iterazioni (per esempio \((7,1)\) ne richiede \(6\)), mentre l'algoritmo di Euclide ne richiede solo \(1\) (\(n\bmod 1=0\)). Ogni iterazione esegue un numero costante di passi, quindi sugli input \((M,1)\) si ha \(S=\Theta(M)\). La dimensione dell'input è \(|I|=(\lfloor\log_2 M\rfloor+1)+1=\Theta(\log_2 M)\), quindi \(M=2^{\Theta(|I|)}\) e

   \[ T(|I|)=2^{\Theta(|I|)}. \]

   SubtractiveGCD è corretto, ma è esponenziale nella dimensione dell'input. Sostituendo le sottrazioni ripetute con una singola operazione \(\bmod\) si ottiene l'algoritmo di Euclide, che è polinomiale.