Slide capitolo 1

Algoritmi e Strutture Dati
Capitolo 1 - Introduzione
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view
a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Introduzione
Problema computazionale
✦
✦
La relazione formale che intercorre fra l'input e l'output desiderato
Algoritmo
✦
La descrizione di una sequenza di azioni che un esecutore deve
compiere per giungere alla soluzione di un problema
✦
Gli algoritmi rappresentano e organizzano input, output
e tutti i dati intermedi necessari per lo svolgimento
✦
Esempio
✦
Input: ingredienti
Algoritmo: ricetta
✦
Output: piatto cucinato
Esecutore: cuoco
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Un po' di storia
Algoritmi nella storia
✦Papiro di Ahmes (algoritmo per la moltiplicazione)
✦Algoritmi di tipo numerico furono studiati da matematici babilonesi
ed indiani
✦Algoritmi in uso fino a tempi recenti furono studiati dai matematici
greci più di 2000 anni fa
✦Algoritmo di Euclide per il Massimo Comune Divisore
✦Algoritmi geometrici (calcolo di tangenti, sezioni di angoli, ...)
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Un po' di storia
Abu Abdullah Muhammad bin Musa
al-Khwarizmi
✦Al-Kitāb al-muḫtaṣar fī ḥisāb al-ğabr
wa-l-muqābala
✦Famoso per:
✦essere uno dei padri dell'algebra
✦aver introdotto i numeri indiani
nel mondo occidentale
✦un notevole influsso sulle lingue:
✦algorismus, algoritmo, algorithm
✦algebra
✦spagnolo: guarismo
portoghese: algarismo
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Problema computazionale: esempi
Minimo
✦
Il minimo di un insieme A è l’elemento di A che è minore o uguale ad
ogni elemento di A
✦
Ricerca
✦
Sia A=a1,...,an una sequenza di dati ordinati e distinti, a1 < a2 < ··· < an.
Eseguire una ricerca della posizione di un dato v in A consiste nel
restituire l’indice corrispondente, se v è presente, oppure 0, se v non è
presente
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Algoritmo: esempio
Minimo
✦
Per trovare il minimo di un insieme, confronta ogni elemento con tutti
gli altri; l’elemento che è minore di tutti è il minimo.
✦
Ricerca
✦
Per trovare un valore v nella sequenza A, confronta v con tutti gli
elementi di A, in ordine, e restituisci la posizione corrispondente;
restituisci 0 se nessuno degli elementi corrisponde.
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Problemi
Le descrizioni precedenti presentano diversi problemi:
✦
Descrizione
✦Descritti in linguaggio naturale, imprecisi
✦Abbiamo bisogno di un linguaggio più formale
✦
Valutazione
✦Esistono algoritmi “migliori” di quelli proposti?
✦Dobbiamo definire il concetto di migliore
✦
Progettazione
✦Questi problemi sono semplici
✦Problemi più complessi devono essere affrontati con opportune
tecniche di programmazione
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Come descrivere un algoritmo
E' necessario utilizzare una descrizione il più possibile formale
✦
Indipendente dal linguaggio: “Pseudo-codice”
✦
Particolare attenzione va dedicata al livello di dettaglio
✦
Da una ricetta di canederli (google:canederli ricetta), leggo:
“... amalgamate il tutto e fate riposare un quarto d'ora...”
✦
✦
Cosa significa “amalgamare”? Cosa significa “far riposare”?
✦
E perché non c'è scritto più semplicemente “prepara i canederli”?
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Esempio: ricerca del minimo in un vettore
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Ricerca in un array ordinato
Problema
✦
Dato un vettore A contenente n elementi, verificare se un certo
elemento v è presente
✦
✦
Esempi: elenco del telefono, dizionario
Una soluzione “banale”
✦
Scorro gli elementi in ordine, finché non trovo
un oggetto “maggiore o uguale” a v
✦
1
5
12
15
20
23
32
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
21
Ricerca in un array ordinato
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Pseudo-codice
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Pseudo-codice
Tipi di dato composto
✦
✦
Vettori, matrici
✦
Record
✦
Puntatori
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Ricorsione
Versioni iterative / ricorsive
✦
✦
Ricorsione di coda
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Problemi
Le descrizioni precedenti presentano diversi problemi:
✦
Descrizione
Descritti in linguaggio naturale, imprecisi
✦
Abbiamo bisogno di un linguaggio più formale
✦
✦
Valutazione
Esistono algoritmi “migliori” di quelli proposti?
✦
Dobbiamo definire il concetto di migliore
✦
✦
Progettazione
Questi problemi sono semplici
✦Problemi più complessi devono essere affrontati con oppurtune
tecniche di programmazione
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi
Risolve correttamente il problema?
✦
✦
Dimostrazione matematica, descrizione “informale”
✦
Nota: Alcuni problemi non possono essere risolti
✦
Nota: Alcuni problemi vengono risolti in modo approssimato
Risolve il problema in modo efficiente?
✦
✦
Definizione di “efficienza”?
✦
Alcuni problemi non possono essere risolti in modo efficiente
✦
Esistono soluzioni “ottime”: non è possibile essere più efficienti
Quali altre proprietà entrano in gioco?
✦
Semplicità, modularità, manutenibilità, espandibilità, sicurezza e
robustezza
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - correttezza
Concetto di invariante
✦
✦
Condizione sempre vera in un certo punto del programma
✦
Esempi:
Invariante di ciclo:
✦
una condizione che è sempre vera all'inizio di un ciclo
✦
“inizio del ciclo”: da definire
✦
Invariante di classe:
✦
una condizione che è sempre vera al termine dell'esecuzione di
un metodo su una classe
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - correttezza
Invariante di min()
✦
All'inizio di ogni iterazione del ciclo for, la variabile min contiene il
minimo parziale degli elementi A[1 .. i − 1]
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - correttezza
Il concetto di invariante di ciclo ci aiuta a dimostrare la correttezza di un
algoritmo:
✦Inizializzazione (caso base):
✦la condizione è vera all'inizio
✦Conservazione (passo induttivo):
Induzione
✦se la condizione è vera prima di un'iterazione
del ciclo, allora rimane vera al termine
(quindi prima della successiva iterazione)
✦Conclusione:
✦Quando il ciclo termina, l'invariante deve
rappresentare la “correttezza” dell'algoritmo
✦Domanda
✦Dimostrare che l'invariante di min() è rispettato
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - correttezza
Domanda: dimostrazione di correttezza di binarySearch()
✦
✦
Suggerimento: per induzione sulla dimensione dell’input
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - efficienza
Complessità di un algoritmo
✦
Analisi delle risorse impiegate da un algoritmo per risolvere un
problema, in funzione della dimensione e dal tipo dell'input
✦
Risorse
✦
✦
Tempo: tempo impiegato per completare l'algoritmo
✦
Spazio: quantità di memoria utilizzata
Banda: quantità di bit spediti
✦
Algoritmi distribuiti
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - efficienza
Contiamo il numero di confronti per il problema del minimo
✦
✦
Algoritmo “banale” accennato nell’introduzione: n(n-1)/2
✦
Algoritmo più efficiente: n-1
Perché contare i confronti?
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - efficienza
Contiamo il numero di confronti per il problema della ricerca
✦Algoritmo “banale” accennato nell’introduzione: n-1
✦Algoritmo più efficiente: log n
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Valutazione algoritmi - altre proprietà
L’elenco può essere lungo:
✦
Semplicità, modularità, manutenibilità, espandibilità, sicurezza e
robustezza
✦
Out-of-scope per algoritmi e strutture dati
✦
✦
Ingegneria del software
Un commento:
✦
✦
Alcune proprietà hanno un costo aggiuntivo in termini di prestazioni
✦Codice modulare → costo gestione chiamate
Java bytecode → costo interpretazione
✦
Progettare algoritmi efficienti è un prerequisito per poter pagare
questi costi
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Problemi
Le descrizioni precedenti presentano diversi problemi:
✦
Descrizione
✦
Descritti in linguaggio naturale, imprecisi
Abbiamo bisogno di un linguaggio più formale
✦
✦
Valutazione
Esistono algoritmi “migliori” di quelli proposti?Dobbiamo definire il
concetto di migliore
✦
✦
Progettazione
✦
Questi problemi sono semplici
Problemi più complessi devono essere affrontati con oppurtune
tecniche di programmazione
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola
Come organizzare un algoritmo
Base di conoscenza
✦
Liste
Strutture di dati
✦
Problemi “classici” e
loro soluzioni
✦
Tecniche di progettazione
✦
Divide-et-impera
✦
Programmazione dinamica
✦
Greedy
✦
Ricerca locale
✦
Backtrack
✦
Probabilismo
✦
Bertossi, Montresor, Algoritmi e strutture di dati © 2014 De Agostini Scuola