Определение алгоритма

Определение алгоритма

Алгоритм — это упорядоченный набор однозначных выполнимых шагов.

Обратите внимание на то, что это определение утверждает, что набор шагов должен быть упорядочен. Это означает, что шаги в алгоритме должны быть структурированы, то есть должны выполняться в определенном порядке. Это не значит, что сначала должен выполняться первый шаг, затем второй и т. д. Например, некоторые алгоритмы, которые называются параллельными, содержат несколько последовательностей шагов, каждая из которых выполняется одним процессором многопроцессорной машины. В таких случаях полный алгоритм не содержит единственную цепочку шагов, которая соответствовала бы сценарию, когда сначала выполняется первый шаг, затем второй и т. д. Вместо этого структура алгоритма включает в себя несколько цепочек, которые ветвятся и снова соединяются по мере того, как разные процессоры выполняют разные части задачи. (Мы обсудим этот процесс более подробно в разделе 6.5.) В качестве другого примера можно привести алгоритмы, которые выполняются схемами, например триггером, который мы обсуждали в разделе 1.1. В этих схемах каждый вентиль выполняет один шаг алгоритма. Шаги упорядочиваются согласно результату выполнения шагов в процессе того, как результат каждого вентиля передается по схеме.

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

Вывести список всех положительных целых чисел

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

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

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

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

studopedia.ru

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

1.1. Определение алгоритма

В Оксфордском словаре указано, что Algorithm – это ошибочное от algorism, который считается синонимом алгебры и арифметики и восходит к IX в.

Позднее этим символом обозначались в трудах Евклида правила нахождения общего делителя двух чисел – алгоритм Евклида.

История появления понятия «алгоритм» связана с именем выдающегося узбекского ученого Мухаммеда бен Муса ал-Хорезми (жил в IX в.), который был математиком, астрономом, географом. Он написал «Арифметический трактат», по которому европейцы впервые познакомились с десятичной позиционной системой счисления, пришедшей к арабам из Индии. После этого четыре арифметических действия долго называли ал-Хорезми (по латыни Algorithmi). В литературе встречалось «алгоритмус», «алгорифм», а в современном варианте произносится как «алгоритм». Этот термин расширил свое первоначальное значение.

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

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

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

К алгоритмам предъявляются ряд требований:

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

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

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

  4. Дискретность, т.е. возможность деления задачи на шаги, элементарные операции.

  5. Понятность, т.е. ориентация на те команды, которые знает исполнитель.

  6. Эффективность.

  7. Правильность.

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

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

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

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

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

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

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

К основным способам описания алгоритмов можно отнести следующее:

  • словесно-формульный (на естественном языке);

  • структурный или блок-схемный;

  • с использованием специальных алгоритмических языков;

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

  • с помощью сетей Петри.

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

StudFiles.ru

Определение алгоритма

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

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

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

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

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

Правила-свойства алгоритмов:

Первое правило – при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от «методов» и «способов». Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

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

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

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

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

StudFiles.ru

Что такое алгоритм?

Kacmpo

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

Оля гетьманенко

Единого «истинного» определения понятия «алгоритм» нет.
«Алгоритм — это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов» . (Привалов Егор Николаевич)

Umbriako

Алгоритм -- одно из основных математических понятий. Однако с алгоритмами человеку приходится иметь дело не только в математике. Почти во всех сферах жизни мы повседневно сталкиваемся с инструкциями, предписаниями, рецептами, правилами, в соответствии с которыми происходит та или иная человеческая деятельность. Вот два простых примера.
(А)
1. Опустить жетон в щель телефонного автомата, снять трубку.
2. Услышав длинный гудок, набрать номер 22 44 45.
3. Если раздаются короткие гудки, то повесить трубку, взять жетон и повторить все заново.
(Б)
Растворить 1-2 чайные ложки порошка в горячей воде. Сахар и молоко добавлять по вкусу.
Похожим образом звучат руководства по эксплуатации стиральной и швейной машины, автомобиля, инструкции по конструированию моделей корабля или самолета.
Неформально алгоритм можно определить как точное и понятное, т. е. сформулированное на определенном языке, конечное описание общего способа решения некоторого класса задач с использованием элементарных исполнимых шагов.
Приведенная формулировка скорее поясняет, что такое алгоритм, чем дает точное определение, поскольку она использует весьма неоднозначные термины. Например, что значит "точное" описание? Для кого оно должно быть "понятным"?
Обычно требуют, чтобы алгоритм
-- представлял собой общий метод решения однотипных задач для любых исходных данных -- параметров алгоритма;
-- был составлен настолько точно, чтобы было возможным его однозначное понимание;
-- представлял собой конечное описание, иначе его передача исполнителю длилась бы бесконечно долго.
Кроме того, необходимо каким-то образом задать исполнителя, который вполне самостоятельно, без нашего участия, умел бы исполнять элементарные шаги некоторого фиксированного заранее набора, а также выстраивать друг за другом исполнение этих шагов в том порядке, как это предписано алгоритмом.
Приведенные выше примеры (А) и (Б) не вполне удовлетворяют всем требованиям, предъявляемым к алгоритму: во-первых, здесь нельзя говорить об общем методе, а кроме того, нет и достаточной точности.
От алгоритма требуют часто, чтобы он заканчивался, т. е. выполнял конечное число элементарных шагов при любых исходных данных. Такой алгоритм называют завершающимся. Хотя существуют и незавершающиеся алгоритмы, которые заканчиваются лишь при входных данных из некоторого непустого подмножества, называемого областью применимости алгоритма, мы почти всегда будем рассматривать только завершающиеся алгоритмы.
Простейшими алгоритмами являются известные правила, по которым выполняются арифметические действия в десятичной системе счисления. Например, для суммирования двух многозначных чисел исполнитель рассматривает слагаемые как строки цифр, расположенных "столбиком", и конструирует строку цифр результата справа налево при обработке пар соответствующих цифр слагаемых выполнением операций следующих двух типов: запись соответствующей цифры суммы, пометка о переносе над соседней слева цифрой. Эти операции рассматриваются как элементарные и выполняются исполнителем по раз и навсегда заданной таблице сложения цифр, которую мы в детстве заучиваем наизусть.

Владислав субботин

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм Маркова).
Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, ткацкий станок, и пр.).
Можно выделить алгоритмы вычислительные (о них в основном идет далее речь), и управляющие. Вычислительные по сути преобразуют некоторые исходные данные в выходные, реализуя вычисление некоторой функции. Семантика управляющих алгоритмов существенным образом может отличаться и сводиться к выдаче необходимых управляющих воздействий либо в заданные моменты времени, либо в качестве реакции на внешние события (в этом случае, в отличие от вычислительного алгоритма, управляющий может оставаться корректным при бесконечном выполнении).
Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Однако в явном виде понятие алгоритма сформировалось лишь в начале XX века.
Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений [1] или «эффективного метода» [2]; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга. В методологии алгоритм является базисным понятием и получает качественно новое понятие как оптимальности по мере приближения к прогнозируемому абсолюту. В современном мире алгоритм в формализованном выражении составляет основу образования на примерах, по подобию.
Содержание [скрыть]
1История термина
2Определения алгоритма
2.1Формальное определение
2.1.1Машина Тьюринга
2.1.2Рекурсивные функции
2.1.3Нормальный алгоритм Маркова
2.2Стохастические алгоритмы
2.3Другие формализации
3Формальные свойства алгоритмов
4Виды алгоритмов
5Нумерация алгоритмов
6Алгоритмически неразрешимые задачи
7Анализ алгоритмов
7.1Время работы
8Наличие исходных данных и некоторого результата
9Представление алгоритмов
10Эффективность алгоритмов
11Пример
12См. также
13Примечания
14Литература
15Ссылки
История термина [править | править вики-текст]
Страница из «Алгебры» аль-Хорезми — хорезмского математика, от имени которого происходит слово алгоритм.
Аль-Хорезми на советской марке
Современное формальное определение вычислительного алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правил

Лариса власова

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

Читайте также