Obiettivi Formativi

Il corso intende fornire gli strumenti per: 1) analizzare le principali tecniche di progettazione di algoritmi; 2) identificare le scelte algoritmiche fondamentali e valutarne i costi computazionali; 3) scegliere le strutture dati più adeguate al problema conoscendo i vari modi di implementarle.

Metodi didattici

Lezioni frontali con l'uso di lavagna, computer e videoproiettore.

Prerequisiti

Elementi di aritmetica modulare. Proprietà delle funzioni di variabili reali. Linguaggio ANSI C.

Verifiche dell'apprendimento

Esame orale sui contenuti del corso.

Programma del Corso

1. Analisi di algoritmi. Costo computazionale di un algoritmo. Modello RAM. Analisi degli algoritmi. Notazione asintotica. Notazione asintotica per equazioni. Proprietà dei simboli della notazione asintotica. Complessità di un algoritmo. Istruzione dominante. Complessità di un problema. Funzioni di uso comune. Funzioni tetto e pavimento. Polinomi. Esponenziali e logaritmi. Fattoriale. Calcolo combinatorio. Strategie di sviluppo degli algoritmi. 2. Sommatorie e Ricorrenze. Sommatorie. Stima di sommatorie. Stima mediante integrali. Produttorie. Ricorrenze. Risoluzione per iterazione. Risoluzione con il metodo principale. 3. Algoritmi elementari. Precisione macchina. Aritmetica razionale. Massimo comune divisore, minimo comune multiplo. MCD con sottrazioni ripetute. MCD con divisioni ripetute. Algoritmo esteso di Euclide. Algoritmo binario. Potenza n-esima. Numeri di Fibonacci. Numeri di Fibonacci e sezione aurea. Un altro calcolo efficiente dell'n-esimo numero di Fibonacci. Analisi dell'algoritmo di Euclide. Generazione di numeri casuali. Il metodo della congruenza lineare. Il metodo della congruenza quadratica. Radice quadrata. Zeri di funzione. Metodo di bisezione. Metodo di Newton-Raphson. 4. Strutture dati. Dati astratti. Rappresentazione di dati astratti. Vettori e record. Matrici. Rappresentazione del tipo matrice in C. Matrici compatte. Liste. Liste semplici. Rappresentazione sequenziale. Rappresentazione collegata con array. Rappresentazione collegata con puntatori. Liste doppiamente puntate. Liste circolari. Liste composite. Alberi. Alberi binari. Rappresentazione sequenziale. Rappresentazione mediante lista. Rappresentazione collegata. Alberi binari di ricerca. Alberi n-ari. Visita di un albero. Tavole. 5. Algoritmi per gli array. Minimo e massimo di un array. Partizione di un array. Fusione di due array ordinati. Eliminazione doppioni da un array ordinato. Ordinamento per selezione diretta. Ordinamento per inserimento diretto. Ordinamento per interscambio. Ordinamento di Shell. Ricerca di un elemento in un array. Ricerca sequenziale. Ricerca binaria. Ricerca di Fibonacci. Ricerca interpolata. Ricerca adattativa. Ricerca calcolata (hash). 6. Quicksort, Mergesort, Heapsort. Ordinamento di Hoare (quicksort). Prestazioni del quicksort. Ordinamento per fusione (mergesort). Ordinamento per heap (heapsort). Code con priorità. Complessità degli algoritmi di ordinamento basati sui confronti. 7. Pile, Code, Liste ordinate. Pile: Implementazione delle operazioni primitive. Code: Implementazione delle operazioni primitive. Liste ordinate: Implementazione delle operazioni primitive. 8. Ordinamento di array in tempo lineare. Un caso semplice: ordinamento per permutazione. Ordinamento per conteggio. Bucket sort. 9. Alberi binari di ricerca. Alberi binari ordinati. Minimo, massimo, predecessore, successore. Ricerca in un albero binario ordinato. Inserimento e cancellazione di un nodo da un albero binario ordinato. Visita di un albero binario ordinato. Visita di un albero binario in preordine e postordine. Altezza di un albero binario ordinato. 10. Alberi Red Black. Alberi binari bilanciati. Proprietà degli alberi RB. Rotazioni. Inserimento, Ricerca e Cancellazione.