SoloDIAG

Generale => Eventi => Topic aperto da: lupin - Gio 25 Ottobre, 09:24:21 - 2018

Titolo: Seminario premio Turing Robert Endre Tarjan 26 ott 14:00 DIAG
Inserito da: lupin - Gio 25 Ottobre, 09:24:21 - 2018
Venerdì 26 ottobre dalle 14:00 alle 14:45 circa si terrà un seminario del premio Turing Robert Endre Tarjan, uno dei padri delle strutture dati moderne. Tarjan parlerà di un nuovo tipo di albero bilanciato, lo Zip Tree. Incontrare un premio Turing di questo spessore è un evento che non capita facilmente.

Il seminario si terrà in Aula Magna al DIAG ed è necessario registrarsi al link:
https://goo.gl/forms/vqwVcECsiO6pKmRz2

I posti sono limitati: il form si chiuderà a 100 registrati. Se pensate di venire, affrettatevi.

Vi accludo sotto tutti i dettagli.

------
Who: Robert Endre Tarjan, Princeton University and Intertrust Technologies

Bio: https://en.wikipedia.org/wiki/Robert_Tarjan

When: Friday, October 26th 2018, 2:00 PM

Where: Aula Magna, Department of Computer, Control, and Management Engineering,
Sapienza University of Rome, via Ariosto 25, 00185 Rome

Title: Zip Trees

Abstract:

We introduce the zip tree, a form of randomized binary search tree.
One can view a zip tree as a treap in which priority ties are allowed
and in which insertions and deletions are done by unmerging and
merging paths(unzipping and zipping) rather than by doing rotations.
Alternatively, one can view a zip tree as a binary-tree representation
of a skip list. Doing insertions and deletions by unzipping and zipping
instead of by doing rotations avoids some pointer changes and can
thereby improve efficiency. Representing a skip list as a binary tree
avoids the need for nodes of different sizes and can speed up searches
and updates. Zip trees are at least as simple as treaps and skip lists
but offer improved efficiency. Their simplicity makes them especially
amenable to concurrent operations.  This is joint work with Caleb
Levy and Stephen Timmel.

To reserve a seat, please register at:
https://goo.gl/forms/vqwVcECsiO6pKmRz2

Contact: Camil Demetrescu <demetres@diag.uniroma1.it>