---+++ <font color="990000" size="+2">Contenuti del corso</font> Questo corso si compone di due parti che saranno portate avanti parallelamanete. La prima, di circa 60 ore, si occuperà della *descrizione e progettazione di algoritmi efficienti*; la seconda, di circa 30 ore, si occuperà di *programmazione*. ---+++ <font color="990000" size="+1"> Descrizione e progettazione di algoritmi efficienti</font> * Introduzione * Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale; * modello RAM; misura di costo uniforme e logaritmico. * Notazione asintotica * Definizione e significato degli insiemi O, Ω e Θ * Il problema della ricerca * Ricerca sequenziale in un vettore disordinato; * complessita' nel caso migliore, peggiore e medio * Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa) * complessita' nel caso migliore, peggiore e medio * Introduzione alla ricorsione * funzioni ricorsive * versione iterativa e ricorsiva di algoritmi: esempi * occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci * calcolo della complessita' delle funzioni ricorsive tramite equazioni di ricorrenza * metodo di sostituzione * metodo iterativo * metodo dell'albero * teorema principale (senza dimostrazione) * Il problema dell'ordinamento: * algoritmi naif: filosofia, codice e complessita' * limitazione inferiore sulla complessita' degli ordinamenti per confronti; dimostrazione * funzione di fusione e merge sort; cenno alla tecnica del divide et impera * quick sort e sua complessita' nel caso peggiore, migliore e medio * heap e heap sort * ordinamento in tempo lineare: counting sort * Strutture dati fondamentali * insiemi dinamici ed operazioni su di essi * vettore non ordinato e ordinato * lista semplice e doppiamente puntata * pila e coda, funzioni di inserimento ed estrazione, coda circolare * coda con priorità * albero * definizione come grafo connesso aciclico * teorema di caratterizzazione degli alberi * alberi radicati, alberi binari, 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 della complessita' tramite equazione di ricorrenza * Dizionari * indirizzamento diretto * tabelle hash * scansione lineare * scansione quadratica * hashing doppio e relative prestazioni (senza dimostrazione) * alberi binari di ricerca * definizione * algoritmo di ricerca e sua complessita' * algoritmo di inserimento e sua complessita' * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita' * algoritmo di cancellazione e sua complessita' * la problematica del bilanciamento (alberi red-black) * rotazioni e cambi di colore * complessità del bilanciamento * Grafi * rappresentazione in memoria * liste di adiacenza * matrice di adiacenza * matrice di incidenza * lista di archi * confronto della complessita' spaziale e temporale in alcune operazioni elementari * visita in ampiezza (BFS) * definizione di albero ricoprente * proprietà degli archi non dell'albero * proprieta' della distanza dalla radice * visita in profondita' (DFS) * proprietà degli archi non dell'albero * proprieta' del numero di archi in funzione della lunghezza del cammino più lungo * similitudini e differenze tra le due visite * loro complessita' al variare della struttura dati usata * [[http://twiki.dsi.uniroma1.it/pub/Infogen/DispenseELibriDiTesto/Dijkstra.pdf][Algoritmo di Dijkstra per il calcolo dei cammini minimi]] * funzionamento * pseudocodice * complessità * dimostrazione della correttezza ---+++ <font color="990000" size="+1">Programmazione</font> *Per i contenuti di questa parte si vedano le informazioni fornite dal prof. Franceschini su [[https://sites.google.com/uniroma1.it/programmazioneinc/home-page][questa pagina]].*
This topic: Infogen
>
InformaticaGenerale20202021CanaleMZ
>
ContenutiDelCorso
Topic revision: r2 - 2021-01-22 - GiancarloBongiovanni
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback