Можно ли написать верификатор, который проверяет, реализует ли данная программа данный алгоритм?

Учитывая, что программа P, написанная на C++, могу написать алгоритм, который найдет, если программа P реализует определенный алгоритм? Есть ли какой-либо алгоритм, который решает эту проблему. Является ли эта проблема разрешимой?Можно ли написать верификатор, который проверяет, реализует ли данная программа данный алгоритм?

Например, я попрошу человека реализовать быстрый алгоритм сортировки, и теперь, если я хочу убедиться, что человек действительно реализовал быстрый алгоритм сортировки. Человек может фактически реализовать какой-то другой алгоритм сортировки, и он будет производить правильный вывод и передать все тестовые файлы (тестирование черного ящика). Один из способов сделать это - изучить исходный код. Я хочу избежать этого ручного усилия и хочу написать программу, которая может выполнять эту работу. Вопрос: «Возможно ли это?».

источник

2013-02-24 Aryaveer

Как насчет того, чтобы человек использовал абстрактный интерфейс для некоторых операций низкого уровня, таких как доступ к элементам и их замена. Затем передайте им конкретный объект, который гарантирует, что вызывающий абонент вызовет эти операции так, как это было бы быстро. –

От Rice's Theorem вы даже не можете вообще решить, является ли фрагмент кода функцией сортировки или нет, изучив код. Разумеется, вы можете узнать, имеет ли он эффект сортировки для некоторого конечного набора входов, запуская его с этими входами и исследуя результаты.

Возможно, вы сможете что-то сделать для конкретного случая данного целевого алгоритма сортировки, исследуя массив, сортируемый во время сортировки, проверяя инварианты, которые являются характерными для целевого алгоритма. Например, каждый вызов в рекурсивной быстрой сортировке приведет к сортировке субары.

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

Следуя за комментариями, предлагаю посмотреть Ahmad Taherkhani's home page. Он продолжил исследования в этой области, включая статью 2012 года по этой теме.

источник

2013-02-24 15:08:49

спасибо, что очень помогли. Мне интересно, будет ли это работать, если мы будем использовать некоторый набор примеров программ, реализующих алгоритм, а затем мы попытаемся классифицировать программу. Как и в проблемах машинного обучения. – Aryaveer

@Aryaveer Ключом к этому было бы найти функции, которые вы можете извлечь из текста, так что точки, которые находятся близко друг к другу в пространстве функций, представляют собой аналогичные алгоритмы. Я сделал несколько поисков в Интернете и нашел [Статический программный анализ для распознавания алгоритмов сортировки] (www.cs.hut.fi/~ahmad/mastersthesis.pdf). Это статья 2008 года, но может быть полезной отправной точкой для поиска цитат, чтобы найти современное состояние. –

Я думал и все еще думал о проверках стека/кучи (учитывая, что вы тестируете и оптимизированные решения).
Вы можете проверить сложность времени и общую сложность памяти, которые будут сузить результаты. даже для Time: O (n lg n) для слияния и быстрого сортировки. вы можете выделить их с распределением памяти, так как они N, Lg (n) по порядку.
Вы также можете проверить, что такое оригинальное возмущение массива ... и т. Д., Но это не имеет решающего веса.

источник

2013-02-24 15:14:21 blackmath

Можно ли написать верификатор, который проверяет, реализует ли данная программа данный алгоритм?

ответ

Смежные вопросы