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

End.

End

End

until удачно & (k=m)

4.4.1. Как разрабатывать алгоритм?

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

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

Эвристика – не совсем чётко очерченная область науки, которая находится на стыке логики, искусственного интеллекта, философии и психологии. Цель эвристики – исследовать методы и правила, как делать открытия и изобретения. Отдельные высказывания о таком исследовании можно уже обнаружить у комментаторов Евклида.

Наиболее известные попытки создать стройную систему эвристики принадлежат Р. Декарту (1596 – 1650) и Г. Лейбницу (1646 – 1716) - двум великим математикам и философам. Первый попытался разработать универсальный метод решения задач, однако его «Правила для направления ума» остались неоконченными. Второй намеревался написать «Искусство изобретения», но не осуществил своего намерения; однако многочисленные отрывки, разбросанные в его трудах, показывают, что у него были интересные мысли по этому вопросу. Он неоднократно подчеркивал значение этого вопроса; так, он писал: «Нет ничего важнее, чем умение найти источник изобретения, – на мой взгляд, это еще интереснее, чем само изобретение».

Б. Больцано (1781 – 1848), логик и математик, оставил интересное и подробное изложение эвристики; он предпослал изложению введение, в котором написал: «… я приложу усилия к тому, чтобы ясно изложить правила и способы исследования, которыми руководствуются все способные люди …».

Следующим в этом ряду назовём Д. Пойа, не столько великого математика, сколько очень талантливого Учителя. Он написал книгу «Как решать задачу?» [14], весьма полезную как учителю, так и ученику не только средней, но и студенту высшей школы (в последнем случае рекомендуем также познакомиться со второй его книгой [15]). По её мотивам написаны книги [2] и [16].

Задача построения алгоритма, как и любая задача, может быть решена в соответствии с методикой, разработанной Д. Пойа [14]. Она заключается в разбиении процесса решения на этапы:

· постановка задачи (понимание постановки задачи);

· составление плана решения (анализ);

· реализация плана (синтез);

· осмысление полученного решения («взгляд назад»)

и в системе чётко сформулированных вопросов к каждому из перечисленных этапов. Назначение вопросов – стимуляция умственной деятельности. В приложении В приведена таблица, заимствованная из [14], в которой к каждому этапу процесса решения даются вопросы и советы, цель которых – помочь решить задачу. Приведём краткие замечания к каждому этапу.

Понимание постановки задачи

Серьёзное внимание должно быть уделено каждому этапу, но особого внимания заслуживает постановка задачи, которая заключается в ясно сформулированных требованиях (условиях) к данным, которые подлежат обработке. Недаром говорят, что правильно поставленная задача – это половина её решения. Если задача сформулирована не вами, то её надо понять настолько ясно, чтобы можно было считать, что поставить её могли бы и вы. При этом важно понять связь данных и условия.

Важно не только понять задачу, важно и хотеть её решить. Прежде всего, должна быть понятна словесная формулировка задачи: что неизвестно? Что дано? В чём состоит условие? Нужно внимательно, многократно и с разных сторон рассмотреть главные элементы задачи.

Если с задачей связана какая-либо геометрическая фигура, необходимо сделать чертёж и указать на нём неизвестное и данные. Если необходимо как-нибудь назвать эти объекты, нужно ввести подходящие обозначения; уделяя определённое внимание подходящему выбору символов, решающий задачу вынужден сосредоточить свои мысли на объектах, для которых следует подыскать символы.

На этой предварительной стадии полезным может оказаться вопрос: возможно ли удовлетворить условию? Притом, что мы удовлетворимся лишь временным ответом, догадкой.

Составление плана решения

При построении плана можно использовать многократно апробированный в проектировании (а построение – это разновидность проектирования) метод «сверху–вниз», когда идея на каждом этапе всё более детализируется. Этот же метод применяется и в технологии программирования.

Можно считать, что есть план, если известно, хотя бы в общих чертах, какие вычисления или построения придётся проделать, чтобы получить неизвестное. Путь от понимания постановки задачи до представления себе плана решения может быть долгим и извилистым. Главный шаг на пути к решению задачи состоит в том, чтобы выработать идею плана. Эта идея может появляться постепенно. Или она может возникнуть вдруг, в один миг, после, казалось бы, безуспешных попыток и продолжительных сомнений (блестящая идея).

Хорошие идеи имеют своим источником прошлый опыт и ранее приобретенные знания. Уместно начать работу с вопроса: известна ли вам какая-нибудь родственная задача? Трудность здесь в том, что обычно оказывается слишком много задач, имеющих с данной какие-либо общие черты. Нужно выбрать те задачи, которые имеют существенную черту, и таковой является неизвестное: вспомните знакомую задачу с тем же или подобным неизвестным. Если повезёт и удастся вспомнить уже решённую такую задачу, то теперь надо извлечь из неё всё, что можно: вот задача, сходная с данной и уже решенная. Нельзя ли воспользоваться ею?

Если подобные вопросы не помогают, необходимо начать поиски новых подходящих точек соприкосновения, исследовать всевозможные аспекты этой задачи; нужно видоизменить, преобразовать, модифицировать задачу. Нельзя ли сформулировать задачу иначе? Существуют следующие специфические средства видоизменить задачу: обобщение, специализация, использование аналогии, отбрасывание части условий и т. д. Видоизменения задачи могут привести к некоторой подходящей вспомогательной задаче: если не удаётся решить данную задачу, попытайтесь предварительно решить сходную. Чтобы не потерять первоначальную задачу в поисках и экспериментировании со вспомогательными задачами, необходимо пользоваться время от времени превосходным вопросом: Все ли данные вы использовали? Всё ли условие?

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