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

10

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ć.

— Nathvi
źródło

Nie widzę, jak stresowanie między „dowolnym” a „an” wyjaśnia, czego naprawdę szukasz. Jeśli jakaś procedura decyzyjna jest powiązana z określonym algorytmem B, wówczas nie ma rzeczywistych danych wejściowych i odpowiedź jest zawsze taka sama. Myślę, że chcesz zapytać, czy „jakikolwiek algorytm w obrębie pewnej klasy algorytmów”, w którym klasa jest powiązana / znana. (edytuj: uwypuklono także komentarz mojego mhuma).

— Nicholas Mancuso,

2

Niejednoznaczność w użyciu „an” i „any” jest dokładnie tym, dlaczego wymyślono kwantyfikatory .

— Nate Eldredge,

2

Zredagowałem pytanie, aby skupić się na odpowiednich częściach. Zwróć uwagę, jak używam dokładnie zerowej matematyki do dokładnego wyrażenia problemu (o ile do tej pory określiłeś swoje pytanie) i zwięźle. Pytanie jest wciąż źle postawione: oczywiście istnieją takie algorytmy. Na przykład istnieje prosty algorytm analizujący wszystkie algorytmy z (bardzo istotnej) klasy algorytmów działających w czasie

. Dlatego oczywiście należy wprowadzić pewne ograniczenia dotyczące zestawów danych wejściowych. (Zauważ, że może nie być „prostego przykładu w psuedocode, który mogę zrozumieć”.)

Θ (n \log n)

$\Theta(n \log n)$

— Raphael

12

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.

— Dave Clarke
źródło

8

@Nathvi Rozumiem, że irytują cię niektóre komentarze, które, jak się zgadzam, nie były tak naprawdę konieczne, ale powinieneś również uważać, aby nie używać terminu „pedantyczny napęd” do pracy bardzo renomowanych naukowców (a przy okazji - mojej odpowiedzi). Masz prawo nie lubić matematyki, ale bez niej nie zajdziesz zbyt daleko, a darmowe, obraźliwe słowa nikomu nie pomogą.

— babou

12

Ż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.

— Yuval Filmus
źródło

2

Moje pytanie nie dotyczy arbitralnie wprowadzonego algorytmu, który, gdyby tak było, to twoja odpowiedź byłaby poprawna, z powodu problemu zatrzymania. Miałbyś rację, gdyby moje pytanie brzmiało: „Czy istnieje algorytm A, który przyjmuje dowolny algorytm B, a następnie wyświetla złożoność czasową algorytmu B?”

— Nathvi,

6

Jeśli algorytm B jest ustalony, to na pewno istnieje algorytm A. Wystarczy algorytm, który nie robi nic poza drukowaniem „O (n)” lub jakiejkolwiek miary złożoności odpowiadającej B. Jeśli istnieje tylko jeden możliwy sygnał wejściowy do algorytmu A, potrzebujemy tylko jednego wyjścia.

— mhum

5

@Nathvi też nie było dla mnie jasne - zrozumiałem również pytanie, ponieważ „czy istnieje algorytm pozwalający znaleźć złożoność dowolnego innego algorytmu” i nadal nie rozumiem twojego prawdziwego pytania. Jeśli lubisz liczyć pozytywne głosy, najwyraźniej> 2 osoby tak to interpretowały. W przypadku nieporozumień naprawdę dobrze jest edytować swoje pytanie, w przeciwnym razie tylko osoby czytające tę rozmowę (a nie wszyscy, którzy czytają pytanie) zrozumieją, o co pytasz i udzielą dobrych odpowiedzi. Wygląda na to, że poczułeś, że odpowiedź DW była wroga - FWIW, nie sądzę, że miało to być ..

— jkff

6

@ignis Odpowiedź może być niepełna, ale zdanie napisane przez Yuval jest całkowicie poprawne. Problem zatrzymania nie jest jakimś egzotycznym przypadkiem ubocznym: jest samą istotą obliczeń.

— David Richerby,

3

@nikie To nie pomaga, jeśli chodzi o to pytanie; granice środowiska wykonawczego są nierozstrzygalne nawet na zbiorze wszystkich zawsze kończących się algorytmów.

— Raphael

9

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].

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

— Raphael
źródło

Czy te techniki zawierają oszacowanie precyzji analizy przeciętnego przypadku?

— Martin Berger

@MartinBerger Niestety nie. Mamy kilka pomysłów na ten temat, ale nic jeszcze nie zestaliło się, a tym bardziej nie zostało wdrożone. Zauważ, że łatwo jest oszukać każdą metodę, która sprawdza tylko skończenie wiele rozmiarów wejściowych, więc ogólnie nie ma nadziei. Przy założeniach dotyczących funkcji wykonawczych i / lub zestawów danych, coś może być możliwe. Narzędzie powinno przynajmniej móc powiedzieć „potrzebuje więcej danych”.

— Raphael

To interesujące. Mam nadzieję, że obejrzysz tę dodatkową pracę.

— Martin Berger,

8

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.

— Babou
źródło