Najdłuższy wspólny podciąg (algorytmy w Pythonie; projekt)

Spis treści

Wymagania dotyczące części algorytmicznej

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ę 4 program powinien znaleźć i wypisać najdłuższy wspólny podciąg;
  3. (alternatywnie) na ocenę 4 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ę 5 program powinien znaleźć i w czytelny sposób (analogiczny do narzędzi typu diff) wypisać różnicę pomiędzy ciągami wejściowymi.

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

Wymagania dotyczące programowania

Należy wybrać jeden z niżej opisanych wariantów: wariant z łańcuchami znaków albo program typu diff.

Wariant z łańcuchami znaków, na oceny 3-5

Program, jako ciągi wejściowe, powinien pobrać od użytkownika (np. używając funkcji input) dwa łańcuchy znakowe (typu str).

Na ocenę 3 wystarczy wypisać na ekranie najdłuższy wspólny podciąg (typu str) albo jego długość (w zależności od wybranego wariantu z algorytmów).

Na ocenę 4 program powinien dodatkowo wypisać skonstruowaną przez algorytm, dwuwymiarową tablicę pomocniczą.

Na ocenę 5 (możliwe tylko przy wyborze wariantu na ocenę 5 z algorytmów) program powinien dodatkowo wypisać różnicę pomiędzy podanymi łańcuchami, tj. wypisać łańcuch w których trzema różnymi kolorami zaznaczone byłyby fragmenty będące odpowiednio: tylko w łańcuchu pierwszym, tylko w łańcuchu drugim, i wspólne. Do pokolorowania wyniku można użyć zewnętrznych bibliotek, np. termcolor.

Program typu diff, na oceny 4,5-5

Ten wariant możliwy jest tylko przy wyborze wariantu na ocenę 5 z algorytmów.

Program, jako ciągi wejściowe, powinien wczytać kolejne linie z dwóch plików.

Nazwy plików powinny być podawane jako parametry wywołania programu (te można odczytać z tablicy sys.argv).

Program powinien wypisać różnicę pomiędzy 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 =.

Na ocenę 5, program powinien dodatkowo pokolorować każdą z linii na jeden z trzech kolorów. Jeden kolor dla linii wspólnych i dwa na linie, którymi pliki się różnią. Do pokolorowania wyniku można użyć zewnętrznych bibliotek, np. termcolor.

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)

Przykładowe pytania sprawdzające z programowania

  • Wyjaśnić jak działa użyta w programie składnia Pythona albo funkcja.
  • Za co odpowiedzialna jest w programie wskazana linia?
Piotr Beling
Piotr Beling
adiunkt

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