Проверка правильности алгоритма

Построение алгоритма

После постановки задачи и построения для нее модели необходимо приступить к разработке алгоритма ее решения. Выбор метода разработки, в большинстве случаев, определяется построенной моделью и может существенно повлиять на эффективность алгоритма решения. Несколько различных алгоритмов могут быть правильными, но, в то же время, значительно отличаться по эффективности (понятие и критерии эффективности будут рассмотрены ниже). Для построения «хорошего» алгоритма необходим тщательный анализ построенной модели и ее ограничений. Следует отметить, что среди начинающих (и не только) программистов существует тенденция уделять разработке алгоритма при создании программы необоснованно меньше времени, чем на собственно создание программы. Опыт преподавания дисциплины «Программирование» на факультете Математики и информатики Тульского государственного педагогического университета позволяет утверждать, что в большинстве случаев студенты недооценивают стадию построения алгоритма и стремятся как можно быстрее перейти к написанию программы. Для некоторых достаточно простых задач такой подход во многом оправдан, но более серьезные требуют тщательного продумывания алгоритма, лежащего в их основе. В конечном итоге это приводит к отождествлению понятий «программирование» и «набор программы» и невозможности дальнейшей отладки полученной программы.

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

Проверка правильности алгоритма, на наш взгляд, является одним из наиболее трудных этапов построения алгоритма. По степени творческих затрат его можно сравнить с процедурой разработки алгоритма. В большинстве случаев правильность алгоритма не следует тривиальным образом из его разработки и требует проведения доказательства. В общем случае можно предложить следующую методику доказательства правильности алгоритма. Пусть алгоритм имеет шагов. Рассмотрим последовательно каждый из шагов, проведем теоретическое обоснование его правомерности и правильности. Далее следует доказать конечность алгоритма, в частности его выполнение за конечное число шагов для любой системы входных данных.

Дата добавления: 2014-01-07