---+++ <font color=990000 size="+1"> A.A. 2014/2015</font> <font color=blue> *Lezioni 1-2: lunedì 2 marzo 2015* Presentazione del corso<br> Introduzione * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale. * modello RAM; misura di costo uniforme e logaritmico. * Pseudocodice </font> <font color=black> *Esercitazioni 1-2: venerdì 6 marzo 2015* Introduzione al Linguaggio C.<br> Cenni alla struttura di un programma C. Funzione main().<br> Primo programma in C: Helloworld.<br> Semplici funzioni: somma e predecessore avendo un esecutore in grado solo di sommare 1.<br> </font> <font color=blue> *Lezioni 3-4: lunedì 9 marzo 2015* Notazione asintotica (1) * Definizione e significato degli insiemi O, Ω e Θ. * Esempi. * Algebra della notazione asintotica. * Valutazione del costo computazionale di un algoritmo. Esercizi assegnati: * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione </font> <font color=blue> *Lezioni 5-6: mercoledì 11 Marzo 2015* Notazione asintotica (2) * Esempi di problemi che si possono risolvere in modo più o meno efficiente * somma dei primi n interi * valutazione di un polinomio in un punto Il problema della ricerca * ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore Esercizi assegnati: * Calcolare l'andamento asintotico di alcune funzioni * Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense) </font> <font color=black> *Esercitazioni 3-4: venerdì 13 marzo 2015* Ancora semplici funzioni in linguaggio C: divisione intera.<br> Cenni all'uso di asserzioni logiche: precondizioni, postcondizioni e invarianti nella progettazione di un programma iterativo.<br> Funzioni: stato locale e globale. Stack di attivazione delle funzioni.<br> Passaggio di parametri: passaggi per valore e per indirizzo.<br> Esempio: funzione scambia.<br> Cenni alla definizione per induzione di funzioni (somma) e relativa funzione ricorsiva in C. </font> <font color=blue> *Lezioni 7-8: lunedì 16 Marzo 2015* Ricorsione * funzioni matematiche ricorsive; * algoritmi ricorsivi: aspetti principali; * calcolo del fattoriale: pseudocodice ricorsivo; * ricerca sequenziale: pseudocodice ricorsivo; * ricerca binaria: pseudocodice ricorsivo; Soluzioni delle equazioni di ricorrenza (1) * metodo di sostituzione; esempi * metodo iterativo; esempi Esercizi assegnati: * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi: * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo) * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva) </font> <font color=blue> *Lezioni 9-10: mercoledì 18 Marzo 2015* Soluzioni delle equazioni di ricorrenza (2) * metodo dell'albero; esempi * metodo del teorema principale (senza dimostrazione); esempi Esercizi svolti in classe: * Calcolare la soluzione delle seguenti equazioni di ricorrenza col metodo iterativo, tenendo conto che per tutte il caso base è T(1)=&Theta(1): * T(n)=2T(n/2)+Θ(n) * T(n)=3T(n/2)+Θ(n) * T(n)=2T(n/3)+Θ(n) Esercizi assegnati: * Calcolare la soluzione delle seguenti equazioni di ricorrenza con quanti più metodi è possibile, tenendo conto che per tutte il caso base è T(1)=&Theta(1): * T(n)=3T(n/2)+Θ(n) * T(n)=3T(n/4)+Θ(n) * T(n)=2T(n/2)+Θ(n^2) * T(n)=T(n/3)+T(2/3n)+Θ(n) * T(n)=4T(n/2)+Θ(n) * T(n)=2T(n/2)+Θ(n^3) * T(n)=16T(n/4)+Θ(n^2) * T(n)=T(n-1)+Θ(n) * T(n)=3T(n/2)+Θ(n log n) </font> <font color=black> *Esercitazioni 5-6: venerdì 20 marzo 2015* Esempio di funzione ricorsiva: calcolo dei numeri di Fibonacci.<br> Inefficienza della funzione ricorsiva che calcola i numeri di Fibonacci: albero delle chiamate ricorsive.<br> Programma iterativo che calcola i numeri di Fibonacci.<br> Programma ricorsivo efficiente. Cenni alla trasformazione sistematica di programmi iterativi in ricorsivi.<br> Problemi con soluzione inerentemente ricorsiva: il problema della torre di Hanoi.<br> Esercizi: predecessore con ricorsione, moltiplicazione egiziana.<br> </font> <font color=blue> *Lezioni 11-12: lunedì 23 Marzo 2015* Soluzioni delle equazioni di ricorrenza (3) Esercizio svolto in classe: * calcolare la soluzione della seguente equazione di ricorrenza con tutti e quattro i metodi, tenendo conto che per tutte il caso base è T(1)=&Theta(1): * T(n)=2T(n/2)+Θ(n) Il problema dell'ordinamento (1) * Algoritmi semplici: insertion sort e selection sort, pseudocodici e complessità nel caso migliore e peggiore. </font> <font color=blue> *Lezioni 13-14: mercoledì 25 Marzo 2015* Il problema dell'ordinamento (2) * Algoritmi semplici: bubble sort, pseudocodice e complessità nel caso migliore e peggiore. * Teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti. * Algoritmi efficienti: merge sort, pseudocodice e complessità Esercizi assegnati: * Scrivere lo pseudocodice iterativo e ricorsivo, e per entrambe le versioni calcolare il costo computazionale, di algoritmi che risolvono i seguenti problemi: * dati in input due interi, n e k, calcolare n^k * calcolare la somma degli elementi di un vettore dato in input * verificare se un dato vettore di caratteri è palindromo * trovare il minimo di un vettore dato in input * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato. * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione. * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione). </font> <font color=black> *Esercitazioni 7-8: venerdì 27 marzo 2015* Introduzione ai vettori in linguaggio C.<br> Vettori e puntatori.<br> Esempio: stampa di un vettore con indici, aritmetica dei puntatori e ricorsiva.<br> Vettori statici e dinamici. Introduzione all'allocazione dinamica.<br> Esercizio: calcolo del baricentro di un vettore. </font> <font color=blue> *Lezioni 15-16: lunedì 30 Marzo 2015* Il problema dell'ordinamento (3) * Algoritmi efficienti: quicksort, pseudocodice e complessità nei casi migliore, peggiore e medio (con dimostrazione) Esercizi assegnati: * Scrivere la funzione di fusione ricorsiva * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2) * Risolvere l'equazione di ricorrenza del Merge sort con tutti i metodi studiati * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n)) * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2. * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort. * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali ed in cui sia già ordinato da destra a sinistra. </font> <font color=blue> *Lezioni 17-18: mercoledì 1 Aprile 2015* Il problema dell'ordinamento (4) * Algoritmi efficienti: heapsort (struttura dati heap, heapify, buildheap, e heapsort: pseudocodice e costo computazionale) Esercizi assegnati: * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice. * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale. * Scrivere lo pseudocodice di una funzione che, dato un heap di n elementi al quale e' stata aggiunta nella posizione (n + 1) una nuova foglia con valore arbitrario, ripristini la proprieta' di heap nel nuovo albero di dimensione (n + 1). Valutare il costo computazionale. </font> <font color=red> *2-7 Aprile 2015: Vacanze di Pasqua* </font> <font color=blue> *Lezioni 19-20: mercoledì 8 Aprile 2015* Il problema dell'ordinamento (5) * Algoritmi di ordinamento lineari: counting sort, bucket sort (pseudocodice e costo computazionale) Esercizi svolti in classe: * Esempio 6.1 delle dispense. Esercizi assegnati * Scrivere lo pseudocodice di una funzione che, dato un heap massimo di n elementi, ripristini la proprieta' di heap dopo che il valore di uno e uno solo dei nodi dello heap sia stato arbitrariamente modificato. Valutare il costo computazionale. </font> <font color=black> *Esercitazioni 9-10: venerdì 10 aprile 2015* Esercizi sui Vettori.<br> Crivello di Eratostene. <br> Calcolo dei Coefficienti Binomiali.<br> Uso di vettori per memorizzare i valori già calcolati dalla funzione ricorsiva.<br> </font> <font color=blue> *Lezioni 21-22: lunedì 13 Aprile 2015* Strutture dati fondamentali (1) * insiemi dinamici ed operazioni su di essi * implementazione di un insieme dinamico su un vettore non ordinato * implementazione di un insieme dinamico su un vettore ordinato * la struttura dati lista * operazioni elementari su liste: scorrimento, ricerca, inserimento in testa, eliminazione * la struttura dati lista doppiamente puntata * eliminazione di un elemento dalla lista doppiamente puntata * la lista circolare * la struttura dati coda * le operazioni enqueue e dequeue </font> <font color=blue> *Lezioni 23-24: mercoledì 15 Aprile 2015* Svolgimento in classe di esercizi preparatori al primo esonero </font> <font color=black> *Esercitazioni 11-12: venerdì 17 aprile 2015* Esercizi in preparazione all'esonero.<br> Correzione esonero 2014: scomposizione in fattori primi. <br> Correzione esonero 2013: verificare se un array è contenuto in un altro. <br> </font> <font color=red> *20-24 Aprile 2015: Settimana di interruzione della didattica e Primo esonero* </font> <font color=black> *Esercitazioni 13-14: lunedì 27 aprile 2015* Introduzione alle matrici.<br> Programmazione top-down: gioco del forza4.<br> </font> <font color=blue> *Lezioni 25-26: mercoledì 29 Aprile 2015* Strutture dati fondamentali (2) * la struttura dati coda con priorità * le operazioni enqueue e dequeue * la struttura dati pila * le operazioni push e pop * funzionamento della pila di sistema (system stack) per la gestione delle chiamate di funzione Esercizi svolti in classe: * Simulare il comportamento di una coda mediante l'uso di più pile * Discussione sull'esercizio n. 3 del primo esonero </font> <font color=blue> *Lezioni 27-28: lunedì 4 Maggio 2015* Strutture dati fondamentali (3) * alberi (1) * definizione tramite la nozione di grafo * caratterizzazione degli alberi * alberi binari completi: relazione tra altezza e numero di nodi * memorizzazione degli alberi: * tramite record e puntatori * posizionale * tramite vettore dei padri Esercizi assegnati: * dato un albero tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale * dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale </font> <font color=blue> *Lezioni 29-30: mercoledì 6 Maggio 2015* Strutture dati fondamentali (4) * alberi (2) * visite di alberi: in-ordine, pre-ordine e post-ordine * pseudocodice ricorsivo * costo computazionale tramite equazione di ricorrenza Esercizi svolti in classe: * Calcolare il numero di nodi di un albero binario * Verificare se una data chiave k è presente in un albero binario * Calcolare l'altezza di un albero binario * Contare i nodi di un albero binario che si trovano a livello k (il livello della radice è zero) * Realizzare una visita in pre-ordine senza ricorsione, mediante l'uso di una pila * Realizzare una visita per livelli mediante l'uso di una coda </font> <font color=black> *Esercitazioni 15-16: venerdì 8 maggio 2015* Ancora sulle matrici: allocazione statica e dinamica delle matrici.<br> Rappresentazione in memoria di una matrice.<br> Esercizi: verifica che una matrice di interi è un quadrato magico.<br> </font> <font color=blue> *Lezioni 31-32: lunedì 11 maggio 2015* Dizionari (1) * definizione di dizionario e problematiche associate * tabelle ad indirizzamento diretto * tabelle hash * il problema delle collisioni * soluzione al problema delle collisioni tramite liste di trabocco * soluzione al problema delle collisioni tramite indirizzamento aperto * scansione lineare * scansione quadratica * hashing doppio </font> <font color=blue> *Lezioni 33-34: mercoledì 13 maggio 2015* Dizionari (2) * alberi binari di ricerca * definizione * algoritmo di ricerca e sua complessita' * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita' * algoritmo di inserimento e sua complessita' * algoritmo di cancellazione e sua complessita' </font> <font color=black> *Esercitazioni 17-18: venerdì 15 maggio 2015* Strutture.<br> Liste o sequenze: definizione induttiva.<br> Rappresentazione in C di liste.<br> Primi programmi sulle liste: inserimento in testa, in coda.<br> Funzione reverse e reverse efficiente ricorsiva.<br> Funzione append.<br> Versioni che creano nuove liste e funzioni che modificano la lista di input.<br> </font> <font color=blue> *Lezioni 35-36: lunedì 18 maggio 2015* Dizionari (3) * alberi Red-Black * definizione * dimostrazione dell'altezza logaritmica * cenni ai meccanismi di ribilanciamento: cambi di colore e rotazioni Grafi (1) * definizione di grafo, grafo diretto, grafo pesato * definizine di passeggiata, cammino, cammino semplice * definizine di circuito e ciclo * relazione di raggiungibilità e sue caratteristiche * definizione di componente connessa * definizione di sottografo, sottografo indotto, sottografo ricoprente </font> <font color=blue> *Lezioni 37-38: mercoledì 20 maggio 2015* Grafi (2) * rappresentazioni in memoria * liste di adiacenza * matrice di adiacenza * matrice di incidenza * lista di archi * confronto della complessita' spaziale e temporale per alcune operazioni elementari * aspetti generali delle visite * differenza concettuale fra visita in ampiezza e visita in profondità * implementazioni possibili: iterativa (tramite coda o pila) e ricorsiva (solo per visita in profondità) * definizione di albero di visita * archi dell'albero e archi non dell'albero * visita in ampiezza (BFS) * pseudocodice della visita in ampiezza * esempio di funzionamento della visita in ampiezza Esercizi assegnati: * Per ciascuno dei modi visti a lezione per memorizzare un grafo, scrivere le funzioni necessarie a crearne uno identico memorizzato in tutti gli altri modi * Modificare la visita in ampiezza in modo da calcolare e memorizzare, per ciascun nodo, la distanza dalla sorgente * Modificare la visita in ampiezza in modo da verificare se il grafo contiene cicli oppure no * Modificare la visita in ampiezza in modo da verificare se il grafo è connesso oppure no </font> <font color=black> *Esercitazioni 19-20: venerdì 22 maggio 2015* Specifica di funzioni su liste tramite equazioni ricorsive.<br> Liste ordinate. Funzione merge su liste. Versione in-place e versione che genera una nuova lista.<br> Funzione reverse in-place.<br> </font> <font color=blue> *Lezioni 39-40: lunedì 25 maggio 2015* Grafi (3) * visita in ampiezza (BFS) * costo computazionale della visita in ampiezza * proprietà degli archi non dell'albero * proprieta' della distanza dalla radice * visita in profondità (DFS) * pseudocodice della visita in profondità * costo computazionale della visita in profondità * proprietà degli archi non dell'albero * relazione fra lunghezza dei cammini e numero di archi del grafo * Algoritmo di Dijkstra (1) * la rete Internet è modellata come un grafo pesato sul quale individuare i cammini di costo minimo * cenni sul funzionamento store-and-forward dei router * fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione </font> <font color=blue> *Lezioni 41-42: mercoledì 27 maggio 2015* Grafi (4) * Algoritmo di Dijkstra * pseudocodice dell'algoritmo * esempio dettagliato di funzionamento su un grafo pesato * costo computazionale dell'algoritmo in funzione dell'implementazione della coda con priorità * dimostrazione per induzione della correttezza dell'algoritmo </font> <font color=black> *Esercitazioni 21-22: venerdì 29 maggio 2015* Definizione induttiva di alberi.<br> Rappresentazione in C di alberi binari.<br> Specifica di funzioni su alberi tramite equazioni ricorsive.<br> Prime funzioni su alberi: costruttori, distruttori, conteggio dei nodi, altezza.<br> Il problema del bilanciamento: versione naif e versione efficiente con un'unica scansione dell'albero.<br> </font> <font color=blue> *Lezioni 43-44: mercoledì 3 giugno 2015* Esercizi svolti in classe: * Dato un albero binario, trovare il nodo che presenta la massima differenza fra i numeri di nodi del proprio sottoalbero sinistro e del proprio sottoalbero destro. Se vi sono più nodi con la massima differenza, restituirne uno fra quelli più vicini alla radice * Dato un vettore di n elementi considerato come un albero binario gestito mediante la notazione posizionale, riempirlo con i primi n valori dell'<A HREF=http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree>albero di Kalkin-Wilf</A> (contati nell'albero per livelli e, in ciascun livello, da sinistra a destra) * Dati due alberi binari di ricerca, fonderli in un unico albero binario di ricerca * Dato un vettore contenente interi positivi e negativi, scrivere una funzione che sistemi tutti i valori negativi a sinistra di tutti i valori positivi </font> <font color=black> *Esercitazioni 23-24: venerdì 5 giugno 2015* Esercitazione in vista dell'esame.<br> Compiti precedenti: somma successivi e somma precedenti in una lista.<br> Trucchi: usare i parametri per memorizzare valori in corso di computazione: stampa indentata di un albero.<br> Altri esercizi sugli alberi: relazione di uguaglianza e di sottoalbero.<br> </font> -- Users.GiancarloBongiovanni - 05 Apr 2016
This topic: Infogen
>
WebHome
>
DiarioDelleLezioni
>
LezioniDegliAnniAccademiciPrecedenti
>
AnnoAccademico2014-2015
Topic revision: r3 - 2018-02-17 - GiancarloBongiovanni
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback