Informatica

ANGELO MONTI

Obiettivi generali:
Questo corso introduce agli studenti i metodi per la progettazione e l’analisi degli algoritmi. Saranno illustrate anche strutture dati non elementari.
Obiettivi specifici:
Gli studenti studieranno varie tecniche algoritmiche di ampia applicazione come la tecnica greedy, il divide et impera, la programmazione dinamica e il backtracking. Le varie tecniche verranno illustrate tramite algoritmi classici come l' algoritmo di Dijkstra e l'algoritmo di Bellman Ford per la ricerca dei cammini minimi, l'algoritmo di Kruskal o l'algorimo di Prim per il problema dell'albero di copertura di costo minimo.
Conoscenze e comprensione: Al termine del corso gli studenti conosceranno le metodologie per la progettazione e l'analisi di algoritmi, le strutture dati non banali, i principali algoritmi.
Applicare conoscenze e comprensione: Al termine del corso gli studenti avranno acquisito familiarità con le principali strutture dati. Sapranno spiegare gli algoritmi e analizzarne la complessità, evidenziando come le prestazioni dipendano dalla struttura dati utilizzata. Messi di fronte ad un nuovo problema avranno a disposizione diverse tecniche algoritmiche a cui far riferimento alla ricerca di un algoritmo efficiente per risolverlo.
Capacità critiche e di giudizio:
Lo studente avrà gli strumenti 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:
Le conoscenze acquisite permetteranno allo studente di affrontare problemi combinatorici utilizzando tecniche algoritmiche e strutture dati più avanzate rispetto a quelle viste nel corso di introduzione agli algoritmi.

Obiettivi generali:

Questo corso introduce agli studenti i metodi per la progettazione e l’analisi degli algoritmi. Studieranno varie tecniche algoritmiche di ampia applicazione come la tecnica greedy, il divide et impera, la programmazione dinamica e il backtracking. Le varie tecniche verranno illustrate tramite algoritmi classici come l' algoritmo di Dijkstra e l'algoritmo di Bellman Ford per la ricerca dei cammini minimi, l'algoritmo di Kruskal o l'algorimo di Prim per il problema dell'albero di copertura di costo minimo. Saranno illustrate anche strutture dati non elementari.

Obiettivi specifici:

*Conoscenza e comprensione:
Al termine del corso gli studenti conosceranno le metodologie per la progettazione e l'analisi di algoritmi, le strutture dati non banali, i principali algoritmi.

*Applicare conoscenza e comprensione:
Al termine del corso gli studenti avranno acquisito familiarità con le principali strutture dati. Sapranno spiegare gli algoritmi e analizzarne la complessità, evidenziando come le prestazioni dipendano dalla struttura dati utilizzata. Messi di fronte ad un nuovo problema avranno a disposizione diverse tecniche algoritmiche a cui far riferimento alla ricerca di un algoritmo efficiente per risolverlo.

*Capacità critiche e di giudizio:
Lo studente avrà gli strumenti 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: Le conoscenze acquisite permetteranno allo studente di affrontare problemi combinatorici utilizzando tecniche algoritmiche e strutture dati più avanzate rispetto a quelle viste nel corso di introduzione agli algoritmi.

Una discreta conoscenza dell’inglese è di aiuto.

Il corso prosegue il cammino iniziato al primo anno con Introduzione agli algoritmi. Il corso è diviso in tre parti.
La prima parte riguarda i grafi e le visite (DFS e BFS). Nella seconda parte di trattano due tecniche di
progettazione ( greedy and divide-et-impera) che funzionano bene per particolari tipi di problemi e
si parla anche di euristiche come metodo per affrontare problemi particolarmente difficili.
Nella terza parte si illustrano la programmazione dinamica e il backtraking, due tecniche potenti e generali.
Tutte le tecniche sono illustrate tramite esempi significativi.

T.H. Cormen, C.Papadimitriou, U. Vazirani. Introduzione agli algoritmi
J. Kleinberg, E. Tardos      Algorithm Design   
S. Dasgupta, C. Papadimitriou, U. Vazirani      Algorithms  
C. Demetrescu, I. Finocchi, G.F. Italiano Algoritmi e strutture dati

Sarà cura della docente distribuire materiale didattico, relativo sia alle lezioni ed esercitazioni (sotto forma di dispense).

Il corso si basa su lezioni e dimostrazioni in presenza e su esercizi da svolgere a casa.

la frequenza non è obbligatoria

La prova di esame consiste in una prova scritta in cui gli studenti devono risolvere alcuni
semplici esercizi. La prova avrà' una durata di 120-150 minuti e comporterà' domande a stimolo
chiuso e risposta aperte. Seguirà un orale a discrezione del docente.
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.

si veda la pagina: https://twiki.di.uniroma1.it/twiki/view/Algoritmi2/WebHome

• introduzione al corso [2 ore]
  • Testi di riferimento: Dispense del docente


• Grafi visite BFS e DFS e loro applicazioni [15 ore]
  • Testi di riferimento: Dispense del docente


• La tecnica greedy [8 ore]
  • Testi di riferimento: Dispense del docente


• Euristiche ed algoritmi d'approssimazione
  • Testi di riferimento: Dispense del docente


• La tecnica del divide et impera [5 ore]
  • Testi di riferimento: Dispense del docente


• La tecnica della programmazione dinamica [15 ore]
  • Testi di riferimento: Dispense del docente


• La tecnica del Backtracking [10 ore]