Ημερομηνία : Παρασκευή, 09 Ιανουαρίου, 2026

Ώρα : 13.00

Τοποθεσία : Αίθουσα Σεμιναρίων του Τομέα Μαθηματικών ΣΕΜΦΕ, κτ. Ε΄, 2ος όροφος

Ομιλητής: κ. Παναγιώτης Χαραλαμπόπουλος (Assistant Professor at King’s College London) https://pcharalampo.github.io/index.html

Τίτλος Ομιλίας: Πρόσφατα Αποτελέσματα στην Προσεγγιστική Αντιστοίχιση Προτύπων

Περίληψη: Η αντιστοίχιση προτύπων είναι μια ενέργεια που οι περισσότεροι από εμάς εκτελούμε καθημερινά, αναζητώντας έναν όρο στο διαδίκτυο ή μια λέξη σε ένα έγγραφο. Στις περισσότερες πρακτικές εφαρμογές, ο εντοπισμός των ακριβών εμφανίσεων ενός προτύπου σε ένα κείμενο δεν επαρκεί, παραδείγματος χάριν λόγω θορυβωδών δεδομένων, ορθογραφικών λαθών ή σφαλμάτων στην αλληλούχιση DNA. Σε αυτή την ομιλία, θα παρουσιάσουμε πρόσφατα δομικά και αλγοριθμικά αποτελέσματα σχετικά με την προσεγγιστική αντιστοίχιση προτύπων (ΠΑΠ) υπό τις πιο θεμελιώδεις αποστάσεις συμβολοσειρών: την απόσταση Hamming και τη (σταθμισμένη) απόσταση επεξεργασίας (edit distance). Συγκεκριμένα, θα εξετάσουμε:

• τον δομικό χαρακτηρισμό «λίγες εμφανίσεις ή σχεδόν περιοδικότητα» και το πώς αυτός οδηγεί σε αποδοτικούς αλγορίθμους ΠΑΠ
• έναν εννοιολογικά απλό νέο αλγόριθμο για ΠΑΠ υπό σταθμισμένη απόσταση επεξεργασίας, ο οποίος –βασιζόμενος σε ριζικά διαφορετικές τεχνικές– έχει σχεδόν την ίδια πολυπλοκότητα με τον (κορυφαίο για ένα ευρύ εύρος παραμέτρων) αλγόριθμο των Landau και Vishkin [J. Algorithms’89] για τη μη σταθμισμένη εκδοχή του προβλήματος.

Η ομιλία θα βασιστεί (κυρίως) στις ακόλουθες κοινές εργασίες με τους Tomasz Kociumaka και Philip Wellnitz: Faster Approximate Pattern Matching: A Unified Approach [FOCS 2020] Pattern Matching under Weighted Edit Distance [FOCS 2025]