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:
- na ocenę 3 wystarczy by program znajdował i wypisywał jedynie długość najdłuższego wspólnego podciągu;
- na ocenę 3,5 program powinien znaleźć i wypisać najdłuższy wspólny podciąg;
- (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;
- na ocenę 4,5 program powinien znaleźć i w czytelny sposób (analogiczny do narzędzi typu diff, tak jak pokazał to w artykule Diffing Florian Hartmann) wypisać różnicę pomiędzy ciągami wejściowymi, tj. wypisać łańcuch, w który w jakiś sposób (np. trzema różnymi kolorami, albo poprzez poprzedzenie znakami
-,+i=) zaznaczone byłyby fragmenty będące odpowiednio: tylko w pierwszym wejściowym łańcuchu, tylko w drugim wejściowym łańcuchu, i wspólne; - 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=(więcej informacji można znaleźć w artykule Diffing Floriana Hartmanna).
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?
- Jaka jest złożoność wybranej części algorytmu, np. tej odpowiedzialnej za odtworzenie najdłuższego wspólnego podciągu na podstawie wcześniej zbudowanej tablic pomocniczej?
- 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)