Tags:
create new tag
view all tags
---++ <font color="blue" size="+3">Lesson Diary A.y. 2023-2024</font> %GREEN% *Monday, September 25, 2023 (Lessons 1-2-3):* %ENDCOLOR% *Introduction* *The Routing Problem i.e. the Least Cost Path Problem (1)* * The routing Problem * The shortest path Problem * shortest paths: BFS * The least cost path Problem (1) * the negative cycle issue * least cost paths: introduction * Bellman-Ford algorithm * Dijkstra algorithm (part) %GREEN% *Thursday, September 28, 2023 (Lessons 4-5):* %ENDCOLOR% *The Routing Problem i.e. the Least Cost Path Problem (2)* * The least cost path Problem (2) * Dijkstra algorithm (part) * Floyd-Warshall algorithm * The Routing Problem on Interconnection Topologies * the packet-switching model * the Butterfly network * routing on the Butterfly network: the greedy algorithm * The concept of blocking network, non-blocking network, and rearrangeable network %GREEN% *Monday, October 2, 2023 (Lessons 6-7-8):* %ENDCOLOR% *The Routing Problem i.e. the Least Cost Path Problem (3)* * The Routing Problem on Interconnection Topologies * The Benes network * routing on the Benes network: the looping algorithm *The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (1)* * The Thompson model * The orthogonal grid drawing of graphs * Layout of the complete binary tree (H-tree) * Collinear Layout of the Complete network * Layout of the Complete network * Relation between bisection width and layout area * Layout of the Butterfly network * The Wise layout %GREEN% *Thursday, October 5, 2023 (Lessons 9-10):* %ENDCOLOR% *The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)* * Layout of the Butterfly network * The Even & Even layout * comparison between the two methods * Optimal area layout %GREEN% *Monday, October 9, 2023 (Lessons 11-12-13):* %ENDCOLOR% *The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)* * Layout of the Hypercube network * Collinear layout * general layout * The 3D layout problem *The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)* * The problem * worms * damages caused by worms * Model of the problem on graphs: minimum vertex cover * Definition * ILP model * a 2-approximation algorithm * independent set and maximum matching in relation to vertex cover * another approximation algorithm %GREEN% *Thursday October 12, 2023 (Lessons 14-15):* %ENDCOLOR% *The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)* * Model of the problem on graphs: minimum vertex cover * Konig-Egevary theorem (without proof) * A related problem: eternal vertex problem *A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)* * Introduction to the frequency assignment problems %GREEN% *Monday October 16, 2023 (Lessons 16-17-18):* %ENDCOLOR% *A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)* * Direct and hidden collisions, interference graph * Introduction to the frequency assignment problems * Direct and hidden collisions, interference graph * L(h,k)-labeling and minimum span (1) * The special case h=k in relation to the square of a graph * Properties of the L(h,k)-labeling and their proofs * Proof of NP-completeness for diameter 2 graphs * Lower bound of Delta+1 on lambda * Example: a graph requiring lambda=Delta squared - Delta * Upper bound of Delta squared + 2 Delta * Griggs and Yeh's conjecture * Exact results: cliques * Exact results: stars * Exact results: trees * Exact results: paths * Exact results: cycles * Exact results: grids * Approximate results: outerplanar graphs %GREEN% *Thursday, October 19, 2023 (Lessons 22-23):* %ENDCOLOR% *Special guest:* Jan Arne Telle - University of Bergen - https://www.uib.no/en/persons/Jan.Arne.Telle *Seminar entitled:* Recognition of Linear and Star Variants of Leaf Powers is in P %GREEN% *Monday, October 23, 2023 (Lessons 24-25-26):* %ENDCOLOR% *A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)* * Variations of the problem * oriented L(2,1)-labeling * L(h1, ..., hk)-labeling * backbone coloring * multiple L(h,k)-labeling * a parenthesis on the 4-color theorem *The minimum energy broadcast i.e. the minimum spanning tree (1)* * The Min Broadcast problem * NP-completeness and inapproximability results (reduction from Min Set Cover) * Relation between Min Broadcast and Min Spanning Tree (MST) %GREEN% *Thursday, October 26, 2023 (Lessons 27-28):* %ENDCOLOR% *The minimum energy broadcast i.e. the minimum spanning tree (2)* * The MST problem * Kruskal algorithm * Prim algorithm * Boruvka algorithm * The Min Broadcast problem * MST heuristics * SPT heuristics * BAIP heuristics * approximation ratio for MST %RED% *Mid-term exam: first part* %ENDCOLOR% %GREEN% *Monday, October 30, 2023 (Lessons 29-30-31):* %ENDCOLOR% *The data mule problem i.e. the TSP* * (Fixed) sensor networks * The Data Mule problem * The TSP * NP-completeness * inapproximability * special cases: metric TSP and Euclidean TSP * generalizations *The Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem* * the connected dominating set problem * the dominating set problem * the connected dominating set problems in unit disk graphs %GREEN% *Thursday, November 2, 2023 (Lessons 32-33):* %ENDCOLOR% *The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)* * (mobile) sensor networks %RED% *Mid-term exam: second part* %ENDCOLOR% %GREEN% *Monday November 6, 2023 (Lessons 34-35-36):* %ENDCOLOR% *The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs(2)* * The problem of centralized deployment * The problem on graphs: min weight matching in bipartite graphs * maximum matching in a bipartite graph * P. Hall theorem (with proof) * corollary to the P. Hall theorem * searching for an augmenting path * Berge theorem on the augmenting paths * algorithm based on Berge theorem * Hopcroft & Karp algorithm * augmenting paths * an algorithm based on searching augmenting paths * ILP formulation %GREEN% *Thursday, November 9, 2023 (Lessons 37-38):* %ENDCOLOR% %RED% *Mid-term exam: third part* %ENDCOLOR% %GREEN% *Monday November 13, 2023 (Lessons 39-40-41):* %ENDCOLOR% *The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)* * Maximum matching in general graphs * blossoms * lemma on the cycle contraction * Edmonds algorithm (idea) * Another application *The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)* * The problem * A Possible Approach: Virtual Forces * A Protocol Based on Voronoi Diagrams * Voronoi Diagrams * hypothesis of general position * properties * complexity * the dual problem: Delaunay triangulation * half-plane intersection (divide et impera) %GREEN% *Thursday November 16, 2023 (Lessons 42-43):* %ENDCOLOR% *The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)* * Algorithms to compute the Voronoi diagram * Fortune algorithm %RED%students'opinions questionnaire - OPIS code: 73X3JB6A (1st year students) and SIJ1BMJY (2nd year students) %ENDCOLOR% [[%ATTACHURL%/guided_path_to_access_student_s_opinions_questionnaire_2022_2023.pdf][HERE]]: instructions for student's opinions questionnaire 2022/2023 %GREEN% *Monday, November 20, 2023 (Lessons 44-45-46):* %ENDCOLOR% *The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)* * Heterogeneous sensors * A new notion of distance: Laguerre distance * Voronoi-Laguerre diagrams * A protocol based on Voronoi-Laguerre distance *Monitoring by UAVs i.e. what? (+some open problems)* %RED% *Thursday, November 23, 2023* %ENDCOLOR% *Canceled* %GREEN% *Monday, November 27, 2023 (Lessons 47-48-49):* %ENDCOLOR% *Other kinds of networks: the phylogeny and medicine cases (+some open problems)* %RED% *Thursday, November 30, 2023* %ENDCOLOR% *Canceled* %GREEN% *Monday, December 4, 2023 (Lessons 50-51-52):* %ENDCOLOR% *Student lessons*: Cukaj, Factor, Fiusco, Korpal, Pinna, Pro %GREEN% *Thursday, December 7, 2023 (Lessons 53-54):* %ENDCOLOR% *Student lessons*: Lundholm, Moldovan, Zhou %GREEN% *Monday, December 11, 2023 (Lessons 55-56-57):* %ENDCOLOR% *Student lessons*: Bertagnoli, D'Ambrosio, Finelli, Florescu, Gaetani, Guarini, Loffredi %RED% *Thursday, December 14, 2023* %ENDCOLOR% *Canceled* %GREEN% *Monday, December 18, 2023 (Lessons 58-59-60):* %ENDCOLOR% %RED% *Mid-term exam* %ENDCOLOR% <!-- GIO 30/11 2h cuscinetto LUN 4/12 3h cuscinetto GIO 7/12 2h 5 student's lessons LUN 11/12 3h 8 student's lessons GIO 14/12 2h 5 student's lessons LUN 18/12 3h MID-TERM GIO 21/12 no lezione %GREEN% *Thursday, November 30, 2023 (Lessons 52-53-54)* %ENDCOLOR% %RED% *Friday, December 16, 2022 (Lessons 55-56): no lesson* %ENDCOLOR% %RED% *Tuesday December 20, 2022 (Lessons 57-58-59): SECOND MID-TERM EXAM* %ENDCOLOR% --> <!--SALTATO QUEST'ANNO 23/24 *The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem* * The problem of minimizing boolean functions * Model of the problem on graphs: the Minimum Set Cover Problem * definition * ILP formulation * relation with the Minimum Vertex Covering Problem * an O(log n)-approximation algorithm * another approximation algorithm * some related problems: * Hitting set problem * Edge Cover problem * Set Packing problem * Exact Cover problem --> [[PreviousYears][Lesson Diary of the Previous Years]] <!-- Commento -->
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r178
<
r177
<
r176
<
r175
<
r174
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r178 - 2023-11-27
-
TizianaCalamoneri
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
P
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-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback