Najdłuższy wspólny problem z podciągami - Longest common subsequence problem

Porównanie dwóch wersji przykładowego pliku na podstawie ich najdłuższego wspólnego podciągu (czarny)

Najdłuższy wspólny podciąg ( LCS ) problemem jest problem ze znalezieniem najdłuższy podciąg wspólne dla wszystkich sekwencji w zbiorze sekwencji (często zaledwie dwóch sekwencji). Różni się on od najdłuższego wspólnego problemu z podciągami : w przeciwieństwie do podciągów, podciągi nie muszą zajmować kolejnych pozycji w oryginalnych sekwencjach. Najdłuższy wspólny problem podciągów jest klasycznym problemem informatycznym , podstawą programów do porównywania danych , takich jak narzędzie diff i ma zastosowanie w lingwistyce obliczeniowej i bioinformatyce . Jest również szeroko stosowany przez systemy kontroli wersji, takie jak Git, do uzgadniania wielu zmian wprowadzonych w zbiorze plików kontrolowanym przez wersje.

Rozważmy na przykład sekwencje (ABCD) i (ACBAD). Mają 5 długości 2 wspólnych podsekwencji: (AB), (AC), (AD), (BD) i (CD); 2 długości-3 wspólne podsekwencje: (ABD) i (ACD); i nie są już wspólnymi podciągami. Tak więc (ABD) i (ACD) są ich najdłuższymi wspólnymi podciągami.

Złożoność

W ogólnym przypadku dowolnej liczby ciągów wejściowych problem jest NP-trudny . Gdy liczba ciągów jest stała, problem można rozwiązać w czasie wielomianowym za pomocą programowania dynamicznego .

Biorąc pod uwagę sekwencje o długościach , wyszukiwanie naiwne testowałoby każdą z podsekwencji pierwszej sekwencji w celu określenia, czy są one również podsekwencjami pozostałych sekwencji; każda podsekwencja może być testowana w czasie liniowym na długości pozostałych sekwencji, więc czas dla tego algorytmu byłby

W przypadku dwóch sekwencji n i m elementów, czas działania podejścia programowania dynamicznego wynosi O ( n × m ). Dla dowolnej liczby sekwencji wejściowych podejście programowania dynamicznego daje rozwiązanie w

Istnieją metody o mniejszej złożoności, które często zależą od długości LCS, rozmiaru alfabetu lub obu.

LCS niekoniecznie jest wyjątkowy; w najgorszym przypadku liczba wspólnych podciągów jest wykładnicza w długościach wejść, więc złożoność algorytmiczna musi być co najmniej wykładnicza.

Rozwiązanie dla dwóch sekwencji

Problem LCS ma optymalną podstrukturę : problem można rozbić na mniejsze, prostsze podproblemy, które z kolei można podzielić na prostsze podproblemy i tak dalej, aż w końcu rozwiązanie stanie się trywialne. W szczególności LCS ma nakładające się podproblemy : rozwiązania podproblemów wysokiego poziomu często ponownie wykorzystują rozwiązania podproblemów niższego poziomu. Problemy z tymi dwoma właściwościami są podatne na dynamiczne podejścia programowania , w których rozwiązania podproblemów są zapamiętywane , to znaczy rozwiązania podproblemów są zapisywane do ponownego wykorzystania.

Przedrostki

Przedrostek S n z S jest zdefiniowany jako pierwsze n znaków S . Na przykład przedrostki S = (AGCA) to

S 0 = ()
S 1 = (a)
S 2 = (AG)
S 3 = (AGC)
S 4 = (Agca).

Niech LCS ( X , Y ) będzie funkcją, która oblicza najdłuższy podciąg wspólne dla X i Y . Taka funkcja ma dwie interesujące właściwości.

Pierwsza nieruchomość

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A , dla wszystkich ciągów X , Y i wszystkich symboli A , gdzie ^ oznacza konkatenację ciągów. Pozwala to na uproszczenie obliczeń LCS dla dwóch sekwencji kończących się tym samym symbolem. Na przykład LCS ("BANANA","ATANA") = LCS ("BANAN","ATAN")^"A", Kontynuując dla pozostałych wspólnych symboli, LCS ("BANANA","ATANA") = LCS (" BAN","AT")^"ANA".

Druga nieruchomość

Jeśli A i B są różnymi symbolami ( AB ), to LCS (X^A,Y^B) jest jednym z ciągów o maksymalnej długości w zbiorze { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) }, dla wszystkich łańcuchów X , Y .

Na przykład LCS („ABCDEFG”,„BCDGK”) jest najdłuższym ciągiem wśród LCS („ABCDEFG”,„BCDG”) i LCS („ABCDEF”,„BCDGK”); gdyby oba miały taką samą długość, jeden z nich mógłby zostać wybrany arbitralnie.

Aby zrealizować nieruchomość, rozróżnij dwa przypadki:

  • Jeśli LCS („ABCDEFG”,„BCDGK”) kończy się na „G”, to końcowe „K” nie może znajdować się w LCS, stąd LCS („ABCDEFG”,„BCDGK”) = LCS („ABCDEFG”,„BCDG ").
  • Jeśli LCS („ABCDEFG”,„BCDGK”) nie kończy się na „G”, to końcowe „G” nie może znajdować się w LCS, stąd LCS („ABCDEFG”,„BCDGK”) = LCS („ABCDEF”, "BCDGK").

Zdefiniowano funkcję LCS

Niech dwie sekwencje zostaną zdefiniowane następująco: i . Przedrostki są ; przedrostki są . Niech stanowią zestaw najdłuższy wspólny podciąg przedrostków i . Ten zestaw sekwencji jest podany w następujący sposób.

Aby znaleźć LCS i , porównaj i . Jeśli są równe, to ciąg jest rozszerzany o ten element, . Jeśli nie są równe, zachowany jest najdłuższy z dwóch ciągów , i . (Jeśli są tej samej długości, ale nie identyczne, obie są zachowane).

Przykład pracy

Zostanie znaleziony najdłuższy podciąg wspólny dla R = (GAC) i C = (AGCAT). Ponieważ funkcja LCS używa elementu „zero”, wygodnie jest zdefiniować puste przedrostki zerowe dla tych sekwencji: R 0 = Ø; i C, 0 = O. Wszystkie prefiksy są umieszczone na stole C w pierwszym rzędzie (co czyni go C olumn nagłówku) i R w pierwszej kolumnie (co czyni go R OW nagłówku).

Struny LCS
Ø A g C A T
Ø Ø Ø Ø Ø Ø Ø
g Ø
A Ø
C Ø

Ta tabela służy do przechowywania sekwencji LCS dla każdego kroku obliczeń. Druga kolumna i drugi wiersz zostały wypełnione Ø, ponieważ gdy ciąg pusty jest porównywany z ciągiem niepustym, najdłuższy wspólny podciąg jest zawsze ciągiem pustym.

LCS ( R 1 , C 1 ) określa się przez porównanie pierwsze elementy w każdej sekwencji. G, a nie są takie same, więc staje się LCS (za pomocą "drugą właściwość") najdłuższy z dwóch sekwencji, LCS ( R 1 , C 0 ) a LCS ( R 0 , C 1 ). Zgodnie z tabelą oba są puste, więc LCS ( R 1 , C 1 ) również jest puste, jak pokazano w poniższej tabeli. Strzałki wskazują, że sekwencja pochodzi zarówno komórki powyżej, LCS ( R 0 , C 1 ), a komórki w lewej LCS ( R 1 , C, 0 ).

LCS ( R 1 , C 2 ) jest określany przez porównanie G i G. Pasują do siebie, więc G jest dołączane do lewego górnego ciągu, LCS ( R 0 , C 1 ), czyli (Ø), dając (ØG), który jest (G).

W przypadku LCS ( R 1 , C 3 ) G i C nie pasują do siebie. Powyższa sekwencja jest pusta; ten po lewej zawiera jeden element, G. Wybór najdłuższego z nich, LCS ( R 1 , C 3 ) to (G). Strzałka wskazuje w lewo, ponieważ jest to najdłuższa z dwóch sekwencji.

LCS ( R 1 , C, 4 ) jest tak samo (G).

LCS ( R 1 , C 5 ) jest tak samo (G).

Wiersz „G” zakończony
Ø A g C A T
Ø Ø Ø Ø Ø Ø Ø
g Ø Ø (G) (G) (G) (G)
A Ø
C Ø

W przypadku LCS ( R 2 , C 1 ) A jest porównywane z A. Te dwa elementy są zgodne, więc A jest dodawane do Ø, dając (A).

W przypadku LCS ( R 2 , C 2 ) A i G nie pasują do siebie, więc najdłuższy z LCS ( R 1 , C 2 ), czyli (G) i LCS ( R 2 , C 1 ), czyli (A ), jest używany. W tym przypadku każdy z nich zawiera jeden element, więc LCS ma dwa podciągi: (A) i (G).

Dla LCS ( R 2 , C 3 ) A nie pasuje C LCS ( R 2 , C 2 ) zawiera sekwencje (a) i (G); LCS ( R 1 , C 3 ) oznacza (G), która jest już zawarta w LCS ( R 2 , C 2 ). Powoduje to, że DPP ( R 2 , C 3 ) zawiera także dwa krótsze sekwencje (a) i (G).

Dla LCS ( R 2 , C 4 ) A pasuje do A, który jest dołączony do lewej górnej komórki, dając (GA).

Dla LCS ( R 2 , C 5 ) A nie pasuje T. W porównaniu dwóch sekwencji, (GA) i (G), przy czym najdłuższy (GA), tak, LCS ( R 2 , C 5 ) to (GA).

Ukończono wiersze „G” i „A”
Ø A g C A T
Ø Ø Ø Ø Ø Ø Ø
g Ø Ø (G) (G) (G) (G)
A Ø (A) (A) i (G) (A) i (G) (GA) (GA)
C Ø

Dla LCS ( R 3 , C 1 ), C i A nie pasują do siebie, więc LCS ( R 3 , C 1 ) otrzymuje najdłuższą z dwóch sekwencji, (A).

W przypadku LCS ( R 3 , C 2 ) C i G nie pasują do siebie. Zarówno LCS ( R 3 , C 1 ) jak i LCS ( R 2 , C 2 ) mają jeden pierwiastek. Powoduje to, że DPP ( R 3 , C 2 ) zawiera dwie krótsze sekwencje (a) i (G).

Dla LCS ( R 3 , C 3 ) C i C są zgodne, więc C jest dołączane do LCS ( R 2 , C 2 ), który zawiera dwie podsekwencje, (A) i (G), dając (AC) i (GC ).

W przypadku LCS ( R 3 , C 4 ), C i A nie pasują do siebie. Łącząc LCS ( R 3 , C 3 ), który zawiera (AC) i (GC) oraz LCS ( R 2 , C 4 ), który zawiera (GA), daje w sumie trzy sekwencje: (AC), (GC) i (GA).

Wreszcie dla LCS ( R 3 , C 5 ) C i T nie pasują do siebie. Powoduje to, że DPP ( R 3 , C 5 ) zawiera trzy sekwencje, (AC), stałe (GC) i (Ga).

Ukończono tabelę LCS
Ø A g C A T
Ø Ø Ø Ø Ø Ø Ø
g Ø Ø (G) (G) (G) (G)
A Ø (A) (A) i (G) (A) i (G) (GA) (GA)
C Ø (A) (A) i (G) (AC) i (GC) (AC) i (GC) i (GA) (AC) i (GC) i (GA)

Ostateczny wynik jest taki, że ostatnia komórka zawiera wszystkie najdłuższe podciągi wspólne dla (AGCAT) i (GAC); są to (AC), (GC) i (GA). Tabela pokazuje również najdłuższe wspólne podciągi dla każdej możliwej pary przedrostków. Na przykład dla (AGC) i (GA) najdłuższy wspólny podciąg to (A) i (G).

Podejście śledzenia

Obliczenie LCS wiersza tabeli LCS wymaga tylko rozwiązań dla bieżącego wiersza i poprzedniego wiersza. Jednak w przypadku długich sekwencji te sekwencje mogą być liczne i długie, wymagając dużo miejsca do przechowywania. Miejsce do przechowywania można zaoszczędzić, zapisując nie rzeczywiste podciągi, ale długość podciągu i kierunek strzałek, jak w poniższej tabeli.

Przechowywanie długości, a nie sekwencji
Ø A g C A T
Ø 0 0 0 0 0 0
g 0 0 1 1 1 1
A 0 1 1 1 2 2
C 0 1 1 2 2 2

Rzeczywiste podsekwencje są wyprowadzane w procedurze śledzenia, która podąża za strzałkami wstecz, zaczynając od ostatniej komórki w tabeli. Gdy długość maleje, ciągi musiały mieć wspólny element. Kilka ścieżek jest możliwych, gdy w komórce są pokazane dwie strzałki. Poniżej znajduje się tabela dla takiej analizy, z liczbami pokolorowanymi w komórkach, w których długość ma się zmniejszyć. Pogrubione liczby wyznaczają sekwencję (GA).

Przykład śledzenia
Ø A g C A T
Ø 0 0 0 0 0 0
g 0 0 1 1 1 1
A 0 1 1 1 2 2
C 0 1 1 2 2 2

Związek z innymi problemami

Dla dwóch ciągów i , długość najkrótszej wspólnej supersekwencji jest związana z długością LCS przez

Odległość edycja wtedy gdy dopuszczalna jest tylko wstawiania i usuwania (podstawień) lub, gdy koszt zastąpienia jest dwukrotnie kosztów insercji lub delecji, jest

Kod dla dynamicznego rozwiązania programistycznego

Obliczanie długości LCS

Poniższa funkcja przyjmuje jako sekwencje wejściowe X[1..m]i Y[1..n], oblicza LCS między X[1..i]i Y[1..j]dla wszystkich 1 ≤ i ≤ mi 1 ≤ j ≤ ni przechowuje go w C[i,j]. C[m,n]będzie zawierać długość LCS Xi Y.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
        C[i,0] = 0
    for j := 0..n
        C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

Alternatywnie można zastosować zapamiętywanie .

Przykład w C#

static int[,] LcsLength(string a, string b)
{
    int[,] C = new int[a.Length + 1, b.Length + 1]; // (a, b).Length + 1
    for (int i = 0; i < a.Length; i++)
        C[i, 0] = 0;
    for (int j = 0; j < b.Length; j++)
        C[0, j] = 0;
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
        {
            if (a[i - 1] == b[j - 1])//i-1,j-1
                C[i, j] = C[i - 1, j - 1] + 1;
            else
                C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);
        }
    return C;
}

Odczytywanie LCS

Poniższa funkcja cofa wybory podjęte podczas obliczania Ctabeli. Jeśli ostatnie znaki w prefiksach są równe, muszą znajdować się w LCS. Jeśli nie, sprawdź, co dało największy LCS utrzymania i , i dokonaj tego samego wyboru. Po prostu wybierz jedną, jeśli były równie długie. Wywołaj funkcję z i . i=mj=n

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    if C[i,j-1] > C[i-1,j]
        return backtrack(C, X, Y, i, j-1)
    return backtrack(C, X, Y, i-1, j)

Przykład w C#

string Backtrack(int[,] C, char[] aStr, char[] bStr, int x, int y)
{
    if (x == 0 | y == 0)
        return "";
    if (aStr[x - 1] == bStr[y - 1]) // x-1, y-1
        return backtrack(C, aStr, bStr, x - 1, y - 1) + aStr[x - 1]; // x-1
    if (C[x, y - 1] > C[x - 1, y])
        return backtrack(C, aStr, bStr, x, y - 1);
    return backtrack(C, aStr, bStr, x - 1, y);
}

Odczytywanie wszystkich LCS

Jeśli wybierasz i daje równie długi wynik, odczytaj oba wynikowe podciągi. Ta funkcja jest zwracana jako zestaw. Zauważ, że ta funkcja nie jest wielomianowa, ponieważ może rozgałęziać się w prawie każdym kroku, jeśli łańcuchy są podobne.

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

Wydrukuj różnicę

Ta funkcja cofnie się przez macierz C i wydrukuje różnicę między dwiema sekwencjami. Zauważ, że otrzymasz inną odpowiedź, jeśli wymienisz i <, z >i poniżej.

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i >= 0 and j >= 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

Przykład

Niech będzie „ ” i będzie „ ”. Najdłuższym wspólnym podciągiem między i jest „ ”. Poniższa tabela, która jest generowana przez funkcję , pokazuje długości najdłuższych wspólnych podciągów między prefiksami i . Rząd TH TH kolumna pokazuje długość LCS między i . XMJYAUZMZJAWXUMJAUCLCSLength

0 1 2 3 4 5 6 7
Ø m Z J A W x U
0 Ø 0 0 0 0 0 0 0 0
1 x 0 0 0 0 0 0 1 1
2 m 0 1 1 1 1 1 1 1
3 J 0 1 1 2 2 2 2 2
4 Tak 0 1 1 2 2 2 2 2
5 A 0 1 1 2 3 3 3 3
6 U 0 1 1 2 3 3 3 4
7 Z 0 1 2 2 3 3 3 4

Te podkreślone liczby pokazują ścieżkę funkcja backtrackwynikałoby to z prawym dolnym rogu do lewego górnego rogu, kiedy czyta się o LCS. Jeśli obecne symbole w i są równe, są częścią LCS i poruszamy się zarówno w górę, jak iw lewo ( pogrubione ). Jeśli nie, idziemy w górę lub w lewo, w zależności od tego, która komórka ma wyższy numer. Odpowiada to przyjęciu LCS między i , albo i .

Optymalizacja kodu

W powyższym algorytmie można dokonać kilku optymalizacji, aby przyspieszyć go w rzeczywistych przypadkach.

Zmniejsz zestaw problemów

Macierz C w algorytmie naiwnym rośnie kwadratowo wraz z długościami sekwencji. W przypadku dwóch sekwencji po 100 elementów potrzebna byłaby macierz 10 000 elementów i należałoby wykonać 10 000 porównań. W większości rzeczywistych przypadków, zwłaszcza w przypadku różnic i poprawek kodu źródłowego, początki i końce plików rzadko się zmieniają, a prawie na pewno nie oba jednocześnie. Jeśli w środku sekwencji zmieniło się tylko kilka pozycji, początek i koniec można wyeliminować. Zmniejsza to nie tylko wymagania dotyczące pamięci dla macierzy, ale także liczbę porównań, które należy wykonać.

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

W najlepszym przypadku, sekwencji bez zmian, taka optymalizacja całkowicie wyeliminowałaby potrzebę macierzy C. W najgorszym przypadku, zmiana pierwszej i ostatniej pozycji w sekwencji, wykonywane są tylko dwa dodatkowe porównania.

Skróć czas porównania

Większość czasu, jaki zajmuje algorytm naiwny, spędza na wykonywaniu porównań między pozycjami w sekwencjach. W przypadku sekwencji tekstowych, takich jak kod źródłowy, chcesz wyświetlać wiersze jako elementy sekwencji zamiast pojedynczych znaków. Może to oznaczać porównanie stosunkowo długich ciągów dla każdego kroku algorytmu. Można dokonać dwóch optymalizacji, które mogą pomóc w skróceniu czasu, jaki zajmują te porównania.

Zredukuj ciągi do haszy

Funkcja mieszająca lub suma kontrolna może służyć do zmniejszania rozmiaru ciągów w sekwencjach. Oznacza to, że w przypadku kodu źródłowego, w którym średnia linia ma długość 60 lub więcej znaków, skrót lub suma kontrolna tej linii może mieć tylko od 8 do 40 znaków. Dodatkowo losowy charakter skrótów i sum kontrolnych gwarantowałby szybsze spięcie porównań, ponieważ wiersze kodu źródłowego rzadko będą zmieniane na początku.

Ta optymalizacja ma trzy podstawowe wady. Po pierwsze, należy poświęcić trochę czasu, aby wstępnie obliczyć skróty dla dwóch sekwencji. Po drugie, na nowe sekwencje haszowane należy przydzielić dodatkową pamięć. Jednak w porównaniu z zastosowanym tutaj algorytmem naiwnym obie te wady są stosunkowo minimalne.

Trzecią wadą są kolizje . Ponieważ nie ma gwarancji, że suma kontrolna lub hash są unikatowe, istnieje niewielka szansa, że ​​dwa różne elementy mogą zostać zredukowane do tego samego hash. Jest to mało prawdopodobne w kodzie źródłowym, ale jest możliwe. Skrót kryptograficzny byłby zatem znacznie lepiej dopasowany do tej optymalizacji, ponieważ jego entropia będzie znacznie większa niż prosta suma kontrolna. Jednak korzyści mogą nie być warte konfiguracji i wymagań obliczeniowych skrótu kryptograficznego dla małych długości sekwencji.

Zmniejsz wymaganą przestrzeń

Jeśli wymagana jest tylko długość LCS, macierz można z łatwością zredukować do macierzy lub do wektora (inteligentniejszego), ponieważ podejście programowania dynamicznego wymaga tylko bieżącej i poprzednich kolumn macierzy. Algorytm Hirschberga pozwala na skonstruowanie samego ciągu optymalnego w tych samych kwadratowych granicach czasu i przestrzeni liniowej.

Dalsze zoptymalizowane algorytmy

Istnieje kilka algorytmów, które działają szybciej niż przedstawione podejście programowania dynamicznego. Jednym z nich jest algorytm Hunta–Szymańskiego , który zazwyczaj działa w czasie (for ), gdzie jest liczbą dopasowań między dwiema sekwencjami. W przypadku problemów z ograniczonym rozmiarem alfabetu metoda czterech Rosjan może być wykorzystana do skrócenia czasu działania algorytmu programowania dynamicznego o współczynnik logarytmiczny.

Zachowanie na losowych ciągach

Począwszy od Chvátala i Sankoffa (1975) , wielu badaczy badało zachowanie najdłuższej wspólnej długości podciągu, gdy dwa podane ciągi są losowane z tego samego alfabetu. Gdy rozmiar alfabetu jest stały, oczekiwana długość LCS jest proporcjonalna do długości dwóch ciągów, a stałe proporcjonalności (w zależności od rozmiaru alfabetu) są znane jako stałe Chvátala-Sankoffa . Ich dokładne wartości nie są znane, ale górne i dolne granice ich wartości zostały udowodnione i wiadomo, że rosną one odwrotnie proporcjonalnie do pierwiastka kwadratowego z rozmiaru alfabetu. Wykazano, że uproszczone modele matematyczne najdłuższego wspólnego problemu podciągów są kontrolowane przez rozkład Tracy-Widoma .

Zobacz też

Bibliografia

Zewnętrzne linki