XVII Международная студенческая научная конференция Студенческий научный форум - 2025

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

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

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

Такими свойствами являются:

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

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

3. Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

4. Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. То есть алгоритм применяется к некоторому классу входных данных (чисел, пар чисел, набору букв и тому подобному [1] .

В 20-х г. 20 века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Первые работы по уточнению понятия алгоритма и его изучению, то есть теории алгоритмов, были выполнены в 1936-1937 годах математиками А. Тьюрингом, Э. Постом, Ж. Эрбраном, А. Черчем, А.А. Марковым. Попытки этих исследователей дать четкое математическое определение алгоритма в конечном итоге были сведены к трем основным типам универсальных алгоритмических моделей.

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

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

Третий тип алгоритмических моделей - это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (подслова) другим словом. Пример моделей этого типа - нормальные алгоритмы Маркова [2].

Нормальные алгоритмы Маркова - это расширение понятия обычных алгоритмов Маркова, введенное Андреем Андреевичем Марковым в начале 20 века. Термин "нормальный" в данном случае используется в значении "стандартный", "обычный", "распространенный". Алгоритмы Маркова широко применяются в различных областях, таких как теория вероятностей, компьютерная наука, лингвистика и другие. Название "нормальный алгоритм" может подчеркивать его популярность и значимость в мире науки и технологий. Они используются для описания более сложных систем, чем простые цепи Маркова. В отличие от классических алгоритмов Маркова, которые могут находиться только в конечном числе состояний, нормальные алгоритмы Маркова могут иметь бесконечное множество состояний [3].

Основные свойства нормальных алгоритмов Маркова:

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

2. Беспамятность: аналогично классическим алгоритмам Маркова, нормальные алгоритмы не имеют памяти о предыдущих состояниях и зависят только от текущего состояния.

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

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

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

Список используемых источников:

1. 1. 1. Белеванцев А. А. Алгоритмы и алгоритмические языки. (Учебно-методическое пособие) - М: МГУ, 2021.-242 с.

      2. Бочарова Т. А. Основы алгоритмизации: учеб. Пособие/Т.А. Бочарова, Н.О.Бегункова-Хабаровск: Изд-во Тихоокеан. Гос. ун-та, 2019.-64 с.

      3. Иванков А. А. Нормальные алгоритмы Маркова: [Электронный ресурс]//csaa.ru— URL: http://csaa.ru/normalnye-algoritmy-markova/ (Дата обращения 27.11.2024)

      4. Волков А. В. нормальные алгоритмы Маркова: [Электронный ресурс]//habr.com— URL: https://habr.com/ru/articles/682972/ (Дата обращения 27.11.2024).