Variants of Longest Common Subsequence and Related Problems

master
dc.abstract.enLongest Common Subsequence (abbreviated LCS) is one of the most well-known algorithmic problems, and its solution (for the case of two input sequences) is usually among the first examples of dynamic programming approaches shown in most introductory algorithmic courses. In this thesis, we aim to present recent results regarding various variants of the problem such as Repetition-Free Longest Common Subsequence, as well as some related problems, including Edit Distance or Dynamic Time Warping Distance. We will also pay extra attention to a multivariate approach to the problem – in particular we will state some conditional lower bounds on time complexity in terms of additional properties of the input strings.pl
dc.abstract.plProblem znajdowania najdłuższego wspólnego podciągu jest niewątpliwie bardzo dobrze znanym zagadnieniem algorytmicznym, a jego rozwiązanie dla przypadku dwóch słów wejściowych przedstawia się zazwyczaj jako jeden ze sztandarowych przykładów zastosowania techniki programowania dynamicznego. W tej pracy przedstawimy wybrane rezultaty z ostatnich lat dotyczące różnych wariantów problemu (takich jak najdłuższy wspólny podciąg niezawierający powtórzeń), a także niektórych problemów pokrewnych, na przykład odległości edycyjnej lub Dynamic Time Warping Distance. Poświęcimy część uwagi wieloparametrycznemu podejściu do analizy złożoności – w szczególności przedstawimy kilka ograniczeń dolnych na złożoność czasową problemu (warunkowanych hipotezą SETH) zależnych od dodatkowych parametrów napisów wejściowych.pl
dc.affiliationWydział Matematyki i Informatykipl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorDuraj, Lechpl
dc.contributor.authorBurczyński, Rafałpl
dc.contributor.departmentbycodeUJK/WMI2pl
dc.contributor.reviewerIdziak, Paweł - 128365 pl
dc.contributor.reviewerDuraj, Lechpl
dc.date.accessioned2023-10-09T21:33:04Z
dc.date.available2023-10-09T21:33:04Z
dc.date.submitted2021-09-23pl
dc.fieldofstudyinformatyka analitycznapl
dc.identifier.apddiploma-154753-214201pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/320731
dc.languageengpl
dc.subject.encomputer science, algorithms, computational complexity, string similarity, longest common subsequence, edit distance, dynamic time warping distancepl
dc.subject.plinformatyka, algorytmika, złożoność obliczeniowa, podobieństwo słów, najdłuższy wspólny podciąg, odległość edycyjnapl
dc.titleVariants of Longest Common Subsequence and Related Problemspl
dc.title.alternativeWarianty problemu znajdowania najdłuższego wspólnego podciągu oraz powiązane problemypl
dc.typemasterpl
dspace.entity.typePublication
dc.abstract.enpl
Longest Common Subsequence (abbreviated LCS) is one of the most well-known algorithmic problems, and its solution (for the case of two input sequences) is usually among the first examples of dynamic programming approaches shown in most introductory algorithmic courses. In this thesis, we aim to present recent results regarding various variants of the problem such as Repetition-Free Longest Common Subsequence, as well as some related problems, including Edit Distance or Dynamic Time Warping Distance. We will also pay extra attention to a multivariate approach to the problem – in particular we will state some conditional lower bounds on time complexity in terms of additional properties of the input strings.
dc.abstract.plpl
Problem znajdowania najdłuższego wspólnego podciągu jest niewątpliwie bardzo dobrze znanym zagadnieniem algorytmicznym, a jego rozwiązanie dla przypadku dwóch słów wejściowych przedstawia się zazwyczaj jako jeden ze sztandarowych przykładów zastosowania techniki programowania dynamicznego. W tej pracy przedstawimy wybrane rezultaty z ostatnich lat dotyczące różnych wariantów problemu (takich jak najdłuższy wspólny podciąg niezawierający powtórzeń), a także niektórych problemów pokrewnych, na przykład odległości edycyjnej lub Dynamic Time Warping Distance. Poświęcimy część uwagi wieloparametrycznemu podejściu do analizy złożoności – w szczególności przedstawimy kilka ograniczeń dolnych na złożoność czasową problemu (warunkowanych hipotezą SETH) zależnych od dodatkowych parametrów napisów wejściowych.
dc.affiliationpl
Wydział Matematyki i Informatyki
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Duraj, Lech
dc.contributor.authorpl
Burczyński, Rafał
dc.contributor.departmentbycodepl
UJK/WMI2
dc.contributor.reviewerpl
Idziak, Paweł - 128365
dc.contributor.reviewerpl
Duraj, Lech
dc.date.accessioned
2023-10-09T21:33:04Z
dc.date.available
2023-10-09T21:33:04Z
dc.date.submittedpl
2021-09-23
dc.fieldofstudypl
informatyka analityczna
dc.identifier.apdpl
diploma-154753-214201
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/320731
dc.languagepl
eng
dc.subject.enpl
computer science, algorithms, computational complexity, string similarity, longest common subsequence, edit distance, dynamic time warping distance
dc.subject.plpl
informatyka, algorytmika, złożoność obliczeniowa, podobieństwo słów, najdłuższy wspólny podciąg, odległość edycyjna
dc.titlepl
Variants of Longest Common Subsequence and Related Problems
dc.title.alternativepl
Warianty problemu znajdowania najdłuższego wspólnego podciągu oraz powiązane problemy
dc.typepl
master
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month

No access

No Thumbnail Available
Collections