Informatica

ANGELO MONTI

Obiettivi specifici

Conoscenza e capacità di comprensione:
Al termine del corso, le studentesse e gli studenti conosceranno le metodologie di base per la progettazione e l'analisi di algoritmi iterativi e ricorsivi, le strutture dati elementari, i principali algoritmi di ordinamento e le implementazioni più semplici dei dizionari.

Conoscenza e capacità di comprensione applicate:
Al termine del corso, le studentesse e 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 progettuali sottostanti e le relative analisi di complessità; saranno in grado di confrontare i comportamenti asintotici dei tempi di esecuzione degli algoritmi studiati; saranno inoltre in grado di progettare soluzioni ricorsive a problemi e di analizzare asintoticamente gli algoritmi risultanti.

Autonomia di giudizio:
Le studentesse e gli studenti avranno le basi per analizzare la qualità di un algoritmo e delle relative strutture dati, sia dal punto di vista dell'efficacia nella risoluzione del problema sia da quello dell'efficienza computazionale con cui il problema viene risolto. Gli esercizi svolti a lezione dalla docente e quelli proposti come lavoro individuale contribuiranno ad affinare tali capacità.

Abilità comunicative:
Le studentesse e gli studenti acquisiranno la capacità di esporre in modo chiaro e organizzato le proprie conoscenze, capacità che verrà verificata sia mediante i quesiti presentati nelle prove scritte sia durante la prova orale. Saranno in grado di esprimere un’idea algoritmica in modo rigoroso e ad alto livello, utilizzando lo pseudocodice. La prova orale, prevista come parte integrante dell'esame, ha l'obiettivo di sviluppare ulteriormente tali abilità.

Capacità di apprendere:
Le conoscenze acquisite permetteranno alle studentesse e agli studenti di affrontare lo studio, sia individuale sia nell’ambito di un corso di laurea magistrale, di tecniche algoritmiche e strutture dati più avanzate.

Obiettivi generali:

Questo corso introduce i metodi di base per la progettazione e l’analisi degli algoritmi. Si studieranno vari algoritmi ben noti che risolvono problemi di base come l’ordinamento o la ricerca, insieme con i più semplici strumenti per analizzarli dal punto di vista dell’efficienza.

Obiettivi specifici:

*Conoscenza e capacità di comprensione:
Al termine del corso, le studentesse e gli studenti conosceranno le metodologie di base per la progettazione e l'analisi di algoritmi iterativi e ricorsivi, le strutture dati elementari, i principali algoritmi di ordinamento e le implementazioni più elementari dei dizionari.

*Conoscenza e capacità di comprensione applicate:
Al termine del corso, le studentesse e 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.

*Autonomia di giudizio:
Le studentesse e gli studenti avranno le basi per analizzare la qualità di un algoritmo e delle relative strutture dati, sia dal punto di vista dell'effettiva risoluzione del problema che da quello dell'efficienza computazionale con la quale il problema viene risolto.
Gli esercizi svolti a lezione dalla docente e quelli proposti da fare a casa affineranno queste capacità.

*Abilità comunicative:
Le studentesse e gli studenti acquisiranno 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. Le studentesse e gli studenti saranno in grado di esprimere un’idea algoritmica in modo rigoroso ad alto livello, in pseudocodice.
La prova orale prevista come parte integrante dell'esame ha l'obiettivo di accrescere queste abilità.

*Capacità di apprendere:
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 più avanzate.

Prerequisiti indispensabili per seguire le lezioni dell'insegnamento del corso 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 Analisi matematica I modulo e del primo corso di Programmazione, obbligatori per tutti e collocato al primo semestre del primo anno di corso.

1. Introduzione
Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale;
modello RAM; misura di costo uniforme e logaritmico.

2. 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

3. Introduzione alla ricorsione
funzioni ricorsive
versione iterativa e ricorsiva di algoritmi: esempi
calcolo del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
metodo di sostituzione
metodo iterativo
metodo dell'albero
teorema principale ( dimostrazione facoltativa )

4. Il problema dell'ordinamento
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

5. 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

6. 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 AVL e teorema per la limitazione dell'altezza
B-alberi

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 modalità di svolgimento è tradizionale; oltre alle consuete lezioni ed esercitazioni frontali, quando disponibile, le studentesse e gli studenti saranno affiancati da un tutor per risolvere (autonomamente o in gruppo) gli esercizi lasciati dalla docente.

la frequenza non è obbligatoria

L’esame mira a valutare l’apprendimento tramite una prova scritta di sbarramento e una prova orale.

La prova scritta è molto snella e consiste in brevi quesiti teorici e nella risoluzione di problemi dello stesso tipo di quelli svolti nelle esercitazioni; la prova orale, a cui può accedere chi abbia conseguito un voto sufficiente alla prova scritta, consiste nella discussione dei temi teorici più rilevanti illustrati nel corso e nell'elaborazione di soluzioni algoritmiche a problemi proposti.


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.

si veda la pagina: https://twiki.di.uniroma1.it/twiki/view/Algoritmi1/VecchiScritti

• introduzione al corso [2 ore]
  • Testi di riferimento: Capitolo 1 delle dispense. 


• Il problema della ricerca [8 ore].
  • Testi di riferimento: Capitolo 3 delle dispense


• Introduzione alla ricorsione [15 ore].  
  • Testi di riferimento: Capitoli 4 e 5 delle dispense


• Il problema dell'ordinamento [10 ore]. 
  • Testi di riferimento: Capitolo 6 delle dispense


• Strutture dati fondamentali e dizionari [25 ore].
  • Testi di riferimento: Capitolo 7 delle dispense