Informatica - erogato in modalità prevalentemente a distanza

Questo insegnamento prevede le seguenti unità didattiche: Introduzone del corso [2 ore] Notazione asintotica [10 ore] Il problema della ricerca [8 ore] Introduzione alla ricorsione [10 ore] Il problema dell'ordinamento [10 ore] Strutture dati fondamentali [20 ore] Segue il programma in maggior dettaglio. 1. Introduzione Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; modello RAM; misura di costo uniforme e logaritmico. 2. Notazione asintotica Definizione e significato degli insiemi O, Ω e Θ 3. Il problema della ricerca Ricerca sequenziale in un vettore disordinato; costo computazionale nel caso migliore, peggiore e medio Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa) costo computazionale nel caso migliore, peggiore e medio 4. Introduzione alla ricorsione funzioni ricorsive versione iterativa e ricorsiva di algoritmi: esempi occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci calcolo del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza metodo di sostituzione metodo iterativo metodo dell'albero teorema principale ( dimostrazione facoltativa ) 5. Il problema dell'ordinamento algoritmi naif: filosofia, pseudocodice e costo computazionale insertion, selection e bubble sort limitazione inferiore sul costo computazionale degli algoritmi di ordinamento per confronti; dimostrazione funzione di fusione e merge sort; cenno alla tecnica del divide et impera ordinamento in tempo lineare: counting sort e bucket sort quick sort e suo costo computazionale nel caso peggiore, migliore e medio heap e heap sort 6. Strutture dati fondamentali insiemi dinamici ed operazioni su di essi vettore non ordinato e ordinato pila e coda, funzioni di inserimento ed estrazione, coda circolare lista semplice e doppiamente puntata coda con priorità albero definizione come grafo connesso aciclico teorema di caratterizzazione degli alberi e dimostrazione alberi radicati, alberi binari, alberi ordinati, alberi binari completi relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo rappresentazione in memoria di un albero binario rappresentazione posizionale rappresentazione con puntatori vettore dei padri visita in pre-, post- ed in-ordine e calcolo del costo computazionale tramite equazione di ricorrenza 7. Dizionari indirizzamento diretto tabelle hash collisioni soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico) costo computazionale nel caso medio soluzioni delle collisioni con indirizzamento aperto vari tipi di scansione (lineare, quadratica ed hashing doppio) costo computazionale nel caso medio alberi binari di ricerca definizione algoritmo di ricerca e suo costo computazionale algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale algoritmo di inserimento e suo costo computazionale algoritmo di cancellazione e suo costo computazionale la problematica del bilanciamento per la limitazione del costo computazionale alberi red black e teorema per la limitazione dell'altezza ( rotazioni ed altri dettagli facoltativi )

Prerequisiti indispensabili per seguire le lezioni dell'insegnamento di Introduzione agli Algoritmi sono le nozioni di base del calcolo ed i fondamenti di un qualsiasi moderno linguaggio di programmazione ad alto livello, ad esempio quelli che vengono forniti negli insegnamenti di Calcolo Differenziale e del primo corso di Programmazione, obbligatorio per tutti e collocato al primo semestre del primo anno di corso.

T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to algorithms, The MIT Press Sarà cura della docente distribuire materiale didattico, relativo sia alle lezioni ed esercitazioni (sotto forma di dispense).

Modalità di svolgimento a distanza. Alla didattica frontale registrata, si affianca una attività di supporto da parte del docente ed una attività di tutoraggio in cui si risponde alle domande degli studenti e si organizzano esercitazioni su argomenti concordati con gli studenti. La frequenza non è obbligatoria.

la frequenza non è obbligatoria.

L’esame mira a valutare l’apprendimento tramite una prova scritta obbligatoria (consistente nella risposta a quesiti teorici e nella risoluzione di problemi dello stesso tipo di quelli svolti nelle esercitazioni) e una prova orale facoltativa (consistente nella discussione dei temi più rilevanti illustrati nel corso). La prova scritta ha una durata di due ore. Per superare l'esame occorre conseguire un voto non inferiore a 18/30. Lo studente deve dimostrare di aver acquisito una conoscenza sufficiente degli argomenti di tutte le parti del programma. Per conseguire un punteggio pari a 30/30 e lode, lo studente deve invece dimostrare di aver acquisito una conoscenza eccellente di tutti gli argomenti trattati durante il corso ed essere in grado di raccordarli in modo logico e coerente.

Modalità di svolgimento a distanza. Alla didattica frontale registrata, si affianca una attività di supporto da parte del docente ed una attività di tutoraggio in cui si risponde alle domande degli studenti e si organizzano esercitazioni su argomenti concordati con gli studenti. La frequenza non è obbligatoria.