Алгоритмизация как обязательный этап разработки программы ( Свойства алгоритма )

Содержание:

Введение

Понятие алгоритма стихийно формировалось с древнейших времён. Современный человек понимает под алгоритмом чёткую систему инструкций о выполнении в определённом порядке некоторых действий для решения всех задач какого-то данного класса.

Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаём, что они регламентированы неким алгоритмом - чёткой системой инструкций. Например, наши действия при входе в магазин «Универсам» (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролёру, взять свою сумку, переложить в неё продукты, сдать корзину, покинуть магазин). Второй пример - приготовление манной каши (500 мл молока довести до кипения, при тщательном помешивании засыпать 100 г манной крупы, при помешивании довести до кипения и варить 10 минут). Автоматизм выполнения этих и многих других действий не позволяет нам осознавать их алгоритмическую сущность.

Но есть немало таких действий, выполняя которые мы тщательно следуем той или иной инструкции. Это главным образом непривычные действия, профессионально несвойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для плёнки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению: «Содержимое большого пакета растворить в 350 мл воды при температуре 18-20 С. Там же растворить содержимое малого пакета. Объём раствора довести до 500 мл. Раствор профильтровать. Проявлять 3-4 роликовых фотоплёнки». Второй пример. Если вы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания.

Актуальность изучения алгоритмов обусловлена следующими причинами:

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

Во-вторых, алгоритмы играют ключевую роль в современных технологических инновациях.

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

Ценовые колебания на экономических рынках могут плодотворно рассматриваться как алгоритмический процесс. Даже эволюцию можно рассматривать как удивительно эффективный алгоритм поиска.

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

1. Основы алгоритмизации

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

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

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

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

Большинство полезных алгоритмов требуют организации данных, участвующих в вычислениях.

1.1. Структурная организация данных

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

Без понимания структур данных и алгоритмов невозможно создать серьезный программный продукт - «они служат базовыми элементами любой машинной программы. В организации структур данных и процедур их обработки заложена возможность проверки правильности работы программы».

Основные понятия структур данных

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

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

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

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

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данных».

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

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

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

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).

Классификация структур данных по признаку изменчивости

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

Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа.

Массив - последовательность элементов одного типа, называемого базовым.

Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа.

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

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

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

Линейные и нелинейные структуры данных

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно разделить на линейные и нелинейные структуры.

Линейные СД - это структуры, в которых связи между элементами не зависят от выполнения какого-либо условия.

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

Строчные структуры - одномерные, динамически изменяемые структуры данных, различающиеся способами включения и исключения элементов

Стек - это последовательность, в которой включение и исключение элемента осуществляются с одной стороны последовательности

Очередь - последовательность, в которую включают элементы с одной стороны, а исключают - с другой (рис. 1.7). Структура функционирует по принципу FIFO («первым пришел - первым обслуживается»).

Дек - линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности

В списковых структурах логический порядок данных определяется указателями.

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

Классификация нелинейных структур

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

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

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

Многосвязная структура обладает следующими свойствами:

1.на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

2.каждый элемент может иметь связь с любым количеством других элементов;

3.каждая связка (ребро, дуга) может иметь направление и вес.

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

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

Сплетения (плексы) обобщают понятия графов и списковых структур.

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

Сплетение - связь элементов, основанная на сплетении указателей. Каждый элемент сплетения может содержать информацию о количестве полей с указателями и формате поля данных.

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

1.2. Свойства алгоритма

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

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

Элементарность (понятность). Каждый шаг алгоритма должен быть простым, чтобы устройство, выполняющее операции, могло выполнить его одним действием.

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

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

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

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

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

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

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

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

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

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

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

1.3. Формы записи

Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе или БЕЙСИКе), то говорят об исходной программе. Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.

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

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

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

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

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

вербальный - алгоритм описывается на человеческом языке;

символьный - алгоритм описывается с помощью набора символов;

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

Общепринятыми способами записи алгоритма являются графическая запись с помощью схем алгоритмов (блок-схем) и символьная запись с помощью какого-либо алгоритмического языка.

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

Начало и конец алгоритма обозначают с помощью одноименных символов.

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

Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом «решение».

Имеются примитивы для операций ввода и вывода данных, а также другие графические символы. В настоящий момент они определены стандартом ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения». Всего сборник ЕСПД содержит 28 документов.

По схеме алгоритма легко составить исходную программу на алгоритмическом языке.

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

1.4. Базовые алгоритмические конструкции

Число реализованных конструкций конечно в любом языке программирования. Структурной элементарной единицей алгоритма является команда, обозначающая один элементарный шаг обработки или отображения информации. Простая команда на языке блок-схем изображается в виде функционального блока «процесс», который имеет один вход и один выход. Из команд проверки условий и простых команд образуются составные команды, имеющие более сложную структуру, но тоже один вход и один выход.

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

- следование;

- ветвление (в полной и сокращенной форме);

- цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.

Линейные алгоритмы. Базовая структура «следование» означает, что несколько операторов выполняются последовательно друг за другом, и только один раз за время выполнения программы. Структура «следование» используется для реализации задач, имеющих линейный алгоритм решения. Это означает, что такой алгоритм не содержит проверок условий и повторений, действия в нем выполняются последовательно, одно за другим.

Разветвляющиеся алгоритмы. Второй базовой структурой является «ветвление». Эта структура обеспечивает, в зависимости от результата проверки условия, выбор одного из альтернативных путей работы алгоритма, причем каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Существует структура с полным и неполным ветвлением.

Структура с полным ветвлением (если - то - иначе) записывается так:

Если <условие>

то <действия 1>

иначе <действия 2>

Все если

Команда выполняется так: если <условие> является истинным, то выполняются <действия 1>, записанные после ключевого слова то, если <условие> является ложным, то выполняются <действия 2>, записанные после слова иначе.

Структура с неполным ветвлением (если - то) не содержит части, начинающейся со слова иначе:

Если <условие>

то <действия 1>

Все если

Команда выполняется так: если <условие> является истинным, то выполняются <действия 1>, записанные после ключевого слова то.

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

Блок, для выполнения которого организуется цикл, называется телом цикла. Остальные операторы служат для управления процессом повторения вычислений: это начальные установки, проверка условия продолжения цикла и модификация параметра цикла. Один проход цикла называется итерацией.

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

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

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

Еще один вид циклов - цикл с параметром, или арифметический цикл. Тело цикла выполняется, пока параметр цикла i пробегает множество значений от начального (In) до конечного (Ik).

1.5. Время выполнения программ

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

1. быть простым для понимания, перевода в программный код и отладки;

2. эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.

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

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

2. Этапы решения задачи на ЭВМ

Работа по решению любой
задачи с использованием компьютера включает в себя следующие шесть этапов:

1.Постановка задачи.

2.Формализация задачи.

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

4.Составление программы на языке программирования.

5.Отладка и тестирование программы.

6.Проведение расчетов и анализ полученных результатов.

Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ.

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

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

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

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

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

Основой профессиональной грамотности программиста является развитое алгоритмическое мышление.

ЭВМ - исполнитель алгоритмов. Как известно, каждый алгоритм (программа) составляется для конкретного исполнителя, т.е. в рамках его системы команд. О каком же исполнителе идет речь при изучении темы «Программирование для ЭВМ»? Ответ очевиден: исполнителем здесь является компьютер, а точнее говоря, комплекс ЭВМ + система программирования. Программист составляет программу на том языке, на который ориентирована система программирования.

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

3. Главные принципы, лежащие в основе создания эффективных алгоритмов

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

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

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

Этот метод выглядит очень разумно. Но, как и большинство общих методов решения задач или разработки алгоритмов, его не всегда легко перенести на конкретную задачу. Осмысленный выбор более простых задач - скорее, искусство или интуиция, чем наука. Более того, не существует общего набора правил для определения класса задач, которые можно решать с помощью такого подхода. Размышление над любой конкретной задачей начинается с постановки вопросов. Частные цели могут быть установлены, когда получены ответы на следующие вопросы:

1.Можем ли мы решить часть задачи? Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?

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

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

4.Встречались ли мы с похожей задачей, решение которой известно? Можно ли видоизменить ее решение для решения нашей задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

Второй метод разработки алгоритмов известен как метод подъема. Алгоритм подъема начинается с принятия начального предположения или вычисления начального решения задачи. Затем начинается насколько возможно быстрое движение «вверх» от начального решения по направлению к лучшим решениям. Когда алгоритм достигнет такой точки, из которой больше невозможно двигаться наверх, алгоритм останавливается. К сожалению, мы не можем всегда гарантировать, что окончательное решение, полученное с помощью алгоритма подъема, будет оптимальным. Эта ситуация часто ограничивает применение метода подъема.

Вообще методы подъема являются «грубыми». Они запоминают некоторую цель и стараются сделать все, что могут и где могут, чтобы подойти ближе к цели. Это делает их несколько недальновидными.

Если начальное значение аргумента х равно а, то метод подъема даст устремление к ближайшей цели, т. е. к значению функции в точке х - Ь, тогда как подлинный максимум этой функции находится при х - с. То есть метод подъема в данном примере находит максимум, но не тот. В этом и заключается «грубость» метода подъема.

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

Заключение

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

Список литературы:

1.Конова Е. А., Поллак Г. А. Алгоритмы и программы. Язык С++: Учебное пособие. - 2-е изд., стер. - СПб.: Издательство «Лань», 2017. - 384с.

2.Царев Р.Ю. Алгоритмы и структуры данных: учеб. пособие / Р. Ю. Царев. - Красноярск: Сиб. федер. ун-т, 2013. - 160c.

3.Панос Луридас Алгоритмы для начинающих: теория и практика для разработчика / Панос Луридас; [пер. с англ. Е.М. Егоровой]. - Москва: Эксмо, 2018. - 608с.

4.Рафгарден Тим Совершенный алгоритм. Основы. - СПб.: Питер, 2019. - 256с.

5.Род Стивенс Алгоритмы. Теория и практическое применение / Род Стивенс. – Москва: Издательство «Э», 2016. – 544с.

6.Роберт Седжвик, Кевин Уэйн Алгоритмы на Java, 4-е изд.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2013. – 848с.

7.Томас Х. Кормен Алгоритмы: вводный курс.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2014. – 208с.

8.Трофимов В. В. Основы алгоритмизации и программирования: учебник для СПО / В. В. Трофимов, Т. А. Павловская; под ред. В. В. Трофимова. – М.: Издательство Юрайт, 2019. – 137с.

9.Игошин В. И. Теория алгоритмов: Учеб. пособие. – М.: ИНФРА-М, 2016. – 318с.

10.Семакин И. Г. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И. Г. Семакин, А. П. Шестаков. – 3-е изд., стер. – М.: Издательский центр «Академия», 2012. – 400с.

11.Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования: учеб. пособие. – 3-е изд., испр. и доп. – М: ФОРУМ, 2008. – 432с.

12.Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006. – 416с.