Corso di Laurea in Informatica Prova scritta del 8 Luglio 2004

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1.

1. Trovare tutte le soluzioni della congruenza 304x ≡ −456 (mod 120)

2. Determinare il numero delle soluzioni x della congruenza tali che −53 ≤ x < 2. Esercizio 2. Sia A = {x ∈ ℕ | 1 ≤ x ≤ 5}. Sia R = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}.

1. Determinare quali delle seguenti formule sono vere.

\begin{matrix}(φ_{1}) ∃x ∈ A ∃y ∈ A (x, y) ∈ R & (φ_{2}) ∀x ∈ A ∃y ∈ A (x, y) ∈ R \\ (φ_{3}) ∃x ∈ A ∀y ∈ A (x, y) ∈ R & (φ_{4}) ∀x ∈ A ∀y ∈ A (x, y) ∈ R \\ (φ_{5}) ∃y ∈ A ∀x ∈ A (x, y) ∈ R & (φ_{6}) ∀y ∈ A ∃x ∈ A (x, y) ∈ R \end{matrix}

2. Sia ora A = ℕ, R = {(n, n + 1) | n ∈ ℕ} e determinare quali delle formule φ_{1}, …, φ_{6} sopra

elencate sono vere. Esercizio 3. Dimostrare per induzione che Σ_{i=1}^{n}i^{2} = \frac{n(n+1)(2n+1)}{6}. Esercizio 4. Dati due insiemi A, B definiamo A△B = (A \ B) ∪ (B \ A). Nella lista che segue individuare tutte le coppie di formule (se ve ne sono) che definiscono lo stesso insieme per ogni scelta di A, B. Si giustifichi la risposta.

\begin{matrix}1) A, & 2) ∅, \\ 3) B \ A, & 4) A△A, \\ 5) B△A, & 6) (A△B) ∩ B, \\ 7) (A ∪ B) \ (A ∩ B), & 8) A△∅. \end{matrix}

Esercizio 5. Deteminare:

1. Quante sono le stringhe binarie di lunghezza 12 con esattamente due 1.

2. Quante sono le stringhe binarie di lunghezza 12 con almeno due 1.

3. Quante sono le stringhe binarie di lunghezza 12 con al massimo due 1.

4. Quante sono le stringhe binarie di lunghezza 12 con esattamente due 1 e tali che gli 1 sono in posizioni non consecutive.