Lamer George
Ну, как уже сказано, зависящие от пользователя циклы проверять нафик не надо

Цитата(neutrino @ 12.4.2005, 21:35)

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

А вот это уже лучше. Есть даже подозрение, что для целочисленных циклов это вполне реально.
У меня у самого какие-ты мыслишки по этому поводу в голове крутятся... но нормально оформится не могут

Цитата(neutrino @ 12.4.2005, 21:35)

Может быть я что-нибудь найду и для таких случаев.

Кстати можно вычислять что-то вроде CRC или хэш-функции от текущего набора данных. Уменьшит расход памяти. Хотя и увеличит время.

Цитата(Lamer @ 12.4.2005, 19:45)

Как ты будешь определять конечность такого алгоритма? Ведь он конечен, только если юзер введет b >= a.

По скольку все переменные ограничены опр. кол-вом битов, то цикл будет конечен в любом случае. Если будет ошибка Overflow Error - это значит цикл дошел до минимального отрицательного числа (зависит от кол-ва бит в переменной). Потом все пойдет по кругу и попадуться 2 одинаковых значения переменной b. В любом случае любое изменение значений переменных до цикла выполнится программой А. А каким образом именно изменится это значение неважно.
Добавлено @ 21:57

Цитата

Ну, как уже сказано, зависящие от пользователя циклы проверять нафик не надо

Что за надсмешки!? Что за морды-смайлы!?

Нет ну правда, разве имеет смысл определение время выполнения алгоритма с циклом в теле которого ввод данных пользователем?
Добавлено @ 22:03

Цитата

А вот это уже лучше. Есть даже подозрение, что для целочисленных циклов это вполне реально.

Можно сказать иначе: в алгоритмах вообще (если в них нет зависимости хода алгоритма от случайных генераций) количество итераций циклов однозначно зависят от входных данных. Нужно придумать как найти эту зависимость оптимальным способом. Неоптимальный способ мы уже нашли - запустить цикл и записать все значения переменных.

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

Еще одна проблемка: цикл в цикле.

Цитата

И не просто кто-то а сам великий математик-зеленая лягушка-Максим8!

ну за великого математика спасибо
а 1000 и так в десятичной системе, не надо его из двоичной переводить
только согласился я лишь в принципиальной возможности...

Цитата

Например искать корреляцию данных

Цитата

А вот это уже лучше

вот вам пример

Код

unsigned int ZhutkoeTransform(unsigned int x) {   //тут происходит очень сложное преобразование, которое является перестановкой } ... unsigned int c; for(c=0;c<0xffffff;c++)   if(ZhutkoeTransform(c)==0)     break;

что мы здесь видим:
есть цикл, который просто пытается найти обратную функцию
учитывая сложность функции никакая корреляция не подойдет, т.к. операции могут быть самые разные (вплоть до того, чтобы переставить биты, использовать представление double и кучу всего, что подскажет фантазия)
кроме того, придется не просто пройти этот цикл, а пройти его для любого набора входных параметров (в этом примере их не было, но обычно, они есть у каждого алгоритма)
уже на векторе из 10 double проверка будет работать невообразимо долго (даже при небольшом алгоритме)...

основная проблема в том, что программа пишется сегодня, а проверять она будет алгоритмы, которые напишут завтра, т.е. абсолютно непредсказуемые (если, конечно, не стоит цель проверять типовые алгоритмы, но это неинтересно)

Это сообщение отредактировал(а) maxim1000 - 12.4.2005, 22:17

maxim1000
Нда...

Если бы функция была непрерывной... И найти бы две точки, где она разного знака... Мечты...

А вот с таким чёрным ящиком хрен чего скажешь.

ЗЫ: При внимательном рассмотрении твоего примера видна, что цикл конечен из-за условия c<0xffffff

Цитата

ЗЫ: При внимательном рассмотрении твоего примера видна, что цикл конечен из-за условия c<0xffffff

ладно-ладно, поймал
заменим break на while(true) и будем считать, что мы не знаем, возвращает ли когда-нибудь функция 0

Цитата(neutrino @ 12.4.2005, 19:59)

"Пример в студию!" © Vit

Например расчет какого-нить хэша файла по весьма сомнительному алгоритму. Имя файла зашито в программу... но сам файл может быть любым, как по размеру, так и по контенту... в т.ч. может существовать единственный возможный контент, вызывающий зацикливание алгоритма (например файл нулевой длины) - и как его искать? И не надо кивать, что файл нулевой длины лишь частный случай, алгоритм проверки не имеет права рассматривать его как специальный - или это уже 2 разных алгоритма.

Цитата

for(unsigned i = 1; i != 0; i++);

а если float? double? hyperlong?

Максим, можно даже проще:
0) п = 2
1) пока тру
2) п = искать следующее простое число
3) конец пока


Добавлено @ 23:29
Как говорится: "сосем ноги!"

Я не готов сейчас рассуждать о теории, но вот хотел сказать, что схожие задачи - вполне реальные - существуют в реальном мире и вот каких успехов в их решении удалось добиться:

Задача о поиске вирусов. Требуется определить, является ли программа зараженной вирусом.

Задача о нахождении уязвимостей в программе - таких, как переполнение буфера и т.п.

Антивирусы комбинируют метод эмуляционной отладки (те запуск тестируемого кода на виртуальной машине), метод сканера (те есть база сигнатур известных вирусных кодов или характерных команд), метод мониторинга (перехват обращений к критичным данным) и - самый продвинутый - эвристический анализ. Помню, как я рассказывал одному челу из др веба про то, как я, написав свой первый вир, был крайне удивлен тем, что веб тут же - весьма точно - определил не только наличие вируса, но и точно вывел его тип. Однако подумав немного я зациклил критичный код на значительное число итераций (тем не менее он оставался рабочим) и ... вирус перестал определятся !

Где-то давно читал, что невозможно написать антивирус (при условии стабильности среды - те та же ось, те же апи и проч.) - всегда будет способ обойти любой алгоритм, и вроде это четко можно доказать.

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

То, что до сих пор идет война на вирусном фронте, говорит скорее за то, что задача нерешаема.

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

Это сообщение отредактировал(а) Chingachguk - 24.4.2005, 23:24