Variante 3D Percorsi di Manhattan

Questa variante ci propone di generalizzare il problema dei percorsi di Manhattan e di risolverlo in uno spazio tridimensionale. Dato un reticolo, come mostrato in figura, ci si chiede in quanti modi diversi ci si può spostare dal punto A al punto B, senza allungare inutilmente il percorso. Il punto A dista dal punto B i passi lungo l’asse y, j passi lungo l’asse x e k passi lungo l’asse z. Continue reading

Problema dei percorsi di Manhattan

Le strade di Manhattan sono di due tipi: Avenues e Streets. Le Avenues sono tutte parallele tra loro e perpendicolari alle Streets, tutte parallele tra loro. Le Streets e le Avenues formano quandi un reticolato. Un impiegato, ad esempio abita, all’incrocio tra la 10a e la 25a Avenue, il suo ufficio si trova all’incrocio tra la 16a Street e la 29a Avenue. Supponendo che cammini sempre in direzione dell’ufficio, che cioè non faccia percorsi inutili, in quanti modi diversi può recarsi in ufficio? Continue reading

Algoritmo di Euclide per il calcolo dell’MCD

L’algoritmo di Euclide è un algoritmo utilizzato per trovare l’MCD (Massimo Comun Divisore) tra due numeri. Inizialmente l’algoritmo consisteva in una serie di sottrazioni: siano a e b due numeri interi ≥ 0, se a e b sono divisibili per un terzo numero c, allora anche la loro differenza è divisibile per c. Dim: supponiamo a > b:

a = kc , b = hc, a-b = kc – hc = c(k – h) ⇒ (implicazione) MCD(a, b) = MCD((a-b), b) fino ad ottenere MCD(a, 0) = a. L’agoritmo può essere così scritto: Continue reading

Java e XML (II)

Dopo una breve introduzione all’XML e alla sua struttura, in quest’ultima puntata ci “sporcheremo” le mani con un po’ di codice andando a scrivere una serie di classi che ci permettono di:

  1. leggere i valori (numerici o testuali) contenuti all’interno di ciascun tag del file XML;
  2. scrivere un file XML direttamente da codice.

Continue reading

Data Encryption Standard (DES)

Prima di descriverne il funzionamento, analizziamo la storia del DES:
Le origini del DES risalgono ai primi anni settanta, a seguito di un progetto della IBM; inizialmente chiamato DEA (Data Encryption Algorithm) era basato su un precedente progetto chiamato Lucifer, un’algoritmo con blocco e chiave di 128 bit sviluppato da un gruppo di ricercatori IBM. Continue reading

Funzioni di hash e MAC

Viene detta funzione di hash una funzione che dato un messaggio qualunque di lunghezza arbitraria, ne produce un’impronta detta digest di lunghezza prefissata (solitamente è di 100-200 bit). L’utilità di una funzione di hash sta nella possibilità di rappresentare (in maniera compatta) l’intero messaggio tramite l’impronta, solitamente firmando l’impronta non il messaggio; perchè questo possa accadere è necessario (e desiderabile) che la funzioni presenti due peculiarità, sia cioè senza collisioni eunidirezionale. In particolare: Continue reading

RSA

L’RSA (dai nomi dei tre ricercatori che lo proposero Rivest, Shamir e Adleman) è il più noto algoritmo di crittografia asimmetrica e può essere utilizzato sia per la cifratura che per la firma.
I passi preliminari sono i seguenti: Continue reading