Ponedeljkov seminar računalništva in informatike - Arhiv
| 2025 | 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
četrtek, 11. december 2025 Ivan DAMNJANOVIĆ: On the number of F-arithmetic expressions in n distinct variables
V ponedeljek, 15. decembra 2025, bo ob 16:00 uri izvedeno
predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE
Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.
ČAS/PROSTOR: 15. december 2025 ob 16.00 v FAMNIT-VP3.
------------------------------------------------
PREDAVATELJ: Ivan DAMNJANOVIĆ
------------------------------------------------
Ivan Damnjanović is pursuing a PhD degree in Mathematical Sciences at the Faculty of Mathematics, Natural Sciences and Information Technologies at the University of Primorska. He previously obtained a PhD degree in Electrical Engineering and Computing at the Faculty of Electronic Engineering at the University of Niš, where he currently works as a teaching assistant at the department of mathematics.
-----------------------------------------------------------------------------------------------------
NASLOV: On the number of F-arithmetic expressions in n distinct variables
-----------------------------------------------------------------------------------------------------
POVZETEK:
How many arithmetic expressions are there in n distinct variables? Here, we provide a Theta(n^2) algorithm for computing this number for arithmetic expressions over an arbitrary field F. We consider several cases of this problem with various restrictions on the allowed operations. An expression tree is an ordered rooted tree whose internal nodes represent operations to be performed, while its leaves correspond to formal variables from a set X. We view any arithmetic expression as an element of F(X) that is obtained by evaluating an expression tree.
Seminar bo potekal v angleškem jeziku v predavalnici FAMNIT-VP3 s pričetkom ob 16:00 uri.
Vabljeni!
ponedeljek, 8. december 2025 Gerth Stølting Brodal: External-Memory Priority Queues and Persistent Search Trees
V ponedeljek, 8. decembra 2025, bo ob 16:00 uri izvedeno
predavanje v okviru PONEDELJKOVEGA SEMINARJA RAČUNALNIŠTVA IN INFORMATIKE
Oddelkov za Informacijske znanosti in tehnologije UP FAMNIT in UP IAM.
ČAS/PROSTOR: 8. december 2025 ob 16.00 v FAMNIT-VP3.
------------------------------------------------------
PREDAVATELJ: Gerth STØLTING BRODAL
------------------------------------------------------
Gerth Stølting Brodal is a Professor at the Department of Computer Science, Aarhus University, Denmark. He received his PhD in computer science in 1997 from Aarhus University. His main research interests are the design and analysis of algorithms and data structures. He has done work on fundamental data structures, including dictionaries and priority queues, persistent data structures, computational geometry, graph algorithms, string algorithms, I/O-efficient and cache-oblivious algorithms and data structures, algorithm engineering, and computational biology.
-------------------------------------------------------------------------------------------------
NASLOV: External-Memory Priority Queues and Persistent Search Trees
-------------------------------------------------------------------------------------------------
POVZETEK:
We present recent results on priority queues and search trees in the external memory model by Aggarwal and Vitter [CACM 1988]. In this model we have an (infinite) external memory and a limited internal memory, where all computations need to be performed in internal memory. The IO cost of a computation is the number of block transfers of data between internal and external memory. In the first part of the talk we discuss the first external memory priority queue that achieves simultaniously optimal amortized internal computation cost and IO cost, where insertions are constant and deletions logarithmic. In the second part we discuss how to make a B-tree partially persistent, i.e., all previous versions of the tree are remembered, while simultaniously speeding up the amortized IO cost of insertions and deletions by a factor B^{1-ɛ̝}, for any constant ɛ̝ > 0.
The talk is based on joint work with Michael Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Casper Moldrup Rysgaard, Nodari Sitchinava, and Rolf Svenning presented at ESA 2025:
http://dx.doi.org/10.4230/LIPIcs.ESA.2025.5 and
http://dx.doi.org/10.4230/LIPIcs.ESA.2025.s
Seminar bo potekal v angleškem jeziku v predavalnici FAMNIT-VP3 s pričetkom ob 16:00 uri.
Vabljeni!
