Teorema master sulle ricorrenze
Siano a ≤ 1 e b ≤ 1 costanti e f(n) una funzione.
Sia T(n) il costo dell'esecuzione della ricorrenza.
Keep reading →
Visite di alberi
Oggi ho scoperto l'acqua calda.
Dopo settimane passate a cercare di memorizzare l'ordine delle visite degli alberi ho realizzato questi grafici sul mio Display a Fibre di Cellulosa™
Keep reading →
Dimostrazione che n^2 >= 2n + 5
Dimostrare per induzione che n2 ≥ 2n + 5 ∀ n ≥ 4
Base: 42 ≥ 2·4 + 5 ⇒ 16 ≥ 13: verificato
Passo induttivo: n2 ≥ 2n + 5 ⇒ (n+1)2 ≥ 2(n+1) + 5
(n+1)2 = n2 + 2n + 1
per ipotesi induttiva (l'ipotesi è n2 ≥ 2n + 5) possiamo dire che
n2 + 2n + 1 ≥ 2n + 5 + 2n + 1
2n + 5 + 2n + 1 = 2n + 2 + 2n + 4 = 2(n+1) + 2(n+2)
il passo induttivo è dimostrato se 2(n+1) + 2(n+2) ≥ 2(n+1) + 5 ⇒ 2n+4 ≥ 5 ⇒ 2n ≥ 5-4 che è vero ∀ n ≥ 4 ∎
Riflessioni di preparazione per il compito di Matematica Discreta
Premessa. Qualche mese fa mi sono preso un bidone: mi ero iscritto all'anno accademico 2014-2015, ma a causa dei crediti riconosciuti dalla carriera precedente mi sono ritrovato iscritto con l'ordinamento 2013-2014.
"amen - ho pensato - tanto le materie saranno sempre le stesse". E invece, mi sono ritrovato con Calcolo 1 e Calcolo 2 trasformati in Calcolo e basta (12 crediti) e Matematica Discreta + Algebra lineare trasformati in Matematica Discreta (12 crediti).
Keep reading →