Любой человек ежедневно встречается с множеством повседневных и профессиональных задач. Для решения многих из них существуют определенные правила (инструкции, предписания), объясняющие, как решать определенную задачу. В процессе решения можно применять готовые правила или формулировать собственные. Чем точнее и понятнее описаны правила решения задач, тем быстрее человек овладеет ими и будет эффективнее их применять. Решение многих задач человек передает техническим устройствам – ПК, автоматам, роботам и т. д. Их применение предъявляет очень строгие требования к точности описания правил и последовательности выполнения действий. Поэтому разрабатываются специальные алгоритмы для четкого и строгого описания различных правил.
Алгоритмизация — это раздел информатики, изучающий методы и приемы построений алгоритма, а также их свойства. Она является основным, базовым компонентом компьютерной грамотности в современном компьютерном мире.
Для достижения положительных результатов важную роль играет умение разрабатывать оптимальный алгоритм решения поставленной задачи, что требует от исполнителя наличия определенных навыков алгоритмизации и системного анализа, а также знания математики, физики, химии, экономики и других дисциплин.
Основу деятельности специалиста практически любой области составляет умение ставить задачи, разрабатывать алгоритмы, получать решения, производить анализ полученных данных и делать выводы. Поэтому в своей будущей профессиональной деятельности студенты должны уметь грамотно применять персональный компьютер (ПК) для решения научных и производственных задач.
9.1 Понятия и свойство алгоритмов
Понятие алгоритма. Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда аль-Хорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике. Правила алгебраических преобразований, способы вычислений корней уравнений также можно отнести к математическим алгоритмам.
Существует множество определений алгоритма приведем два из них:
Определение 1. Алгоритм — система формальных правил (команд), однозначно определяющих процесс решения задачи.
Определение 2. Алгоритм — конечная последовательность общепонятных предложений, формально, не требующая проявления человеческой изобретательности, исполнение которой позволяет за конечное время получить решение некоторой задачи из некоторого класса задач.
Алгоритм обладает рядом характерных свойств:
- Наличие ввода и вывода — свойство, заключающееся в наличии исходных данных для решения задачи и формировании алгоритмом одного или нескольких результатов; другими словами, алгоритм должен иметь входные и выходные данные. Перед разработкой алгоритма следует точно, однозначно определить входные и выходные данные: их состав, типы, диапазоны возможных значений.
- Детерминированность (определенность) — свойство, заключающееся в том, что каждое действие, правило алгоритма должно быть точно (однозначно) определено. Для однозначно понимаемой формы записи действий используют языки программирования.
- Конечность — свойство, заключающееся в том, что работа алгоритма должна заканчиваться после выполнения конечного числа действий (шагов, операций). Типичными действиями алгоритма являются ввод данных, обработка данных (вычисление значений, сортировка чисел и др.), вывод (запись) результатов в определенной форме (например, в форме таблицы или графика).
- Массовость — свойство, заключающееся в возможности решения задачи с различными вариантами наборов исходных данных. Наличие этого свойства имеет важное практическое значение, так как обеспечивает возможность получения различных результатов, используя однажды разработанный алгоритм.
- Эффективность — свойство, заключающееся в использовании для алгоритма достаточно простых действий, которые могут быть выполнены точно и за конечный отрезок времени. Алгоритм должен быть «хорошим» с точки зрения некоторых критериев: продолжительность работы, требуемый объем памяти и др. Для этого в процессе разработки должен выполняться анализ алгоритмов.
9.2 Представление алгоритма
Для представления алгоритмов могут использоваться различные формы:
• словесное описание,
• словесно — формульное описание,
• блок-схема (схема программы, схема данных и другие),
• запись на языке программирования,
• запись в системе команд ЭВМ и другие.
Не все перечисленные формы представления строго соответствуют вышеприведенному определению, однако они находят практическое применение.
В процессе представления алгоритмов в общем случае выполняется переход от одной формы представления к другой в вышеуказанном порядке.
Словесное описание — представление алгоритма с помощью литературного или профессионального языка. Такое описание используется для изложения общей идеи, метода решения задачи. Это может быть инструкция по обработке документов, технология подготовки отчетов и тому подобные документы, в которых излагается последовательность действий, понятных исполнителю. Например, расчет бухгалтером почасовой заработной платы может быть описан следующим образом:
• получить табели учета рабочего времени сотрудников из подразделений,
• проверить правильность данных (количество часов, отработанных каждым сотрудником, не должно превышать количества рабочих часов в текущем месяце и др.),
• умножить тарифную ставку сотрудника (рублей/час) на количество отработанных часов,
• добавить начисления на зарплату (надбавки за руководство подразделением, премиальные и др.),
• вычесть удержания из заработной платы (подоходный налог, отчисления в пенсионный фонд, выплаты на погашение ссуды и др.),
• вычислить суммы по подразделениям, по предприятию,
• оформить ведомости на выдачу заработной платы по установленной форме.
Словесно-формульное описание алгоритма отличается от вышеприведенного словесного описания тем, что в нем используются математические формулы.
Блок-схема алгоритма — представление алгоритма в графической форме, в которой действия над данными изображаются в виде геометрических блоков с поясняющими надписями, а последовательность действий указывается соединительными линиями. Эта форма используется для наглядного представления процессов обработки данных, особенно в случаях с большим количеством проверок логических условий и разветвлений процессов (выбора последующих действий в зависимости от результатов предыдущих). Блок-схемы имеют несколько разновидностей. Государственный стандарт (ГОСТ) 19.701 устанавливает следующие виды графических программных документов:
• схема программ,
• схема данных,
• схема взаимодействия программ,
• схема работы системы,
• схема ресурсов системы
Программа на алгоритмическом языке — запись алгоритма с использо¬ванием операторов выбранного языка программирования. Текст программы, написанной на языке высокого уровня, понятен человеку (программисту). После преобразования этого текста в программу, состоящую из команд ЭВМ, можно выполнить решение задачи по разработанному алгоритму на ЭВМ. Для составления программ на каком-либо языке программирования следует изучить этот язык (алфавит, операторы), приемы использования для решения типовых задач.
Для изображения блок схемы используются следующие графические блоки
| Символ | Наименование | Действия |
| Данные | Символ отображает данные, носитель не определен | |
| Запоминаю-щее устройство с прямым доступом | Символ отображает данные, хранящиеся в запоминающем устройстве с прямым доступом (магнитный диск, гибкий магнитный диск | |
Документ | Символ отображает данные, представленные на носителе в удобочитаемой форме (маши-нограмма, документ для оптического или магнитного считывания, микрофильм, рулон ленты с итоговыми данными, бланки ввода данных) | |
| Ручной ввод | Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключа-тели) | |
| Дисплей | Символ отображает данные, представленные в читаемой фо-рме на носителе в виде ото-бражающего устройства (экран для вязального наблюдения, индикаторы вывода информа-ции) | |
| Процесс | Символ отображает функции об-работки данных любого вида (выполнение определенной опе-рации или группы операций, приводящее к изменению зна-чения, формы или размещения информации | |
| Предопределенный процесс | Символ отображает предопреде-ленный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле) | |
| Решение | Символ отображает решение или функцию переключательно-го типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован пос-ле вычисления условий, опре-деленных внутри этого символа. Соответствующие результаты вычисления могут быть запи-саны по соседству с линиями, отображающими эти пути | |
| Границы цикла | Символ, состоящий из двух час-тей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т. д. помещаются внутри символа в начале или в конце в зависимо-сти от расположения операции, проверяющей условие | |
| Терминатор | Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных) |
9.3 Линейные алгоритмы
В зависимости от состава операций и последовательности выполняемых действий алгоритмы принято разделять на:
• линейные,
• разветвляющиеся,
• циклические.
Основным элементарным действием в вычислительных алгоритмах является присваивание значения переменной величине. Если значение константы определено видом ее записи, то переменная величина получает конкретное значение только в результате присваивания. Присваивание может осуществляться двумя способами: с помощью команды присваивания и с помощью команды ввода.
Рассмотрим как пример правила деления обыкновенных дробей и опишем их так:
- Числитель первой дроби умножить на знаменатель второй дроби.
- Знаменатель первой дроби умножить на числитель второй дроби.
- Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2.
В алгебраической форме это выглядит следующим образом:
Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные a, b, c, d. Результатом — также целые величины m и n.
Формат команды присваивания следующий:
переменная:=выражение
Знак «:=» нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, выполняемые компьютером:
- Вычисляется выражение.
- Полученное значение присваивается переменной.
В приведенном выше алгоритме присутствуют две команды присваивания. В блок-схемах команда присваивания записывается в прямоугольнике. Такой блок называется вычислительным блоком.
В описаниях алгоритмов необязательно соблюдать строгие правила в записи выражений. Их можно писать в обычной математической форме. Это еще не язык программирования со строгим синтаксисом.
В приведенном алгоритме присутствует команда ввода:
ввод a,b,c,d
В блок-схеме команда ввода записывается в параллелограмме — блоке ввода-вывода. При выполнении данной команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать на клавишу ввода Enter. Значения следует вводить в том же порядке, в каком соответствующие переменные расположены в списке ввода. Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточных и конечных величин.
Полученные компьютером результаты решения задачи должны быть сообщены пользователю. Для этих целей предназначена команда вывода:
вывод m,n
С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу.
Поскольку присваивание является важнейшей операцией в вычислительных алгоритмах, обсудим ее более подробно.
Рассмотрим последовательное выполнение четырех команд присваивания, в которых участвуют две переменные величины а и b.
В приведенной ниже таблице напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения.
| Команда | a | b |
| a:=1 | 1 | — |
| b := 2 * а | 1 | 2 |
| а:=b | 2 | 2 |
| b:=а + b | 2 | 4 |
Этот пример иллюстрирует три основных свойства команды присваивания:
• пока переменной не присвоено значение, она остается неопределенной;
• значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной;
• новое значение, присваиваемое переменной, заменяет ее предыдущее значение.
Рассмотрим один очень полезный алгоритм, который приходится часто использовать при программировании. Даны две величины: X и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х= 1, Y= 2, то после обмена должно стать: Х= 2, Y= 1.
Хорошей моделью для решения этой задачи является следующая ситуация: имеются два стакана — один с молоком, другой с водой. Требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей:
- перелить из первого стакана в третий;
- перелить из второго в первый;
- перелить из третьего во второй.
Цель достигнута!
По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача обмена решается последовательным выполнением трех команд присваивания:
| Команда | X | Y | Z |
| Ввод X; Y | 1 | 2 | — |
| Z:=Х | 1 | 2 | 1 |
| Х:=Y | 2 | 2 | 1 |
| Y:=Z | 2 | 1 | 1 |
Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания (Х:= Y) переменная, стоящая справа (Y), сохраняет свое значение.
Алгоритм для деления дробей имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам.
И так в линейных алгоритмах для получения результата решения задачи все запланированные действия должны быть последовательно выполнены по одному разу; при этом заданная последовательность действий не изменяется в зависимости от исходных и промежуточных данных.
Оставить комментарий