?

Log in

Алгоритмы - построение и анализ Упражнения - Теоретическая информатика по-русски [entries|archive|friends|userinfo]
Теоретическая информатика по-русски

[ Профиль | livejournal userinfo ]
[ Архив | journal archive ]

Алгоритмы - построение и анализ Упражнения [Aug. 12th, 2009|09:09 pm]
Теоретическая информатика по-русски
ru_cs
[imephistopheles]
[Current Location |Russian Federation, Тольятти]

Здравствуйте, Книга о которой пойдет речь мне очень нравиться, но некоторые упражнения меня смущают.
Авторы книги говорят о том что ответов к заданиям из книги, никто никогда не получит, они естественно хотели как лучше. В таком подходе есть несколько проблем.
Если задача предпологает четкий конечный результат, который можно проверить эксперементально, то в таком случае проблем не возникает, но если задача на докозательство то в таком случае возникает проблема - Кому доказывать? Конечно можно попробовать что либо докозать книге, но врядли это даст какой либо результат, доказывать что либо себе тоже не имеет особого смысла. Все дело в том что я не могу без аппонента что ли бо докозать.
Вторая проблема - это смысл задачи, которую предложил автор.
Третья проблема - это теоретические вопросы, как определить границы где пора остановиться.
В частности сейчас я хотел бы предложить задачу со второй проблемой:
2.1-3. Рассмотрим задачу поиска
Вход: Последовательность n чисел A = <a1, a2, ... an> и величина v.
Выход: индекс i, обладающий символом v = A[i], или значение NIL, если в массиве A отсутствует значение v.
Составьте псевдокод линейного поиска, при работе которого выполняется сканирование последовательности в поиске значения v. Докажите корректность алгоритма с помощью инварианта цикла. Убедитесь, что выбранные инварианты цыкла удовлетворяют трем условиям.

Задача кажется простой, но есть вопрос по смыслу задачи - говоря о ленейном поиске имеется ввиду простой перебор значений, или сначало сортировка а затем перебор. Еще до этого, в книге, описывался алгоритм сортировка вставкой, он полностью был описан и его корректность была доказана с использованием инварианта цикла, так вот главным аргументом было то что сортировочный массив никак циклом не изменяется, и это как раз и доказывало корректность алгоритма, вообще там три этапа, но это был один из главных. Точнее это свойство "Сохранение".
В задаче, которая описана выше, ничего изменять не прейдеться вообще, а значит цикл инвариантен. Корректность доказана. В случае если требуется сортировка, то эта задача доказана самими авторами книги, и не имеет смысла ее доказывать.

Какое-то решение слишком простое? Возможно я неправельно понял смысла задачи - подскажите.

З.Ы.: Хочу развернуть здесь цикл постов по задачам из книги, которые требуют доказательства и нетревиального решения, как вы на это смотрите? Есть также орошая книга SICP там тоже много таких задач... Жду ваших комментариев.
Всем спасибо за помощь.
Прошу прощения за разного рода орфографические ошибки.
LinkReply