Introduzione al Corso di Algoritmi
Di cosa parliamo oggi:
Una discussione generale su cosa studieremo,perchè lo studeriemo, come lo studieremo, ...
Un esempio illustrativo di cosa studeriemo
Informazione pratiche sul corso:
- Modalità di esame (e come superarlo brillantemente)
- Materiale didattico (libri di testo, materiale di supporto,esercizi di esame...)
- Altro...
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 1/36
Corso di Algoritmi
Obiettivi (ufficiali) del corso: Apprendere metodologieper il progetto ed analisi di algoritmi
Di fatto, acquisiremo strumenti concettuali per larisoluzione di problemi . (Quali problemi? Diqualunque tipo...)
Cosa studieremo?
- Tecniche generali per lo sviluppo di algoritmiefficienti atti a risolvere problemi computazionali diinteresse pratico
- Strumenti per la valutazione degli algoritmi
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 2/36
Perchè studiare algoritmi?
Tecniche algoritmiche permettono di risovere problemi
importantissimi in Informatica (e ben oltre...)
Trasmissione dati in Internet (come si gestisce in pratica il
flusso di dati nei vari router della rete?)
Ricerca nel WEB (come fà Google a trovare le informazioni nel
WEB?)
Bioinformatica (come il DNA determina le nostre
caratteristiche?)
Processi economici (come si gestiscono le aste on-line su
Ebay?, come si effettua la compravendita di azioni su Internet?)
Organizzazione di risorse e servizi (come si schedulano i voli
delle aerolinee? Come si assegnano le frequenze nelle celle
delle reti cellulari?)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 3/36
E non lo dico solo io:
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 4/36
Anche il Corriere della Sera del 15/1/2012!
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 5/36
...e se non siete ancora convinti dell’utilità degli algori tmi, questo dovrebbe...
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 6/36
Iniziamo con un pó di storia...
Il termine Algoritmo deriva dal matematico Persianoal-Khw arizmı (c. 780-850), autore del testo Al-jabrw’al-muqabâla (da cui anche il termine Algebra)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 7/36
Un altro pó di storia...
Algoritmi di tipo numerico furono studiati da matematicibabilonesi ed indiani piú di di 3000 anni fá.
Algoritmi in uso fino a tempi recenti furono studiati daimatematici greci 500 anni a.C.
Esempio: Algoritmo di Euclide per il Massimo ComunDivisore
Esempio: Algoritmi geometrici (calcolo di tangenti,sezioni di angoli, ...)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 8/36
Ma cos’é un Algoritmo?
Algoritmo: procedura computazionale che prende certivalori in input e produce i valori richiesti in outputAlgoritmo: strumento per risolvere un ProblemaComputazionale
Il Problema computazionale (in forma generale oastratta) é definito da una relazione input/output
Un algoritmo é quindi una procedure computazionaleper ottenere la desiderata relazione input/output
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 9/36
Esempi di Problemi Computazionali
Problema dell’Ordinamento:Input: sequenza di numeri 〈a1, . . . , an〉Output: una permutazione 〈a′1, . . . , a
′
n〉 dell’input taleche a′1 ≤ . . . ≤ a′n
Algoritmo di Ordinamento: procedura cheprende in input 〈a1, . . . , an〉 e produce inoutput a′1 ≤ . . . ≤ a′n
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 10/36
Esempi di Problemi Computazionali
Problema della ricerca di un elemento:Input: Tabella A[1 . . . n] ed elemento x
Output: intero i, se x = A[i] per qualche indice i, unmessaggio “Non c’é", altrimenti.
Algoritmo di Ricerca: procedura che prende ininput A[1 . . . n] ed elemento x, e produce inoutput "i" se x = A[i], “Non c’è" altrimenti.
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 11/36
Nella vita reale raramente avrete a che fare con problemi astratti ...
Ciò che accadrà sarà che il vostro capo vi chiederà(ordinerà):
“Mi scriva un programma che elenchi i nostri fornitori in base ai loro tempidi consegna!”
Dovrete avere la capacità di passare da tale problemaconcreto alla sua versione astratta (cioè l’ordinamento) equindi risolverlo con le tecniche che apprenderete in questocorso.
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 12/36
Abbiamo detto che studieremo Algoritmi Efficienti
Cosa intendiamo per Algoritmi Efficienti?
Algoritmi Efficienti = Algoritmi che usano "poche"risorse
Risorse = Tempo e Spazio richiesto dall’algoritmo perprodurre l’output
Problema 1: Come misurare le risorse usate da unalgoritmo? (Analisi degli algoritmi)
Problema 2: Come progettare algoritmi che usano"poche" risorse? (Tecniche generali per il progetto dialgoritmi)
Lo vedremo...
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 13/36
Motivazioni
Perché occuparci di algoritmi efficienti?
Perchè algoritmi efficienti conducono a programmiefficienti
Perchè programmi efficienti si vendono meglio...
Perchè programmi efficienti fanno un miglior usodell’hardware
Perchè programmatori che scrivono programmiefficienti sono piú richiesti...
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 14/36
Obiettivi
Cosa otterrete da questo corso?
Metodi e conoscenze per formulare modelli astratti daproblemi pratici (Problemi Concreti → ProblemiComputazionali)
Metodi e conoscenze per la progettazione di algoritmiefficienti per la risoluzione di problemi computazionali
Metodi e conoscenze per analizzare l’ efficienza dialgoritmi
Un “catalogo" di algoritmi efficienti, pronti per l’uso, perla risoluzione dei piú comuni problemi computazionali
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 15/36
Esempio: Profitto Massimo in anni contigui
Profitti della Ditta ACME-CorporationAnno 1 2 3 4 5 6 7 8 9
Profitto in M$ -3 2 1 -4 5 2 -1 3 -1
Esempi: Tra gli anni 1 e 9 la Ditta ACME ha guadagnato−3 + 2 + 1− 4 + 5 + 2− 1 + 3− 1 = 4 M$, tra gli anni 2 e 6ha guadagnato 2 + 1− 4 + 5 + 2 = 6 M$, tra gli anni 5 e 8ACME ha guadagnato 5 + 2− 1 + 3 = 9 M $
Il Problema del Profitto Massimo in anni contigui è quello ditrovare l’intervallo temporale in cui la Ditta ACME haguadagnato di più (nel nostro esempio l’intervallo (5, 8)).
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 16/36
Astrazione del Problema
Input : un array di reali A[1 . . . N ], il profitto totale neglianni dall’i-esimo allo j-esimo è
V (i, j) =
j∑
x=i
A[x].
Il Problema del Profitto Massimo in anni contigui(PMAC) è quello di trovare indici i ≤ j tali che
∀i′, j′, vale che V (i′, j′) ≤ V (i, j)
Output: V (i, j) tale che
∀i′, j′, vale che V (i′, j′) ≤ V (i, j)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 17/36
Prima Soluzione: Forza Bruta
Idea: Calcolare il valore V (i, j) per ogni coppia i ≤ j, eritornare il valore massimo
VMAX=A[1]for i = 1 to N do
for j = i to N do% qui ci calcoliamo V = V (i, j)V = 0for x = i to j doV = V + A[x]
if V > VMAX then VMAX = Vreturn VMAX
Complessità dell’algoritmo: Θ(N3) (ci sono 3 forinnestati, ciascheduno spazia su al piú N valori)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 18/36
Seconda Soluzione: Approccio Incrementale
Idea: Non è necessario calcolare “separatamente"ciascun V (i, j),ma possiamo usare il fatto che
V (i, j) =∑j
x=iA[x] =∑j−1
x=i A[x]+A[j] = V (i, j−1)+A[j].
VMAX=A[1]for i = 1 to N do
V = 0for j = i to N do
% qui ci calcoliamo V (i, j)V = V + A[j]if V > VMAX then VMAX = V
return VMAX
Complessità dell’algoritmo: Θ(N2) (ci sono 2 forinnestati, ciascheduno spazia su al piú N valori)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 19/36
Terza Soluzione: Divide-et-Impera
Idea: Poni M = ⌊(N + 1)/2⌋. Il PMAC dell’arrayA[1, . . . , N ] deve necessariamente essere uno deiseguenti:
S1: il PMAC dell’array A[1, . . . ,M ],
S1
M M+1oppure S2: il PMAC dell’array A[M + 1, . . . , N ],
S2
M M+1oppure é a "cavallo" di A[M ], ovvero e’ A = A1 ∪ A2
A1 A2
M M+1
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 20/36
Esempio
1 -5 4 2 -7 3 6 -1 2 -4 7 -10 2 6 1 -3
In questo caso S1 = [3, 6] con valore 3 + 6 = 9, eS2 = [2, 6, 1] con valore 2 + 6 + 1 = 9.
1 -5 4 2 -7 3 6 -1 2 -4 7 -10 2 6 1 -3
Ma abbiamo anche A1 = [3, 6, 1], A2 = [2,−4, 7], conA = A1 ∪ A2 = [3, 6, 1, 2,−4, 7], di valore totale3 + 6 + 1 + 2− 4 + 7 = 13.
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 21/36
Dobbiamo quindi trovare S1, S2 e A ...
S1 lo si trova determinando il PMAC di A[1 . . .M ],ovvero chiamando l’algoritmo ricorsivamente sulla partesinistra A[1 . . .M ] dell’array A[1 . . . N ]
S2 lo si trova determinando il PMAC di A[M + 1 . . . N ],ovvero chiamando l’algoritmo ricorsivamente sulla partedestra A[M + 1 . . . N ] dell’array A[1 . . . N ]
Come trovare A lo vediamo in un secondo ...
Il PMAC dell’intero array A[1 . . . N ] sará quindi quelsottovettore che tra S1, S2, ed A, ha valore massimo.
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 22/36
Come trovare A: la fase di Conquer
A1 A2
M M+1i jA1 é della forma A[i . . .M ]:ci sono solo M ≤ N tali sequenze, tante quanti sono i
corrispondenti valori di i, 1 ≤ i ≤ M . Pertanto la sequenza
contigua A1 di valore massimo puó essere trovata usando al
piú O(M) = O(N) operazioni.
Analogamente, A2 é della forma A[M + 1 . . . j]:ci sono solo N −M ≤ N tali sequenze, tante quanti sono i
corrispondenti valori di j,M ≤ j ≤ N . Pertanto la sequenza
contigua A2 di valore massimo puó essere trovata in
O(N −M) = O(N) operazioni.
A = A1 ∪A2 puó essere trovato in O(N) operazioni!
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 23/36
L’Algoritmo Completo Divide-et-Impera
Input: A[i . . . j], con i ≤ j
PMAC(A, i, j)1. if i = j return A[i] else2. trova PMAC(A, i, ⌊(i+ j)/2⌋)3. trova PMAC(A, ⌊(i+ j)/2⌋+ 1, j)4. trova PMAC che contiene sia
A[⌊(i+ j)/2⌋)] che A[⌊(i+ j)/2⌋+ 1]5. return il MASSIMO delle tre sequenze trovate
Detto T (N) il numero di operazioni di PMAC(A, 1, N),abbiamo:1. richiede tempo O(1), 2. e 3. richiedono tempo T (N/2),4. richiede tempo O(N), 5. richiede tempo O(1).
T (N) = 2T (N/2) +O(N) ⇒ T (N) = O(N logN)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 24/36
Analisi dell’ Algoritmo Divide-et-Impera
Per semplificare l’analisi, assumiamo che N = 2h. I passi4. e 5. dell’algoritmo richiedono O(N) operazioni, ovverorichiedono un numero di operazioni ≤ cN , per qualchecostante c. Quindi
T (N) ≤ 2T (N/2) + cN ≤ 2
[
2T (N/22) + cN
2
]
+ cN
= 22T (N/22) + 2cN ≤ 22[
2T (N/23) + cN
22
]
+ 2cN
= 23T (N/23) + 3cN ≤ . . . ≤ 2hT (N/2h) + hcN
Ponendo h = logN , si ha 2h = 2logN = N ,e quindi
T (N) ≤ NT (1) + (logN)cN = O(N logN)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 25/36
Riassumendo...
Abbiamo visto:
un algoritmo basato sulla generazione di tutte lepossibili soluzioni, di complessitá O(N3)
un algoritmo basato sul riuso di dati precedentementecalcolati di complessitá O(N2)
un algoritmo basato su Divide-et-Impera di complessitáO(N logN)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 26/36
Ne é valsa la pena?
Confrontiamo gli algoritmi su di un computer che esegue unmilione di operazioni al secondo.
Algoritmo 1 2 3
Tempo esecuzione N3 N2 N logN
Tempo per risolvere
un problema di taglia 102 1s 1/100s 0.00066438561s
103 16.67m 1s 0.00996578428s
104 277,78h 100s 0.13287712379s
105 31,69y 16,67m 1.66096404744s
106 31688,09y 277,78h 19.9315685693s
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 27/36
Morale della lezione
Ne é valsa la pena
Abbiamo visto che è possibile progettare algoritmiseguendo tecniche "generali" (forza bruta, divide-etimpera, ....)
Abbiamo visto che è possibile analizzare e valutarealgoritmi in base al numero di operazioni che essicompiono per produrre l’output, in funzione della"taglia" dell’input, e che questa analisi riflette ilcomportamento degli algoritmi in pratica
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 28/36
Circa PMAC: si può far meglio di O(N logN)?
Si
Esiste un algoritmo che risolve il Problema del ProfittoMassimo in anni contigui in O(N) operazioni
Però per oggi basta, trovatelo voi....
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 29/36
Informazioni sul corso
Libro di testo: Jon Kleinberg ed Eva Tardos, Algorithm Design,
Addison Wesley, 2005
Alla pagina WEB
http://www.di.unisa.it/professori/uv/ALGO/ALGO.html apparirá
tutto il materiale relativo al corso (copie delle slides usate,
esercizi, date delle prove d’esame, comunicazioni varie, etc.)
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 30/36
Informazioni pratiche sul corso
In generale, le copie delle slide usate al corsocompariranno in anticipo rispetto alla relativa lezione.
É fortemente consigliato che le stampiate e le studiate(o almeno le leggiate...) prima della lezione.
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 31/36
Come superare l’esame con buon voto?
Seguire il corso
Studiare lezione per lezione
Studiare le slide anche prima della lezione
Studiare anche dal libro di testo
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 32/36
Ma soprattutto....
Fare tanti esercizi!
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 33/36
e dove li trovo gli esercizi, direte voi...
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 34/36
Promessa:
Prometto che gli esercizi d’esame liconoscerete in anticipo!
ovvero, gli esercizi d’esame saranno presi dalla lista diesercizi che saranno via via disponibili alla pagina
http://www.dia.unisa.it/∼uv/ALGO/ALGO.html
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 35/36
Orario Lezioni e Ricevimento
Lezioni: Lunedí ore 9:00–11:00, Aula F8, Mercoledí,ore 9:00–11:00, Aula F8
Controllare spesso la pagina WEBwww.dia.unisa.it/professori/uv/ALGO/Avvisi.html pereventuali cambiamenti all’ultimo minuto di orari.
Ricevimento: Lunedí e Mercoledí dopo la lezione
Universita di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Accademico 2014/15 – p. 36/36