Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и другие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P {Q }R

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

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

Время работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

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

Решение задачи при помощи ЭВМ начинается с составления алгоритма. Что же такое алгоритм?

Происхождение термина «алгоритм» связывают с именем великого математика Мухаммеда аль-Хорезми (763–850 гг.), который разработал правила выполнения четырех арифметических действий.

Согласно ГОСТ 19781-74:

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

То есть алгоритм – это четкое указание исполнителю алгоритма выполнить определенную последовательность действий для решения поставленной задачи и получения результата.

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

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

Наличие ввода исходных данных.

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

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

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

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

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

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

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

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

Разработанный алгоритм может быть представлен несколькими способами:

на естественном языке (словесная запись алгоритма);

в виде блок-схем (графическая форма);

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

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

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

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

Сегодня мы дадим ответ на вопрос о том, что такое алгоритм.

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

Что называется алгоритмом

Понятие алгоритма является довольно древним и относится к одному из главных, а также базовых понятий в математике. Термин происходит от латинского написания имени известного восточного математика 787-850 годов Мухаммеда аль-Хорезми - Algorithmi. Этот ученный был первым, кто сформулировал точные правила для записи натуральных чисел, а также правила для подведения отсчётов в столбик. Довольно интересным фактом является и то, что, несмотря на древние корни, само понятие было точно сформулировано лишь в начале ХХ века. Ныне алгоритм является основной составляющей современного бизнеса, любого учебного процесса или же исследования. Именно поэтому каждому современному человеку просто необходимо точно знать, что означает алгоритм.

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

Что такое свойства алгоритмов

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

1. Одним из важнейших свойств является дискретность. Ее мы рассмотрим чуточку ниже.
2. Не менее важной является определенность. Согласно данному свойству каждая команда должна быть однозначной и наводить исполнителя на конкретное действие.
3. Стоит помнить и о понятности алгоритма. В алгоритме должны использоваться только необходимые команды, которые относятся к поставленной задаче.
4. Важным свойством является и результативность (также часто называют конечностью) алгоритма. Свойство «результативность» указывает на то, что в алгоритме имеется определенное, ранее указанное число шагов, выполнение которых приведет к выполнению поставленной задачи.
5. Также любой алгоритм должен обязательно обладать и таким свойством, как массовость. Если алгоритм обеспечивает выполнение всех задач определенного типа, то он обладает свойством массовости.

Что такое алгоритм в информатике

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

Алгоритм, записанный на формальном языке, принято называть программой. Очень часто понятие алгоритма тесно связывается с процессом его записи в программу. Именно поэтому термин алгоритма и программы зачастую считают синонимами

Как создать алгоритм

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

1. Алгоритм обязательно должен писаться на формальном и ясном языке. Неоднозначность или же неясность указаний недопустима.
2. При составлении алгоритма нужно обязательно учесть и то, для кого он составляется. Исполнитель должен понимать все пункты алгоритма и иметь возможность претворить их в жизнь.
3. Желательно делать алгоритм кратким, точным и ясным.

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

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

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

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

Свойство дискретности алгоритма и ее значение

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

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

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

Приветствую, друзья! Мы продолжаем знакомить вас с миром криптографии и криптовалют. Сегодня хотелось бы рассказать о протоколах безопасности Proof of Work и Proof of Stake . В чем их отличие и как переход от одного к другому может сказаться на мире майнинга. Как всегда простыми и интересными словами. Поехали!

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

Proof of Work

Теперь, давайте рассмотрим алгоритм подтверждения транзакций и создания новых блоков, под названием – Proof of Work. Представьте, что все транзакции, это кусочки криптографического пазла () , которые собираются вместе и создают блок. Решение этого пазла (блока) называется майнингом.

Как зарабатывает майнер?

Чтобы подписать блок с неподтвержденными транзакциями, майнерам необходимо вычислить ХЭШ. Вычислив его, майнер создает новый блок и получает вознаграждение в размере 12,5 BTC. Вознаграждение за подписание нового блока, уменьшается каждые 4 года. В начале создания сети Биткойн, оно было 50 BTC.

Как система определяет майнера подписавшего новый блок?

Каждый майнер, желающий создать блок, трудится над очень сложной вычислительной задачей. Сложность которой подбирается сетью так, чтобы в среднем решение находилось 1 раз в 10 минут. Если число майнеров увеличивается, задача усложняется. Следовательно, шансы каждого участника решить задачу за 10 минут, уменьшаются. Чем больше у майнера вычислительной мощности, тем выше его шансы на успех. Майнер, который первым решает задачу и вычисляет ХЭШ, подписывает новый блок и получает награду.

Итак, что мы имеем?

Алгоритм Proof of Work обеспечивает высококачественную защиту. Еще не было ни одного случая взлома сети Биткойн. Однако, данный алгоритм имеет огромный минус, выполняемая работа требует очень больших затрат электроэнергии. Гонка за новыми блоками превратила индустрию майнинга в ненасытного энергетического монстра. И именно для решения этой проблемы и был разработан алгоритм Proof of Stake.

Proof of Stake

Proof of Stake переводится как доказательство доли владения. В этом алгоритме нет майнеров. Люди, подтверждающие транзакции и создающие новые блоки, называются – Валидаторы.

Рассмотрим условный пример

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

Первый валидатор имеет больше всего монет, и вносит 40%. Второй валидатор вносит 25%, третий 20%, и, наконец, последний вносит 15%. С алгоритмом Proof of Work шансы на подписание блока зависят от вычислительной мощности которая у вас есть. Но в Proof of Stake алгоритм работает иначе. Чем больше у вас монет, тем больше у вас шансов подписать новый блок.

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

Преимущества Proof of Stake

Алгоритм Proof of Stake имеет ряд очевидных преимуществ.

1. Нет расхода электроэнергии. При использовании Proof of Stake ресурсы не используются в пустую. Компьютер, хоть и должен быть включен, однако он не проводит сложных вычислений и соответственно не потребляет много электричества.

2. Отсутствует необходимость наращивать вычислительные мощности.

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

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

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

Зарабатывайте и прокачивайте свои мозги вместе с Business Biceps.

В ЧЕМ РАЗНИЦА МЕЖДУ МЕТОДОМ И АЛГОРИТМОМ?

Метод - это совокупность действий, а алгоритм - конкретная последо­вательность действий.

1. Алгоритм более подробен, чем метод. Иллюстрация алгоритма - блок-схема, а иллюстрация метода - устройство, компоненты которого рабо­тают одновременно.

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

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

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

5. Разные алгоритмы, реализующие один и тот же метод, могут давать со­вершенно разные результаты! Покажем это на примере.

ПРИМЕР, ПОКАЗЫВАЮЩИЙ НЕЭКВИВАЛЕНТНОСТЬ АЛГОРИТМОВ МЕТОДА

Метод содержит процедуру Z, поворачивающую двумерное изображение на заданный угол А и добавляющую яркость точкам изображения на вели­чину В, зависящую от расстояния до заданной точки С: В=В(х-хо, у-уо) "Выделенная" точка С может лежать как внутри, так и снаружи границ изо­бражения, это дела не меняет. При повороте она получает новые координа­ты: х 0 , у\.

Очевидно, что возможны два алгоритма: ■ сначала развернуть на заданный угол, затем добавить яркость; » сначала добавить яркость, затем развернуть.

Результаты работы этих двух алгоритмов могут незначительно отличать­ся из-за округления результатов вычисления расстояний: D=((x-xo) 2 + (у-Уо) 2) 1/2 , a D , =((x , -x > o) 2 +(y"-y"o) 2) 1/2 > и в общем случае эти расстояния до и после поворота D и D" не равны.

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

тики - 16 знаков или 1024, все равно D и D" придется округлять после кака^ го-то знака, отбрасывая остальные знаки. Увеличение точности приведет лишь к уменьшению вероятности того, что после округления D и D" будут неравны.

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

Например, критерий имеет вид T new <3-T 0 i d ", где T 0 | d - суммарная яркость изображения до процедуры Z, a T new - после нее. И если в первом алгоритме Ты/Tnew = 0.3333 , а во втором 0.3334, то после проверки критерия выпол­нятся разные ветви алгоритма. Результат неэквивалентности алгоритмов будет хорошо заметен.

Даже если никакого критерия нет, ошибка может накапливаться посте­пенно, на каждом шаге некоторого цикла.

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

Реализация алгоритма - программа

Программа - это реализация, "воплощение" алгоритма на одном из языков программирования. Таким образом, общая схема написания программы сжатия (кодека, т. е. компрессора и декомпрессора), равно как и любой про­граммы вообще, следующая:

1) постановка задачи;

2) выбор метода;

3) создание алгоритма;

4) написание программы;

5) тестирование, оптимизация и настройка.

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