Алгоритм в информатике - виды, структура и свойства

Особенности понятия

Алгоритмы появились вместе с математикой, а первые упоминания о них встречаются в книге математика Мухаммеда бен Мусы аль-Хорезми из города Хорезма. Он описал методы выполнения различных действий с многозначными числами еще в 825 году. Само слово «алгоритм» появилось после того, как книгу ученого перевели на латинский язык в Египте.

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

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

Свойства и виды

Для изучения понятия нужно разобраться в свойствах алгоритма в информатике. Их существует несколько:

• дискретность;
• детерминированность или определенность;
• понятность;
• завершаемость или конечность;
• массовость или универсальность;
• результативность.

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

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

Универсальность или массовость позволяет использовать алгоритм с разными наборами начальных данных. Последнее свойство обеспечивает его завершение в виде определенного числа — результата.

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

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

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

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

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

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

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

Способы записи

Алгоритмы записываются несколькими методами. В информатике используется всего три:

• словесно-формульный;
• графический;
• программный.

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

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

• прямоугольники;
• эллипсы;
• ромбы;
• шестиугольники;
• стрелки;
• пунктирные линии;
• соединительные фигуры.

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

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

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

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

Правила создания

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

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

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

• сначала нужно взять число 1;
• проверить, меньше ли оно, чем 100;
• если да, то узнать, простое ли оно;
• при выполнении условия записать;
• перейти к числу 2;
• повторить операцию.

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

Анализ работы

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

Гипотеза Ричарда Мейса утверждает, что избежать ошибок легче, чем их устранить. Благодаря доказательству корректности программ можно выявить их свойства, применяемые ко всем видам входных данных. Само понятие делится на две разновидности — частичную и полную. При первом типе корректности алгоритм дает правильный результат только для тех случаев, когда он завершается. Во втором случае программа завершает работу корректно для всего диапазона данных.

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

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