Точная инструкция определяющая процесс достижения поставленной цели за конечное число шагов

Вопросы
для подготовки к экзамену по дисциплине
«Информатика»

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

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

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

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

Основными свойствами алгоритмов
являются:

1. Универсальность (массовость)
— применимость алгоритма к различным
наборам исходных данных.

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

3. Однозначность — правила и порядок
выполнения действий алгоритма имеют
единственное толкование.

4. Конечность — каждое из действий и
весь алгоритм в целом обязательно
завершаются.

5. Результативность — по завершении
выполнения алгоритма обязательно
получается конечный результат.

6. Выполнимость — результата алгоритма
достигается за конечное число шагов.

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

Выделяют три крупных класса алгоритмов:

— вычислительные алгоритмы, работающие
со сравнительно простыми видами данных,
такими как числа и матрицы, хотя сам
процесс вычисления может быть долгим
и сложным;

— информационные алгоритмы,
представляющие собой набор сравнительно
простых процедур, работающих с большими
объемами информации (алгоритмы баз
данных);

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

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

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

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

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

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

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

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

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

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

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

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Экзаменационные вопросы

1. Понятие алгоритма, его свойства.

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

Свойства:

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

1. Способы записи алгоритмов. Блок-схемы алгоритмов.

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

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

Блок-схема

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

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

Порядок выполнения действий указываются стрелками

Написание алгоритмов с помощью блок-схем (графически) регламентируются ГОСТом (ГОСТ 19.701-90, ГОСТ 19.002-80, ГОСТ 19.003-80)

Основные условные обозначения

Возможности:

• Наглядно отобразить базовые конструкции алгоритма
• Сосредоточить внимание на структуре алгоритма, а не на синтаксисе языка
• Анализировать логическую структуру алгоритма
• Преобразовывать алгоритм методом укрупнения (сведения к единому блоку) или детализации – разбиения на ряд блоков;
• Использовать принцип блочности при коллективном решении сложной задачи;
• Осуществить быструю проверку разработанного алгоритма (на уровне идеи);

1. Основные алгоритмические структуры.

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

• следование,
• ветвление,
• повторение.

Следование

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

Ветвление

Базовая структура «ветвление». Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма.

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

• если — то — иначе;
• если — то;
• выбор;
• выбор — иначе.

Выбор

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

Повторение

Цикл – это многократное повторение некоторой совокупности действий, которая называется телом цикла.

Циклы:

• С предусловием («пока» или «while»)

Цикл «пока» — определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла

1. Здесь Действие называют телом цикла.
2. Цикл работает до тех пор, пока условие ИСТИННО; как только условие становится ложным, цикл заканчивает работу. В частности, этот цикл может не выполниться ни разу, если при первой же проверке условие ложно.
3. В теле цикла обязательно должно быть действие, которое влияет на изменение условия. В противном случае может произойти «зацикливание» (бесконечный цикл).

• С постусловием («до» или «do… «while»)

Цикл «до» — повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле

1. Здесь Действие называют телом цикла.

1. Цикл работает до тех пор, пока условие ЛОЖНО; как только условие становится истинным, цикл заканчивает работу. Этот цикл выполняется как минимум один раз, так как условие стоит после тела цикла.
2. В теле цикла обязательно должно быть действие, которое влияет на изменение условия. В противном случае может произойти «зацикливание» (бесконечный цикл).

• С параметром («для» или «for»)

Цикл с заданным числом повторений (счетный цикл) – повторение некоторых действий указанное число раз

1. Здесь переменную i называют счетчиком цикла, n1 – начальное значение счетчика, n2 – конечное значение счетчика.

1. Переменная i последовательно принимает все значения от n1 до n2, автоматически увеличиваясь на h – шаг цикла.
2. Действие цикла заканчивается, как только i становится больше n2.
3. Этот цикл используют в задачах, в которых заранее известно количество повторений.

1. Понятие языка программирования. Уровни и поколения языков программирования. Парадигмы программирования.

Язык программирования — формализованный язык, предназначенный для описания программ и алгоритмов решения задач на ЭВМ.

Парадигма — способ организации программы, принцип ее построения. Наиболее распространенными являются процедурная и объектно-ориентированная парадигмы.
Они различаются способом декомпозиции, положенным в основу при создании программы.

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

Объектно-ориентированная декомпозиция предполагает разбиение предметной области на объекты и реализацию этих объектов и их взаимосвязей в виде программы.

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

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

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

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

Основные характеристиками программы являются:

1. Алгоритмическая сложность

2. Состав и глубина проработки реализации функции обработки

3. Полнота и системность функций обработки

4. Объем файлов программ

5. требования ОС и техническим средствам обработки со стороны программного средства

6. Объем диска памяти

7. Размер операционной системы для запуска программы

8. Тип процессора

9. Время ОС

Основные этапы решения задач на ЭВМ:

1. Постановка задачи
2. Определение методов решения
3. Составление алгоритмов
4. Написание программ для ЭВМ
5. Отладка программ на ЭВМ
6. Получение результатов на ЭВМ

1. Программы трансляторы: компиляторы, интерпретаторы.

Транслятор — программа или техническое средство, выполняющее трансляцию программы

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

Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом.

Выходной язык называется целевым языком или объектным кодом.

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

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

Процесс компиляции, как правило, состоит из нескольких этапов:

• лексический анализ;
• синтаксический анализ;
• семантический анализ;
• создание на основе результатов анализов промежуточного кода;
• оптимизация промежуточного кода;
• создание объектного кода, в данном случае машинного.

Достоинства:

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

Недостатки:

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

Интерпретатор – это программа, предназначенная для построчных трансляции и выполнения исходной программы. Такой процесс называется интерпретацией.

Интерпретатор может работать двумя способами:

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

Достоинства:

• Интерпретатор сообщает о найденных им ошибках после трансляции каждой строки программы. Это облегчает процесс поиска и исправления ошибок в программе.

Недостатки:

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

Динамическая или JIT компиляция

Динамическая или JIT компиляция — трансляция, при которой исходный или промежуточный код преобразуется в машинный код непосредственно во время исполнения, «на лету».

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

Достоинства динамической компиляции по сравнению с компиляцией:

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

1. Общая характеристика платформы .NET Framework. Компоненты. Архитектура.

Платформа .NET Framework — это управляемая среда выполнения для ОС Windows, предоставляющая разнообразные службы запускаемым в ней приложениям.

Она состоит из двух основных компонентов:

• среды CLR (Common Language Runtime) — механизма, управляющего выполняющимися приложениями,
• библиотеки классов .NET Framework (Framework Class Library) — библиотеки проверенного кода, предназначенного для повторного использования, который разработчики могут вызывать из своих приложений.

1. Общеязыковая среда выполнения (Common Language Runtime, CLR), ее назначение, функции.

Общеязыковая среда выполнения (Common Language Runtime, CLR) — это исполняющая среда, которая подходит для различных языков программирования.

К функциям CLR относятся:

• двухшаговая компиляция: преобразование программы, написанной на одном из языков программирования в управляемый код на промежуточном языке (Microsoft Intermediate Language, MSIL, или просто IL), а затем преобразование IL-кода в машинный код конкретного процессора, который выполняется с помощью виртуальной машины или JIT-компилятора (Just In Time compiler — компилирование точно к нужному моменту);
• управление кодом: загрузка и выполнение уже готового IL-кода с помощью JIT-компилятора, доступ к метаданным с целью проверки безопасности кода;
• управление памятью при размещении объектов с помощью сборщика мусора (Garbage Collector);
• обработка исключений и исключительных ситуаций, включая межъязыковые исключения;
• осуществление взаимодействия между управляемым кодом (код, созданный для СLR) и неуправляемым кодом;
• поддержка сервисов для разработки разнотипных приложений.
• Компилятор в качестве результата своего выполнения создаёт так называемую сборку – файл с расширением exe или dll, который содержит код на языке IL и метаданные.

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

Программа на этом языке выполняется под управлением системы CLR.

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

CLR вызывает JIT-компилятор, переводящий код с языка IL в машинные команды конкретного процессора, которые немедленно выполняются.

1. Библиотеки классов .NET. Понятие «framework».

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

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

Над этим слоем находится набор классов, позволяющий работать с базами данных и XML.

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

Библиотека классов вместе с CLR образуют каркас (framework), то есть основу платформы.

1. Понятия приложения, проекта, решения.

Приложения (прикладное программное обеспечение) – это программы для обработки информации без использования программирования.

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

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

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

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

Дискретность

Разделение выполнения решения задачи на отдельные операции.

Определенность

Каждая команда алгоритма должна однозначно определять действия исполнителя.

Результативность

Завершение работы алгоритма за конечное число шагов.

Массовость

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

Понятность

Одержание допустимого набора команд, понятного конкретному исполнителю.

Виды алгоритмов

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

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);

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

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

Эвристическийалгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания.

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

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

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

Цикл программы– последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

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

На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

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

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

Порядок выполнения алгоритма:

1.

Действия в алгоритме выполняются в порядке их записи;

2.

Нельзя менять местами никакие два действия алгоритма;

3.

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

Для записи алгоритмов используются специальные языки:

1.

Естественный язык (словесная запись);

2.

Формулы;

3.

Структурограммы;

4.

Синтаксические диаграммы;

5.

Графический (язык блок-схем).

Естественный язык:
если условие то действие 1 иначе действие 2

Структурограмма:

Синтаксическая диаграмма:

Графический язык:

Составление алгоритмов графическим способом подчиняется двум ГОСТам:

1. ГОСТ 19.002-80, соответствует международному стандарту ИСО 2636-73. Регламентирует правила составления блок-схем.

2. ГОСТ 19.003-80, соответствует международному стандарту ИСО 1028-73. Регламентирует использование графических примитивов.

Алгори́тм (лат. algorithmi — от имени среднеазиатского математика Аль-Хорезми^[1]) — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.

Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но тем не менее имеет место исключение (нормальный алгорифм Маркова).

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

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

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

Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений^[2] или «эффективного метода»^[3]; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга.

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

Современное формальное определение вычислительного алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени персидского (хорезмского и мавераннахрского) учёного аль-Хорезми. Около 825 года он написал сочинение Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»), из оригинального названия которого происходит слово «алгебра» (аль-джебр — восполнение). В этой книге впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные.

В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском») — таким образом, латинизированное имя среднеазиатского учёного было вынесено в заглавие книги. Сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому переводу. В течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр, и все они имели в названии слово algoritmi или algorismi.

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XIII века, написанной в стихах, читаем:

Алгоризм был придуман в Греции.

Это часть арифметики.
Придуман он был мастером по имени Алгоризм,
который дал ему своё имя.
И поскольку его звали Алгоризм,

Он назвал свою книгу «Алгоризм».

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). А в популярной средневековой поэме «Роман о Розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Встречался также вариант написания имени Аргус (Argus). И хотя, согласно древнегреческой мифологии, корабль «Арго» был построен Ясоном, именно этому Арго приписывалось строительство корабля.

«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счётного искусства. И в уже упоминавшейся «Романе о розе», и в известной итальянской поэме «Цветок», написанной Дуранте, имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Английский поэт Джефри Чосер в поэме «Книга герцогини» (1369 г.) пишет, что даже «славный счётчик Аргус» (noble countour Argu) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.

Однако со временем такие объяснения всё менее занимали математиков, и слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Именно в таком значении оно вошло во многие европейские языки. Например, с пометкой «устар.» оно присутствует в представительном словаре английского языка Webster’s New World Dictionary, изданном в 1957 г. Энциклопедический словарь Брокгауза и Ефрона предлагает такую трактовку: алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень».

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и абацистов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик Николя Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).

Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат Carmen de Algorismo (латинское carmen и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (Georg Peurbach, 1423—1461) Opus algorismi jocundissimi («Веселейшее сочинение по алгоритму»).

Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем (Nicolaus Oresme, 1323/25-1382) написал математический трактат Algorismus proportionum («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть Algorithmus linealis, то есть правила счёта на линиях.

Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.

В 1684 году Готфрид Лейбниц в сочинении Nova Methodvs pro maximis et minimis, itemque tangentibus… впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747 г.), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» (De usu novi algorithmi in problemate Pelliano solvendo). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

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

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

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой советской энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в следующих изданиях БСЭ.

Алгоритмы становились предметом всё более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой советской энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров.
Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии» (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на ЭВМ».

За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живёт, обогащаясь всё новыми значениями и смысловыми оттенками.

Определения алгоритма[править | править код]

Свойства алгоритмов[править | править код]

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

• Дискретность — алгоритм должен представлять процесс решения задачи как упорядоченное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
• Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.
• Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
• Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. Дональд Кнут процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, называет методом вычисления (англ. computational method)^[4]. Однако довольно часто определение алгоритма не включает завершаемость за конечное время^[5]. В этом случае алгоритм (метод вычисления) определяет частичную функцию^[en]. Для вероятностных алгоритмов завершаемость как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
• Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.
• Результативность — завершение алгоритма определёнными результатами.

Формальное определение[править | править код]

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

Первые попытки уточнения понятия алгоритма и его исследования осуществляли в первой половине XX века Алан Тьюринг, Эмиль Пост, Жак Эрбран, Курт Гедель, А. А. Марков, Алонзо Чёрч. Было разработано несколько определений понятия алгоритма, но впоследствии было выяснено, что все они определяют одно и то же понятие (см. Тезис Чёрча — Тьюринга)^[6]

Российский математик, основоположник структурной лингвистики в Советском Союзе В. А. Успенский считал, что понятие алгоритма впервые появилось у Эмиля Бореля в 1912 году, в статье об определённом интеграле. Там он написал о «вычислениях, которые можно реально осуществить», подчеркивая при этом: «Я намеренно оставляю в стороне большую или меньшую практическую деятельность; суть здесь та, что каждая из этих операций осуществима в конечное время при помощи достоверного и недвусмысленного метода»^[7].

Машина Тьюринга[править | править код]

Основная идея, лежащая в основе машины Тьюринга, очень проста. Машина Тьюринга — это абстрактная машина (автомат), работающая с лентой отдельных ячеек, в которых записаны символы. Машина также имеет головку для записи и чтения символов из ячеек, которая может двигаться вдоль ленты. На каждом шаге машина считывает символ из ячейки, на которую указывает головка, и, на основе считанного символа и внутреннего состояния, делает следующий шаг. При этом машина может изменить своё состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку вправо или влево.^[8]

На основе исследования этих машин был выдвинут тезис Тьюринга (основная гипотеза алгоритмов):

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

Рекурсивные функции[править | править код]

С каждым алгоритмом можно сопоставить функцию, которую он вычисляет. Однако возникает вопрос, можно ли произвольной функции сопоставить машину Тьюринга, а если нет, то для каких функций существует алгоритм? Исследования этих вопросов привели к созданию в 1930-х годах теории рекурсивных функций^[9].

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

Подобно тезису Тьюринга в теории вычислимых функций была выдвинута гипотеза, которая называется тезис Чёрча:

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

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

Нормальный алгоритм (алгорифм) Маркова[править | править код]

Нормальный алгоритм (алгорифм в авторском написании) Маркова — это система последовательных применений подстановок, которые реализуют определённые процедуры получения новых слов из базовых, построенных из символов некоторого алфавита. Как и машина Тьюринга, нормальные алгоритмы не выполняют самих вычислений: они лишь выполняют преобразование слов путём замены букв по заданным правилам^[10].

Нормально вычислимой называют функцию, которую можно реализовать нормальным алгоритмом. То есть алгоритмом, который каждое слово из множества допустимых данных функции превращает в её начальные значения^[11]..

Создатель теории нормальных алгоритмов А. А. Марков выдвинул гипотезу, которая получила название принцип нормализации Маркова:

Подобно тезисам Тьюринга и Черча, принцип нормализации Маркова не может быть доказан математическими средствами.

Стохастические алгоритмы[править | править код]

Однако приведённое выше формальное определение алгоритма в некоторых случаях может быть слишком строгим. Иногда возникает потребность в использовании случайных величин^[12]. Алгоритм, работа которого определяется не только исходными данными, но и значениями, полученными из генератора случайных чисел, называют стохастическим (или рандомизированным, от англ. randomized algorithm)^[13]. Стохастические алгоритмы часто бывают эффективнее детерминированных, а в отдельных случаях — единственным способом решить задачу^[12].

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

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

Некоторые исследователи допускают возможность того, что стохастический алгоритм даст с некоторой заранее известной вероятностью неправильный результат. Тогда стохастические алгоритмы можно разделить на два типа^[14]:

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

Другие формализации[править | править код]

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

• многоленточная и недетерминированная машины Тьюринга;
• регистровая и РАМ-машина — прототип современных компьютеров и виртуальных машин;
• конечные и клеточные автоматы

Виды алгоритмов[править | править код]

Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей её решения. Следует подчеркнуть принципиальную разницу между алгоритмами вычислительного характера, преобразующими некоторые входные данные в выходные (именно их формализацией являются упомянутые выше машины Тьюринга, Поста, РАМ, нормальные алгорифмы Маркова и рекурсивные функции), и интерактивными алгоритмами (уже у Тьюринга встречается C-машина, от англ. choice — выбор, ожидающая внешнего воздействия, в отличие от классической A-машины, где все начальные данные заданы до начала вычисления и выходные данные недоступны до окончания вычисления). Последние предназначены для взаимодействия с некоторым объектом управления и призваны обеспечить корректную выдачу управляющих воздействий в зависимости от складывающейся ситуации, отражаемой поступающими от объекта управления сигналами^[15][16]. В некоторых случаях алгоритм управления вообще не предусматривает окончания работы (например, поддерживает бесконечный цикл ожидания событий, на которые выдается соответствующая реакция), несмотря на это, являясь полностью правильным.

Можно также выделить алгоритмы:

• Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т. п.) — задают определённые действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.
• Гибкие алгоритмы, например, стохастические, то есть вероятностные и эвристические.
• Вероятностный (стохастический) алгоритм даёт программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
• Эвристический алгоритм (от греческого слова «эврика») — алгоритм, использующий различные разумные соображения без строгих обоснований^[17].
• Линейный алгоритм — набор команд (указаний), выполняемых последовательно во времени друг за другом.
• Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого может осуществляться разделение на несколько альтернативных ветвей алгоритма.
• Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций). К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно.
• Вспомогательный (подчинённый) алгоритм (процедура) — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
• Структурная блок-схема, граф-схема алгоритма — графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, так как зрительное восприятие обычно облегчает процесс написания программы, её корректировки при возможных ошибках, осмысливание процесса обработки информации. Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему — набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации».

Нумерация алгоритмов[править | править код]

Нумерация алгоритмов играет важную роль в их исследовании и анализе^[18].
Поскольку любой алгоритм можно задать в виде конечного слова (представить в виде конечной последовательности символов некоторого алфавита), а множество всех конечных слов в конечном алфавите счётное, то множество всех алгоритмов также счётное. Это означает существование взаимно однозначного отображения между множеством натуральных чисел и множеством алгоритмов, то есть возможность присвоить каждому алгоритму номер.

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

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

Алгоритмически неразрешимые задачи[править | править код]

Формализация понятия алгоритма позволила исследовать существование задач, для которых не существует алгоритмов поиска решений. Впоследствии была доказана невозможность алгоритмического вычисления решений ряда задач, что делает невозможным их решение на любом вычислительном устройстве.
Функцию называют вычислимой (англ. computable), если существует машина Тьюринга, которая вычисляет значение для всех элементов множества определения функции. Если такой машины не существует, функцию называют невычислимой. Функция будет считаться невычислимой, даже если существуют машины Тьюринга, способные вычислить значение для подмножества из всего множества входных данных^[19].

Случай, когда результатом вычисления функции является логическое выражение «истина» или «ложь» (или множество {0, 1}), называют задачей, которая может быть решаемой или нерешаемой, в зависимости от вычислимости функции ^[19].

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

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

Доказательство неразрешимости проблемы остановки важно тем, что к ней можно свести другие задачи. Например, простую проблему остановки можно свести к задаче остановки на пустой строке (когда нужно определить для заданной машины Тьюринга, остановится ли она, будучи запущенной на пустой строке), доказав тем самым неразрешимость последней.^[19].

Анализ алгоритмов[править | править код]

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

Использование математического аппарата для анализа алгоритмов и их реализаций называют формальными методами. Формальные методы предусматривают применение формальных спецификаций и, обычно, набора инструментов для синтаксического анализа и доказательства свойств спецификаций. Абстрагирование от деталей реализации позволяет установить свойства системы независимо от её реализации. Кроме того, точность и однозначность математических утверждений позволяет избежать многозначности и неточности естественных языков^[21].

По гипотезе Ричарда Мейса, «избежание ошибок лучше устранения ошибок»^[22]. По гипотезе Хоара, «доказательство программ решает проблему корректности, документации и совместимости»^[23]. Доказательство корректности программ позволяет выявлять их свойства по отношению ко всему диапазону входных данных. Для этого понятие корректности было разделено на два типа:

• Частичная корректность — программа даёт правильный результат для тех случаев, когда она завершается.
• Полная корректность — программа завершает работу и выдаёт правильный результат для всех элементов из диапазона входных данных.

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

{P}Q{S}

где P — это предусловия, должные выполняться перед запуском программы Q, а S — постусловия, истинные после завершения работы программы.

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

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

Распространённым критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объёма входных данных.^[25]

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

Время, которое тратит алгоритм как функция от размера задачи , называют временной сложностью этого алгоритма T(n). Асимптотику поведения этой функции при увеличении размера задачи называют асимптотичной временной сложностью, а для её обозначения используют нотацию «O» большое. Например, если алгоритм обрабатывает входные данные размером за время cn², где c — некоторая константа, то говорят, что временная сложность такого алгоритма O(n²).

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

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

Грубо говоря, анализ средней асимптотической временной сложности можно разделить на два типа: аналитический и статистический. Аналитический метод даёт более точные результаты, но сложен в использовании на практике. Зато статистический метод позволяет быстрее осуществлять анализ сложных задач^[26].

В следующей таблице приведены распространённые асимптотические сложности с комментариями^[27].

Сложность	Комментарий	Примеры
O(1)	Устойчивое время работы не зависит от размера задачи	Ожидаемое время поиска в хеш-таблице
O(log log n)	Очень медленный рост необходимого времени	Ожидаемое время работы интерполирующего поиска n элементов
O(log n)	Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину	Вычисление xn; Двоичный поиск в массиве из n элементов
O(n)	Линейный рост — удвоение размера задачи удвоит и необходимое время	Сложение/вычитание чисел из n цифр; Линейный поиск в массиве из n элементов
O(n log n)	Линеаритмичный рост — удвоение размера задачи увеличит необходимое время чуть более, чем вдвое	Сортировка слиянием или кучей n элементов; нижняя граница сортировки сопоставлением n элементов
O(n²)	Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза	Элементарные алгоритмы сортировки
O(n³)	Кубичный рост — удвоение размера задачи увеличивает необходимое время в восемь раз	Обычное умножение матриц
O(cn)	Экспоненциальный рост — увеличение размера задачи на 1 приводит к c-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат	Некоторые задачи коммивояжёра, алгоритмы поиска полным перебором

Наличие исходных данных и некоторого результата[править | править код]

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

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

Для разработки алгоритмов и программ используется алгоритмизация — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.

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

Представление алгоритмов[править | править код]

Формы записи алгоритма:

• словесная или вербальная: на естественном языке;
• на алгоритмическом языке: языке программирования или псевдокоде;
• в машинном коде (код процессора ЭВМ);
• в математической нотации (см. выше представленные варианты);
• схематическая:
  • графическая (например, блок-схемы и ДРАКОН-схемы);
  • структурограммы (диаграммы Насси-Шнейдермана).

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

Эффективность алгоритмов[править | править код]

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

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач информатики, начиная с 1940-х годов в связи с этим простроен ряд более эффективных в асимптотическом смысле алгоритмов для традиционных задач (например, алгоритмы быстрого умножения^[en], алгоритм Чудновского для вычисления числа ).

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

Алгоритм Евклида — эффективный метод вычисления наибольшего общего делителя (НОД). Назван в честь греческого математика Евклида; один из древнейших алгоритмов, который используют до сих пор^[28].

Описан в «Началах» Евклида (примерно 300 лет до н. э.), а именно в книгах VII и X. В седьмой книге описан алгоритм для целых чисел, а в десятой — для длин отрезков.

Существует несколько вариантов алгоритма, ниже записанный в псевдокоде рекурсивный вариант:

алг нод(a, b)
нач
    если b = 0
       возврат a
    иначе
       возврат нод(b, a mod b)
кон

НОД чисел 1599 и 650:

Шаг 1	1599 = 650*2 + 299
Шаг 2	650 = 299*2 + 52
Шаг 3	299 = 52*5 + 39
Шаг 4	52 = 39*1 + 13
Шаг 5	39 = 13*3 + 0

См. также[править | править код]

• Метаалгоритм
• Аукцион алгоритмов
• Список алгоритмов
• Теория алгоритмов

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

Литература[править | править код]

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms, Third Edition. — 3-е. — М.: «Вильямс», 2013. — 1328 с. — ISBN 978-5-8459-1794-2.
• Дональд Кнут. Искусство программирования = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд.. — М.: «Вильямс», 2006. — Т. 1. Основные алгоритмы. — С. 720. — ISBN 0-201-89683-4.
• Томас Х. Кормен. Алгоритмы: вводный курс = Algorithms Unlocked. — М.: «Вильямс», 2014. — 208 с. — ISBN 978-5-8459-1868-0.
• Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стер.. — М.: ИЦ «Академия», 2008. — 448 с. — ISBN 5-7695-1363-2.

Ссылки[править | править код]

• «Слово „алгоритм“: происхождение и развитие», В. В. Шилов, Журнал «Потенциал» — источник исторических сведений.
• Об алгоритме (недоступная ссылка — история). в энциклопедии «Кругосвет»

Тема 7. Алгоритмизация и программирование

1.    Основные свойства
и способы записи алгоритмов.

2.    История развития ЯП.
Этапы развития языков программирования. Классификация ЯП.

 1.       Основные
свойства и способы записи алгоритмов.

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

Основными свойствами
алгоритмов являются:

1. Универсальность (массовость) — применимость
алгоритма к различным наборам исходных данных.

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

3. Однозначность — правила и порядок
выполнения действий алгоритма имеют единственное толкование.

4. Конечность — каждое из действий и весь алгоритм в целом
обязательно завершаются.

5. Результативность — по завершении
выполнения алгоритма обязательно получается конечный результат.

6. Выполнимость — результата
алгоритма достигается за конечное число шагов.

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

Выделяют три крупных класса алгоритмов:

—
вычислительные алгоритмы, работающие со сравнительно простыми видами
данных, такими как числа и матрицы, хотя сам процесс вычисления может быть
долгим и сложным;

—
информационные алгоритмы, представляющие собой набор сравнительно простых
процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

Алгоритм может быть записан различными
способами:

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

Формальное описание — на формализованном языке, например на языке программирования. 

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

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

Основные элементы
блок-схем:

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

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

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

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

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

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

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

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

Графическое изображение

Разветвляющийся алгоритм

Разветвляющийся
алгоритм — последовательность выполнения шагов алгоритма изменяется в
зависимости от некоторых условий. Осуществляется выбор одного из
двух/нескольких возможных вариантов. Словесно эта конструкция записывается так:

ЕСЛИ условие
справедливо, ТО выполнить действия 1,

ИНАЧЕ выполнить действия
2.

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

Если есть «действия 1»
и «действия 2», то говорят о полной альтернативе

                                     

Полная
альтернатива                                     неполная
альтернатива

Графическое
изображение разветвленного алгоритма

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

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

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

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

Известно, что первым
программистом была женщина — леди Ада Лавлейс, дочь лорда Байрона. Она
разрабатывала программы для одного из первых механических компьютеров,
созданного в начале прошлого века английским ученым Чарльзом Беббиджом. Однако
настоящее программирование в современном понимании началось с момента создания
первой электронной вычислительной машины. Но тем не менее, имя
этой замечательной женщины — Ada — присвоено одному из самых мощных современных ЯП, который является
базовым для министерства обороны США.

2.   История развития ЯП. Этапы развития
языков программирования. Классификация ЯП.

 Первые ЭВМ,
созданные человеком, имели небольшой набор команд и встроенных типов данных, но
позволяли выполнять программы на машинном языке. Машинный язык (МЯ) —
единственный язык, понятный ЭВМ. Он реализуется аппаратно: каждую команду
выполняет некоторое электронное устройство. Программа на МЯ представляет собой
последовательность команд и данных, заданных в цифровом виде. Например, команда
вида 1А12 в 16-ричном виде или 0001101000010010 в двоичном виде
означает операцию сложения (1А) содержимого регистров 1 и 2.

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

           
Стремление программистов оперировать не цифрами, а символами, привело к
созданию мнемонического языка программирования, который называют ассемблером,
мнемокодом, автокодом. Этот язык имеет определенный синтаксис записи
программ, в котором, в частности, цифровой код операции заменен мнемоническим
кодом. Например, команда сложения записывается в виде AR 1,2 и означает сложение (Addition) типа регистр-регистр (Register) для регистров 1 и 2. Теперь
программа имеет более удобночитаемую форму, но ее не понимает ЭВМ. Поэтому
понадобилось создать специальную программу транслятор, который
преобразует программу с языка ассемблера на МЯ. Эта проблема потребовала, в
свою очередь, глубоких научных исследований и разработки различных теорий,
например теорию формальных языков, которые легли в основу создания
трансляторов. Практически любой класс ЭВМ имеет свой язык ассемблера. На
сегодняшний день язык ассемблера используется для создания системных программ,
использующих специфические аппаратные возможности данного класса ЭВМ.

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

Принципиальными отличиями ЯВУ от языков низкого
уровня являются:

·      использование
переменных;

·      возможность
записи сложных выражений;

·      расширяемость
типов данных за счет конструирования новых типов из базовых;

·      расширяемость
набора операций за счет подключения библиотек подпрограмм;

·      слабая
зависимость от типа ЭВМ.

С усложнением ЯП
усложняются и трансляторы для них. Теперь в набор инструментов программиста,
кроме транслятора, входит текстовый редактор для ввода текста программ,
отладчик для устранения ошибок, библиотекарь для создания библиотек программных
модулей и множество других служебных программ. Все вместе это называется системой
программирования. Наиболее яркими представителями ЯВУ являются FORTRAN, PL/1, Pascal, C, Basic, Ada.

Может возникнуть
вопрос: почему создано столько различных языков одного класса? Почему нельзя
создать один язык на все случаи жизни? Ответ на этот вопрос может быть таким
же, как и на вопрос о различных языках народов мира: так уж получилось. Каждый
из разработчиков ЯВУ стремился создать самый лучший и самый универсальный язык,
который позволял бы быстро получать самые эффективные, надежные и безошибочные
программы. Однако в процессе этого поиска выяснилось, что дело не в самом
языке, а в технологии его использования. Поэтому дальнейшее развитие языков
стало определяться новыми технологиями программирования.

Одновременно с
развитием универсальных ЯВУ стали развиваться проблемно-ориентированные ЯП,
которые решали экономические задачи (COBOL), задачи реального времени (Modula-2, Ada), символьной обработки (Snobol), моделирования (GPSS, Simula, SmallTalk), численно-аналитические задачи (Analitic) и другие. Эти специализированные языки
позволяли более адекватно описывать объекты и явления реального мира, приближая
язык программирования к языку специалиста в проблемной области.

Другим направлением
развития ЯП является создание языков сверхвысокого уровня (ЯСВУ).

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

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

К непроцедурным языкам
относят и языки запросов систем управления базами данных (QBE, SQL).