Algoritimi e Strutture Dati Algoritimi e Strutture Dati modulo 2 modulo 2

(1)

Algoritimi e Strutture Dati Algoritimi e Strutture Dati

modulo 2 modulo 2

Moreno Marzolla

Dip. di Informatica—Scienza e Ingegneria Università di Bologna

moreno.marzolla@unibo.it

(2)

Algoritmi e Strutture Dati 2

(3)

Presentiamoci

●

Modulo 2 (II sem.)

– Moreno Marzolla

– moreno.marzolla@unibo.it

– http://www.moreno.marzolla.name/

●

Orario delle lezioni

– Giovedì ore 14:00—16:00, aula M1 Mineralogia

– Venerdì ore 11:30—14:30, aula Ercolani 1

●

Ricevimento

– Previo appuntamento via mail

(4)

“Netiquette”

ossia, le “buone maniere” nell'era di Internet

●

Usate esclusivamente l'indirizzo ufficiale @studio.unibo.it

– Ogni tanto controllate la posta in ingresso

●

Indicate sempre l'oggetto (subject) del messaggio

●

Indicate nome, cognome e numero di matricola nel corpo del messaggio

●

Specificate che il vostro messaggio è relativo al corso di Algoritmi e Strutture Dati

●

Ricordarsi che la posta elettronica è un mezzo di comunicazione asincrono

– Non sempre sono in grado di rispondere immediatamente

– Non date per scontato che io legga la posta a mezzanotte

(5)

Sito web del modulo 2

●

http://www.moreno.marzolla.name/teaching/ASD

– Avvisi

– Lucidi delle lezioni

– Dispensa di esercizi svolti

– Modalità d'esame

(6)

●

Testo adottato

– Alan Bertossi, Alberto Montresor, Algoritmi e strutture di dati Terza Edizione, 2014, Città Studi, ISBN:

9788825173956

●

Testi di consultazione

– Camil Demetrescu, Irene Finocchi,

Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill ISBN:

9788838664687, Giugno 2008

– Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e

strutture dati 2/ed, McGraw-Hill, ISBN:

9788838662515, Maggio 2005

Bibliografia

(7)

Programma del modulo 2

● Strutture Merge-Find

● Tecniche Algoritmiche

– Divide et impera

– Algoritmi greedy

– Programmazione dinamica

● Algoritmi su grafi

– Visita

– Alberi di copertura (spanning trees)

– Cammini minimi

– ...

● Cenni alla teoria della calcolabilità

(8)

Prerequisiti

●

Programmazione Internet + Lab. di prog. Internet

– Algoritmi e Strutture Dati ≠ Programmazione

– In questo corso non si impara a programmare, perché dovete già essere in grado di farlo

●

Nozioni di base di algebra e analisi matematica

– Sommatorie, polinomi, ordini di grandezza delle funzioni, disequazioni

(9)

Scopo del corso

●

Contenuto

– Una panoramica di problemi noti e loro soluzioni

– “Elenco” di algoritmi e strutture dati “standard”

– Come valutare l'efficienza di un algoritmi

●

Metodo

– Principi e tecniche per risolvere problemi

algoritmici

– Come risolvere nuovi problemi, applicando soluzioni note o

“inventando” varianti alle soluzioni note

(10)

10

Scopo del corso

(11)

Modalità d'esame

●

(Già descritte dal prof. Donatiello)

●

Prova scritta su tutti gli argomenti del corso

– 6 appelli d'esame: 3 nella sessione estiva, 1 nella sessione autunnale, 2 nella sessione invernale

– E' consentito usare libri e appunti

– Non c'è orale

●

oppure due progetti di programmazione + discussioni

– Un progetto è già stato assegnato

– Il secondo progetto verrà assegnato alla fine del modulo 2

– Possibilità di recuperare uno dei progetti, sostenendo lo scritto sugli argomenti del modulo mancante

(12)

Osservazioni importanti

●

I progetti non rappresentano un modo per superare l'esame senza studiare la teoria

– La conoscenza della teoria verrà verificata durante la

discussione; chi dimostra preparazione insufficiente non supera la prova.

●

Impegno richiesto

– 12 CFU = 12 x 25 = 300 ore di studio

● ~ 100 ore di lezione

● ~ 200 ore di studio individuale

(13)

Come superare l'esame

●

Seguire le lezioni

– Se qualcosa non è chiaro, fate domande, oppure venite a ricevimento

●

Studiare sul libro

●

Esercitarsi il più possibile

– Gli algoritmi non sono uno sport che si pratica da spettatori

– Sfruttate la dispensa di esercizi svolti

●

Fare pratica in Java

– anche se non intendete svolgere i progetti!

“Se ascolto dimentico; se vedo ricordo; se faccio capisco.”

(14)

Esercizi di ripasso

(15)

Vero o falso?

1. 1325 n

²

+ 12n + 1 =  (n

³

) 2. 76 n

³

= O(n

³

)

3. n

²

log n = O(n

²

) 4. 3

ⁿ

= O(2

ⁿ

)

5. 2

ⁿ

= O(2

^n/2

) 6. 2

ⁿ⁺¹⁰⁰

= O(2

ⁿ

) 7. log n = O(n) 8. n = O(n log n) 9. n

²

= O(n log n)

10. log( n

²

) =  (log n)

(16)

Vero o falso?

1. 1325 n

²

+ 12n + 1 =  (n

³

) FALSO

2. 76 n

³

= O(n

³

) VERO

3. n

²

log n = O(n

²

) FALSO

4. 3

ⁿ

= O(2

ⁿ

) FALSO

5. 2

ⁿ

= O(2

^n/2

) FALSO

6. 2

ⁿ⁺¹⁰⁰

= O(2

ⁿ

) VERO

7. log n = O(n) VERO

8. n = O(n log n) VERO

9. n

²

= O(n log n) FALSO

10. log( n

²

) =  (log n) VERO

11. n(n+1) / 2 = O(n) FALSO

(17)

Esercizio

●

Determinare il costo asintotico dell'algoritmo seguente

– supponiamo n intero positivo

integer AlgA(integer n) if ( n ≤ 1 ) then

return 2*n;

else

integer a ← 2;

for integer i ← 1 to n/2 do a ← a + 2 * i;

endfor

return AlgA( n/2 ) + AlgA( n/2 ) + a;

endif

(18)

Esercizio

●

Determinare il costo asintotico dell'algoritmo seguente

– supponiamo n intero positivo

AlgB( integer n ) integer i ← 1;

while i ≤ n do i ← 2 * i;

endwhile

(19)

Strutture Dati

●

Che differenza c'è tra LinkedList e ArrayList Java?

LinkedList ArrayList Inserimento in testa

Inserimento in coda (add)

Inserimento dopo un elemento di posizione/riferimento dati

Cancellazione di un elemento di posizione/riferimento dati

Accesso al k-esimo elemento

(20)

Strutture Dati

●

Che differenza c'è tra LinkedList e ArrayList Java?

LinkedList ArrayList

Inserimento in testa O(1) O(n)

Inserimento in coda (add) O(1) O(1) amm.

Inserimento dopo un elemento di

posizione/riferimento dati O(1) O(n)

Cancellazione di un elemento di

posizione/riferimento dati O(1) O(n)

Accesso al k-esimo elemento O(k) O(1)

Dalla documentazione di java.util.ArrayList

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

(21)

Min-Heap

●

Consideriamo il min-heap mostrato in figura

●

Mostrare la struttura dello heap dopo ciascuna delle seguenti operazioni

– Rimozione minimo

– Inserimento 5

– Inserimento 21

– Rimozione minimo

7

12 10

25 18 14 26

31

(22)

Caso ottimo / caso pessimo

●

Consideriamo un albero binario di ricerca, che non viene mantenuto bilanciato, con n nodi

●

Quale è il costo dell'operazione di ricerca

– nel caso pessimo?

– nel caso ottimo?