Najdłuższy wspólny podciąg

Spis treści

Wymagania i kryteria oceniania

Należy zaimplementować algorytm szukający najdłuższego wspólnego podciągu dwóch ciągów, o złożoności co najwyżej rzędu iloczynu długości tych ciągów.

Maksymalna możliwa do zdobycia ocena zależy od zaimplementowanej funkcjonalności:

  1. na ocenę 3 wystarczy by program znajdował i wypisywał jedynie długość najdłuższego wspólnego podciągu;
  2. na ocenę 3,5 program powinien znaleźć i wypisać najdłuższy wspólny podciąg;
  3. (alternatywnie) na ocenę 3,5 program możne znajdować jedynie długość najdłuższego wspólnego podciągu, ale złożoność pamięciowa algorytmu powinna być dokładnie rzędu długości krótszego z ciągów wejściowych;
  4. na ocenę 4,5 program powinien znaleźć i w czytelny sposób (analogiczny do narzędzi typu diff) wypisać różnicę pomiędzy ciągami wejściowymi;
  5. na ocenę 5 ciągami wejściowymi dla algorytmu są kolejne linie z dwóch plików, zaś program powinien wypisywać różnicę pomiędzy tymi plikami, tj. wypisać linie z tych plików, poprzedzając linie które się różnią odpowiednimi prefiksami (np. < i >, albo - i +), zaś linie wspólne można opcjonalnie poprzedzić prefiksem =.

Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą zasady działania i złożoności obliczeniowej zaimplementowanego algorytmu lub algorytmów.

Ocena może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Przykładowe pytania sprawdzające z algorytmów

  • Zilustrować działanie algorytmu dla zadanych ciągów wejściowych.
  • Jaka jest złożoność czasowa oraz pamięciowa algorytmu?
  • Z jakiego spostrzeżenia korzysta algorytm? Z jakiej zależności rekurencyjnej?
  • Na czym polega idea programowania dynamicznego?
  • Jaka jest interpretacja liczb w tworzonej przez algorytm dwuwymiarowej tablicy pomocniczej?
  • Jak skorzystać z najdłuższego wspólnego podciągu do wypisania różnic pomiędzy ciągami wejściowymi? (dotyczy wariantów na oceny 4,5-5)
Piotr Beling
Piotr Beling
adiunkt

Moje główne zaintersowania naukowe obejmują sztuczną inteligencję i teorię gier.