1

Maurizio Palesi 1

AlgoritmiAlgoritmi

Maurizio Palesi

Maurizio Palesi 2

Cos’èCos’èRisolvere un problema significa individuareun procedimento che permetta di arrivare alrisultato partendo dai dati

Un algoritmo è un metodo per la soluzionedi un problema adatto ad essereimplementato sotto forma di programma

2

Maurizio Palesi 3

Altre Definizioni di AlgoritmoAltre Definizioni di AlgoritmoUn algoritmo si puo` definire come unprocedimento che consente di ottenere unrisultato atteso eseguendo, in undeterminato ordine, un insieme di passisemplici corrispondenti ad azioni sceltesolitamente da un insieme finito

Maurizio Palesi 4

Derivazione del TermineDerivazione del TermineIl termine deriva dal nome del matematicopersiano Muhammad ibn Musa Al-Khwarizmi

Uno dei primi autori ad aver fatto riferimentoesplicitamente a questo concetto

Tuttavia gli algoritmi erano presenti anchenelle antiche tradizioni matematiche

Es., la matematica babilonese, quella cinese o delKerala trasmettevano le conoscenze in formaalgoritmica

3

Maurizio Palesi 5

Semplicita vs. AmbiguitaSemplicita vs. AmbiguitaAffermando che i passi costituenti di unalgoritmo debbano essere “semplici”, siintende soprattutto che essi siano specificatiin modo non ambiguo,

Immediatamente evidenti a chi sarà chiamatoad applicare l'algoritmo, cioè il suo esecutore

Maurizio Palesi 6

Semplicita vs. AmbiguitaSemplicita vs. Ambiguita“Rompete le uova” può essere un passo legittimo di unalgoritmo di cucina, e potrebbe esserlo anche “Aggiungetesale quanto basta” se possiamo assumere che l'esecutoresia in grado di risolvere da solo l'ambiguità di questa frase“Preparate un pentolino di crema pasticciera” non puòprobabilmente considerarsi semplice

Potrebbe però essere associato a un opportuno rimando a un'altrasezione del ricettario, che fornisca un algoritmo apposito per questaspecifica operazione

Infine, una ricetta che preveda la cottura a microonde nonpuò essere preparata da chi è sprovvisto dell'appositoelettrodomestico!

4

Maurizio Palesi 7

Esempi di AlgoritmiEsempi di AlgoritmiRicetta per cucinare gli spaghetti

Metti l’acqua nella pentolaFai bollire l’acquaMetti la pasta nell’acquaAggiungi un pò di saleAttendi 6 minutiScola la pasta

Maurizio Palesi 8

Esempi di AlgoritmiEsempi di AlgoritmiVerifica se un numero è pari o dispari

Prendi il numeroCalcola il resto della divisione intera delnumero per 2Se il resto è zero

Allora il numero è pariAltrimenti il numero è dispari

5

Maurizio Palesi 9

Esempi di AlgoritmiEsempi di AlgoritmiRicerca utente in un elenco telefonico

DatiUn insieme ordinato di coppie <nome, numero>Un nome X da ricercare

1) Leggi la prima coppia <nome, numero>2) Se non hai oltrepassato l'ultima coppia Allora:

Se nome = X allora il numero di telefono di X è quello letto;Altrimenti leggi la prossima coppia e vai al passo 2)

AltrimentiIl nome X cercato non è nell'elenco

Maurizio Palesi 10

Esempi di AlgoritmiEsempi di AlgoritmiRicerca di un utente X in un elenco telefonico(alternativa)

1) Leggi la prima coppia <nome, numero>2) Se non hai oltrepassato l'ultima coppia E nomeprecede X (secondo l'ordine alfabetico) Allora osservala prossima coppia e ripeti il passo 2)3) Se hai oltrepassato l'ultima coppia OPPURE nomesegue X Allora X non è presente nell'elenco4) Altrimenti il numero telefonico di X è l'ultimo letto

6

Maurizio Palesi 11

Proprietà degli AlgoritmiProprietà degli AlgoritmiL'algoritmo è caratterizzato da

Finitezza: Composto da un numero finito di passielementari. Le operazioni sono eseguite un numerofinito di volte

Non ambiguità: I risultati non variano in funzione dellamacchina/persona che esegue l'algoritmo(deterministico)

Realizzabilità: Deve essere eseguibile con le risorse adisposizione

Maurizio Palesi 12

Proprietà degli AlgoritmiProprietà degli Algoritmi… ma gli esempi precedenti possiedonoqueste proprietà?

Problemi presentiAmbiguitàIpotesi implicite sulle capacità dell’esecutoreUso del linguaggio naturale

7

Maurizio Palesi 13

Definire un AlgoritmoDefinire un AlgoritmoPer definire un algoritmo è necessario

Condurre un'attenta analisi del problemaIndividuare i possibili ingressiPrecisare le usciteDefinire completamente e dettagliatamente lasequenza dei passi che portano alla soluzione

E’ conveniente suddividere il problema in piccolisottoproblemi

Maurizio Palesi 14

Rappresentare un AlgoritmoRappresentare un AlgoritmoE’ necessario far riferimento a dei formalismi che

Non introducano ambiguitàSiano universalmente riconosciuti ed interpretati allostesso modo da un generico esecutorePermettano di rappresentare in modo efficace unalgoritmoCostituiscano un utile strumento per poi poter passarealla fase di codifica in un linguaggio di programmazione

8

Maurizio Palesi 15

Rappresentare un AlgoritmoRappresentare un AlgoritmoRappresentazione grafica

Diagramma di flusso (noto anche comediagramma a blocchi o flow-chart)

Rappresentazione testualeNotazione Lineare Strutturata (opseudocode)

Maurizio Palesi 16

Operazioni di BaseOperazioni di BaseLe operazioni primarie sono

Trasferimento di informazioni (istruzioni di I/O)Lettura dati, scrittura risultati, visualizzazione datiintermedi

Esecuzione di calcoli (valutazione espressioni)Istruzioni di assegnamentoStrutture di controllo (che modificano il flussosequenziale di esecuzione delle operazioni)

9

Maurizio Palesi 17

ingresso/uscita

Elaborazione

elab. predefinita

decisione

inizializzazione

inizio/fine

connessioni

documento

input manuale

disco

mem. sequenziale

Simboli ConvenzionaliSimboli Convenzionali

Maurizio Palesi 18

leggi A

scrivi B

Pseudocodice

leggi A

scrivi B

Diagramma a blocchi

Istruzioni di I/OIstruzioni di I/OLettura di dati in ingresso (input) Scrittura dei risultati in uscita (output)

10

Maurizio Palesi 19

A = 5Alla variabile Aviene assegnato ilvalore 5

Istruzione di AssegnamentoIstruzione di AssegnamentoConcetto di variabile

Identificata da un’etichetta/identificatore simbolicoPuò essere comodo pensare alla variabile come ad uncontenitore in cui possiamo memorizzare o reperire deidati utilizzati durante il calcoloL’istruzione di assegnamento permette di assegnare unvalore ad una variabile

Maurizio Palesi 20

A = B + 3

START

ERROREB non è inizializzata

B = 0

START

A = B + 3

START

A = B + 3

leggi B

CORRETTO CORRETTO

Istruzione di AssegnamentoIstruzione di AssegnamentoInizializzazione

All’inizio di un algoritmo una variabile non ha alcun valoreNon ha quindi senso utilizzarla in una espressione (è un errore!)Essa deve essere inizializzata

O esplicitamente mediante un assegnamentoOppure mediante una operazione di lettura

11

Maurizio Palesi 21

Istruzione di AssegnamentoIstruzione di AssegnamentoE’ stato usato il simbolo = per indicare l’istruzione di assegnamentoAlcuni testi/autori indicano invece il simbolo ← (per evitare confusionecon l’operatore di uguaglianza)Dato il seguente frammento di codice

L’esecutore esegue i seguenti passiPrima valuta l’espressione a destra, cioè calcola il valore di A+1 che vale 6Dopo assegna tale valore alla variabile a sinistra, cioè ad AAlla fine dell’esecuzione di quella istruzione quindi, A vale 6

Cosa fa quell’istruzione?

…A = 5A = A + 1

Maurizio Palesi 22

B = 5*(82-35)/7

A = (B+34)/B*2

Diagramma a blocchi Pseudo-codice

B = 5*(82-35)/7

A = (B+34)/B*2

Valutazione delle EspressioniValutazione delle EspressioniL’esecutore è in grado di valutareespressioni aritmetiche

12

Maurizio Palesi 23

Rappresentazione degli AlgoritmiRappresentazione degli AlgoritmiI diagrammi di flusso possono presentarsi

Ad un livello generaleAd un livello particolare

A seconda del livello di dettaglio con cuispecificano le operazioni da compiereE’ opportuno procedere per fasi successive

Un diagramma globale (di massima) per focalizzare leoperazioni essenziali da compiereUn diagramma di flusso più particolareggiato, che tengaconto di operazioni più semplici e più elementari

Maurizio Palesi 24

Tecniche di ProgrammazioneTecniche di ProgrammazioneProgrammazione top-down

Scomposizione iterativa del problema insottoproblemiI sottoproblemi devono essere indipendenti edavere interfacce ben definiteVisibilità dei dettagli di ogni sottoproblema

Programmazione bottom-up