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