Czy istnieje metoda automatycznej analizy algorytmów w czasie wykonywania?

Zastanawiam się, czy istnieje metoda automatycznej analizy środowiska wykonawczego, która działa co najmniej na odpowiednim podzbiorze algorytmów (algorytmów, które można analizować)?

Poszukałem „Automatycznej analizy algorytmu”, co mi to dało, ale to zbyt math. Chcę tylko prosty przykład w psuedocode, który mogę zrozumieć. Może to być zbyt szczegółowe, ale pomyślałem, że warto spróbować.

COSTA narzędzie robi właśnie to, choć nie jest on w wielu przypadkach, jak można sobie wyobrazić, z powodu problemów obliczalności . Jest wiele artykułów na ten temat; Analiza kosztów kodu Java Bytecode autorstwa E. Alberta, P. Arenasa, S. Genaima, G. Puebla, D. Zanardiniego jest dobrym punktem wyjścia.

Podejście polega na wnioskowaniu o rekurencji w czasie wykonywania z kodu Javabyte, konwersję do postaci zamkniętej. Narzędzie oblicza również granice wykorzystania miejsca.

Żaden algorytm nie może zdecydować, czy dany algorytm kiedykolwiek się zatrzyma, czy nie, dlatego w szczególności żaden algorytm nie może dokładnie analizować złożoności danego algorytmu.

Znam jedno podejście do (pół) automatycznej analizy przypadków średnich, a mianowicie MaLiJAn ¹. Przypomina to rodzaj analizy, którą Knuth stosuje w TAoCP. Podstawową ideą jest

• zamodeluj program (przepływ) jako łańcuch Markowa,
• $n$
• $n$
• użyj algebry komputerowej, aby wyliczyć średni koszt (wrt te funkcje).

Należy zauważyć, że działają tylko dodatkowe miary kosztów (np. Porównania, „czas”) i tylko dokładna wartość oczekiwana jest dokładna (przy założeniu doskonałych funkcji prawdopodobieństwa), nie można wyprowadzić wyższych momentów.

Wszystkie etapy oprócz ekstrapolacji są rygorystyczne [2], a wykazano, że metoda pozwala na uzyskanie dobrze znanych wyników z dużą precyzją - oczywiście przy odpowiednich losowych próbkach wejściowych. Chociaż nie ma gwarancji dowodu ani nawet przybliżenia wyników (etap ekstrapolacji jest jak dotąd czysto heurystyczny), wyniki uzyskane za pomocą tego narzędzia dobrze służą do eksperymentowania z trudnymi do analizy algorytmami i formułowania hipotez [3,4].

1. Pełne ujawnienie: należałem do tej grupy badawczej i uczestniczyłem w rozwoju narzędzia.
2. Analiza maksymalnego prawdopodobieństwa algorytmów i struktur danych autorstwa U. Laube i M. Nebela (2010) [ przedruk ]
3. Inżynieria oprogramowania Java Pivot Duals Pivot Quicksort za pomocą MaLiJAn S. Wild i in. (2012) [ preprint ]
4. Analiza maksymalnego prawdopodobieństwa metody Forda-Fulkersona na specjalnych wykresach autorstwa U. Laube und M. Nebel (2015) [ przedruk ]

Oczywiście, jak zauważył Yuval Filmus, nie należy oczekiwać ogólnego rozwiązania takich problemów. Ale jak to zwykle bywa, rozwiązania można znaleźć dla interesujących podzbiorów ogólnego przypadku.

W żaden sposób nie jestem ekspertem, ani nawet nie posiadam dużej wiedzy w tej dziedzinie, ponieważ znam takie prace. Dotyczy automatycznej analizy średniej złożoności, a pracę wykonał Philippe Flajolet i jego koledzy.

$\lambda\acute\upsilon\omega$

Artykuł, który znalazłem w Internecie, to artykuł z 1990 r .: Automatyczna analiza średnich przypadków algorytmów : Philippe Flajolet, Paul Zimmermann i Bruno Salvy .

Spodziewałbym się, że późniejsze prace rozszerzyły tę pracę, ale tak naprawdę nie wiem. Praca była dość mocno cytowana, a wyszukiwanie jej w Internecie powinno przynieść nowsze prace na ten sam temat.

Obawiam się, że praca Flajoleta i jego współpracowników była bardzo matematyczna i nie spodziewałbym się zbyt łatwego czytania.