Что такое последовательность инструкций

Материал из «Знание.Вики»

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

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

Термин «алгоритм» происходит от имени арабского учёного Мухаммеда аль-Хорезми (около 780—850 годов), который жил и работал на территории современного Узбекистана и Ирана. Аль-Хорезми был известным математиком и астрономом, и его основное достижение заключалось в разработке новой системы записи и вычисления чисел, известной как индийская цифровая система.

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

Термин «алгоритм» стал широко использоваться в математике и науке в последующие века. В XVII веке появилось понятие алгоритма как последовательности команд, выполняемых для решения математической задачи или получения определённого результата. Считается, что основоположником современной теории алгоритмов является математик Готфрид Лейбниц, который в 1684 году предложил идею символьного исчисления и разработал методы для выполнения вычислений с помощью языка символов. С тех пор понятие алгоритма распространилось на различные области науки и техники, и сейчас используется в широком смысле, охватывая различные методы и процедуры решения задач.

Вплоть до 1930-х годов большинство алгоритмов было разработано в рамках конкретных областей, таких как математика, физика или инженерия. Однако с развитием вычислительной техники и информатики возникла необходимость в строгом математическом определении понятия алгоритма. В 1936 году Алан Тьюринг опубликовал свою работу «Вычислимые числа: машины и интуиция», где он предложил формальное определение алгоритма. В своей работе он вводит понятие «универсальной вычислительной машины», которая может исполнять любой алгоритм. Эта работа стала основой для развития теории алгоритмов и компьютерных наук в целом. Тьюринг показал, что существуют задачи, для которых не существует алгоритма, который бы решал их во всех случаях. Это привело к формированию понятия вычислительной неразрешимости и развитию теории сложности вычислений. Таким образом, с появлением формального определения алгоритма появилась возможность точно определять, является ли тот или иной процесс алгоритмом^[2].

В 1950-е годы XX века работы Колмогорова и Маркова принесли значительный вклад в развитие теории алгоритмов. Андрей Колмогоров в своих работах предложил формализацию идеи алгоритма с помощью понятия «колмогоровской сложности» — меры сложности объектов, определяемой длиной наименьшего программного кода, позволяющего их описать. Это понятие имеет важное значение в теории информации и алгоритмической сложности^[3]. Андрей Марков разработал свою модель вычислений, которая стала известна как модель «машин Маркова». Эта модель позволила формально описывать алгоритмические процессы и решать различные задачи, связанные с последовательностями и автоматами.

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

Определение

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

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

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

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

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

Свойства алгоритма могут включать следующие аспекты:

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

2. Однозначность: каждый шаг алгоритма должен быть определён и ясно понятен.

3. Дискретность: алгоритм — состоит из отдельных маленьких шагов, или действий. Эти действия идут в определённом порядке, одно начинается после завершения другого^[5].

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

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

6. Детерминированность: инструкции должны быть чётко определены и не должно возникать разночтений и разногласий ни на одном из этапов выполнения алгоритма^[5].

7. Результативность: завершение алгоритма приводит к определённым результатам.

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

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

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

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

• Линейный алгоритм — это алгоритм, который выполняет каждое действие по очереди и без пропусков. Линейный алгоритм последовательно выполняет инструкции без перехода к другим частям программы, пока не достигнет конца. Такие алгоритмы разработаны для простых и последовательных задач, где каждое действие зависит от предыдущего и не требуется сложной логики или принятия решений.
• Циклический алгоритм — это алгоритм, который выполняется в цикле до выполнения какого-то условия, являются основой для многих программ и позволяют повторять операции множество раз без необходимости повторного написания кода. Циклические алгоритмы используются для обработки повторяющихся задач или для выполнения итераций по коллекциям данных. Циклические алгоритмы могут также использоваться для обхода коллекций данных, таких как массивы или списки. В этом случае цикл выполняется для каждого элемента коллекции.
• Разветвляющийся алгоритм — это алгоритм, в котором происходит ветвление на несколько направлений выполнения в зависимости от условий. Он позволяет программе принимать решения на основе различных ситуаций и выполнять соответствующие действия^[6].
• Блок-схема — это графическое представление последовательности операций или шагов в алгоритме или процессе. Она состоит из блоков, которые представляют операции, принятия решений или ввод-вывод данных, и связей между блоками, обозначающих последовательность выполнения^[7].
• Графы и деревья — алгоритмы для работы с графами и деревьями, включающие поиск пути между вершинами, обходы графов и деревьев, поиск минимального остовного дерева и т. д.
• Вспомогательный алгоритм — это алгоритм, который используется внутри другого алгоритма для выполнения определённой подзадачи или облегчения выполнения основной задачи. Он может выполнять различные операции и иметь разные цели, в зависимости от контекста, в котором используется. Например, вспомогательный алгоритм может выполнять сортировку данных перед их обработкой другим алгоритмом, вычислять промежуточные значения или проверять определённые условия. Вспомогательные алгоритмы часто используются для разделения сложных задач на более простые подзадачи, что упрощает понимание и реализацию основного алгоритма. Они также позволяют повторно использовать код и ускорить выполнение основного алгоритма, освобождая его от необходимости выполнять одни и те же операции несколько раз^[8].
• Рекурсивный алгоритм — это алгоритм, вызывающий себя до тех пор, пока не будет достигнуто некоторое условие возращения.

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

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

1. Словесная форма: алгоритм описывается в виде последовательности шагов на естественном языке, где каждый шаг описывает конкретное действие или операцию. Это наиболее распространённый и понятный способ представления алгоритма.

2. Язык программирования — формальный язык, который используется программистами для написания программ компьютерных приложений. Язык программирования определяет набор правил и синтаксис для создания кода, который затем может быть скомпилирован или интерпретирован на компьютере. Примеры популярных языков программирования включают C, C++, Java, Python, JavaScript, Ruby и многие другие. Каждый язык имеет свои особенности и применяется для решения определённых задач в различных областях разработки программного обеспечения^[9].

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

4. Блок-схема: алгоритм представляется в виде графического обозначения, где каждый блок представляет отдельный шаг, а стрелки указывают на последовательность выполнения шагов. Это визуальный способ представления алгоритма, который позволяет наглядно представить его структуру. Блок-схемы часто используются для более наглядного представления сложных алгоритмов или для обучения программированию^[8].

Примечания

О том, что такое алгоритмы и как они влияют на нашу жизнь.

Картинка с сайта: 1gai.ru

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

1. Алгоритм – это набор конкретных инструкций

Картинка с сайта: 1gai.ru

^{istockphoto.com}

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

Как испечь пирог, найти значение суммы 2+2 или управлять страной в соответствии с Конституцией – все это алгоритмы. Но чаще всего это слово связывают со сферой IT. В этом случае под «алгоритмом» понимается «последовательность инструкций, которые говорят компьютеру, что делать».

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

«Компьютерные алгоритмы должны быть предельно точны. Для их определения могут потребоваться миллионы строк», – подчеркивает профессор.  

2. Люди писали и использовали алгоритмы задолго до появления компьютеров

Картинка с сайта: 1gai.ru

 ^Pixel

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

«Все потому, что для выполнения алгоритма не всегда нужен компьютер – им могут управлять сами люди», – утверждает Домингос.

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

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

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

3. Сегодня алгоритмы повсюду

Картинка с сайта: 1gai.ru

^pixabay.com

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

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

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

«Совершенно очевидно, что каждый раз, когда вы пользуетесь компьютером или Интернетом, вы имеете дело с алгоритмами, – подчеркнул Домингос. – В наши дни они задействованы практически во всем».

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

Картинка с сайта: 1gai.ru

^pixabay.com

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

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

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

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

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

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

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

«Это возможность создавать мощные сложные алгоритмы с минимальным вмешательством человека», – подчеркивает Домингос.

5. Алгоритмы – это не волшебство

Картинка с сайта: 1gai.ru

^Pixel

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

Картинка с сайта: 1gai.ru

^Pixel

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

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

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

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

6. Алгоритмы по-прежнему способны изменить мир

Картинка с сайта: 1gai.ru

^unsplash.com

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

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

^{Обложка: 1Gai.Ru / istockphoto.com}

^{Источник статьи: What is an algorithm, anyway?}

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

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

С какими значениями можно связать слово «алгоритм»:

— цикл;

— метод (способ);

— процесс;

— рецепт;

— инструкция.

Немного истории

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

Впервые термин Algorithm был широко озвучен в средние века — это произошло, когда ученые Европы узнали о методах вычислений, используемых математиком из Азии Мухаммедом аль-Хорезми. Как раз от его имени и образовалось слово «Алгоритм».

Картинка с сайта: otus.ru

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

Картинка с сайта: otus.ru

Еще несколько терминов

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

— человека;

— механизма;

— компьютера;

— роботизированного устройства;

— языка программирования и т. п.

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

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

Картинка с сайта: otus.ru

Подробнее о способах читайте здесь, а о блок-схемах — тут.

Основные свойства

Основные свойства следующие:

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

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

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

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

5. Формальность. «Приказы не обсуждают, а выполняют» — говорит директор. Так и разработчик алгоритма — он формирует задачу исполнителю, к примеру, компьютеру, которому не важен смысл, — он просто выполняет соответствующие команды (задания) и получает результат. Зачем и почему — не его вопросы.

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

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

Сегодня алгоритмов существует огромное множество. Если говорить вкратце, то можно выделить три основные группы:

— линейные;

— разветвляющиеся;

— циклические (они же циклы).

Следует рассмотреть эти группы подробнее, начиная с линейного алгоритма.

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

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

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

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

Пример цикла на блок-схеме:

Картинка с сайта: otus.ru

Источники:

• https://urok.1sept.ru/articles/631785;  
• https://www.sites.google.com/site/algoritmyvidyisvojstva/materialy/sposoby-opisania-vidy-algoritmov;
• https://math-it.petrsu.ru/users/semenova/Informatika/DOC/Sam_Izuch/Algoritm.pdf.