Алгоритм. Основные принципы составления алгоритмов. Примеры. Свойства алгоритма. Понятность — алгоритм должен состоять из команд, "понятных" исполнителю (входящих в систему команд исполнителя) Что такое понятие алгоритма
Каждый алгоритм имеет дело с данными – входными, промежуточными и выходными.
Конечность. Понимается двояко: во-первых, алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно. Во-вторых, алгоритм должен заканчиваться за конечное число шагов. Если строится бесконечный, сходящийся к искомому решению процесс, то он обрывается на некотором шаге и полученное значение принимается за приближенное решение рассматриваемой задачи. Точность приближения зависит от числа шагов.
Элементарность (понятность). Каждый шаг алгоритма должен быть простым, чтобы устройство, выполняющее операции, могло выполнить его одним действием.
Дискретность. Процесс решения задачи представляется конечной последовательностью отдельных шагов, и каждый шаг алгоритма выполняется за конечное (не обязательно единичное) время.
Детерминированность (определенность). Каждый шаг алгоритма должен быть однозначно и недвусмысленно определен и не должен допускать произвольной трактовки. После каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной.
Результативность. Алгоритм имеет некоторое число входных величин – аргументов. Цель выполнения алгоритма состоит в получении конкретного результата, имеющего вполне определенное отношение к исходным данным. Алгоритм должен останавливаться после конечного числа шагов, зависящего от данных, с указанием того, что считать результатом. Если решение не может быть найдено, то должно быть указано, что в этом случае считать результатом.
Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Эффективность. Одну и ту же задачу можно решить по-разному и соответственно за разное время и с различными затратами памяти. Желательно, чтобы алгоритм состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точности и требовало минимальных затрат других ресурсов.
Точное математическое определение алгоритма затрудняется тем, что интерпретация предусмотренных предписаний не должна зависеть от выполняющего их субъекта. В зависимости от своего интеллектуального уровня он может либо вовсе не понять, что имеется в виду в инструкции, либо, наоборот, интерпретировать ее непредусмотренным образом.
Можно обойти проблему интерпретации правил, если наряду с формулировками предписаний описать конструкцию и принцип действия интерпретирующего устройства. Это позволяет избежать неопределенности и неоднозначности в понимании одних и тех же инструкций. Для этого необходимо задать язык, на котором описывается множество правил поведения, либо последовательность действий, а также само устройство, которое может интерпретировать предложения, сделанные на этом языке, и выполнять шаг за шагом каждый точно определенный процесс. Оказывается, что такое устройство (машину) можно выполнить в виде, который остается постоянным независимо от сложности рассматриваемой процедуры.
В настоящее время можно выделить три основных типа универсальных алгоритмических моделей. Они различаются исходными посылками относительно определения понятия алгоритма.
Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики – вычислениями и числовыми функциями. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление обеспечивает однозначность алгоритма и элементарность его шагов. Кроме того, такое представление соответствует идеологии построения компьютеров. Основной теоретической моделью этого типа, созданной в 1930-х гг. английским математиком Аланом Тьюрингом, является машина Тьюринга.
Третий тип – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (под словом понимается последовательность символов алфавита) другим словом. Преимущества этого типа моделей состоят в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (необязательно числовой) природы. Примеры моделей третьего типа – канонические системы американского математика Эмиля Л. Поста и нормальные алгоритмы, введенные советским математиком А. А. Марковым.
Модели второго и третьего типа довольно близки и отличаются в основном эвристическими акцентами, поэтому не случайно говорят о машине Поста, хотя сам Пост об этом не говорил.
Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе, БЕЙСИКе или каком-нибудь другом), то говорят об исходной программе . Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.
Любой способ записи алгоритма подразумевает, что всякий описываемый с его помощью предмет задается как конкретный представитель часто бесконечного класса объектов, которые можно описывать данным способом.
Средства, используемые для записи алгоритмов, в значительной мере определяются тем, кто будет исполнителем.
Если исполнителем будет человек, запись может быть не полностью формализована, на первое место выдвигаются понятность и наглядность. В данном случае для записи могут быть использованы схемы алгоритмов или словесная запись.
Для записи алгоритмов, предназначенных для исполнителей-автоматов, необходима формализация, поэтому в таких случаях применяют формальные специальные языки. Преимущество формального способа записи состоит в том, что он дает возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей интеллектуально охватить этот алгоритм.
Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:
■ вербальный – алгоритм описывается на человеческом языке;
■ символьный – алгоритм описывается с помощью набора символов;
■ графический – алгоритм описывается с помощью набора графических изображений.
Общепринятыми способами записи алгоритма являются графическая запись с помощью схем алгоритмов (блок-схем) и символьная запись с помощью какого-либо алгоритмического языка.
Для описания алгоритма с помощью схем изображают связанную последовательность геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками.
В схемах алгоритмов используют следующие типы графических обозначений.
Начало и конец алгоритма обозначают с помощью одноименных символов (рис. 21.1).
Рис. 21.1.
Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом "процесс" (рис. 21.2).
Рис. 21.2.
Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом "решение" (рис. 21.3).
Рис. 21.3.
Здесь Р означает предикат (условное выражение, условие). Если условие выполнено (предикат принимает значение ИСТИНА), то выполняется переход к одному шагу алгоритма, а если не выполнено, то к другому.
Имеются примитивы для операций ввода и вывода данных, а также другие графические символы. В настоящий момент они определены стандартом ГОСТ 19.701–90 (ИСО 5807–85) "Единая система программной документации. Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения". Всего сборник ЕСПД содержит 28 документов.
По схеме алгоритма легко составить исходную программу на алгоритмическом языке.
В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и циклической структуры.
В алгоритмах линейной структуры действия выполняются последовательно одно за другим.
В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.
В алгоритмах циклической структуры в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла. Вложенным называется цикл, находящийся внутри тела другого цикла. Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла.
В этом случае одно повторение цикла называется итерацией.
Слово "Алгоритм" происходит от algorithmi - латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело - реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его его допустимыми действиями . Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Для алгоритмов, встречающихся в математике, средой того или иного исполнителя могут быть числа разной природы - натуральные, действительные и т.п., буквы, буквенные выражения, уравнения, тождества и т.п.
Данное выше
определение
алгоритма
нельзя считать
строгим - не
вполне ясно,
что такое "точное
предписание"
или "последовательность
действий,
обеспечивающая
получение
требуемого
результата".
Поэтому обычно
формулируют
несколько общих
свойств алгоритмов,
позволяющих
отличать алгоритмы
от других
инструкций.
Такими свойствами являются:
Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов.
Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
На основании этих свойств иногда дается определение алгоритма, например: “Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся детерменированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов.” Такая трактовка понятия “алгоритм” является неполной и неточной. Во-первых, неверно связывать алгоритм с решением какой-либо задачи. Алгоритм вообще может не решать никакой задачи. Во-вторых, понятие “массовость” относится не к алгоритмам как к таковым, а к математическим методам в целом. Решение поставленных практикой задач математическими методами основано на абстрагировании – мы выделяем ряд существенных признаков, характерных для некоторого круга явлений, и строим на основании этих признаков математическую модель, отбрасывая несущественные признаки каждого конкретного явления. В этом смысле любая математическая модель обладает свойством массовости. Если в рамках построенной модели мы решаем задачу и решение представляем в виде алгоритма, то решение будет “массовым” благодаря природе математических методов, а не благодаря “массовости” алгоритма.
Разъясняя понятие алгоритма, часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть дверь ключом, перейти улицу и т. д.. : рецепты приготовления какого-либо лекарства или кулинарные рецепты являются алгоритмами. Но для того, чтобы приготовить лекарство по рецепту, необходимо знать фармакологию, а для приготовления блюда по кулинарному рецепту нужно уметь варить. Между тем исполнение алгоритма – это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, то у нас просто не было бы такой специальности – повар.
Правила выполнения арифметических операций или геометрических построений представляют собой алгоритмы. При этом остается без ответа вопрос, чем же отличается понятие алгоритма от таких понятий, как “метод”, “способ”, “правило”. Можно даже встретить утверждение, что слова “алгоритм”, “способ”, “правило” выражают одно и то же (т.е. являются синонимами), хотя такое утверждение, очевидно, противоречит “свойствам алгоритма”.
Само выражение “свойства алгоритма” некорректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм – искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.
Первое правило – при построении алгоритма прежде всего необходимо задать мно-жество объектов, с которыми будет работать алгоритм. Формализованное (закодирован-ное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей рабо-ты выдает данные, которые называются выходными. Таким образом, алгоритм пре-образует входные данные в выходные.
Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит на-звание переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. счита-ется, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил. В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Итак, алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм каждому определенному набору входных данных ставит в соответствие некоторый набор выходных данных, т. е. вычисляет (реализует) функцию. При рассмотрении конкретных вопросов в теории алгоритмов всегда имеется в виду какая-то конкретная модель алгоритма.
Любая работа на компьютере – это есть обработка информации. Работу компьютера можно схематически изобразить следующим образом:
“Информация” слева и “информация” справа – это разные информации. Компьютер воспринимает информацию извне и в качестве результата своей работы выдает новую информацию. Информация, с которой работает компьютер, носит название “данные”.
Компьютер преобразует информацию по определенным правилам. Эти правила (операции, команды) заранее занесены в память компьютера. В совокупности эти правила преобразования информации называются алгоритмом. Данные, которые поступают в компьютер, называются входными данными. Результат работы компьютера – выходные данные. Таким образом, алгоритм преобразует входные данные в выходные:
Теперь можно поставить вопрос: а может ли человек обрабатывать информацию? Конечно, может. В качестве примера можно привести обычный школьный урок: учитель задает вопрос (входные данные), ученик отвечает (выходные данные). Самый простой пример: учитель дает задание – умножить 6 на 3 и результат написать на доске. Здесь числа 6 и 3 – входные данные, операция умножения – алгоритм, результат умножения – выходные данные:
Вывод: решение математических задач – частный случай преобразования информации. Компьютер (по-английски означает вычислитель, на русском языке – ЭВМ, электронная вычислительная машина) был создан как раз для выполнения математических расчетов.
Рассмотрим следующую задачу.
Длина класса 7 метров, ширина – 5 метров, высота – 3 метра. В классе 25 учеников. Сколько кв. м площади и сколько куб. м воздуха приходится на одного ученика?
Решение задачи:
1. Вычислить площадь класса:
2. Вычислить объем класса:
3. Вычислить, сколько квадратных метров площади приходится на одного ученика:
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика:
105: 25 = 4,2
Ответ:
на одного ученика
приходится
1,4 кв. метров
площади и 4,2 куб.
метров воздуха.
Если теперь убрать вычисления и оставить только “действия”, то получим алгоритм – перечень операций, которые необходимо выполнить, чтобы решить данную задачу.
Получается, что при решении любой математической задачи мы составляем алгоритм решения. Но прежде мы сами и выполняли этот алгоритм, то есть доводили решение до ответа. Теперь же мы будем только писать, что нужно сделать, но вычисления проводит не будем. Вычислять будет компьютер. Наш алгоритм будет представлять собой набор указаний (команд) компьютеру.
Когда мы вычисляем какую-либо величину, мы записываем результат на бумаге. Компьютер записывает результат своей работы в память в виде переменной. Поэтому каждая команда алгоритма должна включать указание, в какую переменную записывается результат. Алгоритм решения нашей задачи будет выглядеть так:
1. Вычислить площадь класса и записать в переменную S.
2. Вычислить объем класса и записать в переменную V.
3. Вычислить, сколько квадратных метров площади приходится на одного ученика и записать в переменную S1.
4. Вычислить, сколько куб. метров воздуха приходится на одного ученика и записать в переменную V1.
5. Вывести на экран значения переменных S1 и V1.
Теперь остается только перевести команды алгоритма с русского языка на язык, понятный компьютеру, и получится программа. Программирование – это есть перевод алгоритма с “человеческого” языка на “компьютерный” язык.
Трактовка работы алгоритма как преобразования входных данных в выходные естественным образом подводит нас к рассмотрению понятия “постановка задачи”. Для того, чтобы составить алгоритм решения задачи, необходимо из условия выделить те величины, которые будут входными данными и четко сформулировать, какие именно величины требуется найти. Другими словами, условие задачи требуется сформулировать в виде “Дано... Требуется” – это и есть постановка задачи.
Алгоритм применительно к вычислительной машине – точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа.
Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
Механические алгоритмы , или иначе детерминированные, жесткие (например алгоритм работы машины, двигателя и т.п.);
Гибкие алгоритмы , например стохастические, т.е. вероятностные и эвристические.
Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.
Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоцияциях и прошлом опыте решения схожих задач.
Линейный алгоритм – набор команд (указаний), выполняемых последовательно во времени друг за другом.
Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
Циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов.
Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.
На рисунке продемонстрированы в условных обозначениях схемы основных конструкций алгоритмов:
а). линейного алгоритма;
б,в,г). разветвляющихся алгоритмов (б-ответвление, в-раздвоение, г-переключение);
д,е,ж). циклических алгоритмов (д,ж-проверка в начале цикла, е-проверка в конце цикла).
Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.
На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
Структурная (блок-, граф-) схема алгоритма – графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.
Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.
Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой схему – набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации “. Здесь форма представления алгоритма смешивается с самим алгоритмом.
Принцип программирования “сверху вниз” требует, чтобы блок-схема поэтапно конкретизировалась и каждый блок “расписывался” до элементарных операций. Но такой подход можно осуществить при решении несложных задач. При решении сколько-нибудь серьезной задачи блок-схема “расползется” до такой степени, что ее невозможно будет охватить одним взглядом.
Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна служить для упрощения изображения алгоритма, а не для усложнения.
При решении задач на компьютере необходимо не столько умение составлять алгоритмы, сколько знание методов решения задач (как и вообще в математике) . Поэтому изучать нужно не программирование как таковое (и не алгоритмизацию), а методы решения математических задач на компьютере. Задачи следует классифицировать не по типам данных, как это обычно делается (задачи на массивы, на символьные переменные и т. д.), а по разделу “Требуется”.
В информатике процесс решения задачи распределяется между двумя субъектами: программистом и компьютером. Программист составляет алгоритм (программу), компьютер его исполняет. В традиционной математике такого разделения нет, задачу решает один человек, который составляет алгоритм решения задачи и сам выполняет его. Сущность алгоритмизации не в том, что решение задачи представляется в виде набора элементарных операций, а в том, что процесс решения задачи разбивается на два этапа: творческий (программирование) и не творческий (выполнение программы). И выполняют эти этапы разные субъекты – программист и исполнитель
В учебниках по информатике обычно пишут, что исполнителем алгоритма может быть и человек. На самом деле алгоритмы для людей никто не составляет (не будем забывать, что не всякий набор дискретных операций является алгоритмом). Человек в принципе не может действовать по алгоритму. Выполнение алгоритма – это автоматическое, бездумное выполнение операций. Человек всегда действует осмысленно. Для того, чтобы человек мог выполнять какой-то набор операций, ему нужно объяснить, как это делается. Любую работу человек сможет выполнять только тогда, когда он понимает, как она выполняется.
Вот в этом – “ объяснение и понимание” – и кроется различие между понятиями “алгоритм” и “способ”, “метод”, “правило”. Правила выполнения арифметических операций – это именно правила (или способы), а не алгоритмы. Конечно, эти правила можно изложить в виде алгоритмов, но толку от этого не будет. Для того, чтобы человек смог считать по правилам арифметики, его нужно научить. А если есть процесс обучения, значит, мы имеем дело не с алгоритмом, а с методом.
При составлении алгоритма программист никому ничего не объясняет, а исполнитель не пытается ничего понять. Алгоритм размещается в памяти компьютера, который извлекает команды по одной и исполняет их. Человек действует по другому. Чтобы решить задачу, человеку требуется держать в памяти метод решения задачи в целом, а воплощает этот метод каждый по-своему.
Очень ярко эта особенность человеческой психологии – неалгоритмичность мышления – проявилась в методичесом пособии А. Г. Гейна и В. Ф. Шолоховича. В пособии излагаются решения задач из известного учебника. Решения задач должны быть представлены в виде алгоритмов. Однако авторы пособия понимают, что если просто написать алгоритм решения задачи, то разобраться в самом решении будет трудно. Поэтому они сначала приводят “нечеткое изложение алгоритма” (т. е. объясняют решение задачи), а затем пишут сам алгоритм.
Л И Т Е Р А Т У Р А
1. Нестеренко А. В. ЭВМ и профессия программиста.
М., Просвещение, 1990.
2. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию.
М., Наука, 1990.
3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера.
М., Энергоатомиздат, 1988.
4. Гейн А.Г. и др.. Основы информатики и вычислительной техники.
М., Просвещение, 1994.
5. Информатика. Еженедельное приложение к газете “Первое сентября”. 1998, № 1.
6. Радченко Н. П. Ответы на вопросы выпускных экзаменов. – Инфоматика и
образование, 1997, №4.
7. Касаткин В.Н. Информация, алгоритмы, ЭВМ. М., Просвещение, 1991.
8. Каныгин Ю. М., Зотов Б. И. Что такое информатика?
М., Детская литература, 1989.
9. Гейн А. Г., Шолохович В.Ф. Преподавание курса “Основы информатики и вычислительной техники” в средней школе. Руководство для учителя.
Екатеринбург, 1992.
10. Извозчиков В.А. Информатика в понятиях и терминах.
11. Газета «Информатика», №35, 1997г.
12. Л.З. Шауцуков Основы информатики в вопросах и ответах.
Автор: Богашова Татьяна, Донец Сергей (КПИ,ФАКС) г.Киев, 1999г.
Оценка:отл.
Сдавался: ПТУ №34
E-Mail:[email protected]
а л г о р и ф м) – одно из основных понятий логики и математики. Под А. понимают точное предписание, задающее вычислит. процесс, ведущий от начальных данных, к-рые могут варьировать, к искомому результату. Встречающиеся выше слова "вычисления", "вычислительный" не следует понимать в узком смысле цифровых вычислений. Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, и хотя здесь буквы играют еще роль заместителей чисел, уже в арифметич. вычислениях появляются символы, не обозначающие никаких величин: скобки, знак равенства, знаки арифметич. действий. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно в таком широком смысле и понимают термин "вычисления" при описании понятия "А.". Так, можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмич. описания процессов управления, изучаемых кибернетикой. З н а ч е н и е А. Само слово "А." восходит к 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, когда она была решена независимо сов. ученым А. А. Мучником и амер. ученым Р. М. Фридбергом. Выл построен пример неразрешимой проблемы разрешения (для перечислимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Черча. Мучник показал даже больше, а именно, что не только проблема Черча, но и никакая другая проблема не может служить "стандартной неразрешимой проблемой" в том смысле, что доказательство неразрешимости любой неразрешимой проблемы разрешения для перечислимого множества могл
система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 89 вв. Аль-Хорезми (Хорезм историческая область на территории современного Узбекистана). Из математических работ Аль-Хорезми до нас дошли только две алгебраическая (от названия этой книги родилось слово алгебра) и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Например, в авторитетном словаре английского языка Webster"s New World Dictionary , изданном в 1957, слово алгоритм снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.
Слово «алгоритм» вновь стало употребительным с появлением электронных вычислительных машин для обозначения совокупности действий, составляющих некоторый процесс. Здесь подразумевается не только процесс решения некоторой математической задачи, но и кулинарный рецепт и инструкция по использованию стиральной машины, и многие другие последовательные правила, не имеющие отношения к математике, все эти правила являются алгоритмами. Слово «алгоритм» в наши дни известно каждому, оно настолько уверенно шагнуло в разговорную речь, что сейчас нередко на страницах газет, в выступлениях политиков встречаются выражения «алгоритм поведения», «алгоритм успеха» и т.д.
Тьюринг А. Может ли машина мыслить
? М., Мир, 1960
Успенский В. Машина Поста.
Наука, 1988
Кормен Т., Лейзерсон, Ривес Р. Алгоритмы. Построение и анализ
. М., МЦНМО, 1999
Найти "АЛГОРИТМ " на
В информатике план действий называют алгоритмом
.
Алгоритм состоит из отдельных шагов – команд
. Ни одну из них нельзя пропустить, чаще всего никакие команды нельзя поменять местами.
Исполнитель
– человек, животное или машина, способные понимать и выполнять некоторые команды.
Среда исполнителя
– предметы, которые окружают исполнителя и с которыми он работает.
Список Команд Исполнителя (СКИ)
– набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.
Для решения большинства задач недостаточно отдать одну команду исполнителю, надо составить для него алгоритм – план действий, состоящий из команд, которые ему понятны (входят в его СКИ).
Алгоритм
– точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ.
Какие бывают алгоритмы
Линейный алгоритм
В линейном алгоритме команды выполняются последовательно, одна за другой. Примером линейного алгоритма может служить алгоритм заварки чая.
Разветвляющийся алгоритм
В разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка. Примером разветвляющегося алгоритма может служить алгоритм перехода улицы.
Циклический алгоритм
В циклическом алгоритме некоторые действия повторяются несколько раз (в информатике говорят, что выполняется цикл). Существуют два вида циклических алгоритмов. В одном из них мы знаем заранее, сколько раз надо сделать эти действия, в другом мы должны остановиться лишь тогда, когда выполним работу, то есть наши действия прекращаются при выполнении какого-то условия.
Примером цикла первого типа является наша жизнь в рабочие дни (от понедельника до субботы) – мы выполняем 6 раз почти одни и те же действия.
Пример цикла второго типа – алгоритм распилки бревна: мы не можем заранее сказать, сколько раз нам надо провести пилой от себя и на себя - это зависит от плотности дерева, качества пилы и наших усилий. Однако мы точно знаем, что надо закончить работу, когда очередное отпиленное полено упадет на землю.
Способы записи алгоритмов
Выделяют три наиболее распространенные на практике способа записи алгоритмов:
- словесный (запись на естественном языке);
- графический (запись с использованием графических символов);
- программный (тексты на языках программирования).
Словесный способ записи алгоритмов
Словесный способ – способ записи алгоритма на естественном языке . Данный способ очень удобен, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить логику действий.
В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника
где S – площадь прямоугольника; а, b – длины его сторон.
Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.
Словестный способ записи алгоритма выглядит так:
- Начало алгоритма.
- Задать численное значение стороны a.
- Задать численное значение стороны b.
- Вычислить площадь S прямоугольника по формуле S=a*b.
- Вывести результат вычислений.
- Конец алгоритма.
Графический способ описания алгоритмов
Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.
Каждому действию алгоритма соответствует геометрическая фигура (блочный символ). Перечень наиболее часто употребляемых символов приведен в таблице ниже.
Так как в линейном алгоритме команды выполняются последовательно, то блок-схема будет иметь вид:
Так как в разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка, то блок-схема примет вид:
В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид:
Программный способ записи алгоритмов
Для того, чтобы алгоритм был понятен роботу, компьютеру или другой машине, недостаточно только написать команды, надо еще и оформить алгоритм в таком виде, в котором его понимает машина (написать программу), т.е. записать его с использованием команд из СКИ, соблюдая правила оформления.
Правила оформления программы:
- любой алгоритм имеет название;
- алгоритм начинается с открывающей фигурной скобки “{“ и заканчивается закрывающей фигурной скобкой “}”; команды, расположенные между этими скобками, называются телом алгоритма;
- в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;
- каждая команда заканчивается знаком “;”, который обозначает конец команды;
- для того, чтобы нам было легче разбираться в программах, используют комментарии - текстовые пояснения, которые начинаются знаками “/*” и заканчиваются знаками “*/”; исполнитель не обращает внимания на комментарии в алгоритме.
Практические задания:
- Составить блок-схему для нахождения периметра квадрата.
- Составить блок схему для заваривания чая.
- Составить блок-схему для перехода перекрестка со светофором.
Использован материал из книг:
- "Современные информационные технологии", авторы преподаватели центра "Турбо"
- "Алгоритмы и исполнители", автор Поляков К.
- Основные принципы составления алгоритмов
- Правила составления рекомендательного письма на английском языке для устройства на работу и образец документа для скачивания Рекомендательное письмо для продавца на английском
- Зачем нужно планировать семейный бюджет и как правильно это делать Финансовое планирование семейного бюджета
- Шорт в трейдинге: особенности торговли на падении рынка Принципы торговли фьючерсами