Czy można napisać weryfikator, który sprawdza, czy dany program implementuje dany algorytm?

Biorąc pod uwagę program P, napisany w C++, czy mogę napisać algorytm, który wyszuka, czy program P implementuje określony algorytm? Czy istnieje algorytm, który rozwiązuje ten problem. Czy ten problem można rozwiązać?Czy można napisać weryfikator, który sprawdza, czy dany program implementuje dany algorytm?

Na przykład proszę osobę, aby zaimplementowała algorytm szybkiego sortowania, a teraz, jeśli chcę się upewnić, że osoba faktycznie zaimplementowała algorytm szybkiego sortowania. Osoba może w rzeczywistości zaimplementować inny algorytm sortowania i wygeneruje poprawne wyniki i przejdzie wszystkie testy (testowanie czarnej skrzynki). Jednym ze sposobów, w jaki mogę to zrobić, jest zapoznanie się z kodem źródłowym. Chcę uniknąć tego ręcznego wysiłku i chcę napisać program, który może wykonać tę pracę. Pytanie brzmi "Czy to możliwe?".

Źródło

2013-02-24 Aryaveer

Co powiedzie się na to, że dana osoba używa abstrakcyjnego interfejsu dla niektórych operacji na niskim poziomie, takich jak dostęp do elementów i zamiana. Następnie przekaż im konkretny obiekt, który sprawi, że wywołujący wywoła te operacje w taki sposób, w jaki robiłby to quicksort. –

Od Rice's Theorem, nie można nawet w ogóle zdecydować, czy fragment kodu jest funkcją sortującą czy nie, poprzez sprawdzenie kodu. Można oczywiście dowiedzieć się, czy ma to wpływ na sortowanie skończonego zestawu danych wejściowych, uruchamiając je za pomocą tych danych wejściowych i badając wyniki.

Możliwe, że będziesz w stanie zrobić coś dla konkretnego przypadku danego algorytmu sortowania, badając sortowaną tablicę podczas sortowania, sprawdzając niezmienniki, które są charakterystyczne dla algorytmu docelowego. Na przykład każde wywołanie rekursywnego szybkiego sortowania spowoduje posortowanie subarray.

============================================== ===================

Kontynuując komentarze, proponuję przejrzeć Ahmad Taherkhani's home page. Kontynuował badania w tej dziedzinie, w tym dokument z 2012 r. Na ten temat.

Źródło

2013-02-24 15:08:49

dzięki, że naprawdę pomogło. Zastanawiam się, czy to zadziała, jeśli użyjemy zestawu przykładowych programów wdrażających algorytm, a następnie spróbujemy sklasyfikować program. Tak jak w przypadku problemów z uczeniem maszynowym. – Aryaveer

@Aryaveer Kluczem do tego byłoby znalezienie funkcji, które można wyodrębnić z tekstu, tak aby punkty znajdujące się blisko siebie w przestrzeni obiektów reprezentowały podobne algorytmy. Zrobiłem kilka wyszukiwania w Internecie i znalazłem [Static Program Analysis for Recognizing Algoriths Sorting] (www.cs.hut.fi/~ahmad/mastersthesis.pdf). Jest to dokument z 2008 roku, ale może być przydatnym punktem wyjścia do cytowania w poszukiwaniu aktualnego stanu wiedzy. –

myślałem i nadal myśli o kontroli stosu/sterty (biorąc pod uwagę jesteś testowania przeciwko zoptymalizowanych rozwiązań również).
Można sprawdzić złożoność czasu i ogólną złożoność pamięci, która zawęzi wyniki. nawet dla Time: O (n lg n) dla łączenia i szybkiego sortowania. można je rozróżnić za pomocą przydziału pamięci, ponieważ są one N, Lg (n) w kolejności.
można również sprawdzić rzeczy takie jak pierwotne zakłócenie tablicy ... ale nie ma to decydującej wagi.

Źródło

2013-02-24 15:14:21 blackmath

Czy można napisać weryfikator, który sprawdza, czy dany program implementuje dany algorytm?

Odpowiedz

Powiązane problemy