Fondamentidi informatica Algoritmi

(1)

Fondamenti di informatica Fondamenti di informatica dell'informazione – UniPR dell'informazione – UniPR unipr.it/people/tomamic/unipr.it/people/tomamic/

Algoritmi

Fondamenti di informatica

Michele Tomaiuolo

[email protected]

(2)

Tomaiuolo – Fondamenti di informaticaTomaiuolo – Fondamenti di informatica . Ingegneria dell'informazione – UniPR. Ingegneria dell'informazione – UniPR p://www.ce.unipr.it/people/tomamic/p://www.ce.unipr.it/people/tomamic/

Informatica

Informatica: information automatique

Programmatore: individua una sequenza di istruzioni per risolvere un problema

Calcolatore, o automa: esegue istruzioni

(3)

Dal problema alla soluzione

Analisi Analisi

Problema

Codifica Codifica

Compilazione Compilazione Descrizione

Descrizione

Soluzione

informale

Algoritmo semi-formale

Codice alto livello

Codice macchina

Soluzione

Programmatore

(4)

Algoritmo

Il termine deriva dal matematico arabo Al-Khwarizmi (IX sec. DC)

Metodo per sommare due numeri nel sistema hindu

Medioevo: algorismus = complesso di operazioni nel calcolo con numeri arabi

Oggi: algoritmo = sequenza finita di passi effettuabili

per risolvere una classe di problemi in un tempo finito

(5)

Elementi di un algoritmo

Passi elementari: azioni atomiche non

scomponibili in azioni più semplici

Processo, o anche

esecuzione: sequenza ordinata di passi

Dati in ingresso:

istanza del problema

(6)

Proprietà degli algoritmi

Finitezza: composto da un numero finito di passi elementari

Non ambiguità (determinismo): i risultati non variano in funzione della macchina/persona che esegue

l'algoritmo

Realizzabilità: deve essere eseguibile con le risorse a disposizione

Efficienza: preferibile uso minimo delle risorse

(7)

Classi di problemi

Problemi non risolvibibili

Es. Questa frase è falsa

Incompletezza Gödel; indecidibilità terminazione

∀ formalizzazione della matematica che assiomatizza ℕ

→ ∃ proposizione né dimostrabile né confutabile

Risolvibili

Trattabili (costo accettabile, “polinomiale”)

Non trattabili (costo “esponenziale”)

(8)

L'algoritmo della biblioteca

Per prendere un libro in biblioteca...

1. Si cerca la scheda del libro nello schedario (schede in ordine per autore e poi per titolo)

2. Si segna su un foglietto il numero di scaffale e la posizione del libro

3. Si ricerca lo scaffale indicato

4. Si accede alla posizione del libro 5. Lo si preleva

6. Si registra: data del prestito e nome dell'utente

Passi non elementari: scomposizione ricorsiva

in sottoproblemi via via più semplici (top-down)

(9)

Cercare una scheda

Il primo passo può essere

espanso nel seguente insieme di passi (sottoprocedura):

1. Si prende la prima scheda dello schedario

2. Autore e titolo coincidono con quello ricercato?

Si: scheda trovata, ricerca conclusa No: si passa alla scheda successiva 3. Si torna a ripetere il controllo (2)

4. Esaurite le schede, il libro non è nella biblioteca

(10)

Cercare più velocemente

Su schedario ordinato si può fare più in fretta

1. Prendere scheda centrale tra quelle considerate (all'inizio tutte)

2. Autore/titolo coincidono con quelli ricercati?

Si: scheda trovata; ricerca finita

3. Autore/titolo vengono dopo quelli cercati?

Si: interessa solo la prima parte delle schede

No: interessa solo la seconda parte delle schede 4. Si ripete tutto sull'insieme dimezzato (1)

5. Esaurite le schede, il libro non è nella biblioteca

(11)

Calcolo MCD (1)

Dati due numeri naturali, determinare il loro Massimo Comun Divisore MCD(m, n)

1. Costruire insieme divisori 1° numero 2. Costruire insieme divisori 2° numero 3. Intersecare i due insiemi

4. Individuare nell'intersezione l'elemento più grande

Nota: scomposizione in passi non elementari

(12)

Calcolo MCD (2)

Dati due numeri naturali, determinare il loro Massimo Comun Divisore MCD(m, n)

1. Scomporre in fattori primi i due numeri 2. Considerare solo fattori comuni

3. Prendere quelli con esponente più piccolo 4. Moltiplicarli tra loro

Es. 54 = 2

¹

· 3

³

; 48 = 2

⁴

· 3

¹

(13)

Calcolo MCD (3)

Dati due numeri naturali, determinare il loro Massimo Comun Divisore MCD(m, n)

1. Se n = 0 → MCD = m; finito 2. r ← m – n; m ← n; n ← r 3. Ripetere dal punto 1

Euclide: MCD(m, n) = MCD(n, m-n), se n > 0 x è divisore di m ed n ↔ x è divisore di n ed m-n

m=kx; n=hx; → m-n=kx-hx=(k-h)x; …

(14)

Calcolo MCD (4)

Dati due numeri naturali, determinare il loro Massimo Comun Divisore MCD(m, n)

1. Se n = 0 → MCD = m; finito

r ← m

^mod

n (resto divisione intera); m ← n; n ← r 1. Ripetere dal punto 1

Euclide: MCD(m, n) = MCD(n, m

^mod

n), se n > 0 x è divisore di m ed n ↔ x è divisore di n ed m

^mod

n;

m

^mod

n = m - n·q = kx - hxq = (k – hq)x; …

(15)

Rappresentazione algoritmi

Occorre rappresentare:

I dati

I passi necessari

Il loro corretto ordine di esecuzione

Due formalismi principali

Diagrammi di flusso

Pseudo codice

(16)

Descrizione dei dati

Variabili (contenitori di valori) necessarie per esprimere le varie istanze di problemi

Una variabile si definisce in termini di:

Nome: il suo identificatore

Tipo: l’insieme dei valori che può assumere (carattere, stringa, intero, reale, booleano)

Valore: il valore assunto attualmente dalla var.

Non confondere nome, tipo e valore!

(17)

Tipi di istruzioni

Assegnamento ed espressioni aritmetico-logiche Istruzioni di I/O

Strutture di controllo

(18)

Istruzioni di assegnamento: depositare un valore in una variabile

A ← 5

Espressioni aritmetiche: eseguire un calcolo aritmetico (e depositarne il risultato)

B + C

A ← A + B

Espressioni logiche: confronto o valutazione della veracità di una espressione logica

A = 5 A ≤ B

Operazioni aritmetiche...

Non è un assegnamento, come sarebbe in C++

(19)

Istruzioni di I/O

Istruzioni di lettura: leggere dei dati da un dispositivo esterno (es. tastiera)

Leggi A

Istruzioni di scrittura: scrivere dei dati su un dispositivo esterno (es. schermo)

Scrivi A

(20)

Strutture di controllo

Tre tipi di strutture di controllo:

Sequenza lineare

Esecuzuione condizionata Iterazione

Teorema di Böhm-Jacopini: è possibile scrivere algoritmi per risolvere qualunque problema usando solo queste strutture di

controllo (purché esista un algoritmo risolutivo)

(21)

Diagramma di flusso

Flow-chart: formalismo grafico per gli algoritmi

Descrizione più efficace e meno ambigua di una descrizione a parole

Costituito da due tipi di entità:

Nodi Archi

È un grafo orientato

Passi di un algoritmo e loro sequenza

(22)

Tipi di nodi

Start Start

StopStop

Var ← Expr Var ← Expr

Condiz.

No

VarVar

ExprExpr

Si

Inizio

Fine

Elaborazione / assegnamento

Decisione

Lettura dati

Scrittura dati

Expr1 = Expr2 Expr1 ≠ Expr2 Expr1 < Expr2 Expr1 ≤ Expr2 Expr1 > Expr2 Expr1 ≥ Expr2 Expr1 = Expr2 Expr1 ≠ Expr2 Expr1 < Expr2 Expr1 ≤ Expr2 Expr1 > Expr2 Expr1 ≥ Expr2

(23)

Strutture di controllo

While

Si

I No O

Do-While

I

If-Then-Else If-Then

No

Si O

I

Si O

I

Es. “Battere gli albumi finché non

montano”

Es. “Battere gli albumi finché non

montano”

Es. “Se non c'è il lievito, usare

due cucchiaini di bicarbonato”

Es. “Se non c'è il lievito, usare

due cucchiaini di bicarbonato”

(24)

Somma di 3 numeri

Start Start

Var1 Var1 Var2 Var2

Var3 Var3

Somma ← Var1 + Var2 + Var3 Somma ← Var1 + Var2 + Var3

Somma Somma

Stop Stop

(25)

Somma di N numeri

Start Start

I ← 0 Somma ← 0

No NN

Si I < N

I < N VarVar I ← I + 1

Somma ← Somma + Var I ← I + 1

Somma ← Somma + Var Controllo su

variabile I Controllo su

variabile I

Variabile I incrementata

nel corpo del ciclo Variabile I incrementata

nel corpo del ciclo

(26)

Pseudo codice

Sorta di linguaggio che descrive un algoritmo attraverso istruzioni simili alle istruzioni di un linguaggio di programmazione

Si descrivono algoritmi utilizzando pseudo codice perché:

Più rapidi per appuntare bozze di soluzioni

Semplice (…) passare dalla descrizione in pseudo

codice alla effettiva descrizione in un linguaggio di

programmazione

(27)

Strutture di controllo

Condizione semplice

Se condizione { …

}

Condizione a due vie

Se condizione { …

} Altrimenti { …

Iterazione

Finché condizione { …

}

Iterazione

Ripeti { …

} Finché condizione

(28)

Somma di 3 numeri

Leggi Var1 Leggi Var2 Leggi Var3

Somma ← Var1 + Var2 + Var3

Scrivi Somma

(29)

Somma di N numeri

Leggi N I ← 0

Somma ← 0

Finché I < N { Leggi Var

Somma ← Somma + Var I ← I + 1

}

Scrivi Somma

(30)

Programmazione top-down

Tecnica consistente nella scomposizione ricorsiva di un problema in sotto problemi

Si presta molto bene per la definizione di algoritmi con i diagrammi di flusso

All’inizio il diagramma di flusso è rappresentato da un nodo (“soluzione al problema”)

Questo nodo viene scomposto in una rete di nodi, in modo ricorsivo

La scomposizione termina quando i singoli nodi

rappresentano solo istruzioni eseguibili

(31)

– Fondamenti di informatica – Fondamenti di informatica ia dell'informazione – UniPRia dell'informazione – UniPR unipr.it/people/tomamic/unipr.it/people/tomamic/

Somma di N numeri

Start Start

Leggi e somma i numeri Leggi e somma i numeri

Inizializzazione Inizializzazione

I ← 0 Somma ← 0

I ← 0 Somma ← 0 NN

I < N I < N

No

VarVar Si

Start Start

StopStop

Somma di N numeri Somma di N numeri

I ← I + 1

Somma ← Somma + Var I ← I + 1

Somma ← Somma + Var

(32)

Sistema software ad oggetti

Sistema procedurale

Insieme di procedure che si chiamano tra loro

Sistema ad oggetti

Insieme di oggetti che si scambiano messaggi Per richiedere ad altri l’esecuzione di servizi

La complessità diminuisce tanto più quanto…

Lo stato dei singoli oggetti è nascosto

L’insieme dei servizi offerti dai singoli oggetti è coeso

(ma generale)

(33)

Approccio allo sviluppo

Programmazione procedurale: top-down

Analisi problema x trovare algoritmo risolutore

Scomposizione problema in problemi più semplici

OOP: top-down e bottom-up (riuso)

Analisi problema e descrizione degli oggetti che ne fanno parte (astrazioni generali e coese)

Scomposizione oggetti in parti più semplici (e messaggi/servizi scambiati)

Definizione e riuso oggetti relativamente semplici

(34)

Modularità e astrazione

Modularità

Codice di un oggetto scritto e mantenuto indipendentemente dal resto

Oggetto già creato passato facilmente tra gli altri componenti all'interno del sistema

Information-hiding o data-encapsulation

Interazione solo con i metodi di un oggetto

→ Dettagli interni dell'implementazione nascosti al

mondo esterno (black-box)

(35)