Tags:
create new tag
view all tags

Lesson Diary A.y. 2017-2018

Friday September 29, 2017 (Lessons 1-2,5):

Introduction

The Routing Problem i.e. the Shortest Path Problem (1)

  • The routing Problem
  • The shortest path Problem (1)
    • shortest paths: BFS
    • the negative cycle issue
    • least cost paths: introduction

Monday October 2, 2017 (Lessons 2,5-5):

The Routing Problem i.e. the Shortest Path Problem (2)

  • The shortest path Problem (2)
    • least cost paths (cnt.d): * Bellman-Ford algorithm
      • Dijkstra algorithm
      • Floyd-Warshall algorithm
  • The Routing Problem on Interconnection Topologies (1)
    • 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
    • the Benes network

Friday October 6, 2017 (Lessons 5-7,5):

The Routing Problem i.e. the Shortest Path Problem (3)

  • The Routing Problem on Interconnection Topologies (2)
    • 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
  • Collinear Layout of the Complete network
  • Layout of the Complete network

Monday October 9, 2017 (lessons 7,5-10):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

  • Layout of the Butterfly network (1)
    • the Wise layout
    • the Even & Even layout
    • comparison between the two methods

Friday October 13, 2017 (lessons 10-12,5):

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

Monday October 16, 2017 (lessons 12,5-15):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem

  • 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 with vertex cover
    • another approximation algorithm
    • Konig-Egevary theorem

The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)

  • The problem of minimizing boolean functions
  • Model of the problem on graphs: the Minimum Set Covering Problem
    • definition
    • ILP formulation
    • relation with the Minimum Vertex Covering Problem
    • an O(log n)-approximation algorithm

Friday October 20, 2017 (lessons 15-17,5):

The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)

    • another approximation algorithm
    • some related problems
      • Hitting set problem
      • Edge Cover problem
      • Set Packing problem
      • Exact Cover problem

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph
  • L(h,k)-labeling and minimum span
    • The special case h=k in relation to the suqre of a graph
    • Properties of the L(h,k)-labeling and their proofs

Monday October 23, 2017 (lessons 17.5-20):

Student Lessons with the presence of the teacher (1) see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

Friday October 27, 2017 (lessons 20-22.5):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

    • Proof of NP-completeness for diameter 2 graphs
    • Lower bound of Delta+1 on lambbda
    • 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
    • Approximate results: outerplanar graphs

Monday October 30, 2017 (lessons 22.5-25):

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
    • frequency assignment in GSM networks
  • 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)

Friday November 3, 2017 (lessons 25-27.5): The minimum energy broadcast i.e. the minimum spanning tree (2)

  • The MST problem
    • Kruskal algorithm
    • Prim algorithm
    • Boruvka algorithm
  • the Min Broadcast broblem
    • MST euristic
    • SPT euristic
    • BAIP euristic
    • approximation ratio for SPT

Monday November 6, 2017 (lessons 27.5-30): 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

Friday November 10, 2017 (lessons 30-32.5):

Attendance at the Workshop in honour of Janos Korner (both students and teacher)

Monday November 13, 2017 (lessons 32.5-35):

Student Lessons with the presence of the teacher (2) see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

Friday November 17, 2017 (lessons 35-37.5):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

  • (mobile) sensor networks
  • the problem of centralized deployment
  • the problem on graphs: min weight matching in a bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem
    • searching an augmenting path
    • Berge theorem on the augmenting paths
    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm

Monday November 20, 2017 (lessons 37.5-40):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

  • Minimum weight perfect matching in bipartite graphs
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation
  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm (idea)

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)

  • The problem
  • A Possible Approach: Virtual Forces

EVALUATION OF THE COURSE

Friday November 24, 2017 (lessons 40-42.5):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

  • A Protocol Based on Voronoi Diagrams
  • Voronoi Diagrams
    • hypthesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
  • Algorithms to compute the Voronoi diagram
    • half-plane intersection (divide et impera)
    • Fortune's algorithm

Monday November 27, 2017 (lessons 42.5-45):

Student Lessons with the presence of the teacher (3) see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

Friday December 1, 2017 (lessons 45-47.5):

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? (1)

Some theses proposals

Monday December 4, 2017 (lessons 47.5-50):

IT Meeting - http://www.studiareinformatica.uniroma1.it/38-it-meeting-lunedi-4-dicembre-2017

Friday December 8, 2017:

Holiday

Monday December 11, 2017 (lessons 50-52.5):

Monitoring by UAVs i.e. What? (2)

Some theses proposals

Some problems in (co-)Phylogeny

Some other theses proposals

Friday December 15, 2017 (lessons 52.5-55):

Student Lessons with the presence of the teacher (4) see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

Monday December 18, 2017 (lessons 55-57.5):

Student Lessons with the presence of the teacher (5) see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

Friday December 22, 2017 (lessons 57.5-60):

Mid term exam

Previous years' Diaries

Lesson Diary A.y. 2016-2017

Monday September 26, 2016 (Lessons 1-2):

Introduction

The Routing Problem i.e. the Shortest Path Problem (1)

  • The routing Problem
  • The shortest path Problem (1)
    • shortest paths: BFS
    • the negative cycle issue
    • least cost paths: introduction * Bellman-Ford algorithm

Friday September 30, 2016 (Lessons 3-4):

The Routing Problem i.e. the Shortest Path Problem (2)

  • The shortest path Problem (2)
    • least cost paths (cnt.d):
      • Dijkstra algorithm
      • Floyd-Warshall algorithm
  • The Routing Problem on Interconnection Topologies (1)
    • the packet switching model
    • the Butterfly network

Monday October 3, 2016 (Lessons 5-6):

The Routing Problem i.e. the Shortest Path Problem (3)

  • The Routing Problem on Interconnection Topologies (2)
    • routing on the Butterfly network: the greedy algorithm
    • the concept of blocking network, non-blocking network and rearrangeable network
    • 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
  • Collinear Layout of the Complete network
  • Layout of the Complete network

Friday October 7, 2016 (lessons 7-8):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

  • Layout of the Butterfly network (1)
    • the Wise layout
    • the Even & Even layout
    • comparison between the two methods

Monday October 10, 2016 (lessons 9-10):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)

  • Layout of the Butterfly network (2)
    • Optimal area Layout of the Butterfly
  • Layout of the Hypercube network
    • Collinear layout
    • general layout
  • The 3D layout problem

Friday October 14, 2016 (lessons 11-12):

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 with vertex cover
    • another approximation algorithm

Monday October 17, 2016 (lessons 13-14):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

  • minimum vertex cover (cntd)
    • Konig-Egevary theorem
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)
  • The problem of minimizing boolean functions
  • Model of the problem on graphs: the Minimum Set Covering Problem
    • definition
    • ILP formulation
    • relation with the Minimum Vertex Covering Problem
    • an O(log n)-approximation algorithm
    • another approximation algorithm

Friday October 21, 2016 (lessons 15-16):

The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)

    • some related problems
      • Hitting set problem
      • Edge Cover problem
      • Set Packing problem
      • Exact Cover problem

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph

Monday October 24, 2016 (lessons 17-18): A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

  • L(h,k)-labeling and minimum span
    • The special case h=k in relation to the suqre 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 lambbda
    • Exemple: a graph requiring lambda=Delta squared - Delta

Friday October 28, 2016 (lessons 19-20): A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

  • L(h,k)-labeling and minimum span (cntd)
    • 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
    • Approximate results: outerplanar graphs (part)

Monday October 31, 2016 (lessons 21-22): No lessons, due to security check after the earthquacke of October 30.

Friday November 4, 2016 (lessons 23-24): A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)

  • L(h,k)-labeling and minimum span (cntd) * Approximate results: outerplanar graphs (part)
  • variations of the problem:
    • oriented L(2,1)-labeling
    • L(h1, ..., hk)-labeling
    • backbone coloring
    • multiple L(h,k)-labeling
    • frequency assignment in GSM networks
  • a parenthesis on the 4 color theorem

Monday November 7, 2016 (lessons 25-26): Mid term evaluation (part 1).

Friday November 11, 2016 (lessons 27-28): Mid term evaluation (part 2).

Monday November 14, 2016 (lessons 29-30): 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)

Friday November 18, 2016 (lessons 31-32): The minimum energy broadcast i.e. the minimum spanning tree (2)

  • The MST problem
    • Kruskal algorithm
    • Prim algorithm
    • Boruvka algorithm
  • the Min Broadcast broblem
    • MST euristic
    • SPT euristic
    • BAIP euristic
    • approximation ratio for SPT

Monday November 21, 2016 (lessons 33-34): 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

Friday November 25, 2016 (lessons 35-36):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

  • (mobile) sensor networks
  • the problem of centralized deployment
  • the problem on graphs: min weight matching in a bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem
    • searching an augmenting path
    • Berge theorem on the augmenting paths

Monday November 28, 2016 (lessons 37-38):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm
  • Minimum weight perfect matching in bipartite graphs
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation
  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm (idea)

Friday December 2, 2016 (lessons 39-40):

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
    • hypthesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
  • Algorithms to compute the Voronoi diagram
    • half-plane intersection (divide et impera)

Monday December 5, 2016 (lessons 41-42):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

  • Algorithms to compute the Voronoi diagram (cntd)
    • Fortune's algorithm
  • Heterogeneous sensors
  • A new notion of distance: Laguerre distance
  • Voronoi-Laguerre diagrams
  • A protocol based on Voronoi-Laguerre distance

Friday December 9, 2016 (lessons 43-44): No lesson: the building is closed

Monday December 12, 2016 (lessons 45-46): Student lessons

Friday December 16, 2016 (lessons 47-48): IT meeting

Monday December 19, 2016 (lessons 49-50): Student lessons

Tuesday December 20, 2016 (lessons 51-52): Student lessons

Lesson Diary A.y. 2015-2016

Tuesday September 22, 2015 (Lessons 1-2):

Introduction

The Routing Problem i.e. the Shortest Path Problem (1)

  • The routing Problem
  • The shortest path Problem (1)
    • shortest paths: BFS
    • the negative cycle issue
    • least cost paths: introduction

Friday September 25, 2015 (Lessons 3-4):

The Routing Problem i.e. the Shortest Path Problem (2)

  • The shortest path Problem (2)
    • least cost paths (cnt.d):
      • Bellman-Ford algorithm
      • Dijkstra algorithm
      • Floyd-Warshall algorithm
  • The Routing Problem on Interconnection Topologies (1)
    • the packet switching model
    • the Butterfly network
    • routing on the Butterfly network: the greedy algorithm

Tuesday September 29, 2015 (Lessons 5-6):

The Routing Problem i.e. the Shortest Path Problem (3)

  • The Routing Problem on Interconnection Topologies (2)
    • the concept of blocking network, non-blocking network and rearrangeable network
    • 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
  • Collinear Layout of the Complete network

Friday October 2, 2015 (lessons 7-8):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

  • Layout of the Complete network
  • Layout of the Butterfly network
    • the Wise layout

Friday October 2, 2015 (lessons 9-10):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)

  • Layout of the Butterfly network (3)
    • the Even & Even layout
    • comparison between the two methods

Tuesday October 6, 2015 (lessons 11-12):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (4)

  • Layout of the Butterfly network (4)
    • Optimal area Layout of the Butterfly
  • Layout of the Hypercube network
  • The 3D layout problem

Tuesday October 9, 2015 (lessons 13-14):

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 with vertex cover

Tuesday October 13, 2015 (lessons 15-16):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

  • minimum vertex cover (cntd)
    • another approximation algorithm
    • Konig-Egevary theorem
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 Covering 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

Tuesday October 20, 2015 (lessons 17-18):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph
  • L(h,k)-labeling and minimum span
    • The special case h=k in relation to the suqre of a graph
    • Properties of the L(h,k)-labeling and their proofs
    • Proof of NP-completeness for diameter 2 graphs

Friday October 23, 2015 (lessons 19-20):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

  • L(h,k)-labeling and minimum span (cntd.)
    • Lower bound of Delta+1 on lambbda
    • Exemple: 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

Tuesday October 27, 2015 (lessons 21-22):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

  • L(h,k)-labeling and minimum span (cntd.)
    • Approximate results: outerplanar graphs
  • variations of the problem:
    • oriented L(2,1)-labeling
    • L(h1, ..., hk)-labeling
    • backbone coloring
    • multiple L(h,k)-labeling
    • frequency assignment in GSM networks
  • a parenthesis on the 4 color theorem

Friday October 30, 2015 (lessons 23-24):

The minimum energy broadcast i.e. the minimum spanning tree (1)

Friday November 6, 2015:

Mid term exam

Tuesday November 10, 2015 (lessons 25-26):

The minimum energy broadcast i.e. the minimum spanning tree (2)

  • the Min Broadcast broblem
    • MST euristic
    • SPT euristic
    • BAIP euristic
    • approximation ratio for SPT

Friday November 13, 2015 (lessons 27-28):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

  • the problem of centralized deployment
  • the problem on graphs: min weight matching in a bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem
    • searching an augmenting path
    • Berge theorem on the augmenting paths

Tuesday November 17, 2015 (lessons 29-30):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm
  • Minimum weight perfect matching in bipartite graphs
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation
  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm (idea)

Friday November 20, 2015 (lessons 31-32):

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
    • hypthesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
  • Algorithms to compute the Voronoi diagram
    • half-plane intersection (divide et impera)

Tuesday November 24, 2015 (lessons 33-34):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

  • Algorithms to compute the Voronoi diagram (cntd)
    • Fortune's algorithm
  • Heterogeneous sensors
  • A new notion of distance: Laguerre distance
  • Voronoi-Laguerre diagrams
  • A protocol based on Voronoi-Laguerre distance

Lesson Diary A.y. 2014-2015

Tuesday September 29, 2014 (Lessons 1-2):

Introduction

The Routing Problem i.e. the Shortest Path Problem (1)

  • The routing Problem
  • The shortest path Problem (1)
    • shortest paths: BFS
    • least cost paths: introduction

Friday October 3, 2014 (Lessons 3-4):

The Routing Problem i.e. the Shortest Path Problem (2)

  • The shortest path Problem (2)
    • least cost paths (cnt.d):
      • Bellman-Ford algorithm
      • Dijkstra algorithm
      • Floyd-Warshall algorithm
  • The Routing Problem on Interconnection Topologies (1)
    • the packet switching model
    • the Butterfly network
    • routing on the Butterfly network: the greedy algorithm

Tuesday October 7, 2014 (Lessons 5-6):

The Routing Problem i.e. the Shortest Path Problem (3)

  • The Routing Problem on Interconnection Topologies (2)
    • the concept of blocking network, non-blocking network and rearrangeable network
    • 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 Butterfly network (1)

Friday October 10, 2014 (lessons 7-8):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

  • Layout of the Butterfly network (2)
    • the Wise layout
    • the Even & Even layout
    • comparison between the two methods

Tuesday October 14, 2014 (lessons 9-10):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)

  • Layout of the Butterfly network (3)
    • Optimal area Layout of the Butterfly
  • Layout of the Hypercube network
  • The 3D layout problem

Tuesday October 17, 2014 (lessons 11-12):

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 in relation with vertex cover

Tuesday October 21, 2014 (lessons 13-14):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

  • minimum vertex cover (cnt.d)
    • matching in relation with vertex cover
    • another approximation algorithm
    • Konig-Egevary theorem
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 Covering 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

Friday October 24, 2014:

No lesson because of bus and train strike

Tuesday October 28, 2014 (lessons 15-16):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph
  • L(h,k)-labeling and minimum bandwidth
    • The special case h=k in relation to the suqre of a graph
    • Properties of the L(h,k)-labeling and their proofs

Friday October 31, 2014 (lessons 17-18):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

  • L(h,k)-labeling and minimum bandwidth (cntd.)
    • Proof of NP-completeness for diameter 2 graphs
    • Lower bound of Delta+1 on lambbda
    • Exemple: 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

Tuesday November 4, 2014 (lessons 19-20):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

  • L(h,k)-labeling and minimum bandwidth (cntd.)
    • Exact results: paths
    • Exact results: cycles
    • Approximate results: outerplanar graphs
  • variations of the problem:
    • oriented L(2,1)-labeling
    • L(h1, ..., hk)-labeling
    • backbone coloring
    • multiple L(h,k)-labeling

Friday November 7, 2014 (lessons 21-22):

Mid term exam

Tuesday November 11, 2014 (lessons 23-24):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4) * variations of the problem (cnt.d):

    • frequency assignment in GSM networks
  • a parenthesis on the 4 color theorem
The minimum energy broadcast i.e. the minimum spanning tree (1)

Friday November 14, 2014 (lessons 25-26):

The minimum energy broadcast i.e. the minimum spanning tree (2)

  • the Min Broadcast broblem
    • MST euristic
    • SPT euristic
    • BAIP euristic

Tuesday November 18, 2014 (lessons 27-28):

The minimum energy broadcast i.e. the minimum spanning tree (3)

  • the Min Broadcast broblem (cnt.d)
    • approximation ratio for SPT

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

  • the problem of centralized deployment
  • Ithe problem on graphs: min weight matching in a bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem

Friday November 21, 2014 (lessons 29-30):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

  • Maximum matching in bipartite graphs
    • searching an augmenting path
    • Berge theorem on the augmenting paths
    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm
  • Minimum weight perfect matching in bipartite graphs
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation
  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm (idea)

Tuesday November 25, 2014 (lessons 31-32):

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
    • hypthesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
  • Algorithms to compute the Voronoi diagram
    • half-plane intersection (divide et impera)

Friday November 28, 2014 (lessons 33-34): The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

  • Algorithms to compute the Voronoi diagram (cnt.d)
    • Fortune's algorithm
  • Heterogeneous sensors
  • A new notion of distance: Laguerre distance

Tuesday December 2, 2014 (lessons 35-36):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)

  • Voronoi-Laguerre diagrams
  • A protocol based on Voronoi-Laguerre distance

Friday December 5, 2014 (lessons 37-38):

Student lessons (1)

Tuesday December 9, 2014 (lessons 39-40):

Student lessons (2)

Tuesday December 16, 2014 (lessons 41-42):

Student lessons (3)

Lesson Diary A.y. 2013-2014

Monday September 30, 2013 (Lessons 1-2):

Introduction

The Routing Problem i.e. the Shortest Path Problem (1)

  • The routing Problem
  • The shortest path Problem (1)
    • shortest paths: BFS
    • least cost paths:
      • Bellman-Ford algorithm
      • Dijkstra algorithm

Friday October 4, 2013 (lessons 3-4):

The Routing Problem i.e. the Shortest Path Problem (2)

  • The shortest path Problem (2)
    • least cost paths (cntd.):
      • 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
    • the Benes network
    • routing om the Benes network: the looping algorithm

Monday October 7, 2013 (lessons 5-6):

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 Butterfly network (1)
    • the Wise layout
    • the Even & Even layout

Friday October 11, 2013 (lessons 7-8):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

  • Layout of the Butterfly network (2)
    • Overview of other results
    • Optimal area Layout of the Butterfly
  • Layout of the Hypercube network
  • The 3D layut problem

Monday October 14, 2013 (lessons 9-10):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)

  • The problem
    • worms
    • damages caused by worms
    • worm expansion
  • Model of the problem on graphs
  • minimum vertex cover
    • definition
    • ILP model
    • a 2-approximation algorithm
    • independent set in relation with vertex cover
    • matching in relation with vertex cover
    • another approximation algorithm

Friday October 18, 2013 (lessons 11-12):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

  • minimum vertex cover (cntd.)
    • Konig-Egevary theorem
The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem
  • The problem of minimizing boolean functions
  • Its equivalence with the Minimum Set Covering Problem
  • the Minimum Set Covering 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

Monday October 21, 2013 (lessons 13-14):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph
  • L(h,k)-labeling and minimum bandwidth
    • The special case h=k in relation to the suqre of a graph
    • Properties of the L(h,k)-labeling and their proofs
    • Proof of NP-completeness for diameter 2 graphs

Friday October 25, 2013 (lessons 15-16):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

  • L(h,k)-labeling and minimum bandwidth (cntd.)
    • Lower bound of Delta+1 on lambbda
    • Exemple: 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

Monday October 28, 2013 (lessons 17-18):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

  • L(h,k)-labeling and minimum bandwidth (cntd.)
    • Approximate results: outerplanar graphs
  • variations of the problem:
    • oriented L(2,1)-labeling
    • L(h1, ..., hk)-labeling
    • backbone coloring
    • multiple L(h,k)-labeling
    • frequency assignment in GSM networks
  • a parenthesis on the 4 color theorem

Monday November 4, 2013 (lessons 19-20):

The minimum energy broadcast i.e. the minimum spanning tree (1)

Friday November 8, 2013 (lessons 21-22):

The minimum energy broadcast i.e. the minimum spanning tree (2)

  • the Min Broadcast broblem
    • MST euristic
    • SPT euristic
    • BAIP euristic
    • approximation ratio for SPT

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

  • the problem of centralized deployment
  • Ithe problem on graphs: min weight matching in a bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem

week November 11-15: No classes - midterm exams

Monday November 18, 2013 (lessons 23-24):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

  • Maximum matching in bipartite graphs
    • searching an augmenting path
    • Berge theorem on the augmenting paths
    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm
  • Minimum weight perfect matching in bipartite graphs
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation
  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm

Friday November 22, 2013 (lessons 25-26): 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
    • hypthesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
  • Algorithms to compute the Voronoi diagram
    • half-plane intersection (divide et impera)

Monday December 2, 2013 (lessons 27-28): The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

  • Algorithms to compute the Voronoi diagram (cnt.d)
    • Fortune's algorithm

Friday December 6, 2013 (lessons 29-30): 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 Voroi-Laguerre distance

Monday December 9, 2013 (lessons 31-32):

Student Lessons

Friday December 13, 2013 (lessons 33-34):

Student Lessons

Monday December 16, 2013 (lessons 35-36):

Student Lessons

Diario delle Lezioni A.A. 2012-2013

Mercoledi' 3 Ottobre 2011 (Ore 1-2):

Introduzione al Corso

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (1)

  • Il problema dell'instradamento
  • Il problema del cammino di costo minimo
    • cammini piu' corti: visita in ampiezza
    • cammini minimi:
      • algoritmo di Bellman-Ford

Lunedi' 8 Ottobre 2012 (Ore 3-4):

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (2)

    • cammini minimi (segue):
      • algoritmo di Dijkstra
      • algoritmo di Floyd-Warshall

  • Instradamento sulle Topologie di Interconnessione
    • il modello di packet switching
    • la Butterfly
    • instradamento sulla Butterfly

Mercoledi' 10 Ottobre 2012 (Ore 5-6):

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (3)

    • concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
    • la Benes
    • looping algorithm e instradamento sulla Benes

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)

  • Il modello di Thompson
  • Il disegno ortogonale di grafi su griglia
  • Il layout della Butterfly
    • il layout di Wise

Lunedi' 15 Ottobre 2012 (Ore 7-8):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)

  • Il layout della Butterfly (segue)
    • il layout di Even ed Even
    • panoramica di altri risultati
    • Layout della butterfly di area ottima

Mercoledi' 17 Ottobre 2012 (Ore 9-10):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)

  • Il layout dell'ipercubo
  • il problema del layut 3D

Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (1)

  • Il problema
    • i worm
    • danni causati dai worm
    • diffusione dei worm

Lunedi' 22 Ottobre 2012 (Ore 11-12):

Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)

  • Modello del problema su grafi
  • la minima copertura di nodi
    • definizione
    • un algoritmo 2-approssimante
    • insieme indipendente e sua relazione con la copertura di nodi
    • accoppiamento e sua relazione con la copertura di nodi
    • un ulteriore algoritmo approssimante
    • teorema di Konig-Egevary

Mercoledi' 24 Ottobre 2012 (Ore 13-14):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)

  • Introduzione ai problemi di assegnazione di frequenze
  • Collisioni dirette, collisioni nascoste e grafo delle interferenze
  • L(h,k)-etichettatura e minima banda
    • Il caso speciale h=k in relazione al quadrato di un grafo

Lunedi' 29 Ottobre 2012 (Ore 15-16):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)

  • L(h,k)-etichettatura (segue)
    • Dimostrazione delle proprietÓ della L(h,k)-etichettatura (h e k primi tra loro ed interi)
    • Dimostrazione della NP-completezza per grafi di diametro 2
    • Limitazione inferiore di Delta+1 su lambbda
    • Esempio di grafo che richiede lambda=Delta quadro - Delta
    • Limitazione superiore di Delta quadro + 2 Delta
    • Congettura di Griggs e Yeh
    • Risultati esatti: clicche

Lunedi' 5 Novembre 2012 (Ore 17-18):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)

  • L(h,k)-etichettatura (segue)
    • Risultati esatti: clicche
    • Risultati esatti: stelle
    • Risultati esatti: alberi
    • Risultati esatti: cammini
    • Risultati esatti: cicli

Mercoledi' 7 Novembre 2012 (Ore 19-20): Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)

  • L(h,k)-etichettatura (segue)

    • Risultati approssimati: grafi outerplanar
  • varianti del problema:
    • L(2,1)-etichettatura orientata
    • L(h1, ..., hk)-etichettatura
    • backbone coloring
    • L(h,k)-etichettatura multipla
    • assegnazione di frequenze in reti GSM
  • una divagazione sul teorema dei 4 colori

Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)

12-15 Novembre 2012: settimana di interruzione della didattica

Lunedi' 19 Novembre 2012 (Ore 21-22): Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)

  • Relazione tra MinBroadcast e MinSpanningTree
  • Il problema del Minimo Albero Ricoprente
    • Algoritmo di Kruskal
    • Algoritmo di Prim
    • Algoritmo di Boruvka
  • Il problema del Min Broadcast
    • Euristica MST
    • Euristica SPT
    • Euristica BAIP
    • fattore di approssimazione per SPT

Mercoledi' 21 Novembre 2012 (Ore 23-24):

Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)

  • Il problema del Dispiegamento centralizzato
  • Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
  • Accoppiamento massimo in grafi bipartiti
    • teorema di P. Hall (dimostrazione)
    • corollario del th. di P. Hall (dim.)
    • equivalenza con il problema del minimo flusso
    • cammini aumentanti

Lunedi' 26 Novembre 2012 (Ore 25-26):

Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)

  • Accoppiamento massimo in grafi bipartiti
    • teorema del cammino aumentante di Berge (dim.)
    • il problema della ricerca di un camino aumentante
    • algoritmo basato sul th. di Berge
    • l'algoritmo di Hopcroft e Karp
  • Accoppiamento perfetto di peso minimo in grafi bipartiti
    • cammini aumentanti
    • un algoritmo basato sui cammini aumentanti
    • formulazione del problema come programmazione lineare
  • Accoppiamento massimo in grafi qualunque
    • boccioli (blossoms)
    • lemma della contrazione dei cicli

Mercoledi' 28 Novembre 2012 (Ore 27-28):

Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (3)

    • algoritmo di Edmonds

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)

  • Il problema
  • L'approccio basato sulle forze virtuali

Lunedi' 3 Dicembre 2012 (Ore 29-30):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)

  • L'approccio basato sui diagrammi di Voronoi
  • Diagramma di Voronoi
    • posizione generale
    • proprieta'

  • Diagramma di Voronoi
    • complessita'
    • Il problema duale: la triangolazione di Delaunay
    • algoritmi per calcolare il diagramma di Voronoi: divide et impera
    • algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - prima parte

Mercoledi' 5 Dicembre 2012 (Ore 31-32):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)

  • Diagramma di Voronoi
    • algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - seconda parte

  • Dispiegamento con sensori eterogenei
  • Distanza di Laguerre
  • Diagramma di Voronoi-Laguerre
  • L'approccio basato sui diagrammi di Voronoi-Laguerre
    • proprieta' dell'algoritmo

Diario delle Lezioni A.A. 2011-2012

Lunedi' 3 Ottobre 2011 (Ore 1-2):

Introduzione al Corso

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (1)

  • Il problema dell'instradamento
  • Il problema del cammino di costo minimo
    • cammini piu' corti: visita in ampiezza

Giovedi' 6 Ottobre 2011 (Ore 3-4):

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (2)

    • cammini minimi:
      • algoritmo di Bellman-Ford
      • algoritmo di Dijkstra
      • algoritmo di Floyd-Warshall

  • Instradamento sulle Topologie di Interconnessione
    • il modello di packet switching
    • la Butterfly
    • instradamento sulla Butterfly

Lunedi' 10 Ottobre 2011 (Ore 5-6):

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (3)

    • concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
    • la Benes
    • looping algorithm e instradamento sulla Benes

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)

  • Il modello di Thompson
  • Il disegno ortogonale di grafi su griglia

Mercoledi' 12 Ottobre 2011 (Ore 7-8):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)

  • Il layout della Butterfly
    • il layout di Wise
    • il layout di Even ed Even
    • panoramica di altri risultati

Lunedi' 17 Ottobre 2011 (Ore 9-10):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)

  • Layout della butterfly di area ottima
  • Layout tridimensionale dell'ipercubo
    • il problema del layut 3D
    • l'ipercubo
    • cenni sul layout dell'ipercubo e sulla limitazione inferiore

Mercoledi' 19 Ottobre 2011 (Ore 11-12):

Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi

  • Il problema
    • i worm
    • danni causati dai worm
    • diffusione dei worm
  • Modello del problema su grafi
  • la minima copertura di nodi
    • definizione
    • un algoritmo 2-approssimante
    • insieme indipendente e sua relazione con la copertura di nodi
    • accoppiamento e sua relazione con la copertura di nodi
    • un ulteriore algoritmo approssimante
    • teorema di Konig-Egevary

Lunedi' 24 Ottobre 2011 (Ore 13-14):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)

  • Introduzione ai problemi di assegnazione di frequenze
  • Collisioni dirette, collisioni nascoste e grafo delle interferenze
  • L(h,k)-etichettatura e minima banda
    • Il caso speciale h=k in relazione al quadrato di un grafo
    • Dimostrazione delle proprietÓ della L(h,k)-etichettatura (h e k primi tra loro ed interi)

Mercoledi' 26 Ottobre 2011 (Ore 15-16):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)

  • L(h,k)-etichettatura (segue)
    • Dimostrazione della NP-completezza per grafi di diametro 2
    • Limitazione inferiore di Delta+1 su lambbda
    • Esempio di grafo che richiede lambda=Delta quadro - Delta
    • Limitazione superiore di Delta quadro + 2 Delta
    • Congettura di Griggs e Yeh
    • Risultati esatti: clicche
    • Risultati esatti: stelle
    • Risultati esatti: alberi

Mercoledi' 9 Novembre 2011 (Ore 17-18):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)

  • L(h,k)-etichettatura (segue)
    • Risultati esatti: cammini
    • Risultati esatti: cicli
    • Risultati approssimati: grafi outerplanar

Lunedi' 21 Novembre 2011 (Ore 19-20):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4) * varianti del problema:

    • L(2,1)-etichettatura orientata
    • L(h1, ..., hk)-etichettatura
    • backbone coloring
    • L(h,k)-etichettatura multipla
    • assegnazione di frequenze in reti GSM
  • una divagazione sul teorema dei 4 colori

Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)

Mercoledi' 23 Novembre 2011 (Ore 21-22): Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)

  • Il problema del Minimo Albero Ricoprente
    • Algoritmo di Kruskal
    • Algoritmo di Prim
    • Algoritmo di Boruvka
  • Il problema del Min Broadcast
    • Euristica MST
    • Euristica SPT
    • Euristica BAIP
    • fattore di approssimazione per SPT

Lunedi' 28 Novembre 2010 (Ore 23-24):

Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)

  • Il problema del Dispiegamento centralizzato
  • Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
  • Accoppiamento massimo in grafi bipartiti
    • teorema di P. Hall (dimostrazione)
    • corollario del th. di P. Hall (dim.)
    • equivalenza con il problema del minimo flusso
    • cammini aumentanti
    • teorema del cammino aumentante di Berge (dim.)

Mercoledi' 30 Novembre 2010 (Ore 25-26):

Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)

  • Accoppiamento massimo in grafi bipartiti
    • il problema della ricerca di un camino aumentante
    • algoritmo basato sul th. di Berge
    • l'algoritmo di Hopcroft e Karp
  • Accoppiamento perfetto di peso minimo in grafi bipartiti
    • cammini aumentanti
    • un algoritmo basato sui cammini aumentanti
    • formulazione del problema come programmazione Lineare
  • Accoppiamento massimo in grafi qualunque
    • boccioli (blossoms)
    • lemma della contrazione dei cicli
    • algoritmo di Edmonds

Lunedi' 5 Dicembre 2011 (Ore 27-28):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)

  • Il problema
  • L'approccio basato sulle forze virtuali
  • L'approccio basato sui diagrammi di Voronoi
  • Diagramma di Voronoi
    • posizione generale
    • proprieta'

Mercoledi' 7 Dicembre 2011 (Ore 29-30):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)

  • Diagramma di Voronoi
    • complessita'
    • Il problema duale: la triangolazione di Delaunay
    • algoritmi per calcolare il diagramma di Voronoi: divide et impera
    • algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)

  • Dispiegamento con sensori eterogenei
  • Distanza di Laguerre
  • Diagramma di Voronoi-Laguerre

Lunedi' 12 Dicembre 2011 (Ore 31-32):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)

  • L'approccio basato sui diagrammi di Voronoi-Laguerre
    • proprieta' dell'algoritmo

Mercoledi' 14 Dicembre 2011 (Lauree)

Vacanze natalizie

Mercoledi' 11 Gennaio 2012 (Ore 33-34):

Tesine

Lunedi' 16 Gennaio 2012 (Ore 35-36):

Tesine

Mercoledi' 18 Gennaio 2012 (Ore 37-38):

Tesine


Diario delle Lezioni A.A. 2010-2011

Lunedi' 18 Ottobre 2010 (Ore 1-2):

Lectio Magistralis: Dott. Prabhakar Raghavan

Giovedi' 21 Ottobre 2010 (Ore 3-4):

Introduzione al Corso

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (1)

  • Il problema dell'instradamento
  • Il problema del cammino di costo minimo
    • cammini piu' corti: visita in ampiezza
    • cammini minimi:
      • algoritmo di Bellman-Ford
      • algoritmo di Dijkstra
      • algoritmo di Floyd-Warshall

Lunedi' 25 Ottobre 2010 (Ore 5-6):

Il Problema dell'Instradamento ovvero il Cammino pi¨ Corto o di Costo minimo (2)

  • Instradamento sulle Topologie di Interconnessione
    • il modello di packet switching
    • la Butterfly
    • instradamento sulla Butterfly
    • concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
    • la Benes
    • looping algorithm e instradamento sulla Benes

Giovedi' 28 Ottobre 2010 (Ore 7-8):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)

  • Il modello di Thompson
  • Il disegno ortogonale di grafi su griglia
  • Il layout della Butterfly
    • il layout di Wise
    • il layout di Even ed Even
    • panoramica di altri risultati

Lunedi' 1 Novembre 2010: festa

Giovedi' 4 Novembre 2010 (Ore 9-10):

Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)

  • Layout della butterfly di area ottima
  • Layout tridimensionale dell'ipercubo
    • il problema del layut 3D
    • l'ipercubo
    • cenni sul layout e sulla limitazione inferiore

Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Vertici (1)

  • Il problema
    • i worm
    • danni causati dai worm
    • diffusione dei worm

Lunedi' 8 Novembre 2010 (Ore 11-12):

Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)

  • Modello del problema su grafi
  • la minima copertura di nodi
    • definizione
    • un algoritmo 2-approssimante
    • insieme indipendente e sua relazione con la copertura di nodi
    • accoppiamento e sua relazione con la copertura di nodi
    • un ulteriore algoritmo approssimante
    • teorema di Konig-Egevary

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)

  • Introduzione ai problemi di assegnazione di frequenze

Giovedi' 11 Novembre 2010 (Ore 13-14):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)

  • Collisioni dirette, colisioni nascoste e grafo delle interferenze
  • L(h,k)-etichettatura e minima banda
    • Dimostrazione delle proprietÓ della L(h,k)-etichettatura (h e k primi tra loro ed interi)
    • Il caso speciale h=k
    • Dimostrazione della NP-completezza per grafi di diametro 2
    • Limitazione inferiore di Delta+1 su lambbda
    • Esempio di grafo che richiede lambda=Delta quadro - Delta
    • Limitazione superiore di Delta quadro + 2 Delta

Lunedi' 15 Novembre 2010 (Ore 15-16):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)

  • L(h,k)-etichettatura (segue)
    • Congettura di Griggs e Yeh
    • Risultati esatti: clicche
    • Risultati esatti: stelle
    • Risultati esatti: alberi
    • Risultati esatti: cammini
    • Risultati esatti: cicli
    • Risultati approssimati: grafi outerplanar

Giovedi' 18 Novembre 2010 (Ore 17-18):

Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4) * L(h,k)-etichettatura (segue)

    • Risultati approssimati: grafi outerplanar
  • varianti del problema:
    • L(2,1)-etichettatura orientata
    • L(h1, ..., hk)-etichettatura
    • backbone coloring
    • assegnazione di frequenze in reti GSM
    • una divagazione sul teorema dei 4 colori

Lunedi' 22 Novembre 2010 (Ore 19-20):

Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)

  • Il problema del MinBroadcast
  • NP-completezza e risultati di non approssimabilita' di MinBroadcast (riduzione da MinSetCover)
  • Relazione tra MinBroadcast e MinSpanningTree
  • Il problema del Minimo Albero Ricoprente
    • Algoritmo di Kruskal
    • Algoritmo di Prim
    • Algoritmo di Boruvka
  • Il problema del Min Broadcast
    • Euristica MST
    • Euristica SPT
    • Euristica BAIP
    • fattore di approssimazione per SPT

Giovedi' 25 Novembre 2010 (Ore 21-22):

Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)

  • Il problema del Min Broadcast
    • fattore di approssimazione per BAIP
    • fattore di approssimazione per MST
    • idea della dimostrazione della lim. sup. di 6 per MST

Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)

  • Il problema del Dispiegamento centralizzato
  • Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
  • Accoppiamento massimo in grafi bipartiti
    • teorema di P. Hall (dimostrazione)
    • corollario del th. di P. Hall (dim.)
    • equivalenza con il problema del minimo flusso
    • cammini aumentanti
    • teorema del cammino aumentante di Berge (dim.)
    • il problema della ricerca di un camino aumentante
    • algoritmo basato sul th. di Berge
    • l'algoritmo di Hopcroft e Karp

Settimana di interruzione della didattica

Lunedi' 6 Dicembre 2010 (Ore 23-24):

Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)

  • Accoppiamento perfetto di peso minimo in grafi bipartiti
    • cammini aumentanti
    • un algoritmo basato sui cammini aumentanti
    • formulazione del problema come programmazione Lineare
  • Accoppiamento massimo in grafi qualunque
    • boccioli (blossoms)
    • lemma della contrazione dei cicli
    • algoritmo di Edmonds

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)

  • Il problema
  • L'approccio basato sulle forze virtuali
  • L'approccio basato sui diagrammi di Voronoi
  • Diagramma di Voronoi
    • posizione generale
    • proprieta'

Giovedi' 9 Dicembre 2010 (Ore 25-26):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)

  • Diagramma di Voronoi
    • complessita'
    • Il problema duale: la triangolazione di Delaunay
    • algoritmi per calcolare il diagramma di Voronoi: divide et impera
    • algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)

Lunedi' 13 Dicembre 2010 (Ore 27-28):

Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)

  • Dispiegamento con sensori eterogenei
  • Distanza di Laguerre
  • Diagramma di Voronoi-Laguerre
  • L'approccio basato sui diagrammi di Voronoi-Laguerre
    • proprieta' dell'algoritmo

Giovedi' 16 Dicembre 2010 (Lauree)

Lunedi' 20 Dicembre 2010 (Incontro con le aziende)

Vacanze natalizie

Lunedi' 10 Gennaio 2011 (Ore 29-30):

Tesine

Giovedi' 13 Gennaio 2011 (Ore 31-32):

Tesine

Venerdi' 14 Gennaio 2011 (Ore 33-34):

Tesine

Lunedi' 17 Gennaio 2011 (Ore 35-36):

Tesine

Giovedi' 20 Gennaio 2011 (Ore 37-38):

Tesine

Edit | Attach | Watch | Print version | History: r92 < r91 < r90 < r89 < r88 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r92 - 2017-12-04 - TizianaCalamoneri






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback