Algoritmi e Strutture Dati Laurea in Informatica Calendario: 2 Marzo – 12 Giugno Aula: LuM250 Orario: Mer, Gio, Ven 15.30-17.30 Numero crediti = 8 (~ 64 ore) ~ 48 ore di teoria, ~16 ore di esercizi Docenti: Paolo Baldan (7 crediti) Livio Colussi (1 credito) Modalità d’Esame a. Prova scritta (5 appelli - indispensabile iscriversi nella lista di esame che verrà attivata su UNIWEB) b. Registrazione, con possibile colloquio (discussione dello scritto con qualche domanda di teoria) Materiale didattico Testo: Introduzione agli Algoritmi e Strutture Dati (3° ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. McGraw-Hill. Trad. di: Introduction to Algorithms and Data Structures (3° ed). T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. MIT Press. Pagina del corso con altro materiale (note, link, ecc.: www.math.unipd.it/~baldan/Algoritmi Programma Le prime 5 parti del testo (con qualche omissione): I. Fondamenti: notazione per gli algoritmi e primi esempi di algoritmi e di analisi degli algoritmi II. Ordinamento e statistiche d’ordine III. Strutture dati fondamentali IV. Tecniche avanzate di progettazione ed analisi degli algoritmi V. Strutture dati avanzate INTRODUZIONE I problemi computazionali, gli algoritmi che li risolvono e le tecniche per sviluppare tali algoritmi Esempio1: problema dell’ordinamento Input: a1,a2,...,an Output: a'1,a'2,...,a'n permutazione (riarrangiamento) di a1,a2,...,an tale che a'1 a'2 ... a'n TECNICA INCREMENTALE InsertionSort Soluzione1: Algoritmo Insertion-Sort. A A 1 n 1j n A key key 1 j n 1 i j n j n j n j n A A 1 key A i1 i A 1 A 1 n j Insertion-Sort(A) n = A.length for j = 2 to n key = A[j] // inseriamo A[j] nella sequenza // ordinata A[1..j-1] i=j-1 while i > 0 and A[i] > key A[i+1] = A[i] i=i–1 A[i+1] = key Insertion-Sort(A) n = A.length for j = 2 to n key = A[j] // inseriamo A[j] nella // sequenza ordinata // A[1..j-1] i=j–1 while i > 0 and A[i] > key A[i+1] = A[i] i=i–1 A[i+1] = key void Insertion-Sort(vector<T> A) { int i, j, n = A.size(); T key; for (j = 1; j < n; j++) { key = A[j]; // inseriamo A[j] nella // sequenza ordinata // A[0..j-1] i = j – 1; while (i >= 0 && A[i] > key) { A[i+1] = A[i]; i--; } A[i+1] = key; } } 5 5 # 2 2 2 2 2 2 2 2 2 2 2 # 5 5 5 5 5 5 # 4 4 4 4 8 8 8 8 # # 8 8 5 5 5 5 5 A 4 7 4 7 4 7 4 7 4 7 4 7 4 7 # 7 8 7 8 7 8 # # 8 7 8 key 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 2 8 4 7 Insertion-Sort(A) n = A.length for j = 2 to n // inserisce A[j] nella // sequenza ordinata // A[1..j-1] key = A[j] i=j–1 while i > 0 and A[i] > key A[i+1] = A[i] i=i–1 A[i+1] = key 2 2 # 1 1 1 1 1 1 1 4 4 2 2 2 2 2 2 2 2 5 5 4 4 4 # 3 3 3 3 A 7 8 7 8 5 7 5 7 5 7 4 5 4 5 4 5 4 5 4 5 key 1 # 8 8 8 7 7 7 # 6 3 3 3 3 # 8 8 8 7 7 6 6 6 6 6 6 6 # 8 8 1 3 6 Insertion-Sort(A) n = A.lenght for j = 2 to n // inserisce A[j] nella // sequenza ordinata // A[1..j-1] key = A[j] i=j–1 while i > 0 and A[i] > key A[i+1] = A[i] i=i–1 A[i+1] = key Analisi di Insertion-Sort: correttezza Insertion-Sort(A) n = A.length for j = 2 to n A 1 key = A[j] i=j-1 while i > 0 and A[i] > key j n A 1 i j n 1 i j n j n A[i+1] = A[i] i=i–1 A i 1 A[i+1] = key A j n A 1 Correttezza InsertionSort Analisi di Insertion-Sort: complessità Insertion-Sort(A) // c0 n = A.length // c1 for j = 2 to n // c2 n key = A[j] // c3 (n 1) i = j -1 // c4 (n 1) n while i > 0 and A[i] > key // c5 j 2 (t j 1) n A[i+1] = A[i] // c6 j 2 t j n 0 t j j i=i–1 // c7 j 2 t j A[i+1] = key // c8 (n 1) T IS (n) c0 c1 c2 n (c3 c4 c8 )( n 1) c5 j 2 (t j 1) (c6 c7 ) j 2 t j n n caso migliore: tj 0 0 tj j T (n) c0 c1 c2 n (c3 c4 c8 )( n 1) IS min c5 j 21 (c6 c7 ) j 2 0 n n IS Tmin (n) (c2 c3 c4 c5 c8 )n (c0 c1 c3 c4 c5 c8 ) bn a caso peggiore: t j j 1 0 tj j IS Tmax (n) c0 c1 c2 n (c3 c4 c8 )( n 1) c5 j 2 j (c6 c7 ) j 2 ( j 1) n IS max T n 1 (n) (c5 c6 c7 )n 2 2 1 1 1 (c2 c3 c4 c5 c6 c7 c8 )n 2 2 2 (c0 c1 c3 c4 c8 ) c ' n 2 b' n a ' caso medio: t j IS med T c5 T 0 tj j (n) c0 c1 c2 n (c3 c4 c8 )( n 1) n IS med j 1 2 j 1 j 2 2 (c6 c7 ) j 2 j21 n 1 (n) (c5 c6 c7 )n 2 4 3 1 1 (c2 c3 c4 c5 c6 c7 c8 )n 4 4 4 (c1 c3 c4 c5 c8 ) c" n b" n a" 2