Лекция
Привет, Вы узнаете о том , что такое требования к алгоритмам, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое требования к алгоритмам , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.
Результативность - получение результата за конечное число шагов.
Первое, что следует отметить в любом алгоритме, – это то, что он применяется к исходным данным и выдает результаты. В технических терминах это означает, что алгоритм имеет входы и выходы. Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данными – входными, промежуточными и выходными. Поэтому вместе с уточнением понятия алгоритма нужно уточнить и понятие данных, т. е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать.
Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». Во многих случаях хорошо понятно, что это значит: к таким алгоритмическим объектам относятся числа, векторы, матрицы смежностей графов, формулы. С такими объектами, как «хорошая книга» или «осмысленное утверждение», с которыми легко управляется любой человек (но каждый по-своему!), алгоритм работать откажется, пока они не будут описаны как данные с помощью других, более подходящих объектов.
В теории алгоритмов фиксируют конкретные конечные наборы исходных объектов (называемых элементарными) и конечный набор средств построения других объектов из элементарных. Набор элементарных объектов образует конечный алфавит исходных символов (цифр, букв и т. д.), из которых строятся другие объекты. Слова конечной длины в конечных алфавитах (в частности, числа) – наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) – естественная единица измерения объема обрабатываемой информации. Более сложный случай алгоритмических объектов – формулы. Они также определяются индуктивно и также являются словами в конечном алфавите, однако не каждое слово в этом алфавите является формулой. В этом случае обычно основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям. Такая проверка называется синтаксическим анализом.
Для размещения данных требуется память. Память обычно считается однородной и дискретной, т. е. состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ алфавита данных. Таким образом, единицы измерения объема данных и памяти согласованы. При этом память может быть бесконечной.
Дискретность - запись алгоритма в виде конечного числа шагов, каждый последующий шаг выполняется после предыдущего.
Алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно.
Детерминированность - определенность (операция на каждом шаге должна понимать однозначно).
Последовательность шагов алгоритма детерминирована, т. е. после каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной.
Алгоритм должен отвечать требованию результативности, т. Об этом говорит сайт https://intellect.icu . е. остановки после конечного числа шагов с указанием того, что считать результатом. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления функции f(x), обязан показать, что алгоритм останавливается после конечного числа шагов (как говорят, сходится) для любого х из области задания f. Однако проверить результативность (сходимость) гораздо труднее, чем требования, изложенные в пп. 1–4. В отличие от них сходимость обычно не удается установить простым просмотром описания алгоритма; общего же метода проверки сходимости, пригодного для любого алгоритма А и любых данных х, вообще не существует.
Массовость - возможность использования данного алгоритма для решения целого класса задач при различных исходных данных.
Понятность - понятная запись для исполнителя.
Эффективность. Алгоритм должен приводить к результату за как можно короткое время и использовать минимум ресурсов компьютера (памяти).
9 Требование конечности процесса реализации.
Алгоритм должен заканчиваться.
9 Следует различать:
Будем предполагать, что описание алгоритма и механизм его реализации конечны (память, как уже говорилось, может быть бесконечной, но она не включается в механизм). Требования к конечности процесса реализации совпадают с требованиями результативности (см. п. 5).
Рассмотрим следующую задачу: дана последовательность P из n положительных чисел (n – конечное, но произвольное число); требуется упорядочить их, т. е. построить последовательность R, в которой эти же числа расположены в порядке возрастания. Почти сразу же приходит в голову следующий простой способ ее решения: просматриваем Р и находим в ней наименьшее число; вычеркиваем его из Р и выписываем его в качестве первого числа R; снова обращаемся к Р и находим в ней наименьшее число; приписываем его справа к полученной части R и так далее, до тех пор, пока в Р не будут вычеркнуты все числа.
Возникает естественный вопрос: что значит «и так далее»? Для большей ясности перепишем описание способа решения в более четкой форме, разбив его на шаги и указав переходы между шагами.
Многие сочтут такое описание достаточно ясным (и даже излишне формальным), чтобы, пользуясь им, однозначно получить нужный результат. Однако это впечатление ясности опирается на некоторые неявные предположения, к правильности которых мы привыкли, но которые нетрудно нарушить. Например, что значит «дана последовательность чисел»? Является ли таковой последовательность 
? Очевидно, да, однако в нашем описании ничего не сказано, как найти наименьшее число среди таких чисел. В нем вообще не говорится о том, как искать наименьшие числа, по-видимому, предполагается, что речь идет о числах, представленных в виде десятичных дробей, и что известно, как их сравнивать.
Следовательно, необходимо уточнять формы представления данных. Ведь для каждого представления существует свой алфавит (который, помимо цифр, может включать запятые, скобки, знаки операций и функций и т. д.) и свой способ сравнения чисел (например, способ перевода в десятичную дробь), тогда как конечность алфавита требует фиксировать его заранее, а конечность описания алгоритма позволяет включить в него лишь заранее фиксированное число способов сравнения. Фиксация представления чисел в виде десятичных дробей также не решает всех проблем. Сравнение 10 – 20-разрядных чисел уже не может считаться элементарным действием: сразу нельзя сказать, какое из чисел больше: 208112377001,15 или 12834901467,0048. В машинных алгоритмах само представление числа еще требует дальнейшего уточнения: нужно, во-первых, ограничить число разрядов (цифр) в числе, так как от этого зависит, сколько ячеек памяти будет занимать число, а во-вторых, договориться о способе размещения десятичной запятой в числе, т. е. выбрать представление в виде числа с фиксированной или плавающей запятой, поскольку способы обработки этих двух представлений различны. Наконец, любой, кто имел дело с программированием, отметит, что на шаге 1 требуется узнать две вещи: само наименьшее число (чтобы записать его в R) и его место в Р, т. е. его адрес в той части памяти, где хранится Р (чтобы вычеркнуть его из Р), а следовательно, нужно иметь средства указания этого адреса.
Таким образом, даже в этом простом примере несложный анализ показывает, что описанию, которое выглядит вполне ясным, еще далеко до алгоритма. Мы столкнулись здесь с необходимостью уточнить почти все основные характеристики алгоритма, которые отмечались ранее: алфавит данных и форму их представления, память и размещение в ней элементов Р и R, элементарные шаги (поскольку шаг 1 явно не элементарен). Кроме того, становится ясным, что выбор механизма реализации (скажем, человека или компьютера) будет влиять и на сам характер уточнения: у человека требования к памяти, представлению данных и к элементарности шагов гораздо более слабые и «укрупненные», отдельные незначительные детали он может уточнить сам.
Пожалуй, только два требования к алгоритмам в приведенном описании выполнены в достаточной мере (они-то и создают впечатление ясности). Довольно очевидна сходимость алгоритма: после выполнения шагов 1 и 2 либо работа заканчивается, либо из Р вычеркивается одно число; поэтому ровно после n выполнений шагов 1 и 2 из Р будут вычеркнуты все числа и алгоритм остановится, а R будет результатом. Кроме того, не вызывает сомнения детерминированность: после каждого шага ясно, что делать дальше, если учесть, что здесь и в дальнейшем используется общепринятое соглашение – если шаг не содержит указаний о дальнейшем переходе, то выполняем шаг, следующий за ним в описании.
Анализ данных, представленных в статье про требования к алгоритмам, подтверждает эффективность применения современных технологий для обеспечения инновационного развития и улучшения качества жизни в различных сферах. Надеюсь, что теперь ты понял что такое требования к алгоритмам и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория конечных автоматов
Комментарии
Оставить комментарий
Теория конечных автоматов
Термины: Теория конечных автоматов