Computer Science - Informatica

TIZIANA CALAMONERI

Obiettivi generali
Acquisire conoscenze relativamente al progetto di algoritmi complessi per risolvere problemi su grafi che modellano problemi inerenti le reti (cablate, senza fili e di sensori).

Obiettivi specifici
Conoscenza e comprensione
Al termine del corso gli studenti conosceranno le metodologie di base per l'analisi di problemi relativi alle reti e l’identificazione dei problemi su grafi che più si avvicinino; conosceranno inoltre gli algoritmi risolutivi di alcuni dei principali problemi su grafi.

Applicare conoscenza e comprensione:
Al termine del corso gli studenti avranno acquisito familiarità con l’analisi delle problematiche legate alle reti. Saranno in grado di riconoscere quale sia il problema su grafi che più si avvicina e di progettare nuove strutture dati e i relativi algoritmi, rielaborando quelli esistenti, per risolvere il problema di partenza.

Capacità critiche e di giudizio
Lo studente avrà le basi per analizzare la qualità di un algoritmo per le reti, 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 durante la prova orale.

Capacità di apprendimento
Le conoscenze acquisite permetteranno allo studente, una volta concluso il ciclo di studi, di affrontare problemi reali in modo critico ed efficace e di progettare soluzioni efficienti.

Obiettivi generali

Acquisire conoscenze relativamente al progetto di algoritmi complessi per risolvere problemi su grafi che modellano problemi inerenti le reti (cablate, senza fili e di sensori).

Obiettivi specifici

*Conoscenza e comprensione:
Al termine del corso gli studenti conosceranno le metodologie di base per l'analisi di problemi relativi alle reti e l’identificazione dei problemi su grafi che più si avvicinino; conosceranno inoltre gli algoritmi risolutivi di alcuni dei principali problemi su grafi.

*Applicare conoscenza e comprensione:
Al termine del corso gli studenti avranno acquisito familiarità con l’analisi delle problematiche legate alle reti. Saranno in grado di riconoscere quale sia il problema su grafi che più si avvicina e di progettare nuove strutture dati e i relativi algoritmi, rielaborando quelli esistenti, per risolvere il problema di partenza.

*Capacità critiche e di giudizio:
Lo studente avrà le basi per analizzare la qualità di un algoritmo per le reti, 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 durante la prova orale.

*Capacità di apprendimento:
Le conoscenze acquisite permetteranno allo studente, una volta concluso il ciclo di studi, di affrontare problemi reali in modo critico ed efficace e di progettare soluzioni efficienti.

Per frequentare proficuamente le lezioni dell'insegnamento Network Algorithms sono indispensabili i fondamenti degli Algoritmi e le strutture dati, che saranno utilizzati come base già consolidata.
Queste conoscenze vengono usualmente fornite in due corsi della laurea triennale in Informatica (almeno 12cfu). Gli studenti consapevoli di non possedere questi prerequisiti sono fortemente incoraggiati ad ottenerli prima di seguire le lezioni.

Questo insegnamento prevede le seguenti unità didattiche:

Introduzone del corso [2 ore]
Reti cablate [16 ore]
Reti senza fili [16 ore]
Reti di sensori mobili [16 ore]
Tesine degli studenti [10 ore].

Segue il programma in maggior dettaglio.

0. Introduzione al corso

1. reti cablate
1.1. Il problema dell'instradamento ovvero il problema della ricerca del cammino più corto di costo minimo (pesi pari al costo o alla probabilità di guasto della connessione)
1.2. Il problema del layout di topologie di interconnessione ovvero il problema del disegno ortogonale su griglia
1.3. Il problema di infettare (e difendere) una rete con un worm ovvero il problema della minima copertura di vertici
1.4. Il problema di minimizzare un circuito booleano ovvero il problema della minima copertura di insiemi

2. reti wireless ad hoc/wireless ad hoc networks
2.1. Il problema dell'assegnazione di frequenze ovvero un problema di colorazione di grafi
2.2. Il problema del broadcast con minimo dispendio di energia ovvero il problema del minimo albero ricoprente
2.3. Il problema del data mule ovvero il problema del commesso viaggiatore
2.4. Il Data Collection in reti di sensori ovvero il problema dell'insieme dominante connesso

3. reti di sensori mobili
3.1. Il problema del dispiegamento centralizzato di sensori mobili ovvero il problema dell'accoppiamento perfetto di costo minimo su grafo bipartito
3.2. Il problema del dispiegamento distribuito di sensori mobili ovvero il problema del diagramma di Voronoi
3.3. Monitorare tramite UAVs ovvero TSP multiplo con vincoli (più o meno)

Gli argomenti del corso riguardano per lo più la ricerca recente, per cui non c'è un libro di testo, quanto invece un numero di articoli.
Per ulteriori dettagli, si veda qui: https://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaDelCorso

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.

Per gli studenti che seguono le lezioni, l'esame è composto da due parti orali, entrambe obbligatorie.
Una prima prova di esame consiste in una breve lezione (circa mezz'ora), tenuta dallo studente, su un argomento assegnato dal docente (tesina). Questo esonera lo studente da tutto il capitolo del programma relativo all'argomento della lezione svolta.

Una seconda prova consiste nell'esame orale su tutti gli altri capitoli.

Gli studenti possono dividere quest'ultima in due parti e decidere liberamente quanti capitoli portare durante la prima parte, che potrà essere sostenuta approssimativamente a metà novembre.

Si sottolinea che, per come sono organizzati gli argomenti, questo esame è sconsigliato agli studenti che, per qualsiasi ragione, non seguano le lezioni. Tuttavia, gli studenti che comunque vogliano sostenere questo esame dovranno sostenere un unico orale su tutti gli argomenti del programma.

ogni argomento trattato a lezione: https://twiki.di.uniroma1.it/twiki/view/Algoreti/DiarioDelleLezioni

• Introduzone del corso [2 ore]


• Reti cablate [16 ore]


• Reti senza fili [16 ore]


• Reti di sensori mobili [16 ore]


• Tesine degli studenti [10 ore].