giovedì 20 Febbraio 2020

Download in corso

Softwareone.it

Algoritmi

Cos’è un algoritmo ?

Il termine algoritmo o “procedimento di calcolo” è un insieme finito ed ordinato di operazioni per risolvere una classe di problemi.

Possiamo definire il termine l’algoritmo come una sequenza ordinata e finita di istruzioni.

Pubblicità

Il primo algoritmo scoperto si trova in un papiro egiziano del 1650 a.C, contiene un procedure per la moltiplicazione; tale algoritmo viene tuttora utilizzato 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” per indicare il concetto di eseguibilità.

Alcuni esempi di algoritmi

L’esempio scelto riguarda un algoritmo di cifratura; si tratta di un processo che codifica un testo in modo tale da non poter più essere leggibile in modo corretto.

Il codice segreto è 73546 aggiungere il numero 3 ad ogni singola cifra del codice segreto, lo riscrive in questo modo:

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

C’è un problema per quanto riguarda la prima cifra, in quanto 7+3=10 e 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).

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.

Questo, come già detto, è un esempio molto semplice che rendere bene l’idea di termine algoritmo.

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

Quali sono i vantaggi ?

Esiste un problema da risolvere?

Per quanto riguarda l’eseguibilità, altro non ha fatto che operare una semplice addizione usuale.

Le istruzioni date sono eseguibili e non ambigue?

Non c’è traccia di ambiguità in ciò che 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).

Decodifica

Esiste l’algoritmo inverso che prende il nome di decodifica, il cui scopo è, partendo dalla chiave, rigenerare il codice segreto originario.

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.

calcolo delle radici di una equazione di secondo grado del tipo 

ax + bx + c = 0

Come potremmo “generare” un nuovo termine di algoritmo risolutivo basandoci sulle nostre conoscenze?

Generiamo una sequenza di passi che possano portarci alla soluzione del problema. 

Calcoliamo il delta dell’equazione e distinguiamo i tre casi;

  • Caso delta negativo → esistono due soluzioni complesse coniugate;
  • delta nullo → esiste una soluzione doppia pari a –b/2a; 
  • Caso delta positivo:
  • Calcola le due soluzioni secondo la formula nota:

Le due soluzioni sono x1 e x2. 

Il problema è sempre lo stesso;

si considera l’algoritmo come un qualcosa da legare esclusivamente all’ utilizzo del computer per cui risulta difficile riconoscerlo nelle sue più svariate forme ed applicazioni in ambiti che vanno al di là della “macchina”. 

Domanda: possiamo usare l’algoritmo dell’esempio precedente per costruirne uno leggermente più complesso?

La risposta è si.

Supponiamo di voler generare l’algoritmo risolutivo di una disequazione di secondo grado. 

Per semplicità consideriamo esclusivamente il caso a > 0.

Schematizzare un Algoritmo

Possiamo schematizzare la nostra sequenza di passi: 

 delta positivo:
Calcola le radici dell’equazione associata con l’algoritmo precedente;
Se il segno è “>” le soluzioni sono esterne alle due radici; 
Se il segno è “<” le soluzioni sono interne alle radici;

Caso delta nullo:
calcola la radice doppia dell’equazione associata con l’algoritmo precedente; 
Se il segno è “>” le soluzioni saranno tutte tranne la radice stessa; 
Se il segno è “<” non ci sono soluzioni reali. 
Caso delta negativo:
Se il segno è “>” la soluzione è tutto l’asse reale; 
Se il segno è “<” non ci sono soluzioni reali. 

Possiamo spingerci oltre e magari scrivere un semplicissimo programmino in un linguaggio di programmazione (per esempio in Pascal) che traduca il nostro esempio di algoritmo in modo che possa essere eseguito da un computer.

In questo modo, paradossalmente, si coglie meglio il senso di un algoritmo visto come cosa assolutamente distaccata ma necessaria per la stesura di un programma. 

Potremmo scrivere il nostro programmino in questo modo: 

program diseq; 
uses crt; 
var a,b,c:integer; 
x1,x2, delta:real;
segno:char;
begin 
clrscr; 
write('inserisci a>0 '); 
readln(a); 
write('inserisci b '); 
readln(b); 
write('inserisci c '); 
readln(c); 
write('inserisci segno < o > '); 
readln(segno); 
delta:=sqr(b)-4*a*c;

if delta>=0 then 
begin 
x1:=(-b+sqrt(delta))/(2*a); x2:=(-b-sqrt(delta))/(2*a); 
if segno='>' then 
writeln('soluzione = x < ',x1:8:2,' e x > ',x2:8:2) 
else 
writeln('soluzione = ',x1:8:2,' < x < ',x2:8:2); 
end; 
else 
begin 
if segno='>' then 
writeln('soluzione = per ogni x ') 
else 
writeln('soluzione = insieme vuoto'); 
end; 
readln;
end. 

Esempio scritto in Pascal serve a far vedere come possa essere tradotto in una “lingua” che il computer è capace di comprendere.

https://it.wikipedia.org/wiki/Algoritmo

05-01-2019
Pubblicità