это процесс построения алгоритма решения задачи. Алгоритм и алгоритмизация в информатике

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

Классический подход

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

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

Возможные определения

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

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

Процессы и этапы

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

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

• Какие системы информационной обработки будут эффективными в конкретном случае?
• Каковы математические методики функционирования применительны к крупным системам?

Особенности вопроса

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

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

Как это работает?

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

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

Кому и как?

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

• анализ исходных данных;
• выявление самых значимых аспектов;
• формализацию ключевых моментов;
• представление данных символами;
• формирование цельной последовательности операций.

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

Зачем это нужно?

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

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

Информация и алгоритмы

Представленные в алгоритмической форме сведения – данные, продуцируемые алгоритмизацией. Для них невозможны многозначные интерпретации. Что такое алгоритм в информатике, математике, логике? Это такая последовательность, которую исполнитель может понять, имея перед собой только этот документ и никаких сторонних источников, условий, объяснений операциям. В алгоритме всегда указывается порядок действий. Без этой информации система не может считаться полноценной и применимой на практике.

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

• линейные;
• циклические;
• ветвления;
• смешанные.

А если поподробнее?

Если внимательно изучить основы алгоритмизации, можно найти подробное описание всех типов последовательностей действий. Разберем их детальнее.

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

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

Продолжая тему

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

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

Инструкции и алгоритмы

Фактически с алгоритмизацией, как и с основами информатики, мы сталкиваемся в повседневной жизни, просто привыкли к этому и не замечаем, не обращаем внимание. К примеру, технологические инструкции – это классический образец алгоритма.

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

Алгоритмизация: подход расширенный и специализированный

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

Объект алгоритмизации

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

Ключевое условие, первое, которое проверяется применительно к объекту – присутствие его именно в таком состоянии, которое допускает исполнение предусмотренных алгоритмом функций. В случае если объект не прошел предварительную подготовку, он неисправен, не подходит (словом, любое препятствие), состояние становится неработоспособным, следовательно, действия, предписанные алгоритмом, не могут выполняться.

Алгоритмизация применительно к реальности

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

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

А что с обучением?

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

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

Линейные алгоритмы и алгоритмы с ветвлениями — урок. Информатика, 6 класс.

Линейные алгоритмы

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

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

Например, линейным является следующий алгоритм посадки дерева:

1. Выкопать в земле ямку;
2. Опустить в ямку саженец;
3. Засыпать ямку с саженцем землёй;
4. Полить саженец водой.

С помощью блок-схемы данный алгоритм можно изобразить так:

 

Алгоритмы с ветвлениями

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

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

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

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

 

Логику принятия решения можно описать так: ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2>.

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

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

 

 

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

 

Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?

 

 

Источники:

Босова Л. Л., Босова А. Ю., Информатика: учебник для 6 класса. М. : БИНОМ. Лаборатория знаний, 111 с.

Типы алгоритмов

Что такое алгоритм?

Определение 1

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

Понятие алгоритма появилось еще в IX веке нашей эры и произошло от имени его создателя, известного математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi). Наука, занимающаяся формированием и созданием алгоритмов, называется алгоритмикой.

Классификация алгоритмов

Как правило, основой для классификации алгоритмов является порядок выполнения команд (шагов). На основании данного признака специалисты в данной области выделяют три основных типа алгоритмов:

• Линейные алгоритмы;
• Алгоритмы с разветвлением;
• Циклические алгоритмы.

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

Линейные алгоритмы

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

Простым примером линейного алгоритма может выступить алгоритм утренних действия:

1. Проснуться;
2. Встать с постели;
3. Обуть тапочки;
4. Зайти в ванную;
5. Почистить зубы;
6. Вернуться в комнату;
7. Застелить постель;
8. Одеться;
9. Приготовить завтрак;
10. Позавтракать.

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

Рисунок 1. Линейный алгоритм. Автор24 — интернет-биржа студенческих работ

Для составления линейного алгоритма необходимо:

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

Замечание 1

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

Алгоритмы с разветвлением

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

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

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

1. Есть ли на улице дождь?
2. Если дождь идет, то необходимо надеть плащ.
3. Если дождя нет, холодно на улице?
4. Если холодно, надеть джемпер;
5. Если не холодно, надеть футболку.

Замечание 2

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

Пример записи разветвляющегося алгоритма представлен на рисунке 2.

Рисунок 2. Автор24 — интернет-биржа студенческих работ

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

Для составления разветвляющегося алгоритма необходимо:

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

Стоит отметить, разветвляющиеся алгоритмы могут быть как полными, так и неполными. Пример таких алгоритмов представлен на рисунках 3-4.

Рисунок 3. Алгоритм с полным разветвлением. Автор24 — интернет-биржа студенческих работ

Рисунок 4. Алгоритм с неполным разветвлением. Автор24 — интернет-биржа студенческих работ

Разветвляющие алгоритмы встречаются чаще линейных, но не являются самыми популярными и используемыми в сфере программирования.

Циклические алгоритмы

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

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

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

Пример записи циклического алгоритма представлен на рисунке 5.

Рисунок 5. Циклический алгоритм. Автор24 — интернет-биржа студенческих работ

Для составления циклического алгоритма необходимо:

• Установить, какая из последовательностей операций должна быть в основе цикла;
• Определить вводные данные о количестве повторений тела цикла до начала цикла. Исходя из этих данных, определить какой из видов циклического цикла наиболее целесообразно использовать: цикл с параметром, постусловием или предусловием;
• Установить условие окончания выполнения заданного цикла;
• Установить вводные переменные;
• Записать алгоритм, который отражает ввод данных, вычисление, вывод окончательного результата;
• Протестировать полученный алгоритм на предмет его корректного функционирования.

Учебный алгоритмический язык — Википедия

Материал из Википедии — свободной энциклопедии

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

При изучении информатики в школах для изучения основ алгоритмизации применяется т. н. Русский алгоритмический язык (школьный алгоритмический язык), использующий понятные школьнику слова на русском языке. Алголо-подобный алгоритмический язык с русским синтаксисом был введён в употребление академиком А. П. Ершовым в середине 1980-х годов в качестве основы для «безмашинного» курса информатики. Впервые был опубликован в учебнике «Основы информатики и вычислительной техники» в 1985 г.

[1] Язык также применялся для записи алгоритмов в учебнике А. Г. Кушниренко, Г. В. Лебедева и Р. А. Свореня «Основы информатики и вычислительной техники» для 9-10 классов (1990 г. и последующие переиздания; общий тираж составил 7 млн экземпляров)^[2].

Обычные величины/значения:

• цел – целые числа из диапазона от -32768 до 32767 (2 байта)
• вещ – вещественные числа от -1038 до 1038 (4 байта) Например: 3.14; 0.314е1; 27e-2 = 0.27
• лог – логические переменные (да, нет) (1 байт) (да>нет)
• сим – символьные переменные (‘a’, ‘5’, ‘.’, ‘,’ …) (1 байт)
• лит – литерные (строковые) переменные (‘’, ‘мама мыла раму’) (256 байт)

Для табличных величин к обычным добавляется таб, например:

цел таб 
вещ таб
лог таб
сим таб
лит таб

Описание переменных:

цел а,в,с
вещ х,у

Команда присваивания:

Имя := значение;
Имя := Имя2;
Имя := значение выражения

Виды величин

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

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

алг название алгоритма (аргумент и результат)
   дано условия применимости алгоритма
   надо цель выполнения алгоритма
нач описание промежуточных величин
|  последовательность команд (тело алгоритма)
кон

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

Пример вычисления суммы квадратов:

алг Сумма квадратов (арг цел n, рез цел S)
   дано | n > 0
   надо | S = 1*1 + 2*2 + 3*3 + … + n*n
нач цел i
|  ввод n; S:=0
|  нц для i от 1 до n
|  |  S := S + i * i
|  кц
|  вывод "S = ", S
кон

Для подкрепления теоретического изучения программирования по алгоритмическому языку специалистами мехмата МГУ в 1985 г. был создан редактор-компилятор «Е-практикум» («Е» — в честь Ершова), позволяющий вводить, редактировать и исполнять программы на алгоритмическом языке^[3].

В 1986 г. для «Е-практикума» был выпущен комплект учебных миров (исполнителей): «Робот», «Чертёжник», «Двуног», «Вездеход», которые позволяют просто вводить понятия алгоритма. «Е-практикум» был реализован на компьютерах: Ямаха, Корвет, УКНЦ и получил широкое распространение.

Данный язык программирования постоянно дорабатывался и описание более позднего варианта «Е-практикума» появилось в учебнике 1990 года. Система программирования «КуМир» («Комплект Учебных Миров»), поддерживающая этот учебник, была выпущена в свет предприятием «ИнфоМир» в 1990 году. Язык этой системы также называется «КуМир».

В настоящий момент язык переживает своё второе рождение в связи с разработкой пакета «КуМир» для Windows и Linux. В системе используется несколько исполнителей; основные — это классические «Робот» и «Чертёжник». Пакет включен в дистрибутив ALT Linux Школьный.

Система «КуМир» разработана в НИИСИ РАН по заказу Российской академии наук и распространяется свободно на условиях лицензии GNU GPL 2.0.

В последние несколько лет школьный алгоритмический язык включается как один из предлагаемых в текстах задач ЕГЭ по информатике.

Эффективность алгоритма — Википедия

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

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

Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов^[en], оптимизатор объектного кода^[en], и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».

Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа:

«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»^[1].

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

Современные компьютеры намного быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:

«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании» ^[2]

Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.

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

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

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

Теоретический анализ[править | править код]

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

Некоторые примеры нотации «O» большое:

Обозначение	Название	Примеры
O(1){\displaystyle O(1)\,}	постоянное	Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хеш-функции для выбора элемента.
O(log⁡n){\displaystyle O(\log n)\,}	логарифмическое	Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче.
O(n){\displaystyle O(n)\,}	линейное	Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса.
O(nlog⁡n){\displaystyle O(n\log n)\,}	квазилинейное, логарифмически линейное	Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием
O(n2){\displaystyle O(n^{2})\,}	квадратное	Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками
O(cn),c>1{\displaystyle O(c^{n}),\;c>1}	экспоненциальное	Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора

Проверочные испытания: измерение производительности[править | править код]

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

Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark Collection^[3], а The Computer Language Benchmarks Game^[en] сравнивает производительность реализаций типичных задач в некоторых языках программирования.

(Достаточно легко создать «самодельные» тесты производительности для получения представления об относительной эффективности различных языков программирования, используя набор пользовательских критериев, как это сделал Христофер Коувел-Шах в статье «Nine language Performance roundup»)^[4]

Вопросы реализации[править | править код]

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

Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных, детализация^[en], сборка мусора, параллелизм на уровне команд и вызов подпрограмм^[6].

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

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

Измерения обычно выражаются как функция от размера входа n.

Два наиболее важных измерения:

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

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

• Прямое потребление энергии: энергия, необходимая для работы компьютера.
• Косвенное потребление энергии: энергия, необходимая для охлаждения, освещения, и т. п.

В некоторых случаях нужны другие, менее распространённые измерения:

• Размер передачи: пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие. Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
• Внешняя память: память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
• Время отклика: параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
• Общая стоимость владения: параметр важен, когда предназначен для выполнения одного алгоритма.

Время[править | править код]

Теория[править | править код]

Для анализа алгоритма обычно используется анализ временно́й сложности алгоритма, чтобы оценить время работы как функцию от размера входных данных. Результат обычно выражается в терминах «O» большое. Это полезно для сравнения алгоритмов, особенно в случае обработки большого количества данных. Более детальные оценки нужны для сравнения алгоритмов, когда объём данных мал (хотя такая ситуация вряд ли вызовет проблемы). Алгоритмы, которые включают параллельные вычисления, могут оказаться для анализа более трудными.

Практика[править | править код]

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

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

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

Память[править | править код]

Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма^[en], чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое.

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

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

Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.

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

• Кэш (часто, статическая RAM) — работает на скоростях, сравнимых с ЦПУ
• Основная физическая память (часто, динамическая RAM) — работает чуть медленнее ЦПУ
• Виртуальная память (зачастую, на диске) — даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.

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

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

Критика текущего состояния программирования[править | править код]

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

Мэй утверждает:

В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с N x N до N x log(N) имеет сильный эффект при больших N … Для N=30 миллиарда, эти изменения аналогичны 50 годам технологических улучшений.

• Программист Адам Н. Розербург в своём блоге «The failure of the Digital computer », описал текущее состояние программирования как близкое к «Software event horizon» (уровню программной катастрофы, намек на фантастический «shoe event horizon» (уровень обувной катастрофы), описанный Дугласом Адамсом в его книге «Hitchhiker’s Guide to the Galaxy» (Автостопом по галактике)^[8]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».

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

• Анализ алгоритмов
• Арифметическое кодирование — вид энтропийного кодирования с переменной длиной кода^[en] для эффективного сжатия данных
• Ассоциативный массив — структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA^[en] или массивов Джуди^[en]
• Тест производительности — метод измерения сравнительного времени исполнения в определённых случаях
• Наилучший, наихудший и средний случай^[en] — соглашения по оценке времени выполнения по трём сценариям
• Двоичный поиск — простая и эффективная техника поиска в отсортированном списке
• Таблица ветвления^[en] — техника сокращения длины команд, размера машинного кода, и зачастую, памяти
• Оптимизирующий компилятор — компилятор, использующий различные методы получения более оптимального программного кода при сохранении функциональных возможностей
• Вычислительная сложность математических операций^[en]
• Вычислительная сложность — понятие в информатике, обозначающее зависимости объёма работы от размера входных данных
• Вычислительная мощность компьютера — количественная характеристика скорости выполнения операций на компьютере
• Сжатие данных — сокращение объёма передачи данных и занимаемого дискового пространства
• Индекс — данные, увеличивающие скорость выборки данных из таблиц
• Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности
• Сборка мусора — автоматическое освобождение памяти после использования
• Зелёные информационные технологии^[en] — движение за внедрение «зелёных» технологий, потребляющих меньше ресурсов
• Код Хаффмана — алгоритм эффективного кодирования данных
• Improving Managed code Performance — Microsoft MSDN Library
• Локальность ссылок^[en] — во избежание задержек, вызванных кэшированием из-за нелокального доступа к памяти
• Оптимизация циклов^[en]
• Управление паматью
• Оптимизация (информатика)
• Анализ производительности — методы измерения фактической производительности алгоритма в реальном времени
• Вычисления в реальном времени — пример критичных по времени приложений
• Динамический анализ^[en] — оценка ожидаемого времени работы и расщепляемость алгоритма
• Одновременная многопоточность
• Упреждающее исполнение^[en], когда вычисления проводятся, даже если ещё неизвестно, понадобятся ли их результаты, или немедленное вычисление^[en] как противоположность ленивым вычислениям
• Временна́я многопоточность
• Шитый код — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом)
• Таблица виртуальных методов — механизм поддержки динамического соответствия (или метода позднего связывания)