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

Общие определения

Единого «истинного» определения понятия «алгоритм» нет. Наиболее известные варианты определения опираются на интуитивное понятие «задачи»:

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

Формальные признаки алгоритмов

• Детерминированность : в каждый момент времени следующий шаг работы однозначно определяется состоянием исполнителя. Алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
• Понятность : алгоритм должен включать только команды из заранее оговоренной системы команд исполнителя.
• Завершаемость (конечность): при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
• Массовость : алгоритм должен быть применим к разным наборам исходных данных.

Алгоритмы анализа данных

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

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

Литература

1. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания : Дис. док. физ.-мат. наук: 05-13-17. - Вычислительный центр АН СССР, 1992. - 274 с. (

Алгоритм

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

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

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

История термина

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

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

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

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона . В нём алгорифм (кстати, до революции использовалось написание алгориѳм , через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

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

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

Алгоритм - это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (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 .

Машина Тьюринга

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

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

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

Рекурсивные функции

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

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

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

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

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

Нормальный алгоритм Маркова

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

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

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

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

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

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

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

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

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

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

Другие формализации

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

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

и другие.

Формальные свойства алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

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

P {Q }R

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

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

Время работы

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

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

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

Именно асимптотическая сложность определяет размер задач, которые алгоритм способен обработать. Например, если алгоритм обрабатывает входные данные размером за время cn ², где c - некоторая константа , то говорят, что временная сложность такого алгоритма O (n ²).

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

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

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

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

Наличие исходных данных и некоторого результата

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

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

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

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

Представление алгоритмов

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

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

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

Эффективность алгоритмов

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

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

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

Описан в «Началах» Евклида (примерно 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

См. также

Примечания

1. Kleene 1943 in Davis 1965:274
2. Rosser 1939 in Davis 1965:225
3. (Игошин, с. 317)
4. Basics: The Turing Machine (with an interpreter! . Good Math, Bad Math (9 февраля 2007). Архивировано из первоисточника 2 февраля 2012.
5. (Игошин, раздел 33)
6. Энциклопедия кибернетики , т. 2 , c. 90-91.
7. (Игошин, раздел 34)
8. «Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time.» Henri Cohen A Course in Computational Algebraic Number Theory. - Springer-Verlag, 1996. - P. 2. - ISBN 3-540-55640-0
9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives"t, Clifford Stein . - ISBN 0-262-03293-7
10. (Раздел 12, с. 12-22 в Atallah, 2010)
11. (Игошин, раздел 36)
12. Peter Linz An Introduction to Formal Languages and Automata. - Jones and Bartlett Publishers, 2000. - ISBN 0-7637-1422-4
13. "computability and complexity", Encyclopedia of computer Science and Technology , Facts On File, 2009,

Понятность - алгоритм должен состоять из команд, "понятных" исполнителю (входящих в систему команд исполнителя).

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

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

Pезультативность (или конечность)- алгоpитм должен пpиводить к pешению задачи (или к ответу, что решения нет) за конечное число шагов.

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

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

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

Эти действия называются допустимыми действиями исполнителя. Только их и можно использовать.

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

Сложность алгоритма

Сложность алгоритма позволяет оценить, насколько быстро растет трудоёмкость алгоритма с увеличением объема входных данных. Под трудоемкостью понимается количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Обычно оценка сложности алгоритма представляется в виде O(f(N)), где O – функция сложности, а N – число обрабатываемых наблюдений или примеров. Наименее затратными являются алгоритмы, для которых функция сложности имеет вид f(N)=C и f(N)=C*N, где С – константа. В первом случае вычислительные затраты не зависят от количества обрабатываемых данных, а во втором случае – линейно возрастают. Самыми затратными являются алгоритмы, сложность которых имеет степенную и факториальную зависимости от числа обрабатываемых наблюдений.

СОРТИРОВКА

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.

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

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

МЕТОДЫ ПОИСКА

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

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

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

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

4.1. Определение алгоритма

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

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

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

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

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

Любой алгоритм должен обладать следующими свойствами:

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

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

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

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

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

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

правило начала;

правило непосредственной переработки информации (описание последовательности действий);

правило окончания;

правило извлечения результатов.

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

4.3. Основные способы описания алгоритмов

К основным способам описания алгоритмов можно отнести следующие:

словесно-формульный (пошаговый);

структурный или блок-схемный;

с помощью граф-схем;

с помощью сетей Петри.

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

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

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

Шаг 1. Ввести три числа a ,b ,c .

Шаг 2. Вычислить дискриминант

Шаг 3. Проверить условие: если d <0, то идти на шаг 8, иначе идти на шаг 4.

Шаг 4. Вычислить 1-й корень

Шаг 5. Вычислить 2-й корень

Шаг 6. Вывести два числа x 1 ,x 2 .

Шаг 7. Идти на шаг 9.

Шаг 8. Вывести текст "Уравнение не имеет действительных корней".

Шаг 9. Конец.

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

Функциональная вершина используется для представления функцииf:X →Y .

Предикатная вершина используется для представления функции (или предиката)p :X →(T ,F ), то есть логического выражения, передающего управление по одной из двух возможных ветвей.

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

Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем (рис. 4.1).

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

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

Структурное программирование – процесс разработки алгоритмов с помощью структурных блок-схем.

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

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

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

принцип модульности;

принцип нисходящей разработки программы;

сквозной структурный контроль;

принцип простой структуры программы.

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

Единого «истинного» определения понятия «алгоритм» нет.

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

«Алгоритм - это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

«Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

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

«Алгоритм - строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

«Алгоритм - это последовательность действий, направленных на получение определённого результата за конечное число шагов».

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

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

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

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

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

«Алгоритм - это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».

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

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

1. Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность - определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
3. Понятность - алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
4. Конечность - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
5. Массовость - алгоритм должен быть применим к разным наборам исходных данных.
6. Результативность - завершение алгоритма определёнными результатами.
7. Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
8. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

Основные виды алгоритмов:

1)Прикладные алгоритмы - предназначены для решения определённых прикладных задач.

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

2)Рекурсивные алгоритмы - алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения.

3)Начиная с конца XX - начала XXI века активно разрабатываются параллельные алгоритмы - предназначены для вычислительных машин, способных выполнять несколько операций одновременно.

Способы описания алгоритмов

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

Литература

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс», 2006. - С. 1296.
2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. - 3-е изд. - М.: «Вильямс», 2006. - С. 720.
3. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. - М.: «Вильямс», 2007. - С. 480.