Алгоритм: понятие, свойства, структура и виды. Основные свойства алгоритма Дать определение алгоритму

Понятность - алгоритм должен состоять из команд, "понятных" исполнителю (входящих в систему команд исполнителя).

Дискpетность (прерывность, раздельность) - алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов.

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

Pезультативность (или конечность)- алгоpитм должен пpиводить к pешению задачи (или к ответу, что решения нет) за конечное число шагов.

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

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

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

Эти действия называются допустимыми действиями исполнителя. Только их и можно использовать.

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

Сложность алгоритма

Сложность алгоритма позволяет оценить, насколько быстро растет трудоёмкость алгоритма с увеличением объема входных данных. Под трудоемкостью понимается количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Обычно оценка сложности алгоритма представляется в виде O(f(N)), где O – функция сложности, а N – число обрабатываемых наблюдений или примеров. Наименее затратными являются алгоритмы, для которых функция сложности имеет вид f(N)=C и f(N)=C*N, где С – константа. В первом случае вычислительные затраты не зависят от количества обрабатываемых данных, а во втором случае – линейно возрастают. Самыми затратными являются алгоритмы, сложность которых имеет степенную и факториальную зависимости от числа обрабатываемых наблюдений.

СОРТИРОВКА

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.

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

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

МЕТОДЫ ПОИСКА

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

Назад Вперёд

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

Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.

Задачи урока:

Дидактические : Обеспечить условия:

• для изучения и закрепления основных понятия по теме;
• для усвоения, закрепления темы.

Воспитательные : Обеспечить условия:

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

Развивающие : Обеспечить условия:

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

Демонстрационный материал к уроку:

1. Мультимедийная презентация
2. Портрет Мухаммеда Бен Муссы аль-Хорезми.

Ход урока

1. Организационный момент. (2 мин.)
2. Актуализация знаний. Постановка учебной задачи. (3 мин.)
3. Изложение нового материала. (30 мин.)
4. Закрепление нового материала (10 мин.)

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

Появление алгоритмов связывают с зарождением математики.

Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.

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

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

Свойства алгоритма

1. Дискретность
2. Детерминированность
3. Массовость
4. Результативность
5. Конечность
6. Дискретность (от лат. Discretus –разделенный, прерывистый) – это свойство предполагает, что любой алгоритм должен состоять из последовательности шагов, следующих друг за другом.
7. Детерминированность (от лат. Determinate – определенность, точность) - это свойство указывает, что любое действие в алгоритме должно быть строго и недвусмысленно определенно и описано для каждого случая.
8. Массовость – это свойство подразумевает, что один и тот же алгоритм может применяться для решения целого класса задач, отличающихся исходными данными.
9. Результативность (конечность) алгоритма - исполнение алгоритма должно закончиться за конечное число шагов.

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

Пример: Алгоритм «Зарядка»

1. Потянитесь, лежа в постели.
2. Сядьте на кровати, поставив ноги на пол.
3. Нагнитесь вперед, пытаясь достать руками пальцы ног.
4. Выгните спину дугой.
5. Сосчитайте до 10.
6. Вернитесь в исходное положение.

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

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

Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить а на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.

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

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

Линейный алгоритм – это такой, в котором все операции выполняются

последовательно одна за другой.

Пример: Алгоритм посадки дерева .

1. Выкопать в земле ямку;
2. Опустить в ямку саженец;
3. Засыпать ямку с саженцем землей;
4. Полить саженец водой.

Разветвляющийся алгоритм – это алгоритм в котором выполняется либо одна, либо другая группа действий в зависимости от истинности или ложности условия.

Полная форма

Если <условие>, то <действие 1>, иначе <действие 2>

Неполная форма

Если <условие>, то <действия>

Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.

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

Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ »

Пример: Алгоритм «Упражнение для глаз»

1. Возьмите карандаш.
2. Установите его в исходное положение у кончика носа
3. Повторите 10 раз, следя за движение карандаша:
   • Переместите карандаш на расстояние вытянутой руки;
   • Верните карандаш в исходное положение
4. Положите карандаш
5. Конец алгоритма

Цикл с постусловием

Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»

Алгоритм «Пульс»

1. Удобно положите левую руку ладонью вверх.
2. Два пальца правой руки положите на запястье левой руки.
3. Заметьте положение секундной стрелки
4. Сосчитайте очередной удар
5. Посмотрите на часы
6. Если секундная стрелка прошла полный круг, то закончите действия, иначе перейдите к п.4

Конец алгоритма

Цикл с предусловием

Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»

Алгоритм «Бочка»

1. Подойдите к бочке
2. Если бочка неполна (есть место для воды) , то перейдите к п.3, иначе конец алгоритма.
3. Наберите ведро воды
4. Вылейте ведро в бочку
5. Перейдите к п.2.

Конец алгоритма

Задания для закрепление материала

1. Последовательность действий ученика 6 класса Васи: «Если Павлик дома, будем решать задачи по математике. В противном случае следует позвонить Марине и вместе готовить доклад по биологии. Если же Марины нет дома, то надо сесть за сочинение.»
2. Составить блок-схему действий школьника, которому перед вечерней прогулкой следует выполнить домашнее задание по математике.

а л г о р и ф м) – одно из основных понятий логики и математики. Под А. понимают точное предписание, задающее вычислит. процесс, ведущий от начальных данных, к-рые могут варьировать, к искомому результату. Встречающиеся выше слова "вычисления", "вычислительный" не следует понимать в узком смысле цифровых вычислений. Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, и хотя здесь буквы играют еще роль заместителей чисел, уже в арифметич. вычислениях появляются символы, не обозначающие никаких величин: скобки, знак равенства, знаки арифметич. действий. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно в таком широком смысле и понимают термин "вычисления" при описании понятия "А.". Так, можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмич. описания процессов управления, изучаемых кибернетикой. З н а ч е н и е А. Само слово "А." восходит к 9 в. (оно происходит от Algoritmi, являющегося, в свою очередь, лат. транслитерацией, произведенной, по-видимому, в 12 в., арабского имени хорезмийского математика аль-Хорезми). В наши дни простейшие А. появляются уже в начальной школе – это А. арифметич. действий (в ср.-век. Европе А. как раз и называлась совр. школьная арифметика, т.е. десятичная позиционная система счисления и искусство счета в ней, поскольку трактат аль-Хорезми был одним из первых, если не самым первым, благодаря к-рому Европа познакомилась с позиционной системой). Подчеркнем, что в начальной школе обучают именно А. счета. Говоря об умении человека складывать числа, имеют в виду не то, что он для любых двух чисел рано или поздно сумеет найти их сумму, а то, что он владеет нек-рым единообразным приемом сложения, применимым к любым двум конкретным записям чисел, т.е., иными словами, А. сложения (примером такого А. является известный А. сложения чисел "столбиком"). А. встречаются в науке на каждом шагу, умение решать задачу "в общем виде" всегда означает, по существу, владение нек-рым А. Понятие задачи "в общем виде" уточняется при помощи понятия массовой проблемы. Под термином "проблема" можно понимать задачу нахождения объекта, обладающего теми или иными свойствами; этот объект наз. решением проблемы (в частности, для проблемы нахождения ответа на какой-то вопрос решением является ответ "да" или "нет" на поставл. вопрос). Проблема неразрешима, если она не имеет решения, т.е. не существует объекта, обладающего нужными свойствами. Ясно поэтому, что неразрешимость проблемы не дает оснований для агностич. выводов; напротив, установление неразрешимости конкретной проблемы есть важный познават. акт. Массовая проблема задается серией отдельных, "единичных" проблем и состоит в требовании найти общий метод (т.е. А.) их решения. Неразрешимость массовой проблемы означает невозможность найти соответств. А. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему – проблему нахождения А. для решения всех проблем этого класса; здесь проявляется связь таких категорий диалектики, как единичное, особенное и всеобщее. Ролью массовых проблем и определяется значение А. Установление неразрешимости той или иной массовой проблемы (т.е. отсутствия е д и н о г о алгоритма, позволяющего найти решения в с е х единичных проблем данной серии) является важнейшим познавательным актом, показывающим, что для решения конкретных единичных проблем принципиально необходимы специфические для каждой такой проблемы методы. Существование неразрешимых массовых проблем служит, т.о., конкретным воплощением неисчерпаемости процесса познания. Содержат. явления, к-рые легли в основу образования понятия "А.", издавна занимали важное место в науке. Многие задачи, возникавшие в математике и логике, заключались в поисках тех или иных конструктивных методов. Поиски таких методов, особенно усилившиеся в связи с созданием удобной математич. и логич. символики, а также осмысление принципиального отсутствия этих методов в ряде случаев – все это было мощным фактором развития науч. знания. Осознание невозможности решить любую задачу прямым вычислением привело к созданию в 19 в. теоретико-множеств. концепции. Лишь после периода бурного развития этой концепции (в рамках к-рой вопрос о конструктивных методах в совр. их понимании вообще не возникает) оказалось возможным в последние десятилетия вновь вернуться к вопросам конструктивности, но уже на новом уровне, обогащенном выкристаллизовавшимся понятием "А." (еще одна иллюстрация к положению Ленина о спиралеобразном характере развития познания). И хотя понятие "А." не является столь далеко идущей абстракцией, как, скажем, понятие "множество", нельзя считать случайным, что исторически первое из этих понятий возникло позднее второго. П р и м е р ы А. Подобно понятиям "множество", "соответствие", "натуральное число", "отношение" и т.п., понятие "А." является первичным логико-математич. понятием (одной из категорий логики и математики). Оно не допускает формального определения через более простые понятия, а (как и др. математич. категории) абстрагируется непосредственно из опыта. Понятие "А." может быть усвоено лишь на примерах. П р и м е р 1. Возможными начальными данными являются конечные непустые комбинации, составленные из палочек (I), т.е. объекты I, II, III и т.д. А. состоит из след. правил (выполнять к-рые надлежит начиная с правила 1°): 1°. Подчеркни снизу крайнюю слева палочку и перейди к выполнению правила 2°. 2°. Надчеркни сверху крайнюю справа палочку и перейди к выполнению правила 3°. 3°. Рассмотри подчеркнутую палочку и, если она не надчеркнута, перейди к выполнению правила 4°. 4°. Рассмотри палочку непосредственно следующую за подчеркнутой; если она не надчеркнута, перейди к выполнению правила 5°; если же она надчеркнута, перейди к выполнению правила 7°. 5°. Перенеси нижнюю черточку с подчеркнутой палочки на непосредственно за ней следующую и перейди к выполнению правила 6°. 6°. Перенеси верхнюю черточку с надчеркнутой палочки на непосредственно ей предшествующую и перейди к выполнению правила 7°. 7°. Сотри надчеркнутую палочку и все следующие за нею палочки и перейди к выполнению правила 8°. 8°. Сотри нижнюю черточку у подчеркнутой палочки; то, что получилось, и есть результат. Применяя этот А. к комбинации ||||, взятой в качестве начального данного, получим последовательно: по правилу 1° – |||, по правилу 2° – ? || , по правилам 3°, 4°, 5° – | ? | , по правилам 6°, 3°, 4° – | ? | по правилу 7° – | ?, по правилу 8° – || (результат). Если же попытаться применить А. к комбинации |||, то получим: по правилу 1° – ? ||, по правилу 2° – ? | , по правилам 3°, 4°, 5° – | ? , по правилу 6° – | I |, далее нужно перейти к выполнению правила 3°, но правило 3° выполнимо лишь при условии, что подчеркнутая палочка не надчеркнута. Т.о., для создавшейся ситуации А. не содержит указаний, как поступать дальше; произошла т.н. безрезультатная остановка (остановка, не сопровождающаяся получением результата). Легко подметить, что вообще сформулиров. А. дает результат при применении его к любой комбинации из четного числа палочек, и результатом в этом случае является комбинация, состоящая из половинного числа палочек; А. не дает результата в применении к любой комбинации, состоящей из нечетного числа палочек. Пример 2. В логике и математике всякий конечный набор знаков наз. "алфавитом", входящие в него знаки – "буквами" алфавита, а конечная (в т.ч. пустая) последовательность написанных друг за другом букв к.-л. алфавита наз. "словом" в этом алфавите. Напр., арабские цифры образуют алфавит, а всякая десятичная запись целого числа является словом в этом алфавите. Рассмотрим алфавит (а, в) из двух букв: а и в. Примерами слов в этом алфавите являются: в, ав, вва ааававв и т.д. Условимся называть "допустимым" переход от слова в этом алфавите к др. слову в этом же алфавите согласно одному из след. двух правил: 1) если слово имеет вид аР, где P – произвольное слово, перейти к слову Рв; 2) если слово имеет вид ва?, где? – произвольное слово, перейти к слову Рава. Далее формулируется след, предписание: "исходя из к.-л. слова (взятого в качестве начальных данных), делай допустимые переходы до тех пор, пока не получится слово вида аа?; когда слово такого вида получится, отбрось первые две буквы, а то, что останется, и есть результат". Поскольку каждый раз выполнимо не более одного правила перехода, то сформулиров. предписание образует А., возможными начальными данными к-рого служат слова в алфавите (а, в). Возьмем в качестве начальных данных слово ваваа. Согласно правилу 2 получим вааава. Снова применяя правило 2, получим ааваава. В силу нашего предписания надо остановиться; результатом (применения А. к слову ваваа) является ваава. Возьмем в качестве начальных данных слово ваава. По правилу 2 получим аваава. По правилу 1 получим ваавав. Далее получим последовательно ававава, вававав, вававава и т.д. Можно доказать, что процесс никогда не закончится (т.е. никогда не возникает слово, начинающееся с двух букв а, и для каждого из получающихся слов можно будет совершить допустимый переход). Т.о., А. не дает результата при применении к слову ваава. Возьмем в качестве начальных данных слово ваав. Последовательно получим ваавв, аввава, ввавав. Далее ни одно из правил 1 и 2 не выполнимо, и в то же время результат не получился. Поэтому в применении к слову аваав А. также не дает результатов. Основные черты А. По утверждению А. А. Маркова, для А. характерны следующие осн. черты: а) о п р е д е л е н н о с т ь алгоритмич. предписания, заключающаяся в его не оставляющей места произволу точности и общепонятности (в силу этой определенности предписания алгоритмич. процесс является д е т е р м и н и р о в а н н ы м: каждая стадия процесса однозначно определяет следующую стадию); б) м а с с о в о с т ь, заключающаяся в возможности для каждого А. исходить из варьируемых в известных пределах начальных данных; в) результативность, заключающаяся в направленности его на получение искомого результата. Детерминированность А. обеспечивает возможность сообщения его одним лицом другому лицу с тем, что это другое лицо сможет выполнять А. без участия первого; это же свойство детерминированности делает возможным передачу выполнения А. машине. Массовость А. предполагает, что существует нек-рая совокупность (для каждого А. своя) возможных начальных данных. Как задается эта совокупность – это уже другой вопрос. Можно считать, что соответствующая какому-либо А. совокупность возможных начальных данных не задается отдельно от А., а указывается естеств. образом самим содержанием этого А. (так, для А. сложения столбиком соответствующая совокупность состоит из всех пар записей чисел в десятичной системе). Когда какой-то конкретный объект выбирается в качестве начальных данных А., то говорят о п р и м е н е н и и А. к этому объекту. Если А. дает результат при применении его к нек-рому объекту, то говорят, что он п р и м е н и м к этому объекту. Результативность А. вовсе не означает, что А. обязан быть применим к любому объекту из соответствующей совокупности возможных начальных данных (см. примеры1 и 2). Здесь уместно отметить, что можно построить такой А., для к-рого не существует никакого А., к-рый распознавал бы по произвольным начальным данным первого А., применим к ним первый А. или нет. Основные абстракции теории А. В науч. практике сложился ряд специфич. для математики и логики абстракций. Таковы прежде всего абстракция актуальной бесконечности, абстракция отождествления, абстракция потенциальной осуществимости. Сов. ученый А. А. Марков показал, что две последние необходимы при рассмотрении А. Алгоритмич. процесс расчленяется на отд. шаги, каждый из к-рых предполагается настолько элементарным, что возможность его фактич. осуществления не вызывает сомнений. Вместе с тем число этих элементарных шагов, требующееся для получения результата, может быть настолько велико, что достижение результата может считаться практически неосуществимым. Однако представление о практич. осуществимости или неосуществимости того или иного числа шагов является относительным. Оно меняется с развитием вычислит. средств (в принципе может меняться и представление об элементарности отд. шага). В теории А. поэтому отвлекаются от "практич. осуществимости" и считают осуществимым любое конечное число шагов. Тем самым при изучении А. допускают абстракцию потенциальной осуществимости, состоящую в отвлечении от реальных границ наших возможностей. Развитие быстродействующих электронных вычислит. машин быстро отодвигает эти границы все дальше и дальше. То, что было лишь потенциально осуществимым вчера, становится практически осуществимым сегодня. Это сближает теорию А. с практикой работы на вычислит. машинах и позволяет этим двум дисциплинам взаимно обогащать друг друга. Передача машине решения задач к.-л. серии невозможна без предварит. составления А. решения. Составление такого А. имеет, как правило, принципиальное значение (так, в проблеме машинного перевода основным является именно составление А. перевода). Абстракция потенциальной осуществимости необходима при рассмотрении не только алгоритмич. процессов, но и самих объектов, участвующих в этих процессах (в т.ч. "начальных данных" и "результатов"). Так, чтобы говорить о любом натуральном числе (точнее, о записи этого числа, скажем, в десятичной системе), надо разрешить себе рассматривать записи столь больших чисел, что эти записи не уместились бы на земном шаре; т.о., и здесь, отвлекаясь от физич. осуществимости такой записи, используют абстракцию потенциальной осуществимости. Вообще к абстракции потенциальной осуществимости необходимо прибегнуть для того, чтобы рассуждать о сколь угодно длинных словах в заданном алфавите. Объекты, построение и рассмотрение к-рых возможно в рамках абстракции потенциальной осуществимости (при противопоставлении ее абстракции актуальной бесконечности), наз. конструктивными объектами. Таковы натуральные числа, представленные своими записями в к.-л. системе их обозначений, слова в заданном алфавите и т.д., а также пары, тройки и вообще конечные последовательности, составленные из записей чисел, слов в алфавите и т.п.; рациональные числа (к-рые можно представить как тройки натуральных) и др. Конструктивными объектами являются и выражения т.н. исчислений, или формальных систем, что позволяет применить к последним аппарат теории А. Всякий А. (понимаемый как предписание) может (после записи этого предписания в виде комбинации каких-то символов) рассматриваться как конструктивный объект. Напротив, объекты, рассмотрение к-рых невозможно без привлечения абстракции актуальной бесконечности, не относятся к числу конструктивных объектов. Так, напр., конструктивными объектами не являются действительные числа (в смысле Кантора, Дедекинда или Вейерштрасса), геометрич. точки (поскольку анализ такой абстракции, как "точка", приводит к представлению о точке как об актуально бесконечной системе малых тел) и т.д. Конструктивные объекты группируются естеств. образом в совокупности, примерами к-рых служат совокупность всех слов в данном алфавите и вообще любая совокупность всех объектов к.-л. "типа" из числа перечисл. выше типов конструктивных объектов. Каждая такая совокупность конструктивных объектов задается способом конструирования принадлежащих к ней объектов. Другой осн. абстракцией, используемой при рассмотрении конструктивных объектов и А., является абстракция отождествления. В нек-рых случаях о двух объектах говорят как об одинаковых. Условия "одинаковости" устанавливаются каждый раз применительно к данной ситуации. Так, напр., при производстве вычислений человеком на бумаге обычно бывает безразличным шрифт, к-рым пишутся цифры, и записи 1647 и 1647 рассматриваются как одинаковые; однако можно представить себе ситуации, когда существенно различие прямого и курсивного шрифтов (как, напр., при восприятии слов, встречающихся в данной Философской Энциклопедии). Тогда две записи будут уже рассматриваться как неодинаковые, но записи 1647 и 1647 все равно – в обычных случаях – как одинаковые (хотя физически это разные объекты). Обычно принимают, что конструктивные объекты состоят из нек-рых достаточно простых "элементарных частей" (подобно тому, как слова – из букв) и два конструктивных объекта считаются одинаковыми, если они состоят из одинаковых элементарных частей, расположенных в одинаковом порядке. Без понятия "одинаковости", на основе к-рого считаются, напр., одинаковыми цифры, написанные мелом на доске, и цифры, написанные чернилами в тетради, невозможно обучение. Абстракция отождествления позволяет говорить об одинаковых объектах как об одном и том же объекте. Она приводит к образованию понятия "абстрактного объекта": именно, два одинаковых конкретных объекта считаются представителями одного и того же абстрактного объекта. Каждый А. примененный к одинаковым объектам, приводит также к одинаковым объектам. Поэтому можно считать, что каждый А., задает процесс преобразования абстрактных конструктивных объектов. Это свойство А. (вместе с детерминированностью) обусловливает их повторимость или воспроизводимость: будучи выработан в форме А. над абстрактными конструктивными объектами, А. может быть повторно воспроизведен для любых конкретных конструктивных объектов, допустимых для данного А. Из сказанного должно стать ясным, что начальные данные равно как окончат. результаты, возникающие при осуществлении к.-л. А., суть всегда конструктивные объекты (всякое "состояние" алгоритмич. процесса есть конструктивный объект!). Невозможность даже потенциально осуществимых процессов над неконструктивными объектами связана и с отсутствием способа опознавания их как одинаковых или неодинаковых (ср. известное положение кибернетики о преимуществах дискретных форм хранения информации перед непрерывными). Существуют различные т. зр. относительно методов, допустимых при изучении А. Одна из них, выдвигаемая представителями конструктивного направления в математике и логике, состоит в том, что, поскольку для образования понятия А. достаточно абстракций отождествления и потенциальной осуществимости, то развитие теории А. должно вестись в рамках этих абстракций. Другая т. зр. допускает при изучении А. любые методы, вообще допускаемые к логике и математике, в т.ч. и требующие абстракции актуальной бесконечности. Так, можно себе представить случай, когда для доказательства того, что нек-рый А., будучи применен к нек-рому объекту, даст результат, потребуется использование тесно связанного с абстракцией актуальной бесконечности закона исключенного третьего. Основные понятия теории А. К числу осн. понятий, возникающих на основе понятия А., относятся понятия вычислимой функции, разрешимого множества и перечислимого множества. Функция наз. вычислимой, коль скоро существует А., вычисляющий эту функцию в след. смысле: а) А. применим к любому объекту, входящему в область определения функции, и дает в качестве результата то значение функции, к-рое она принимает для этого объекта, взятого в качестве ее аргумента; б) А. не применим ни к какому объекту, не входящему в область определения функции. Множество, расположенное в нек-рой совокупности конструктивных объектов (т.е. множество, составленное из каких-то объектов этой совокупности), наз. разрешимым (относительно объемлющей совокупности), коль скоро существует А., разрешающий это множество (относительно указ. совокупности) в след. смысле: А. применим к любому объекту из объемлющей совокупности и дает в качестве результата ответ на вопрос, принадлежит ли этот объект рассматриваемому множеству или нет. Наконец, непустое множество (см. Пустое) наз. перечислимым, коль скоро существует А., перечисляющий это множество в след. смысле: а) результат применения А. к любому натуральному числу существует и принадлежит рассматриваемому множеству; б) каждый элемент рассматриваемого множества может быть получен как результат применения А. к нек-рому натуральному числу. По определению, пустое множество также относят обычно к классу перечислимых. Одна и та же вычислимая функция (соответственно, разрешимое множество, перечислимое множество) может вычисляться (соответственно, разрешаться, перечисляться) посредством различных А. Из определений вытекает, что аргументы и значения вычислимой функции, элементы разрешимого или перечислимого множества суть всегда конструктивные объекты. Заменяя конструктивные объекты (нек-рой фиксиров. совокупности) их номерами в произвольной алгоритмич. нумерации (т.е. такой нумерации, для к-рой существует А. получения по объекту его номера и обратно), можно, как это часто делают в теории А., ограничиться рассмотрением лишь таких вычислимых функций, аргументы и значения к-рых суть натуральные числа, и лишь таких разрешимых и перечислимых множеств, элементы к-рых суть также натуральные числа. Можно доказать, что всякое разрешимое множество перечислимо. В то же время удалось построить перечислимое, но не разрешимое множество. Этот первый конкретный пример (опубликован амер. ученым А. Черчем в 1936 в статье "Одна неразрешимая проблема элементарной теории чисел") отсутствия А. (а именно, А., разрешающего построенное множество) явился источником или образцом почти всех дальнейших примеров такого рода. Оказалось, что множество разрешимо тогда, и только тогда, когда перечислимо и оно, и его дополнение (до объемлющей совокупности объектов). Т.о., существуют такие дополнения к перечислимым множествам, к-рые сами неперечислимы. Связь теории А. с логикой. Понятия разрешимого и перечислимого множеств тесно связаны о классификацией определений (мы ограничиваемся здесь лишь такими определениями, каждое из к-рых определяет объекты нек-рого типа или, что то же самое, нек-рый класс объектов). Как известно, существуют две осн. схемы определений: "через род и видовое отличие" и "по индукции". При определении "через род и видовое отличие" задается нек-рая объемлющая совокупность объектов ("род") и указывается признак ("видовое отличие"), выделяющий среди объектов указ, совокупности класс определяемых объектов. Если; считать, что это определение конструктивно, т.е. что объекты конструктивны и что наличие или отсутствие видового отличия у элемента рода алгоритмически распознаваемо, то определяемое множество оказывается разрешимым (и каждое разрешимое множество можно определить таким образом). Тем самым разрешимые множества отождествляются с множествами, конструктивно определяемыми через род и видовое отличие. Определение "по индукции" состоит из двух частей: базисной части, содержащей нек-рый перечень объектов, к-рые объявляются принадлежащими к определяемому классу, и индуктивной части, гласящей, что если объекты такого-то и такого-то вида принадлежат к определяемому классу, то и объекты такого-то и такого-то вида, связанные с первыми объектами нек-рым отношением, также принадлежат к определяемому классу. (Возможны и более сложные случаи т.н. перекрестных определений, когда одновременно определяется друг через друга несколько классов объектов). Если предполагать определение конструктивным, т.е. объекты конструктивными, перечень исходных объектов, содержащийся в базисной части, конечным, а содержащиеся в индуктивной части правила перехода от уже определенных объектов к новым алгоритмическими (в том смысле, что наличие или отсутствие отношения, о к-ром идет речь в индуктивной части, распознается посредством какого-то А.), то мы приходим к понятию множества, конструктивно определяемого по индукции, или (синоним) эффективно порождаемого множества (поскольку такое определение задает эффективный порождающий п р о ц е с с, на отд. этапах развертывания к-рого "возникают" или "порождаются" определяемые объекты). Примером конструктивного определения по индукции служит определение допустимых шахматных позиций (т.е. позиций, к-рые могут возникнуть на доске в процессе игры). Базисная часть содержит одну единств. исходную позицию. Индуктивная часть содержит правила ходов фигур. Множество допустимых позиций, т.о., эффективно порождаемо. Другим примером эффективно порождаемого множества служит множество всех доказуемых формул к.-л. формальной системы или исчисления: базисная часть определения доказуемых формул содержит аксиомы, индуктивная часть – правила вывода (аксиомы объявляются доказуемыми по определению и далее говорится, что если какие бы то ни было формулы доказуемы, то и формулы, полученные из них по правилам вывода, также доказуемы). Порождающим процессом является здесь процесс доказательства всех доказуемых формул. Наконец, процесс опровержения всех опровержимых формул исчисления также является примером эффективного порождающего процесса. Понятие эффективного порождающего процесса очень тесно связано с понятием А. Мы дали определение (приблизительное) эффективного порождающего процесса, опирающееся на понятие А. В свою очередь, понятие порождающего процесса позволяет определить на его основе если не само понятие А., то, во всяком случае, понятие вычислимой функции. Действительно, пусть нек-рый порождающий процесс способен "порождать" объекты, имеющие вид пар (х, у), и пусть у любых двух "порожденных" пар с совпадающими первыми членами совпадают и вторые члены. Тогда процесс след. образом определяет функцию y = f(x): функция определена для объекта х0 тогда, и только тогда, когда х0 есть первый член к.-л. порожденной пары: значение функций для аргумента х0 равно в таком случае второму члену этой пары. Функция, определенная в указ. смысле эффективным порождающим процессом, очевидно, вычислима [чтобы найти f(x0), надо развертывать процесс до тех пор, пока не найдем пары с х0 в качестве первого члена]. Обратно, всякую вычислимую функцию можно определить посредством эффективного порождающего процесса. Алгоритмич. процессы и порождающие процессы близки друг другу с логич. точки зрения. В основании каждого из них лежат лишь конструктивные понятия. Различие между ними состоит в том, что алгоритмич. процесс развертывается на основе требования, а порождающий – на основе разрешения действовать определенным образом. Здесь проявляется различие между необходимым и возможным (в алгоритмич. процессе каждый этап однозначно, т.е. с необходимостью, определяется предыдущим этапом, в то время как при развертывании порождающего процесса после каждого этапа возникает лишь множество возможностей для след. этапа). При надлежащих уточнениях понятия эффективного порождающего процесса выясняется, что каждое эффективно порождаемое множество перечислимо, и обратно. Это обстоятельство, в сочетании с приведенными выше взаимоотношениями между перечислимым и разрешимым множествами, позволяет заключить следующее. Всякий класс объектов, допускающий конструктивное определение через род и видовое отличие, допускает и конструктивное определение по индукции, но не обратно: существует класс объектов, конструктивно определяемый по индукции, но не допускающий конструктивного определения через род и видовое отличие; дополнение к этому классу объектов (по объемлющей совокупности конструктивных объектов) не допускает эффективного индуктивного определения. Каждый конструктивный порождающий процесс можно представить в виде процесса получения доказуемых формул подходящего исчисления. Поэтому пример класса, обладающего только что описанными свойствами, можно построить в виде класса всех доказуемых формул нек-рого исчисления. Более того, оказалось, что это обстоятельство имеет место для любого достаточно содержат. исчисления (напр., для исчисления предикатов или для исчислений, формализующих арифметику), т.к., если исчисление достаточно содержательно, то в нем можно выразить любой эффективный порождающий процесс. Класс всех доказуемых формул такого исчисления (являясь, конечно, перечислимым) не является разрешимым, так что не существует А., распознающего доказуемость формул исчисления; в этом смысле говорят, что исчисление неразрешимо. Поскольку класс всех доказуемых формул исчисления не является разрешимым, то дополнит. к нему класс всех недоказуемых формул не является перечислимым и, следовательно, не может быть получен никаким порождающим процессом; в частности, невозможно построить такое исчисление, в к-ром "опровергались" бы все недоказуемые формулы первонач. исчисления и только они; тем более, все эти недоказуемые формулы не могут быть опровергнуты средствами самого первонач. исчисления, так что в первонач. исчислении имеются т.н. неразрешимые (т.е. ни доказуемые, ни опровержимые) формулы. В этих рассуждениях можно ограничиться лишь такими формулами, к-рые при содержат. интерпретации исчисления выражают осмысленные (т.е. либо истинные, либо ложные) суждения, и обнаружить, следовательно, и среди таких формул неразрешимые. Отсюда вытекает, что можно предъявить формулу, выражающую истинное суждение, но не доказуемую в исчислении; в этом смысле говорят, что система неполна. Подчеркнем, что в силу общего характера проводимых рассуждений свойство неполноты присуще любому достаточно содержат. исчислению. Понятие неразрешимости исчисления опирается на понятие А., и неудивительно что факт неразрешимости устанавливается на основе исследований в области теории А. Весьма существенным (и, может быть, неожиданным на первый взгляд) является то обстоятельство, что такой общелогич. факт, как неполнота исчислений (факт, выражающий принципиальную невозможность полностью формализовать процесс логич. вывода и впервые строго доказанный австр. ученым К. Геделем еще в 1931, до уточнения понятия "А."), может быть получен, как мы только что видели, средствами теории А. Это обстоятельство уже одно показывает огромные возможности применений теории А. к вопросам логики. Эти применения не ограничиваются приведенным примером. Еще в 1932 сов. ученый А. Н. Колмогоров предложил истолкование созданной интуиционистами конструктивной логики при помощи содержат. средств, не имеющих никакого отношения к установкам интуиционизма; именно, каждое предложение конструктивной логики Колмогоров предложил истолковывать как проблему. Понятие проблемы требовало, однако, конкретизации, к-рая могла быть дана только на базе уже разработанной теории А. Два конкретных класса проблем, пригодных для интерпретации конструктивной логики, предложили, соответственно, амер. ученый С. К. Клини в 1945 и сов. ученый Ю. Т. Медведев в 1955. В 1956 сов. ученый Н. А. Шанин выдвинул новую концепцию, согласно к-рой не всякое высказывание конструктивной логики требует истолкования в виде проблемы. К этому кругу идей примыкают вопросы "конструктивизации", или "нахождения конструктивных аналогов", классич. математич. понятий и предложений; решение этих вопросов также возможно лишь на основе теории А. Конструктивизация осн. понятий математич. анализа привела к разрабатываемому сейчас т.н. конструктивному математич. анализу. Намечаются пути конструктивизации и др. математич. теорий. Одним из осн. приемов, используемых при конструктивизации, является переход от изучаемых предметов к их именам, к-рые всегда являются конструктивными объектами. П р о б л е м ы р а з р е ш е н и я. Частным случаем массовых проблем являются разрешения проблемы. Проблемы разрешения к.-л. множества есть проблема построения А., разрешающего это множество. Соответств. серия единичных проблем состоит здесь из проблем ответа на вопрос о принадлежности к множеству, поставленный для каждого объекта из объемлющей совокупности конструктивных объектов. Обратно, всякая массовая проблема, соответств. серии единичных проблем ответа на вопрос, может быть рассмотрена как проблема разрешения нек-рого множества, а именно – множества тех единичных проблем, ответом на к-рые служит "да". Отсюда ясна важная роль проблем разрешения. Именно они подвергались изучению с т. зр. их разрешимости. Среди проблем разрешения выделяются проблемы, поставленные для классов доказуемых формул исчислений. Проблема разрешения класса всех доказуемых формул к.-л. исчисления наз. также проблемой разрешения самого исчисления. (В рус. текстах проблему разрешения наз. обычно "проблемой разрешимости"; однако "проблемой разрешимости" лучше называть проблему: "ответить, имеет ли решение данная проблема разрешения"). Неразрешимые массовые проблемы. Проблема разрешения для к.-л. исчисления всегда есть проблема разрешения перечислимого множества. Вообще все естественно возникавшие в математике проблемы разрешения оказывались проблемами разрешения перечислимых множеств. Таков упоминавшийся выше первый пример неразрешимой проблемы разрешения (и одновременно первый пример неразрешимой массовой проблемы вообще), опубликованный Черчем в 1936. Такова т.н. проблема тождества для ассоциативных систем, доказательства неразрешимости к-рой опубликовали в 1947 независимо друг от друга А. А. Марков и амер. ученый Э. Л. Пост; этот результат представляет интерес как первый пример доказательства неразрешимости массовой проблемы, возникшей (еще в 1914) вне логики и теории А. Такова и знаменитая проблема тождества для групп, поставленная еще в 1912, неразрешимость к-рой доказана в 1952 сов. ученым П. С. Новиковым (Ленинская премия, 1957). Каждая из проблем тождества состоит в отыскании А., устанавливающего эквивалентность или неэквивалентность двух слов в заданном алфавите (от того или иного определения эквивалентности зависит, имеем ли мы дело с ассоциативной системой или группой). Поэтому проблему тождества можно рассматривать как проблему разрешения множества всех пар эквивалентных друг другу слов (относительно совокупности всевозможных пар слов). При этом, поскольку можно задать порождающий процесс получения всех пар эквивалентных друг другу слов, множество всех таких пар перечислимо. С в о д и м о с т ь. Начиная с примера Черча 1936 и по 1944 все доказательства неразрешимости массовых проблем проводились или могли быть проведены след. единообразным методом. Заведомо неразрешимая проблема, исследованная Черчем, сводилась к рассматриваемой массовой проблеме, так что если бы рассматриваемая массовая проблема была разрешимой, то оказалась бы разрешимой и проблема Черча (в этом смысле можно сказать, что доказательство неразрешимости рассматриваемой проблемы сводилось к доказательству неразрешимости проблемы Черча). Возник вопрос, для всякой ли неразрешимой проблемы разрешения ее неразрешимость может быть установлена таким способом. Этот вопрос, получивший название проблемы сводимости, был поставлен Постом в 1944; одновременно Пост привел несколько примеров неразрешимых проблем разрешения, неразрешимость к-рых была установлена им методом, отличным от описанного выше (эти примеры не решали еще проблему сводимости, поскольку оставался открытым вопрос, нельзя ли и для них найти такие доказательства неразрешимости, к-рые сводились бы к доказательству неразрешимости проблемы Черча; впоследствии для нек-рых из указанных примеров такие доказательства были действительно найдены). Проблема сводимости стояла в центре исследований по теории А. вплоть до 1956, когда она была решена независимо сов. ученым А. А. Мучником и амер. ученым Р. М. Фридбергом. Выл построен пример неразрешимой проблемы разрешения (для перечислимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Черча. Мучник показал даже больше, а именно, что не только проблема Черча, но и никакая другая проблема не может служить "стандартной неразрешимой проблемой" в том смысле, что доказательство неразрешимости любой неразрешимой проблемы разрешения для перечислимого множества могл

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

Общие определения

Единого «истинного» определения понятия «алгоритм» нет. Наиболее известные варианты определения опираются на интуитивное понятие «задачи»:

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

Формальные признаки алгоритмов

• Детерминированность : в каждый момент времени следующий шаг работы однозначно определяется состоянием исполнителя. Алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
• Понятность : алгоритм должен включать только команды из заранее оговоренной системы команд исполнителя.
• Завершаемость (конечность): при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
• Массовость : алгоритм должен быть применим к разным наборам исходных данных.

Алгоритмы анализа данных

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

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

Литература

1. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания : Дис. док. физ.-мат. наук: 05-13-17. - Вычислительный центр АН СССР, 1992. - 274 с. (

Алгоритм

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

Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Однако, в явном виде понятие алгоритма сформировалось лишь в начале 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
10. (Раздел 12, с. 12-22 в Atallah, 2010)
11. (Игошин, раздел 36)
12. Peter Linz An Introduction to Formal Languages and Automata. - Jones and Bartlett Publishers, 2000. - ISBN 0-7637-1422-4
13. "computability and complexity", Encyclopedia of computer Science and Technology , Facts On File, 2009,