195.092 Algorithm Design in Different Models of Computation
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2017S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

to be informed

Inhalt der Lehrveranstaltung

We explore a two-dimensional  "world" which has one axis for algorithmic methods and a second axis for models of computation. This world is explored by considering canonic problems such as maximum matching, minimum vertex cover, maximal independent set, and packing and covering. The axis of algorithmic methods consists of greedy selection, augmenting paths, primal-dual, and multiplicative weights. The models of computation are: the standard sequential model, distributed algorithms (LOCAL and CONGEST models), sublinear algorithms, online algorithms, and online learning.
Each model of computation is characterized by a dierent constraint that limits the algorithm designer. For example: in online algorithms, irrevocable decisions must be made before the whole input is revealed; in sublinear algorithms, decisions must be made based on seeing only a small fraction of the input; in distributed algorithms, decisions must be made based only on local information.
Overcoming these challenges often requires one to resort to approximate solutions. For example, instead of computing a maximum matching, we are satis ed with a matching, the cardinality of which at least (1 - ¿) times the maximum cardinality matching. Randomization is often employed to cope with partial information.

Weitere Informationen

This is a visiting professor course of the Vienna PhD School of Informatics.

It will be held by Guy Even, Tel-Aviv University.

 

The course will be held as blocked course.


 


Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.13:00 - 16:0020.03.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Di.11:00 - 14:0021.03.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Mi.13:00 - 16:0022.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Do.11:00 - 14:0023.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Fr.13:00 - 16:0024.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Di.13:00 - 16:0002.05.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Mi.13:00 - 15:0003.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Do.13:00 - 16:0004.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Fr.13:00 - 16:0005.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
LVA wird geblockt abgehalten

LVA-Anmeldung

Von Bis Abmeldung bis
16.02.2017 00:00 20.03.2017 23:59

Anmeldemodalitäten:

Please register in TISS.

Curricula

StudienkennzahlSemesterAnm.Bed.Info
PhD Vienna PhD School of Informatics

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Weitere Informationen

  • Anwesenheitspflicht!

Sprache

Englisch