Formalizzazione di un algoritmo

Naturalmente la forma varia in modo significativo in funzione del livello di dettaglio che si

desidera esprimere:

se noi vogliamo dare l’idea di un algoritmo, tendenzialmente non scendiamo nei dettagli,

scendiamo nella logica dell’algoritmo, quindi ci saranno delle operazioni che sono descritte a

grandi linee dopodiché ci si chiede come faccio a fare questa operazione? e si scenderà

ancora di più nel dettaglio fino a quelle che sono le famose operazioni elementari.

ESEMPI:

Il crivello di Eratostene è un Algoritmo e il prof lo ha semplicemente raccontato prima di farci

vedere l’esempio grafico questo racconto si dice che è una sua formalizzazione

⇒

"storytelling" (testo + immagini)

Tra questo e la macchina ci sono 2 passaggi:

1)​ Il primo è rappresentare quello che si racconta in un modo formale Dall’algoritmo

⇒

alla formalizzazione dell’algoritmo

2)​ Il secondo passaggio è trasformare l’algoritmo in un programma quindi in un

→

software che possa essere eseguito sul nostro computer vuol dire che il livello di

→

formalizzazione che scegliamo per descrivere il nostro algoritmo è qualcosa che deve

comprendere il computer quindi automaticamente vuol dire che il modo di

→

formalizzare le cose deriva dal linguaggio di programmazione che vogliamo

utilizzare⇒

Questa è la cosa molto importante : LA MACCHINA È SEMPRE LA STESSA, È INVECE IL

PROGRAMMA IN CUI IMPLEMENTO IL MIO ALGORITMO A CAMBIARE , IL LINGUAGGIO DI

PROGRAMMAZIONE IN SE MI PERMETTE DI USARE LA MACCHINA A MIO PIACIMENTO

L’IMPORTANTE È CHE IL LINGUAGGIO CHE USO SIA UNA FORMALIZZAZIONE

"COMPRENSIBILE" AL CALCOLATORE CHE LO PUÒ "ESEGUIRE"

Un programma quindi un algoritmo tradotto in un linguaggio di programmazione

→

eseguibile dal computer→ si dice che è "buono" se alla sua base c'è una "buona"

progettazione dell'algoritmo, a prescindere dal linguaggio utilizzato Possiamo già stabilire

→

che ci sono diversi algoritmi che possono risolvere lo stesso problema ma qualcuno lo fa

meglio (=meno tempo/meno operazioni) e questa cosa prescinde dalla macchina e dal

linguaggio di programmazione LA SOLUZIONE AL MIO PROBLEMA NON DEVE ESSERE SOLO

→

EFFICACE MA DEVE ESSERE ANCHE EFFICIENTE →

[RICORDATI QUESTA FRASE ALL’ESAME - E RICORDATI ANCHE CHE GLI ESERCIZI CHE FAREMO IN

CLASSE SONO RIVOLTI AD UN’ANALISI CRITICA DEL PERCHÉ TRA 2 ALGORITMI CHE RISOLVONO LO

STESSO PROBLEMA UNO È PIù BUONO DELL’ALTRO]

QUALI SONO LE QUALITÀ FORMALI DI UN ALGORITMO? può sempre capitare una domanda

del genere all’esame

A prescindere dalla forma di rappresentazione un buon algoritmo deve essere caratterizzato

da 4 proprietà fondamentali:

1)​ Ordinalità: : le operazioni descritte dall’algoritmo devono svolgersi secondo una

Consideriamo come esempio una ricetta… prima fai l’impasto e

sequenza definita :

poi inforni non l’incontrario stessa cosa vale per l’algoritmo non posso scrivere sul

→

monitor il risultato senza aver addirittura l’input su cui lavorare

2)​ Eseguibilità: ogni operazione che io scrivo all’interno di un algoritmo deve essere

La ricetta non può prevedere "un

possibile, non deve essere astrusa o assurda:

cucchiaino di polvere di fata" tra gli ingredienti! stesso modo un passo nel mio

→Allo

algoritmo non può essere usata la magia nera per ottenere questo risultato

3)​ Assenza di ambiguità: le operazioni devono essere note e condivise tra ideatore ed

Il "quanto basta" usato nelle ricette viola questo requisito!

esecutore:

4)​Terminazione: deve essere garantita la terminazione delle operazioni, entro un

numero finito di passi, cioè un algoritmo DEVE iniziare e DEVE finire e UN ALGORITMO

CHE NON TERMINA NON È UN ALGORITMO: "…mettere in forno a 180° per 30' e servire

caldo. Buon appetito!" Non posso avere algoritmi che vadano all’infinito!

→

NOTA: il numero di passi di un algoritmo è un indicatore dell'efficienza Se per risolvere

→

un problema io ci metto 100 passi è una cosa ma se per lo stesso problema ce ne

metto 10 di passi sicuramente quest’ultimo è più efficiente Tutti e due però godono

→

della proprietà di terminazione

ALCUNI ESEMPI:

- Somma dei primi "n" interi:

• Partendo da 0, incremento di un valore pari all'intero successivo: Ordinalità (OK),

Eseguibilità (OK), Assenza di Ambiguità (OK), Terminazione (OK) 0+1+2+3+4+5+...+n-1+n

⇒

- Calcolo di tutte le cifre decimali di

• Effettuo la divisione aritmetica tra una circonferenza ed il suo diametro:

Ordinalità (OK)

-​ Eseguibilità (OK)

-​ Assenza di Ambiguità (OK)

-​ Terminazione (KO!) Perché le cifre decimali di sono infinite NON È UN

→ →

-​

ALGORITMO