Tags:
tag this topic
create new tag
view all tags
---++!! <big>Algoritmi per le Reti </big> ---+++!! Informatica & Tecnologie Informatiche, A.A. 2007/2008 ---++++!! Docente: [[http://www.dsi.uniroma1.it/~finocchi][Irene Finocchi]] ---- %TOC% ---- <!-- * *Appelli e prenotazioni*: sono in rete i fogli di prenotazione per gli appelli del [[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2008_01_22_ScrittoAlgoReti][22 gennaio]] e del [[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2008_02_13_ScrittoAlgoReti][13 febbraio]]. --> ---++++ Avvisi * *Risultati appello 11 settembre*: è possibile verbalizzare *martedì 14 ottobre alle ore 11:00* nel mio ufficio. <center> | | *Es. 1.1* | *Es. 1.2* | *Es. 2* | *Es. 3* | *Voto proposto* | | Abblasio | 4 | 4 | / | 9 | Insuff. | | Ascolillo | 4 | 6 | / | 2 | Insuff. | | Cammarano | 6 | 2 | 5 | 10 | 23 | | Carloppi | 2 | 1 | 2 | 2 | Insuff. | | Coschignano | 8 | 2 | / | 10 | 20 | | De Rosa | 6 | 1 | / | 10 | Insuff. | | Di Cola | 8 | 2 | 5 | 10 | 25 | | Mauro | 8 | 8 | 10 | 10 | 30L | | Rossi | 7 | 7 | / | 5 | 19 | | Spaccini | 4 | 3 | 10 | 10 | 27 | </center> * *Appello settembre*: è in rete il foglio di prenotazione per l'appello dell'[[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2008_09_11_AlgoritmiPerLeReti][11 settembre]]. * *Consegna progetti*: i progetti software vanno consegnati entro il 30 settembre 2008. * *Risultati esame 8 luglio 2008 e verbalizzazioni*: i risultati sono disponibili a [[%ATTACHURL%/8luglio08.pdf][questo link]]. Nei prossimi giorni metterò in rete le soluzioni degli esercizi. Sarà possibile verbalizzare e vedere il compito (eventualmente anche quello dell'appello del 16 giugno) il giorno *mercoledì 10 settembre 2008*, dalle ore *10:30* alle ore *11:30*, presso il mio ufficio. * *Soluzioni*: sono in rete le soluzioni dell'appello del 16 giugno. Contengono anche la discussione degli errori più tipici che avete commesso. * *Verbalizzazione*: sarà possibile verbalizzare l'esame del 16 giugno (o eventualmente un esame sostenuto precedentemente, purché nel corrente anno accademico), il giorno *giovedì 26 giugno 2008*, dalle ore *9:30* alle ore *10:00*, presso l'ufficio della Prof.ssa Calamoneri. * *Risultati esame 16 giugno 2008*: i risultati sono disponibili a [[%ATTACHURL%/16giugno08.pdf][questo link]]. Hanno superato l'esame gli studenti che hanno conseguito un voto maggiore o uguale a 18. Nei prossimi giorni metterò in rete le soluzioni ideali degli esercizi e un ulteriore avviso con la data per la verbalizzazione. * *Prenotazioni*: sono in rete i fogli di prenotazione per gli appelli del [[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2008_06_16_AlgoReti][16 giugno]] e dell'[[http://twiki.di.uniroma1.it/twiki/view/Prenotazioni/2008_07_08_AlgoReti][8 luglio]]. * *<font color=blue>Sarò in congedo obbligatorio per maternità fino al 4 agosto 2008</font>*. In tale periodo sarò sostituita dalla Prof.ssa Calamoneri, a cui potete rivolgervi per eventuali dubbi. Le modalità d'esame rimarranno ovviamente invariate (preparerò comunque io i compiti). * *Soluzioni esercizi*: ho messo in rete le soluzioni (ideali) degli esercizi dell'appello del 13 febbraio '08. * *Verbalizzazioni per gli appelli del 29/1/2008 e del 13/2/2008*: sono attualmente in maternità e quindi non verro' in dipartimento nell'immediato. Potete verbalizzare in uno degli appelli estivi oppure in settembre. Se avete particolare urgenza (ad esempio, dovete laurearvi nella sessione di maggio o vi serve il voto datato febbraio 2008 per ottenere una borsa di studio), mandatemi mail e farò in modo di farvi avere il verbale tramite un collega. * *Risultati esame 13 febbraio 2008*: i risultati sono disponibili a [[%ATTACHURL%/appello13febbraio08.pdf][questo link]]. Hanno superato l'esame gli studenti che hanno conseguito un voto maggiore o uguale a 18. * *Risultati esame 29 gennaio 2008*. Hanno superato l'esame i seguenti studenti: * David Bona 18 * Silvia Di Pompeo 24 * Fabio Portieri 22<br /> * Informazioni sul *[[ProgettoSoftware][progetto software]]* opzionale. * *Risultati secondo esonero*: i voti complessivi proposti dopo il secondo esonero sono disponibili a [[SecondoEsonero][questo link]]. Per la visione del compito e la verbalizzazione, potete venire *giovedì 24 gennaio* alle 11:00 nel mio ufficio. * [[%ATTACHURL%/RisultatiProvaIntermedia.pdf][Risultati della prima prova intermedia]]: hanno superato la prova gli studenti che hanno conseguito un voto maggiore o uguale a 18. ---++++ Orari <b>Orari delle lezioni:</b> le lezioni si sono svolte durante il primo semestre (il martedì e il venerdì dalle 10.30 alle 12.00 in Aula Seminari, via Salaria 113, terzo piano). <br> <b>Orario di ricevimento:</b> per appuntamento al termine del corso. Attualmente sospeso per maternità. ---++++ Obiettivi formativi Il corso si prefigge lo studio di problemi algoritmici legati alle reti di comunicazione, di trasporti e di informazione. Approfondiremo classici problemi di ottimizzazione combinatoria su reti, quali problemi di cammini minimi (che hanno un'importanza fondamentale nella progettazione di protocolli di routing), e problemi di flusso e taglio. Presenteremo inoltre brevemente metodologie algoritmiche fondamentali per le applicazioni emergenti in Internet e nel Web, con particolare attenzione rivolta a problematiche algoritmiche relative al funzionamento dei motori di ricerca. ---++++ Propedeuticità Nessun insegnamento è propedeutico, ma il corso tiene conto che si abbiano le conoscenze impartite nei corsi di Algoritmi 1 e Algoritmi 2. ---++++ Modalità d'esame <font color=green>L'esame consiste in una prova scritta obbligatoria, una prova orale facoltativa, ed un progetto facoltativo. L'orale puo' essere richiesto dal docente nel caso di voti dubbi, o dallo studente nel caso voglia aumentare il voto ottenuto allo scritto (ovviamente, a proprio rischio e pericolo!). Informazioni sul progetto sono disponibili su [[ProgettoSoftware][questa pagina]].</font> <b>Prove intermedie</b>: sono previste una prova scritta intermedia (martedì 13 novembre) che riguarda solamente gli argomenti svolti nella prima parte del corso, ed un secondo esonero al termine del corso per coloro che abbiano superato la prova intermedia. <font color=green><b>Per partecipare alle prove scritte (inclusa la prima prova intermedia) è obbligatoria la prenotazione.</b></font> ---++++ Programma per l'A.A. 2007-2008 * Cammini minimi e routing: richiami al problema dei cammini minimi, agli algoritmi di Dijkstra e di Bellman-Ford. Distance vector protocol: implementazione distribuita asincrona dell'algoritmo di Bellman-Ford. Algoritmi di Floyd-Warshall e di Johnson per il calcolo dei cammini minimi tra tutte le coppie di nodi. * Problemi di flusso e taglio: definizioni, teorema di massimo flusso-minimo taglio, cammini aumentanti, algoritmo di labeling, capacity scaling, shortest augmenting path, approccio preflow-push. Guardare il diario delle lezioni per un elenco dettagliato degli argomenti svolti ed i relativi riferimenti bibliografici. <!-- * Web Information Retrieval: cenni alla struttura di un motore di ricerca: crawling, compressione, indicizzazione, ricerca. Fondamenti teorici del crawling: visite di grafi. Strutture dati per l'indicizzazione. Algoritmi di ranking: link analysis, Page Rank e HITS. --> ---++++ Libri di testo e materiale didattico Non esiste (purtroppo o per fortuna!) un unico libro di testo per il corso. Nel diario delle lezioni vi indicherò di volta in volta quali sono le fonti da cui gli argomenti affrontati a lezione sono stati tratti. Trovate di seguito un elenco di libri, articoli, dispense e lucidi che useremo durante il corso. Tutti i libri dovrebbero essere disponibili in biblioteca: se così non fosse fatemelo sapere. L'elenco è destinato a variare nel tempo, quindi consultatelo spesso. <b>Libri utili</b> * [AMO93] R. K. Ahuja, T. L. Magnanti e J. B. Orlin. Network Flows. Prentice Hall, 1993. * [CLRS01] T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Introduction to algorithms. MIT Press e Mc Graw Hill, 2001. * [DFI04] C. Demetrescu, I. Finocchi e G. F. Italiano. Algoritmi e Strutture Dati. Mc Graw Hill, 2004. * [KT06] R. Kleinberg ed E. Tardos. Algorithm Design. Addison Wesley, 2006. * [KR03] J. F. Kurose e K. W. Ross. Computer Networking: a Top-Down Approach Featuring the Internet. Addison-Wesley, 2003. <!-- * [WMB99] I. H. Witten, A. Moffat e T. C. Bell. Managing Gigabytes. Morgan Kaufmann, 1999.--> <b>Articoli scientifici</b> <!-- * [BP98] S. Brin e L. Page. [[http://citeseer.ist.psu.edu/brin98anatomy.html][The Anatomy of a Large-Scale Hypertextual Web Search Engine]]. In Proceedings of the 7th International World Wide Web Conference, 107-117, 1998. * [H00] M. Henzinger. [[http://citeseer.ist.psu.edu/henzinger00web.html][Web Information Retrieval - An Algorithmic Perspective]]. In Proceedings of the 8th Annual European Symposium on Algorithms, LNCS 1879, 1-8, 2000. * [K99] J. Kleinberg. [[http://citeseer.ist.psu.edu/kleinberg99authoritative.html][Authoritative sources in a hyperlinked environment]]. Journal of the ACM, 46, 604-632, 1999. * [LM05] A. N. Langville e C. D. Meyer. [[http://citeseer.ist.psu.edu/langville03survey.html][A survey of eigenvector methods for Web Information Retrieval]]. SIAM Review, 47(1), 135-161, 2005. --> * [Zwick95] Uri Zwick. The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science, 148, 165-170, 1995. Il draft dell'articolo e' disponibile on-line presso la [[http://www.cs.tau.ac.il/%7Ezwick/][pagina Web di Uri Zwick]], seguendo il link GRAPH ALGORITHMS. <b>Dispense e lucidi</b> * [Kleinberg-Reti] [[%ATTACHURL%/KleinbergReti.pdf][Grafi e reti]]. Alcuni appunti da un corso tenuto da Jon Kleinberg. * [Intro] [[%ATTACHURL%/slides1.pdf][Introduzione al corso, tipologie di reti]]. Lucidi usati a lezione. * [DVP] [[%ATTACHURL%/slides2.pdf][Distance Vector Protocol]]. Lucidi usati a lezione. <!-- * [Pagerank] [[%ATTACHURL%/pagerankPanconesi.pdf][The Stationary Distribution of Markov Chain]]. Appunti a cura del Prof. Panconesi sulla convergenza dell'algoritmo pagerank. * [HITS] [[%ATTACHURL%/hitsPanconesi.pdf][Eigenvalues and Search Engines]]. Appunti a cura del Prof. Panconesi sulla convergenza dell'algoritmo HITS. --> ---++++[[DiarioLezioni][Diario delle lezioni]] ---++++ Esercizi Gli esercizi elencati di seguito sono stati esplicitamente assegnati e/o svolti a lezione. Potete trovarne molti altri nei libri [AMO93, CLRS01, DFI04, KT06]. Svolgere esercizi è estremamente utile per rielaborare personalmente gli argomenti presentati a lezione (e quindi per superare l'esame!). 1 Problema 13.2 preso da [DFI04] 2 Problema 13.8 preso da [DFI04] 3 Considerare la dimostrazione del teorema di correttezza delle stime vista a lezione, e dimostrare che deve essere v=x. 4 Esibire un'istanza su cui l'algoritmo di Bellman-Ford esegue molti rilassamenti inutili: mi aspetto che l'algoritmo esegua mediamente Theta(n) rilassamenti per passata. Istanze su cui ci sono piu' rilassamenti inutili all'inizio, e il loro numero decresce (lentamente) all'avanzare dell'esecuzione, sono ok. 5 Discutere se l'algoritmo di Dijkstra funziona ancora nel caso in cui esistono archi di peso negativo nel grafo, ma tutti escono dalla sorgente. Nel caso di risposta negativa mostrare un controesempio, nel caso di risposta affermativa dare una dimostrazione formale. 6 Considerate un grafo in cui esistono archi di peso negativo, e ripesate gli archi aggiungendo una costante C (la stessa per tutti gli archi) sufficientemente grande in modo che i nuovi pesi siano tutti maggiori o uguali a zero. Eseguite l'algoritmo di Dijkstra sul grafo con i nuovi pesi. L'albero dei cammini minimi prodotto e' un albero dei cammini minimi anche rispetto alla pesatura originale? Se si, dare una dimostrazione formale. Se no, dare un controesempio e discutere da dove nasce il problema. 7 Dato un grafo G, una tabella delle distanze D tra tutte le coppie di nodi, e due nodi x e y, progettare un algoritmo che ricostruisca un cammino minimo da x a y. 8 Nell'algoritmo di Johnson, perche' occorre aggiungere il nodo fittizio s per calcolare i valori della funzione h? 9 Dato un grafo (orientato e con pesi positivi sugli archi) e dati due nodi s e t, progettare un algoritmo per trovare il cammino da s a t con il più alto "collo di bottiglia". Il collo di bottiglia di un cammino e' un arco di peso minore o uguale al peso di tutti gli altri archi del cammino. ---++++ Testi d'esame degli appelli precedenti * Appello del [[%ATTACHURL%/appello16giu08.pdf][16 giugno 2008]] e [[%ATTACHURL%/appello16giu08sol.pdf][soluzioni]] * Appello del [[%ATTACHURL%/appello13feb08.pdf][13 febbraio 2008]] e [[%ATTACHURL%/appello13feb08sol.pdf][soluzioni]] * Appello del [[%ATTACHURL%/appello29gen08.pdf][29 gennaio 2008]] * Esonero dell'[[%ATTACHURL%/appello8gen07.pdf][8 gennaio 2008]] * Appello dell'[[%ATTACHURL%/appelloStraordinario8gen07.pdf][8 gennaio 2008]] * Esonero del [[%ATTACHURL%/appello13nov7.pdf][13 novembre 2007]] * Esame del [[%ATTACHURL%/appello17sett07.pdf][17 settembre 2007]] * Esame del [[%ATTACHURL%/appello2luglio07.pdf][2 luglio 2007]] * Esame del [[%ATTACHURL%/appello19giugno07.pdf][19 giugno 2007]] * Esonero del [[%ATTACHURL%/esonero12giugno07.pdf][12 giugno 2007]] * Esonero del [[%ATTACHURL%/esoneroAlgoReti-190407.pdf][19 aprile 2007]]
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r49
<
r48
<
r47
<
r46
<
r45
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r49 - 2008-10-07
-
IreneFinocchi
Log In
or
Register
Algoreti Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Prenotazioni esami
Laurea Triennale ...
Laurea Triennale
Algebra
Algoritmi
Introduzione agli algoritmi
Algoritmi 1
Algoritmi 2
Algoritmi per la
visualizzazione
Architetture
Prog. sist. digitali
Architetture 2
Basi di Dati
Basi di Dati 1 Inf.
Basi di Dati 1 T.I.
Basi di Dati (I modulo, A-L)
Basi di Dati (I modulo, M-Z)
Basi di Dati 2
Calcolo
Calcolo differenziale
Calcolo integrale
Calcolo delle Probabilitą
Metodi mat. per l'inf. (ex. Logica)
canale AD
canale PZ
Programmazione
Fond. di Programmazione
Metodologie di Programmazione
Prog. di sistemi multicore
Programmazione 2
AD
EO
PZ
Esercitazioni Prog. 2
Lab. Prog. AD
Lab. Prog. EO
Lab. Prog. 2
Prog. a Oggetti
Reti
Arch. di internet
Lab. di prog. di rete
Programmazione Web
Reti di elaboratori
Sistemi operativi
Sistemi Operativi (12 CFU)
Anni precedenti
Sistemi operativi 1
Sistemi operativi 2
Lab. SO 1
Lab. SO 2
Altri corsi
Automi, Calcolabilitą
e Complessitą
Apprendimento Automatico
Economia Aziendale
Elaborazione Immagini
Fisica 2
Grafica 3D
Informatica Giuridica
Laboratorio di Sistemi Interattivi
Linguaggi di Programmazione 3° anno Matematica
Linguaggi e Compilatori
Sistemi Informativi
Tecniche di Sicurezza dei Sistemi
ACSAI ...
ACSAI
Computer Architectures 1
Programming
Laurea Magistrale ...
Laurea Magistrale
Percorsi di studio
Corsi
Algoritmi Avanzati
Algoritmica
Algoritmi e Strutture Dati
Algoritmi per le reti
Architetture degli elaboratori 3
Architetture avanzate e parallele
Autonomous Networking
Big Data Computing
Business Intelligence
Calcolo Intensivo
Complessitą
Computer Systems and Programming
Concurrent Systems
Crittografia
Elaborazione del Linguaggio Naturale
Estrazione inf. dal web
Fisica 3
Gamification Lab
Information Systems
Ingegneria degli Algoritmi
Interazione Multi Modale
Metodi Formali per il Software
Methods in Computer Science Education: Analysis
Methods in Computer Science Education: Design
Prestazioni dei Sistemi di Rete
Prog. avanzata
Internet of Things
Sistemi Centrali
Reti Wireless
Sistemi Biometrici
Sistemi Distribuiti
Sistemi Informativi Geografici
Sistemi operativi 3
Tecniche di Sicurezza basate sui Linguaggi
Teoria della
Dimostrazione
Verifica del software
Visione artificiale
Attivitą complementari
Biologia Computazionale
Design and development of embedded systems for the Internet of Things
Lego Lab
Logic Programming
Pietre miliari della scienza
Prog. di processori multicore
Sistemi per l'interazione locale e remota
Laboratorio di Cyber-Security
Verifica e Validazione di Software Embedded
Altri Webs ...
Altri Webs
Dottorandi
Commissioni
Comm. Didattica
Comm. Didattica_r
Comm. Dottorato
Comm. Erasmus
Comm. Finanziamenti
Comm. Scientifica
Comm Scientifica_r
Corsi esterni
Sistemi Operativi (Matematica)
Perl e Bioperl
ECDL
Fondamenti 1
(NETTUNO)
Tecniche della Programmazione 1° modulo
(NETTUNO)
Seminars in Artificial Intelligence and Robotics: Natural Language Processing
Informatica generale
Primo canale
Secondo canale
II canale A.A. 10-11
Informatica
Informatica per Statistica
Laboratorio di Strumentazione Elettronica e Informatica
Progetti
Nemo
Quis
Remus
TWiki ...
TWiki
Tutto su TWiki
Users
Main
Sandbox
Home
Site map
AA web
AAP web
ACSAI web
AA2021 web
Programming web
AA2021 web
AN web
ASD web
Algebra web
AL web
AA1112 web
AA1213 web
AA1920 web
AA2021 web
MZ web
AA1112 web
AA1213 web
AA1112 web
AA1314 web
AA1415 web
AA1516 web
AA1617 web
AA1819 web
Old web
Algo_par_dis web
Algoreti web
More...
Algoreti Web
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
View
Raw View
Print version
Find backlinks
History
More topic actions
Edit
Raw edit
Attach file or image
Edit topic preference settings
Set new parent
More topic actions
Account
Log In
Register User
Questo sito usa cookies, usandolo ne accettate la presenza. (
CookiePolicy
)
Torna al
Dipartimento di Informatica
E
dit
A
ttach
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