Pagina 2
Pubblicità

Algoritmi

Cos'è un algoritmo ?

Il termine algoritmo significa "procedimento di calcolo" ed è un insieme finito ed ordinato di operazioni per risolvere una classe di problemi, per esempio (una ricetta da cucina, ad esempio, può essere considerata come un algoritmo che partendo da un insieme di singoli alimenti di base ed eseguendo una sequenza di passi, produce come risultato un piatto composto), possiamo quindi definire l'algoritmo come una sequenza ordinata e finita di istruzioni. Il primo algoritmo di cui si abbia documentazione si trova in un papiro egiziano del 1650 a.C. (circa) che contiene un algoritmo per la moltiplicazione, tale algoritmo viene tuttora utilizato nei circuiti di unità aritmetico/logiche dei calcolatori elettronici.

Le proprietà principali di un algoritmo

  • finitezza ; l'algoritmo deve essere composto da un numero finito di passi.
  • non ambiguità ; l'algoritmo deve essere interpretato in modo univoco dall'esecutore sia esso umano o artificiale.
  • terminazione ; l'esecuzione deve terminare dopo un tempo finito.
  • eseguibilità ; gli informatici utilizzano il termine "efficace" er indicare il concetto di eseguibilità.
  • Alcuni esempi di algoritmi

    Pubblicità
    .

    Quali sono i vantaggi ?

    L’esempio scelto riguarda un algoritmo di cifratura, cioè si tratta di un processo che codifica un testo in modo tale da non poter più essere “leggibile” in modo corretto (in pratica se ne smarrisce il significato).

    Giovanni è un giovane che spesso usa il bancomat per prelevare denaro contante dalla sua banca. Purtroppo non riesce a memorizzare il codice segreto della tessera per cui è costretto a scriverselo su un fogliettino di carta che conserva nel portafogli. Giustamente pensa che perdendo un giorno il portafogli potrebbe consegnare al fortunato “ritrovatore” tutti i mezzi necessari per il prelevamento di contanti (bancomat + codice segreto) e decide quindi di inventarsi un sistema che possa permettergli in modo univoco di ricordare il codice segreto, cioè utilizza un algoritmo ad hoc che viene chiamato di codifica.

    Il codice segreto del bancomat di Giovanni è 73546. Giovanni decide di aggiungere il numero 3 ad ogni singola cifra del suo codice segreto, cioè lo riscrive in questo modo:

    codice: (7+3)(3+3)(5+3)(4+3)(6+3).

    Ora nota che c’è un problema per quanto riguarda la prima cifra, in quanto 7+3=10 e quindi il nuovo codice avrebbe una cifra in più e potrebbe quindi risultare di difficile decifratura (algoritmo inverso che ci permette di tornare al codice originario). Decide quindi di superare questa situazione potenzialmente problematica prendendo in considerazione solo le unità, nel nostro esempio la cifra 0.

    Il nuovo codice, corrispondente al codice segreto codificato è: 06879, che è del tutto diverso da quello originario. Se il trovatore del portafogli di Giovanni applicherebbe questo codice per prelevare i soldi non otterrebbe alcun risultato positivo, ma, come ben sappiamo, al terzo tentativo fallito di inserimento del codice bancomat la scheda viene ritirata dallo sportello automatico, proteggendo così il conto di Giovanni.

    Questo, come già detto, è un esempio molto semplice e che crediamo possa rendere bene l’idea del concetto di algoritmo.

    Ma siamo davvero sicuri che il processo utilizzato nell’esempio precedente sia effettivamente un algoritmo?

    Esiste un problema da risolvere? Certo che si. Giovanni introduce questo processo per “nascondere” il proprio codice segreto.

    Pubblicità

    Arriva ad un risultato in tempo limitato? Lo abbiamo appena visto nell’esempio. In poco più di un attimo Giovanni ha la soluzione al suo problema.

    Le istruzioni date sono eseguibili e non ambigue? Per quanto riguarda l’eseguibilità, altro non ha fatto che operare una semplice addizione usuale. Non c’è traccia di ambiguità in ciò che Giovanni si è costruito perché la chiave (cioè il numero 3 da aggiungere) è predefinita e non varia durante il processo, ma anche perché non lascia spazio a problemi nella decodifica (bisogna solo che si ricordi che se il numero è inferiore alla chiave – cioè a 3 – significa che è stato ottenuto considerando solo la cifra delle unità rispetto al risultato della somma).

    Bene, ora siamo veramente convinti che abbiamo fatto un buon esempio di algoritmo, ma soprattutto vogliamo insistere sul fatto che esso è “lontano” dall’uso del computer, distaccato da determinate discipline, ma può essere riferito esclusivamente ad un episodio legato ad una problematica di vita quotidiana.

    Per completezza di informazione aggiungiamo che, esiste l’algoritmo inverso che prende il nome di decodifica, il cui scopo è, partendo dalla chiave, rigenerare il codice segreto originario.

    Vediamo comunque con quale percorso si giunge al codice corretto (o decifrato), partendo da quello cifrato che, se ci ricordiamo, è 06879 e la chiave è il numero 3. Ci sono cifre inferiori al 3? Si c’è uno zero come prima cifra. Allora al posto di 0 scriviamo 10 e facciamo la seguente operazione:

    (10-3)(6-3)(8-3)(7-3)(9-3)

    A questo punto otteniamo il codice originario operando semplicemente le sottrazioni nelle parentesi: otteniamo così il codice 73546, che è proprio il codice originario del bancomat

    Pubblicità
    Pagina 1 - 2