Как найти свойство алгоритма - Сайт, где вы сможете решить свои вопросы

Алгори́тм (лат. 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].

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

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

Имея описание программы для машины Тьюринга, требуется определить, завершит ли работу программа за конечное время или будет работать бесконечно, получив некоторые входные данные.^[20]

Доказательство неразрешимости проблемы остановки важно тем, что к ней можно свести другие задачи. Например, простую проблему остановки можно свести к задаче остановки на пустой строке (когда нужно определить для заданной машины Тьюринга, остановится ли она, будучи запущенной на пустой строке), доказав тем самым неразрешимость последней.^[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)	Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину	Вычисление xⁿ; Двоичный поиск в массиве из n элементов
O(n)	Линейный рост — удвоение размера задачи удвоит и необходимое время	Сложение/вычитание чисел из n цифр; Линейный поиск в массиве из n элементов
O(n log n)	Линеаритмичный рост — удвоение размера задачи увеличит необходимое время чуть более, чем вдвое	Сортировка слиянием или кучей n элементов; нижняя граница сортировки сопоставлением n элементов
O(n²)	Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза	Элементарные алгоритмы сортировки
O(n³)	Кубичный рост — удвоение размера задачи увеличивает необходимое время в восемь раз	Обычное умножение матриц
O(cⁿ)	Экспоненциальный рост — увеличение размера задачи на 1 приводит к c-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат	Некоторые задачи коммивояжёра, алгоритмы поиска полным перебором

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Иллюстрация выполнения алгоритма Евклида для вычисления НОД чисел 1599 и 650.

НОД чисел 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

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

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

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

↑ АЛГОРИ́ТМ : [арх. 30 октября 2018] / А. Л. Семёнов // А — Анкетирование. — М. : Большая российская энциклопедия, 2005. — С. 426. — (Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов ; 2004—2017, т. 1). — ISBN 5-85270-329-X.
↑ Kleene 1943 in Davis 1965: 274
↑ Rosser 1939 in Davis 1965: 225
↑ Кнут, 2006, 1.1. Алгоритмы.
↑ Robert Andrew Wilson, Frank C. Keil. The MIT Encyclopedia of the Cognitive Sciences. — MIT Press, 2001. — С. 11. — 1106 с. — ISBN 9780262731447. Архивная копия от 17 ноября 2021 на Wayback Machine
↑ (Игошин, с. 317)
↑ В. А. Успенский: «Математика — это гуманитарная наука» // Троицкий вариант. — 2014. — 28 января (№ 2(146)). — С. 4—6. Архивировано 27 ноября 2018 года.
↑ Basics: The Turing Machine (with an interpreter!). Good Math, Bad Math (9 февраля 2007). Архивировано 11 февраля 2012 года.
↑ (Игошин, раздел 33)
↑ Энциклопедия кибернетики, т. 2, c. 90—91.
↑ (Игошин, раздел 34)
↑ ¹ ² «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.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives’t, Clifford Stein. Introduction to Algorithms (англ.). — 2-е. — MIT Press, 2001. — P. 531. — ISBN 0-262-03293-7.
↑ (Раздел 12, с. 12—22 в Atallah, 2010)
↑ Dina Goldin, Peter Wegner. The origins of the Turing Thesis Myth, CS-04-14, October 2004
↑ Interactive Computation Is More Powerful Than Non Interactive. Архивировано 19 ноября 2015 года., c2.com
↑ М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982, C. 155.
↑ (Игошин, раздел 36)
↑ ¹ ² ³ Peter Linz. An Introduction to Formal Languages and Automata (англ.). — Jones and Bartlett Publishers (англ.) (рус., 2000. — ISBN 0-7637-1422-4.
↑ computability and complexity, Encyclopedia of computer Science and Technology, Facts On File, 2009, ISBN 978-0-8160-6382-6.
↑ (O’Regan, раздел 4.5)
↑ (раздел 5.3.6 в Enders, 2003)
↑ (раздел 5.3.7 в Enders, 2003)
↑ (O’Regan, с. 119)
↑ А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов = The Design and Analysis of Computer Algorithms. — М.: «Мир», 1979.
↑ (раздел 11 в Atallah, 2010)
↑ (раздел 1 в Atallah, 2010)
↑ Knuth D. The Art of Computer Programming, Volume 2: Seminumerical Algorithms (англ.). — 3rd. — Addison–Wesley, 1997. — ISBN 0201896842.

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

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = 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.

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

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

Источник

Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки

Код ОГЭ: 1.3.1. Алгоритм, свойства алгоритмов, способы записи алгоритмов.
Блок-схемы. Представление о программировании

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

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

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

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

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

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

Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:

Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

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

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

Словесная запись алгоритма

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

■ Пример 1. Записать в словесной форме правило деления обыкновенных дробей.

Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.

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

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

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

Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).

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

■ Пример 2. Исполнитель Крот имеет следующую систему команд:

вперед k — продвижение на указанное число шагов вперед;
поворот s — поворот на s градусов по часовой стрелке;
повторить m [команда1 … командаN] — повторить m раз серию указанных команд.

Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?

Повторить 5 [вперед 10 поворот 72]

Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.

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

■ Пример 3. В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).

Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).

Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

Блок–схема

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

Основные элементы блок–схемы алгоритма:

Общий вид блок–схемы алгоритма:

■ Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.

Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.

Решение.

Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».
Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».
Вычисляется результат выполнения алгоритма: X := 0, Y := 1.

Ответ: X := 0, Y := 1.

Алгоритмические языки

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

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

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

Псевдокод

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

Служебные слова учебного алгоритмического языка:

Стандартная структура алгоритма

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

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

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

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

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

Примеры заголовков алгоритмов:

В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.

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

На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.

Описание величин и действия над ними

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

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

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

В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.

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

Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).

Значение — то, чему равна переменная в конкретный момент. Значение переменной можно задать двумя способами: присваиванием и с помощью процедуры ввода.

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

Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10^-2 и –7,123456*10²).

Над числовыми данными можно выполнять арифметические операции и операции сравнения.

Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.

Литерный тип представляет собой символы и строки, он дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов. Эти последовательности заключаются в двойные кавычки: «результат», «sum_price». В качестве символов могут быть использованы буквы, цифры, знаки препинания, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). В учебном алгоритмическом языке литерные величины обозначаются лит.

Над литерными величинами возможны операции сравнения и слияния. Сравнение литерных величин производится в соответствии с их упорядочением: «a» < «b», «b» < «с» и т. д. Слияние (конкатенация) литерных величин приводит к образованию новой величины: «пол» + «е» образует «поле».

Логический тип определяет логические переменные, которые могут принимать только два значения — истина (True) или ложь (False). Над логическими величинами можно выполнять все стандартные логические операции.

Команды учебного алгоритмического языка

Учебный алгоритмический язык использует следующие команды для реализации алгоритма:

ОПЕРАЦИЯ ПРИСВАИВАНИЯ

Ко всем типам величин может быть применена операция присваивания, которая обозначается знаком «:=» и служит для вычисления выражения, стоящего справа, и присваивания его значения переменной, указанной слева. Например, если переменная H имела значение 12, а переменная М — значение 3, то после выполнения оператора присваивания H := М + 10 значение переменной H изменится и станет равным 13.

Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).

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

ВВОД И ВЫВОД ДАННЫХ

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

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

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

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

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

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

Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:

Путь 200 м

Тот же результат был бы получен, если бы изменить строку вывода на

вывод «Путь «, v * t, » м»

Конспект по информатике «Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки».

Вернуться к Списку конспектов по информатике.

Источник

Кто же ты такой, алгоритм?

Время на прочтение
11 мин

Количество просмотров 8.9K

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

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

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

Бесконечность не предел

Но перед этим немного вспомним математику. Из школьного курса математики мы знаем, что чисел существует бесконечно много — какое бы большое число мы не взяли, всегда можно прибавить единицу и получить число еще большее. Обычно в школе этим и ограничиваются. В университете на курсе высшей математики нам расскажут, что бесконечности на самом деле бывают разные: множества, элементы которого можно пронумеровать натуральными числами считаются счётно-бесконечными. К таким множествам относят сами натуральные числа (числу 1 мы дадим номер один, числу 2 номер два и т.д.), целые числа – натуральные плюс ноль и отрицательные целые числа (первый номер отдаем нулю, второй – числу 1, третий – числу -1, то есть каждой положительное число k получает номер 2k, а каждое отрицательное число -m получает номер 2m + 1). К счетно-бесконечным множествам относят четные, нечетные и даже рациональные числа (числа представимые в виде несократимой дроби m/n, где m – целое, n – натуральное). Получается, что натуральных чисел ровно столько же, сколько четных, и, в то же время, ровно столько же, сколько целых. «Количество» (мощность) множества натуральных чисел обозначается символом ℵ₀ (алеф-ноль).

Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.

Про бесконечные дроби

Не стоит делать ошибку, записывая в иррациональные числа все бесконечные дроби. Иррациональными являются только те числа, которые нельзя представить в виде несократимой дроби вида m/n. В десятичной системе счисления дроби 1/3 и 2/7 тоже окажутся бесконечными, однако их «бесконечность“ обусловлена выбранной системой счисления. В системе счисления по основанию 21 эти дроби будут иметь конечное представление, а вот, например, дробь 1/2 окажется бесконечной (периодической).

Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ℵ₁(алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).

На сколько велика бесконечность?

Допустим в наш алфавит вошли все придуманные на земле символы: русский алфавит, японские иероглифы, шумерская клинопись и т.д. Тогда в наше множество войдут все написанные когда-либо книги, все книги, которые будут написаны и все книги, которые никто не стал бы писать (например, хаотичные последовательности символов). Кроме того, представим книгу, толщиной в Солнечную систему и диагональю листа равной диаметру Млечного Пути, набранную 12-м шрифтом. В наше придуманное множество войдут все такие книги, отличающиеся хотя бы одним символов, и не только они, ведь вселенная бесконечна! Кто мешает представить себе книгу, размером в миллиарды световых лет? А все такие книги? Уже на этом этапе воображение может давать сбои, а ведь наше множество всего лишь счетное. Чтобы дополнить множество до континуума, нужно рассмотреть бесконечную книгу, по сравнению с которой, предыдущие книги — детские игрушки. Но и одной бесконечной книги нам не хватит, нужно рассмотреть все бесконечные книги.

Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам «тревожной лампочкой»: осторожно, выход за пределы конструктивного.

Алгоритмы и вычислимость

Суть работы компьютера заключается в проведении некоторого вычисления — преобразования одной порции информации в другую порцию. Причем результатом работы не обязательно должно быть число, главное, чтобы информация была представлена в некоторой объективной форме. Обычно под такой формой имеют в виду конечные цепочки символов некоторого алфавита. Получается, компьютерное вычисление есть некоторая функция в сугубо математическом смысле, с областью определения и значений в рассмотренном выше множестве A*. Именно тут возникают определенные проблемы. Если мы можем вычислить функцию, то можем записать промежуточные вычисления в виде текста. Более того, в виде тексте можно описать вообще правила вычисления. Мы знаем, что множество всех текстов счетное. Однако выясняется, что множество всех функций над натуральными числами имеет мощность континуум. Если мы пронумеруем все тексты, то получается функций вида A* -> A* тоже континуум. Получается, что некоторые функции вычислимы, а некоторые нет.

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

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

Частично-рекурсивные функции и тезис Черча

Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.

Курт Гедель наиболее известен тем, что сформулировал и доказал 2 теоремы о неполноте. Между прочим, сделал он это в возрасте всего лишь 24 лет.

Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к «натуральным функция» путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово «частичные» показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:

Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.

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

Ученые долго не могли привести пример частично-рекурсивной функции, не являющейся примитивно-рекурсивной (без оператора минимизации). Наконец это удалось Вильгельму Аккерману. Предложенная функция Аккермана растет так быстро, что количество цифр в десятичной записи числа A(4,4) превосходит количество атомов во Вселенной.

Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое «конструктивное преобразование». Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:

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

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

С помощью такого незамысловатого автомата можно формализовать любой алгоритм.

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

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

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

Обязательные свойства

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

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

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

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

«Винегрет» из свойств из того же учебника по информатике.

Необязательные свойства

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

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

Про зависающие программы

Программы, которые не могут зациклиться, на самом деле входят в класс примитивно-рекурсивных — подмножество частично-рекурсивного класса. Отличает их отсутствия оператора минимизации. Он то и вносит пикантности. Если вы используете «неарифметический цикл» while или рекурсию, для которых нельзя заранее определить, сколько раз они выполняться, то ваша программа сразу переходит из класса примитивно-рекурсивных в класс частично-рекурсивных.

Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на «последовательности действий», а на обмене сообщениями между абстрактными объектами.

Заключение

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

Материал данной статьи во многом опирается на 1-ый том «Программирование: введение в профессию» А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В «От Диофанта до Тьюринга» и трехтомник А. Шеня по математической логике и теории алгоритмов.

Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.

Источник

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

Понятие алгоритма

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

Слово “алгоритм” произошло от имени
среднеазиатского математика Мухамеда
из Хорезма (по-арабски – Аль Хорезми (IX
в)) и использовалось в математике для
обозначения правил выполнения четырех
арифметических действий: сложения,
умножения, вычитания и деления.

Мухаммед Аль
Хорезми подробно объясняет правила
действия с числами, записанными в
десятично-позиционной системе счисления,
и исследует квадратные уравнения. Слова
“алгебра” и “алгоритм” впервые
появились в переводе его трактатов.
Первое из них означало операцию переноса
членов из одной части уравнения в другую,
а второе – искаженное имя автора – Аль
Хорезми – Algorithmi.
Оно применялось первоначально для
обозначения правил вычисления в
десятичной позиционной системе счисления.

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

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

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

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

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

Исполнителя характеризуют:

Среда;
Система команд;
Отказы.

Среда (обстановка) – это “место
обитания” исполнителя. Например,
среда ТР.

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

Отказы исполнителя возникают, если
команда вызывается при недопустимом
для нее состоянии среды.

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

Результативность. Алгоритм имеет
некоторое число входных величин –
аргументов, задаваемых до начала работы.
Цель выполнения алгоритма – получение
результата (результатов), имеющего
вполне определенное отношение к исходным
данным. Можно сказать, что алгоритм
указывает последовательность действий
по преобразованию исходных данных в
результаты.
Массовость. Для алгоритма можно
брать различные наборы данных, т.е.
использовать один и тот же алгоритм
для решения целого класса однотипных
задач. Вместе с тем существуют алгоритмы,
которые применимы только к единственному
набору исходных данных. Например, для
алгоритма пользования автоматическим
турникетом при входе в метро существует
единственный вариант исходного данного
– жетон. Поэтому понятие массовости
требует уточнения. Можно считать, что
каждого алгоритма существует свой
класс объектов, допустимых в качестве
исходных данных. Тогда свойство
массовости означает, применимость
алгоритма ко всем объектам этого класса.
А количество объектов класса (конечное
или бесконечное) – свойство самого
класса исходных данных.
Понятность. Чтобы алгоритм можно
было выполнить, он должен быть понятен
исполнителю. Понятность алгоритма
означает знание исполнителя алгоритма
о том, что надо делать для его
исполнения.

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

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

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

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

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

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

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

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

Построение такого формального определения
было начато с формализации объектов
(операндов) алгоритма, т.к. в интуитивном
понятии алгоритма его объекты могут
иметь произвольную природу. Ими могут
быть, например, числа, показания счетчиков,
фиксирующих параметры некоторого
процесса и т.п. Однако, полагая, что
алгоритм имеет дело не с самими реальными
объектами, а их образами, можно считать,
что операнды алгоритма есть слова
в произвольном алфавите. Тогда получается,
что алгоритм преобразует слова в
произвольном алфавите в слова того же
алфавита. Дальнейшая формализация
понятия алгоритма связана с формализацией
действий над операндами и порядка этих
действий. Одна из таких формализаций
была предложена в 1936 г. английским
математиком А. Тьюрингом, который
формально описал конструкцию некоторой
абстрактной машины (машины Тьюринга)
как исполнителя алгоритма и высказал
основной тезис о том, что всякий алгоритм
может быть реализован соответствующей
машиной Тьюринга. Примерно в это же
время американским математиком Э. Постом
была предложена другая формальная
алгоритмическая схема – машина Поста,
а в 1954 г. советским математиком А.А.
Марковым была разработана теория класса
алгоритмов, названных им нормальными
алгоритмами, и высказан основной
тезис о том, что всякий алгоритм
нормализуем.

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

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

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

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

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

Источник

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

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

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

Кто пользуется алгоритмами

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

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

Для чего нужны алгоритмы

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

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

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

Алгоритмы применяются во всех направлениях IT и во многих других отраслях. Инструкции для автоматизированного станка или линии производства — алгоритмы, рецепт блюда — тоже.

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

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

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

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

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

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

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

Какими бывают алгоритмы

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

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

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

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

Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

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

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

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

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

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

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

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

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

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

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

O(1) означает, что алгоритм выполняется за фиксированное константное время. Это самые эффективные алгоритмы.
O(n) — это сложность линейных алгоритмов. n здесь и дальше обозначает размер входных данных: чем больше n, тем дольше выполняется алгоритм.
O(n²) тоже означает, что чем больше n, тем выше сложность. Но зависимость тут не линейная, а квадратичная, то есть скорость возрастает намного быстрее. Это неэффективные алгоритмы, например с вложенными циклами.
O(log n) — более эффективный алгоритм. Скорость его выполнения рассчитывается логарифмически, то есть зависит от логарифма n.
O(√n) — алгоритм, скорость которого зависит от квадратного корня из n. Он менее эффективен, чем логарифмический, но эффективнее линейного.

Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими степенями. Их сложность растет очень быстро, и их лучше не использовать.

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

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

Использование алгоритмов в IT

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

Разработка ПО и сайтов. Алгоритмы используются для парсинга, то есть «разбора» структур с данными, таких как JSON. Парсинг — одна из базовых задач, например в вебе. Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений, настройке поведения приложения и многом другом.

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

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

Поисковые задачи. Алгоритмы поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые системы вроде Google или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки

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

Словесная запись алгоритма

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

Блок–схема

Алгоритмические языки

Псевдокод

Стандартная структура алгоритма

Описание величин и действия над ними

Команды учебного алгоритмического языка

ОПЕРАЦИЯ ПРИСВАИВАНИЯ

ВВОД И ВЫВОД ДАННЫХ

Кто же ты такой, алгоритм?

Бесконечность не предел

Алгоритмы и вычислимость

Частично-рекурсивные функции и тезис Черча

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

Обязательные свойства

Необязательные свойства

Заключение

Понятие алгоритма

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

Кто пользуется алгоритмами

Для чего нужны алгоритмы

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

Какими бывают алгоритмы

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

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

Использование алгоритмов в IT

Вам также может понравиться

Как найти вещество х в схеме превращений

Как найти места для копа металлолома

Как найти терминальную стоимость

Добавить комментарий Отменить ответ

Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки