Informatica

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). Il materiale per l'anno in corso è disponibile qui: https://twiki.di.uniroma1.it/twiki/view/Intro_algo/AD/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 ma fortemente consigliata.

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 tradizionale La frequenza non è obbligatoria.

Obiettivi generali Introduzione ai metodi di base per la progettazione e l'analisi degli algoritmi, iterativi e ricorsivi, ed alla valutazione della loro efficienza computazionale. Obiettivi specifici Conoscenza e comprensione: Al termine del corso gli studenti conosceranno le metodologie di base per la progettazione e l'analisi di algoritmi iterativi e ricorsivi, le strutture dati elementari, alcuni modi per scandire tali strutture, i principali algoritmi di ordinamento e le implementazioni più elementari dei dizionari. Applicare conoscenza e comprensione: Al termine del corso gli studenti avranno acquisito familiarità con le principali strutture dati di base, in particolare quelle che implementano i dizionari. Sapranno spiegarne gli algoritmi e analizzarne la complessità, evidenziando come le prestazioni dipendano dalla struttura dati utilizzata. Saranno in grado di progettare nuove strutture dati e i relativi algoritmi, rielaborando quelli esistenti; sapranno spiegare i principali algoritmi di ordinamento, illustrando le strategie di progetto sottostanti e le relative analisi di complessità; saranno in grado di confrontare i comportamenti asintotici dei tempi di esecuzione degli algoritmi studiati; saranno in grado di progettare soluzioni ricorsive di problemi e di analizzare asintoticamente gli algoritmi risultanti. Capacità critiche e di giudizio: Lo studente avrà le basi per analizzare la qualità di un algoritmo e delle relative strutture dati, sia dal punto di vista della effettiva risoluzione del problema che da quello della efficienza computazionale con la quale il problema viene risolto. Capacità comunicative: Lo studente acquisirà la capacità di esporre in modo chiaro ed organizzato le proprie conoscenze, capacità che verrà verificata sia mediante i quesiti presentati nelle prove scritte che durante la prova orale. Lo studente sarà in grado di esprimere un'idea algoritmica in modo rigoroso ad alto livello, in pseudocodice. Capacità di apprendimento successivo: Le conoscenze acquisite permetteranno allo studente di affrontare lo studio, individuale o previsto nell'ambito di un corso di laurea magistrale, di tecniche algoritmiche e di strutture dati di base.

I prerequisiti del corso di Introduzione agli Algoritmi sono i fondamenti di un qualsiasi moderno linguaggio di programmazione ad alto livello, ad esempio quelli che vengono forniti nell'insegnamento 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).

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 avrà una durata di circa due ore e può essere sostituita da due prove intermedie, entrambe della durata di due ore, la prima delle quali si svolgerà a metà corso e la seconda immediatamente dopo la fine del corso. La prima prova intermedia sarà incentrata principalmente sugli argomenti illustrati nella prima metà del corso (semplici algoritmi ricorsivi, risoluzione di equazioni di ricorrenza, algoritmi di ordinamento naif), la seconda sugli argomenti illustrati nella seconda metà del corso (algoritmi per la soluzione di problemi di ordinamento, su liste e alberi). 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 entrambe 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 in presenza. Alla didattica in aula, si affianca una attività di *tutoraggio* in cui si risponde alle domande degli studenti e si organizzano esercitazioni su argomenti concordati con gli studenti.