Основные требования к алгоритмам(Вычегжанин)

ТЕОРИЯ АЛГОРИТМОВ

Главные понятия

Главные требования к методам(Вычегжанин)

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

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

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

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

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

Чтоб сделать метод следует Основные требования к алгоритмам(Вычегжанин) знать:

1. какую работу должен делать метод.

2. какими должны быть входные данные.

3. какими должны быть выходные данные.

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

Разглядим некие главные принципы, по которым строятся методы, и выясним, что все-таки конкретно в понятии метода нуждается в уточнении.

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

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

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

Так как мы собираемся уточнять понятие метода, необходимо уточнить и понятие данных, другими словами указать, каким требованиям должны удовлетворять Основные требования к алгоритмам(Вычегжанин) объекты, чтоб метод мог с ними работать. Ясно, что эти объекты должны быть верно определены и отличимы как друг от друга, так и от "необъектов".

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

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

К примеру, в АЛГОЛе определение идентификатора дано последующим образом: идентификатор Основные требования к алгоритмам(Вычегжанин) – это или буковка, или идентификатор, к которому приписана справа буковка либо цифра.

Слова конечной длины (к примеру, числа) – более обыденный тип алгоритмических данных, а число знаков в слове – естественная единица измерения объема обрабатываемой инфы. Более слож­ный случай алгоритмических объектов – формулы. Они также опреде­ляются индуктивно и также Основные требования к алгоритмам(Вычегжанин) являются словами в конечном алфавите, но не каждое слово в этом алфавите является формулой. В данном случае перед главным методом идут вспомогательные, которые инспектируют, удовлетворяют ли начальные данные необходимым требованиям. Такая проверка именуется синтаксическим анализом.

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

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

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

5-ое, естественно для метода востребовать результативности Основные требования к алгоритмам(Вычегжанин), т.е. остановки после конечного числа шагов с указанием того, что считать результатом. Но, проверить результативность (сходимость) еще сложнее, чем прошлые требования. Сходимость обычно не удается установить обычным просмотром метода. Общего способа проверки сходимости применимого для хоть какого метода и всех данных вообщем не существует.

Шестое, следует различать:

описание Основные требования к алгоритмам(Вычегжанин) метода (программку);

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

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

(Набиулин)

К примеру: разглядим последующую задачку: дана последо­вательность Р из Основные требования к алгоритмам(Вычегжанин) n положительных чисел ( n – конечное, но случайное число); требуется упорядочить их, другими словами выстроить последовательность R, в какой эти же числа распололжены в порядке возрастания.

Простой метод, который приходит в голову: просматриваем Р и находим меньшее число; вычеркиваем его из Р и выписываем его как 1-ое число R; опять Основные требования к алгоритмам(Вычегжанин) просматриваем Р и находим меньшее число, приписываем его справа к R и т.д., пока в Р не будут вычеркнуты все числа.

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

Шаг 1. Ищем в Р меньшее число.

Шаг 2. Отысканное число Основные требования к алгоритмам(Вычегжанин) записываем справа к R и вычеркиваем из Р.

Шаг 3. Если в Р нет чисел, перебегаем к шагу 4, по другому перебегаем к шагу 1.

Шаг 4. Конец. Результатом считать последовательность R, построенную к этому моменту.

Большая часть сочтет описание довольно ясным, чтоб пользуясь им, совершенно точно получить подходящий итог. Это воспоминание опирается на некие неявные Основные требования к алгоритмам(Вычегжанин) догадки, к корректности которых мы привыкли, но которые несложно нарушить: что означает "дана последо­вательность чисел"? Является ли такой запись ? Разумеется, да, но в описании не сказано, как отыскать меньшее посреди таких чисел. В нем вообщем не говорится о том, как находить меньшие числа. Подразумевается, что идет речь Основные требования к алгоритмам(Вычегжанин) о числах, представленных в виде десятичных дробей и понятно, как их ассоциировать. Нужно уточнить формы представления данных. При всем этом нельзя заявить, что допустимо хоть какое представление чисел. Ведь для каждого представления существует собственный алфавит (который кроме цифр может включать запятые, скобки, знаки операций и функций) и собственный метод сопоставления Основные требования к алгоритмам(Вычегжанин) чисел (к примеру, метод перевода в десятичную дробь). Представление чисел в виде десятичных дробей тоже не решает всех заморочек. Сопоставление 10-20–и разрядных чисел уже не может считаться простым действием: попытайтесь сходу сказать, какое число больше 90811557001,15 либо 32899901467,0048.

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

В этом примере мы столкнулись с необходимостью уточнить практически все главные свойства метода, которые отмечались ранее: алфавит данных и форму их представления, память и размещение в ней частей, простые шаги. Не считая того, выбор механизма реализации (человек либо ЭВМ) будет оказывать влияние и на сам нрав уточнения: у человека Основные требования к алгоритмам(Вычегжанин) требования к памяти, представлению данных и к элементарности шагов еще более слабенькие и "укрупненные". В приведенном описании только два требования выполнены в достаточной мере: достаточно явна сходимость метода (после шагов 1 и 2 или работа завершается, или из Р вычеркивается число, потому после n выполнений 1 и 2 шагов метод остановится) и не Основные требования к алгоритмам(Вычегжанин) вызывает сомнения детерминированность: если учитывать принятое соглашение – если шаг не содержит указаний о предстоящем переходе, производится шаг, последующий за ним в описании.

Блок–схемы алгоритмов

Связи меж шагами можно изобразить в виде графа:

Таковой граф, в каком верхушкам соответствуют шаги, а ребрам – переходы меж шагами, именуется блок-схемой метода. Его верхушки могут Основные требования к алгоритмам(Вычегжанин) быть 2-ух видов:

1) из которой выходит одно ребро – операторы;

2) из которой выходит два ребра – логические условия либо предикаты.

Не считая того, имеется единственный оператор конца (из которого не выходит ни 1-го ребра) и единственный оператор начала. Принципиальной особенностью блок-схем будет то, что связи которые она обрисовывает, не зависят Основные требования к алгоритмам(Вычегжанин) от того, являются ли шаги простыми либо представляют собой самостоятельные методы – блоки. Для данного блока непринципиально, как устроены другие блоки; для программирования блока довольно знать, где лежит начальная информация, какова форма её предcтавления, что должен делать блок и куда записывать итог. Блок-схемы соответствуют логике, которой пользуется программер Основные требования к алгоритмам(Вычегжанин) для сотворения сложных, многовариантных, итеративных планов действий.

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


osnovnie-tipi-kristallicheskih-reshetok.html
osnovnie-tipi-lichnostnih-akcentuacij.html
osnovnie-tipi-narushenij-semejnih-vzaimodejstvij.html