Файл: Алгоритмизация как обязательный этап разработки программы.pdf

Эвристическое программирование - метод программирования, основанный на моделировании мыслительной деятельности человека. Используется для решения задач, не имеющих строго формализованного алгоритма или связанных с неполнотой исходных данных [10].

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

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

Любая программа выполняется в компьютере. Посмотрим, как соотносятся между собой компоненты программы и компьютерной архитектуры:

---

• компоненты программы находятся в памяти. В принципе, память является общей для них всех, но логически она разделяется на области, именуемые сегментами. Прежде всего, это сегмент данных, содержащий, естественно, данные программы. Алгоритмическая компонента (выражения, операторы) также находится в памяти в собственном сегменте команд;
• одновременное нахождение в памяти «алгоритма» и данных соответствует принципу хранимой программы. Перед загрузкой в память эти же компоненты находятся в программном файле, который представляет собой точную копию представления программы в памяти – «образ памяти». Это позволяет рассматривать всю программу (в том числе и алгоритм) как данные для работы других программ, например, трансляторов;
• набор операций, выполняемый в программе, соответствует системе команд процессора, на котором она выполняется. Сюда же входят команды, которые обеспечивают заданный в программе порядок действий (операторов).

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

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

Определение программы уже давно дано в простой формуле: «Программа = алгоритм + данные». Но в ней алгоритм и данные не просто «складываются» в одно целое как независимые части, но являются двумя взаимозависимыми элементами. Это своего рода «Янь и Инь» программы, олицетворяющие единство и борьбу двух противоположных начал (в философии этот принцип положен в основу диалектики – учения о развитии). Попробуем привести несколько аналогий, поясняющих сущность взаимодействий в этой «парочке»:

• если данные можно в какой-то мере обладают свойствами пространства (объем, протяженность), то алгоритм – свойствами времени (эффективность, быстродействие). Тезис «проигрывая в пространстве, выигрываем во времени» здесь также уместен: эффективность программ может быть принципиально повышена за счет использования дополнительных структур данных в памяти;
• cинтаксически данные являются аналогом существительных (объектов, над которыми производятся действия), набор операций – аналогом глаголов (выполняемых действий). Программа в целом аналогично предложению, описывающему процесс – последовательность действий над заданными предметами с целью получения результата.

---

Взаимосвязь алгоритма и данных в программе не является простой и линейной. Процесс выполнения любой программы можно рассматривать с двух точек зрения: как последовательность выполнения операций (команд), в которых содержится информация об операндах (данных), которые они обрабатывают – поток команд (поток управления). С другой стороны – любой элемент данных можно рассматривать как результат выполнения действий над исходными данными и как источник данных (операнд) для последующих результатов. Т.е. в программе также присутствует логическая последовательность вычислений (преобразований данных), называемая потоком данных. Исторически сложилось, что в традиционной (фон Неймановской) архитектуре в программе в явном виде задается последовательность команд, т.е. программа выглядит как поток управления, в котором алгоритмическая компонента является первичной (ведущей), а данные – вторичной (ведомой) [11].

5. Алгоритмизация - обязательный этап программирования

Алгоритмизация – это сложный процесс, носящий в значительной степени творческий характер. По оценкам специалистов, постановка задачи и ее алгоритмизация нередко составляют 20 - 30% общего времени на разработку программных средств решения задачи. Сложность и ответственность реализации данного этапа объясняется тем, что для решения одной и той же задачи, как правило, существует множество различных алгоритмов, отличающихся друг от друга уровнем сложности, объемами вычислительных работ, составом необходимой исходной и промежуточной информации и другими факторами, которые оказывают существенное влияние на эффективность выбранного способа решения задачи.

Процесс алгоритмизации решения задачи в общем случае реализуется по следующей схеме:

• выделение автономных этапов процесса решения задачи (как правило, с одним входом и одним выходом);

• формализованное описание содержания работ, выполняемых на каждом выделенном этапе;

• проверка правильности реализации выбранного алгоритма на различных примерах решения задач.

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

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

---

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

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

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

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

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

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

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

---

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

Составление алгоритмов решения задач - это работа творческая. Нет универсального способа, позволяющего без особого труда составлять любые алгоритмы. К сожалению, такого способа не существует, ведь жизненные ситуации и задачи так разнообразны и непредсказуемы! Если бы дело обстояло иначе, появилась бы реальная возможность автоматизировать сам процесс алгоритмизации, поручив его некоторому исполнителю - вероятно, очень высокоинтеллектуальному компьютеру [3].

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

• обеспечение оптимального времени решения задачи;
• обеспечение оптимального использования имеющихся ресурсов (памяти);
• обеспечение требуемой точности вычислений;
• минимальные стоимостные затраты;
• возможность использования стандартных подпрограмм.

При дальнейшей постановке задачи на ПК отыскивается наиболее рациональный способ решения задачи.

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

---