Szanowni Państwo,
w czwartek 20 listopada 2025 r. o godzinie 10:15 w sali 110 INF odbędzie się kolejne Seminarium Instytutu Informatyki.
Wykład pt. „Ulam’s metric in higher dimensions” wygłosi dr Sebastian Bala.
Metryka Ulama opisuje minimalną liczbę przestawień (operacji wycięcia i ponownego wstawienia elementów permutacji), które są potrzebne, aby przejść od jednej permutacji do drugiej. Wyznaczenie elementów, które należy „przenieść”, prowadzi do rozwiązania klasycznego problemu najdłuższej wspólnej podsekwencji (Longest Common Subsequence, LCS).
Badania zapoczątkowane pracami Ulama przyniosły szereg ważnych rezultatów w informatyce, matematyce, statystyce i fizyce.
W swoim wystąpieniu dr Sebastian Bala przedstawi uogólnienie oryginalnej definicji metryki Ulama na przypadek wielowymiarowy, motywowane praktycznymi zastosowaniami krotek permutacji w przemyśle. Omówione zostaną własności tak zdefiniowanej metryki, a także złożoność obliczeniowa i możliwości aproksymacji w analizie tego typu struktur.
Ulam’s metric defines the minimal number of moves (extraction followed by re-insertion of permutation elements) to go between a~given pair of permutations, and determination of moved elements resolves the Longest Common Subsequence problem. The extensive research that followed Ulam’s work provided many influential discoveries in computer science, mathematics, statistics and physics. In this paper, motivated by successful industrial applications of $k$-tuples of permutations, we extend Ulam’s original definition to provide a framework of multidimensional metric and study its complexity and approximability.
Na seminarium zapraszamy pracowników, doktorantów i studentów zainteresowanych zagadnieniami z pogranicza informatyki teoretycznej, kombinatoryki i zastosowań przemysłowych.