Введение в алгоритм A. Понятность алгоритма означает что он должен быть записан с помощью Что значит составить алгоритм

Единого «истинного» определения понятия «алгоритм» нет.

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

«Алгоритм - это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

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

«Алгоритм - точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

«Алгоритм - строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

«Алгоритм - это последовательность действий, направленных на получение определённого результата за конечное число шагов».

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

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

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

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

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

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

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

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

1. Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность - определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
3. Понятность - алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
4. Конечность - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
5. Массовость - алгоритм должен быть применим к разным наборам исходных данных.
6. Результативность - завершение алгоритма определёнными результатами.
7. Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
8. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

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

1)Прикладные алгоритмы - предназначены для решения определённых прикладных задач.

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

2)Рекурсивные алгоритмы - алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения.

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

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

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

Литература

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс», 2006. - С. 1296.
2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. - 3-е изд. - М.: «Вильямс», 2006. - С. 720.
3. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. - М.: «Вильямс», 2007. - С. 480.

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

Термин "алгоритм" происходит от имени средневекового математика Абу Джафара ибн Мусы аль-Хорезми. Редакция последней части имени ученого в европейских странах привела к образованию термина "алгорифм" или "алгоритм". Европейцы, начавшие осваивать современную десятичную систему счисления в XII в., знакомились с трудами арабских ученых, и труд упомянутого выше жителя Хорезма, посвященный правилам счета в десятичной системе счисления, был широко известен. Поэтому и наполнение термина "алгоритм" было следующим: операции над числами.

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

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

Современное содержание понятия алгоритма можно определить следующим образом.

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

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

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

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

Любой алгоритм должен обладать следующими свойствами:

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

детерминированность (это означает, что, каждый шаг алгоритма должен быть понятен исполнителю и не должен быть истолкован неоднозначно);

массовость (это означает, что алгоритм должен предназначаться для реализации целого класса однотипных задач, а не для одной конкретной задачи);

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

Для задания алгоритма необходимо описать следующие его элементы:

набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

правило начала;

правило непосредственной переработки информации (описание последовательности действий);

правило окончания;

правило извлечения результатов.

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

4.3. Основные способы описания алгоритмов

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

словесно-формульный (пошаговый);

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

с помощью граф-схем;

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

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

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

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

Шаг 1. Ввести три числа a ,b ,c .

Шаг 2. Вычислить дискриминант

Шаг 3. Проверить условие: если d <0, то идти на шаг 8, иначе идти на шаг 4.

Шаг 4. Вычислить 1-й корень

Шаг 5. Вычислить 2-й корень

Шаг 6. Вывести два числа x 1 ,x 2 .

Шаг 7. Идти на шаг 9.

Шаг 8. Вывести текст "Уравнение не имеет действительных корней".

Шаг 9. Конец.

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

Функциональная вершина используется для представления функцииf:X →Y .

Предикатная вершина используется для представления функции (или предиката)p :X →(T ,F ), то есть логического выражения, передающего управление по одной из двух возможных ветвей.

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

Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем (рис. 4.1).

Любая программа для машины может быть представлена структурной блок-схемой.

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

Структурное программирование – процесс разработки алгоритмов с помощью структурных блок-схем.

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

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

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

принцип модульности;

принцип нисходящей разработки программы;

сквозной структурный контроль;

принцип простой структуры программы.

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

а л г о р и ф м) – одно из основных понятий логики и математики. Под А. понимают точное предписание, задающее вычислит. процесс, ведущий от начальных данных, к-рые могут варьировать, к искомому результату. Встречающиеся выше слова "вычисления", "вычислительный" не следует понимать в узком смысле цифровых вычислений. Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, и хотя здесь буквы играют еще роль заместителей чисел, уже в арифметич. вычислениях появляются символы, не обозначающие никаких величин: скобки, знак равенства, знаки арифметич. действий. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно в таком широком смысле и понимают термин "вычисления" при описании понятия "А.". Так, можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмич. описания процессов управления, изучаемых кибернетикой. З н а ч е н и е А. Само слово "А." восходит к 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, когда она была решена независимо сов. ученым А. А. Мучником и амер. ученым Р. М. Фридбергом. Выл построен пример неразрешимой проблемы разрешения (для перечислимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Черча. Мучник показал даже больше, а именно, что не только проблема Черча, но и никакая другая проблема не может служить "стандартной неразрешимой проблемой" в том смысле, что доказательство неразрешимости любой неразрешимой проблемы разрешения для перечислимого множества могл

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

История происхождения термина

Понятие об алгоритме впервые было сформировано благодаря математику по имени Мухаммед Аль-Хорезми. Он жил на Востоке в 8-9-м веках и написал два великих труда. Первый из них дал начало слову «алгебра», а второй - понятию «алгоритм». Он обозначал арифметические операции, которые мы знаем как сложение, вычитание, умножение и деление. В 1957 году в одном из изданий английского словаря авторы посчитали, что алгоритм - это понятие устаревшее. Опять оно активно вошло в обиход лишь с появлением компьютеров. Им обозначали действия, которые входили в определенный процесс. Но он не обязательно должен быть только математическим. Тут подразумевается алгоритм действий любого характера, например, приготовления какого-либо блюда. С того времени это понятие не сходит с уст почти всех людей.

Попытки определения термина

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

Что обозначает термин «алгоритм»?

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

Свойства, общие для всех алгоритмов

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

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

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

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

• Механические - жесткая, единственно верная последовательность для достижения требуемого результата (обеспечение работы двигателя и т. д.).
• Гибкие: 1) вероятностные - имеют несколько путей для достижения верного решения; 2) эвристические - схема алгоритма, которая не имеет однозначной программы действий (предписания и т. д.), ведь она основана на личных качествах человека, его опыте.
• Вспомогательные - ранее разработанные и полностью предназначенные для разрешения конкретной задачи.

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

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

1. Линейный - все действия выполняются последовательно, друг за другом.
2. Разветвляющийся алгоритм - это такой, в котором выполнение определенного условия приводит к выбору одного из двух возможных вариантов дальнейших действий.
3. Циклический - одни и те же действия повторяются над разными исходными данными, таким образом подбираются наиболее подходящие.

Структура алгоритмов

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

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

• Первым правилом является то, что нужно определить большое количество объектов, которые смогут поддаться построенному алгоритму. Программист с помощью кодировки переводит их в данные. Они бывают входные и выходные. Первые служат для начала работы, вторые становятся ее результатом. Это называется преобразованием данных.
• Второе правило говорит о том, что работа с алгоритмом требует свободной памяти. Ведь без нее не будет возможности разместить входные данные, работать с ними и получить выходные. Память состоит из ячеек. Если одной из них дать имя, она станет переменной.
• Третье правило уже описывалось выше как одна из характеристик алгоритма, а именно - дискретность. То есть алгоритм состоит из отдельных операций, или шагов.
• Четвертое правило напоминает о детерминированности алгоритма. То есть после каждого действия нужно указать, какое будет следующим, либо остановить процесс.
• Последнее правило гласит, что после определенного числа шагов алгоритм завершает свою работу, имея тот или иной результат. А какой именно, указывает сам программист.

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

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

В этой статье мы разберем основные понятия алгоритма.

История появления алгоритмов

Алгоритм - понятие, появившиеся в XII веке. Само слово "алгоритм" происходит от латинской интерпретации имени известного математика среднего востока Мухаммеда аль Хорезми, который написал книгу "Об индийском счете". В этой книге описано, как правильно записывать натуральные числа, используя арабские цифры, и приведено описание алгоритма действий столбиком над такими числами.

В XII веке книга "Об индийском счете" была переведена на латинский язык, тогда-то и появилось данное определение.

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

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

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

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

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

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

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

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

Графический вариант построения алгоритма

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

Изображаются не как попало. Для того чтобы их мог понять любой человек применяются чаще всего блок-схемы и структурограммы Насси-Шнейдермана.

Также блок-схемы изображаются в соответствии с ГОСТ-19701-90 и ГОСТ-19.003-80.
Графические фигуры, применяемые в алгоритме, делятся на:

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

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

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

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

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

Как правильно построить алгоритм?

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

Общая методика по записи включает в себя следующие пункты:

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

У каждого алгоритма должны быть четко обозначены начало и конец.

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

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

• Имя схемы.
• Данные.
• Начало.
• Команды.
• Конец.

Правильное построение схемы существенно облегчит вычисление алгоритмов.

Геометрические фигуры, отвечающие за разные действия в алгоритме

Горизонтально расположенный овал - начало и конец (знак завершения).

Горизонтально расположенный прямоугольник — вычисление или другие действия (знак процесса).

Горизонтально расположенный параллелограмм — ввод или вывод (знак данных).

Горизонтально расположенный ромб — проверка условия (знак решения).

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

Модели алгоритмов представлены ниже на рисунке.

Формульно-словестный вариант построения алгоритма.

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

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

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

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

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

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

Вывод

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