• Non ci sono risultati.

ALGORITMI E STRUTTURE DATI

N/A
N/A
Info
Scarica
Protected

Academic year: 2022

Condividi "ALGORITMI E STRUTTURE DATI"

Copied!
62
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 62 pagine )

Testo completo

(1)

ALGORITMI E STRUTTURE DATI

INFORMAZIONI SUL CORSO COSA È UN ALGORITMO ESEMPI DI ALGORITMI

(2)

INFORMAZIONI SUL CORSO

STRUTTURA DEL CORSO

▸ Introduzione alla progettazione di algoritmi (complessità, ricorsione, strutture dati)

▸ Ordinamento e selezione

▸ Strutture dati per l’indicizzazione (alberi binari di ricerca, hash)

▸ Strutture relazionali (grafi e algoritmi su grafi)

(3)

INFORMAZIONI SUL CORSO

LIBRI E MATERIALE

▸ Cormen, Leiserson, Rivest, Stein

Introduction to Algorithms (Introduzione agli algoritmi) 3rd edition.

MIT Press (McGraw Hill per l’edizione italiana) (È un libro grosso, con tanti

argomenti oltre a quelli che vedremo).

AL GO RI TH M S

I N T RO D U CT I O N T O

T H I R D E D I T I O N T H O M A S H.

CH ARL ES E.

R O N A L D L.

C L I F F O R D ST EI N RI VEST L EI SE RSO N C O RM EN

(4)

INFORMAZIONI SUL CORSO

SOFTWARE E MATERIALE DEL CORSO

▸ Il materiale del corso (slide ed esempi di codice) sarà disponibile online sul sito e-learning del corso

▸ Come software si utilizzerà Python versione 3.6 o successive

(disponibile su https://www.python.org)

▸ Solitamente preinstallato su macOS e Linux

▸ È possibile usare un ambiente Python 3 online senza

installazione su repl.it (https://repl.it)

(5)

INFORMAZIONI SUL CORSO

ESAME E HOMEWORK

▸ L’esame avrà una parte scritta ed una orale, obbligatorie.

▸ Scritto: risoluzione di problemi tipo quelli visti durante il corso.

▸ Orale: domande sulla teoria e risoluzione di problemi, vale ±5 punti.

▸ Provette: ci saranno due provette intermedie. Chi le supera entrambe può saltare lo scritto (vale la media delle provette come voto dello scritto).

▸ Homework: verranno dati settimanalmente alcuni esercizi per casa, sia problemi da risolvere che esercizi implementativi. Chi li consegna in tempo, in funzione del voto preso, avrà dei punti bonus allo scritto (massimo 3 punti, ma il passaggio da 29 a 30 costa due punti).

▸ La lode si può prendere solo con l’orale, di norma con un voto sullo scritto di

almeno 27.

(6)

INFORMAZIONI SUL CORSO

LET’S START!

Cos’è un algoritmo?

(7)

ALGORITMI

COSA È UN ALGORITMO? (DEFINIZIONE INFORMALE)

Una procedura computazione ben definita

che prende un valore o insieme di valori come input e produce un valore o insieme di valori come output Un algoritmo è quindi un insieme di operazioni

che trasformano un input in un output

(8)

ALGORITMI

ALCUNI ESEMPI COMUNI

Input: un insieme ben definito di pezzi di lego Output:

Le istruzioni contengono un insieme di passi non ambigui che trasformano l’input nell’output

(9)

ALGORITMI

ALCUNI ESEMPI COMUNI

Input: un insieme ben definito di pezzi di ingredienti

Output: tartufi al tiramisù

Anche in questo caso le istruzioni contengono un insieme di passi non ambigui (più o meno) che trasformano l’input nell’output

(10)

ESEMPIO: ALGORITMI DI ORDINAMENTO

ORDINARE UN MAZZO DI CARTE

Abbiamo un mazzo di carte che è stato mescolato

Vogliamo disporre le carte in ordine crescente

Siamo in grado di dare un algoritmo?

Iniziamo a formalizzare il problema

🂣 🂤 🂡 🂦 🂥 🂢

(11)

🂦 🂥 🂤 🂣 🂢 🂡

🂣 🂤 🂡 🂦 🂥

ESEMPIO: ALGORITMI DI ORDINAMENTO

ORDINARE UN MAZZO DI CARTE

Dati in ingresso (input)

Un mazzo di carte non necessariamente ordinate

Dati in uscita (output)

Una permutazione del mazzo di carte fornito in input in cui tutte le carte sono ordinate in ordine crescente

🂢

(12)

🂦 🂥 🂤 🂣 🂢 🂡

🂣 🂤 🂡 🂦 🂥

ESEMPIO: ALGORITMI DI ORDINAMENTO

ORDINARE UN MAZZO DI CARTE

Dati in ingresso (input)

Un mazzo di carte non necessariamente ordinate

Dati in uscita (output)

Una permutazione del mazzo di carte fornito in input in cui tutte le carte sono ordinate in ordine crescente

CI SERVE UNA PROCEDURA MECCANICA CHE DALL’INPUT PRODUCA L’OUTPUT

🂢

(13)

ESEMPIO: ALGORITMI DI ORDINAMENTO

IDEE?

🂢🂥 🂦 🂤 🂡 🂣

(14)

ESEMPIO: ALGORITMI DI ORDINAMENTO

IDEA: INSERIMENTO DI UNA CARTA ALLA VOLTA

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥 🂦 🂤 🂡 🂣

(15)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥 🂦 🂤 🂡 🂣

(16)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥 🂦 🂤 🂡 🂣

(17)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥 🂦 🂤 🂡 🂣

CONTINUEREMO AD ESEGUIRE QUESTE ISTRUZIONI

FINCHÉ LA CONDIZIONE

NON SARÀ SODDISFATTA

(18)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥 🂦 🂤 🂡 🂣

X

(19)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥 🂦 🂤 🂡 🂣

X

(20)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥 🂦 🂤 🂡 🂣

X

NON DOBBIAMO FARE NIENTE

(NON CI SONO ALTRE CARTE GIÀ IN ORDINE)

(21)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Non Ordinate Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥 🂦 🂤 🂡 🂣

X

(22)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂤 🂡 🂣

(23)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂤 🂡 🂣

2 > 5

? NO

IL TEST FALLISCE

E QUINDI PROSEGUIREMO

CON L’ISTRUZIONE NUMERO…

(24)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂡 🂣 🂤

(25)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂡 🂣 🂤

(26)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 5 > 6

? NO

🂡 🂣 🂤

(27)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂡 🂤 🂣

(28)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂡 🂤 🂣

(29)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂡 🂤 🂣

QUI INVECE IL TEST HA SUCCESSO QUINDI DOBBIAMO ESEGUIRE

L’OPERAZIONE DI SCAMBIO

6 > 1

? SI

(30)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

ORA CHE DOBBIAMO FARE?

CONTINUIAMO CON L’ISTRUZIONE 2.3

O TORNIAMO ALLA 2.1?

(31)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

ORA CHE DOBBIAMO FARE?

CONTINUIAMO CON L’ISTRUZIONE 2.3 O TORNIAMO ALLA 2.1?

5 > 1

? SI

(32)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

(33)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 2 > 1

? SI

🂣

(34)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

(35)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

(36)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 🂣

(37)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦 🂤

🂡 6 > 4

? SI

🂣

(38)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 🂣

(39)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 5 > 4

? SI

🂣

(40)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 🂣

(41)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 2 > 4

? NO

🂣

(42)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 🂣

(43)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

Carte Non Ordinate

🂦

🂤

🂡 🂣

(44)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

6 > 3

? SI

(45)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

(46)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

5 > 3

? SI

(47)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

(48)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

4 > 3

? SI

(49)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

(50)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

2 > 3

? NO

(51)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

1. Inizialmente non si hanno carte ordinate 2. Finché ci rimangono carte non ordinate

2.1. Prendi una carta dalla lista di carte non ordinata e chiamala X 2.2. Metti X in fondo alla lista di carte ordinate

2.3. Finché la carta che precede X ha valore maggiore del valore di X, scambia X con la carta che lo precede

🂢 🂥

X

🂦

🂤

🂡 🂣

Carte

Non Ordinate

2 > 3

? NO

ORA LA CONDIZIONE NON È PIÙ VERA

E ABBIAMO TERMINATO

(52)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

Carte Ordinate

🂢 🂤 🂥 🂦

🂡 🂣

Siamo riusciti ad ottenere un mazzo di carte ordinato Rimangono alcune domande:

‣ Correttezza: questo algoritmo funziona con ogni input?

‣ Efficienza: quanti passi ci mettiamo ad ordinare un mazzo di carte al crescere di ?

n n

(53)

ESEMPIO: ALGORITMI DI ORDINAMENTO

OPZIONE 2: INSERIMENTO DI UNA CARTA ALLA VOLTA

▸ Quante comparazioni dobbiamo fare nel caso peggiore?

▸ Inserire una carte nella lista della carte ordinate richiede non più di comparazioni

▸ Dobbiamo inserire carte nella lista delle carte ordinate per ordinarle tutte

▸ Quindi il numero di comparazioni è limitato superiormente da

n

n

n 2

(54)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero più piccolo di m ed n che li divide entrambi.

Idea: provo tutti i possibili divisori, dal più grande al più piccolo….

(55)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero più piccolo di m ed n che li divide entrambi.

Idea: provo tutti i possibili divisori, dal più grande al più piccolo….

def MCD(m,n):

mcd = 0

for i=1 to floor(sqrt(n)):

if i | n:

if n//i | m:

return n//i else if i | m mcd = i return mcd

(56)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero più piccolo di m ed n che li divide entrambi.

Idea: provo tutti i possibili divisori, dal più grande al più piccolo….

def MCD(m,n):

mcd = 0

for i=1 to floor(sqrt(n)):

if i | n:

if n//i | m:

return n//i else if i | m mcd = i return mcd

Complessità

l’algoritmo fa nel caso peggiore sqrt(n) iterazioni del ciclo for.

Ci piace questa complessità?

Proviamo con n = 210?

(57)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero più piccolo di m ed n che li divide entrambi.

Idea: provo tutti i possibili divisori, dal più grande al più piccolo….

def MCD(m,n):

mcd = 0

for i=1 to floor(sqrt(n)):

if i | n:

if n//i | m:

return n//i else if i | m mcd = i return mcd

Complessità

l’algoritmo fa nel caso peggiore sqrt(n) iterazioni del ciclo for.

Ci piace questa complessità?

Proviamo con n = 210?

e con 2100?

(58)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero p più piccolo di m ed n che li divide entrambi.

(59)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero p più piccolo di m ed n che li divide entrambi.

Idea: ci penso un poco…

partiamo da m = qn + r:

se r = 0, allora n | m, e ho finito

se r≠ 0, siccome p | m e p | n, allora p | r quindi MCD(m, n) = MCD(n, r)

(60)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero p più piccolo di m ed n che li divide entrambi.

def Euclide(m,n):

while n≠0:

m, n = n, m mod n return m

Idea: ci penso un poco…

partiamo da m = qn + r:

se r = 0, allora n | m, e ho finito

se r≠ 0, siccome p | m e p | n, allora p | r quindi MCD(m, n) = MCD(n, r)

(61)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero p più piccolo di m ed n che li divide entrambi.

def Euclide(m,n):

while n≠0:

m, n = n, m mod n return m

Idea: ci penso un poco…

partiamo da m = qn + r:

se r = 0, allora n | m, e ho finito

se r≠ 0, siccome p | m e p | n, allora p | r quindi MCD(m, n) = MCD(n, r)

Complessità:

Partiamo da m = qn + r m > n, ergo q≥1 e n>r

Segue m = qn + r ≥ qr + r ≥ r + r = 2r Quindi r ≤ m/2.

Ergo in due passi di Euclide, m dimezza.

L’algoritmo termina dopo non più di 2 log2 m passi.

(62)

ALGORITMI

EFFICIENCY MATTERS: MASSIMO COMUNE DIVISORE

Input: due numeri interi m ed n, m>n

Output: il più grande intero p più piccolo di m ed n che li divide entrambi.

def Euclide(m,n):

while n≠0:

m, n = n, m mod n return m

Idea: ci penso un poco…

partiamo da m = qn + r:

se r = 0, allora n | m, e ho finito

se r≠ 0, siccome p | m e p | n, allora p | r quindi MCD(m, n) = MCD(n, r)

Compariamo la complessità quando m = 2100 e n = 2100-1 Complessità:

Partiamo da m = qn + r m > n, ergo q≥1 e n>r

Segue m = qn + r ≥ qr + r ≥ r + r = 2r Quindi r ≤ m/2.

Ergo in due passi di Euclide, m dimezza.

L’algoritmo termina dopo non più di 2 log2 m passi.

Riferimenti

Scarica adesso ( PDF - 62 pagine - 3.73 MB )

Outline

CONTINUIAMO CON L’ISTRUZIONE 2.3 O TORNIAMO ALLA 2.1?

Documenti correlati

Algoritmi e Strutture Dati

Esistono due classi di memoria: automatica e statica La classe di memoria automatica è relativa a quegli oggetti locali ad un blocco (funzione o programma) che viene liberata

Algoritmi e Strutture Dati

E responsabilità del programmatore controllare che il numero ed il tipo degli argomenti passati ad una funzione corrisponda con quanto specificato nella dichiarazione della

Algoritmi e Strutture Dati

L Insertion Sort è uno algoritmo di ordinamento molto efficiente per ordinare un piccolo numero di elementi. L idea di ordinamento è quella che potrebbe usare un persona

Algoritmi e Strutture Dati

L’array A[p…r] viene “suddiviso” in due sotto- array “non vuoti” A[p… q] e A[q+1…r] in cui ogni elemento di A[p…q] è minore o uguale ad ogni elemento

Algoritmi e Strutture Dati

Lo scopo del gioco è quello di trasferire i dischi dal paletto di sinistra a quello di destra, senza mai mettere un disco su un altro di dimensione più piccola4. Regole

Algoritmi e Strutture Dati

Si noti che l ordine in cui i piatti sono tolti dallo stack è inversa all ordine in cui essi sono stati inseriti nello stack, visto che solo il top dello stack è accessibile..

Algoritmi e Strutture Dati

Nella situazione iniziale, tutti gli elementi sono posti nello Stack H dove l elemento al Top è la testa (Head) della coda, mentre quello al Bottom rappresenta la fine

Algoritmi e Strutture Dati

La funzione crea_lista() crea due puntatori ad elemento, uno di nome p (puntatore al primo elemento della lista) e l'altro di nome punt (puntatore che permette di scorrere la