Лекция № 5. Формальные системы называют также исчислениями или дедуктивными системами, правила формальной системы - правилами вывода

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

Посылки – заключение», т.е. если уже построены объекты вида A1, …, An, то объект вида Аn+1 также считается построенным.

Примером формальной системы может служить множество арифметических формул с переменными а, b, с и целочисленными константами (или, если выражаться более точно, формальная система, задающая множество таких формул). Алфавит системы состоит из символов переменных, знаков, арифметических переменных и скобок: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, с, +, -, ×,:, (,). Исходные объекты: а, b, с, 0, 1, 2,..., 9 (переменные и цифры являются формулами). При этом цифры называются числами. Правила построения:

а) Если A и В - числа и А ¹ 0, то АВ - число; всякое число есть формула. Это правило говорит о том, что частный вид формул - числа получаются путем приписывания одних чисел к другим, причем слева не должно быть нуля.

б) Если F₁ и F₂ - формулы (исходные или построенные), то (F₁ + F₂), (F₁ – F₂), (F₁ × F₂), (F₁: F₂) тоже являются формулами. Это правило - объединенная формулировка четырех (по числу арифметических операций) различных правил.

В данной системе выводимы, например, формулы 1024, (b - 73), (((34 × b) + (a × с)) + 15); многие привычные для нас формулы, такие как 34b + ac +15, получающиеся из предыдущей опусканием некоторых знаков операций и скобок, в этой системе не выводимы. Для того чтобы получать такие «привычные» формулы, нужно ввести несколько более сложные правила. Формальные системы, порождающие различные классы символьных выражений, называются формальными грамматиками, а множества выражений, которые они порождают, - формальными языками. Все языки программирования, как вы уже знаете, являются формальными языками.

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

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

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

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

Как видно из примеров, формальные системы весьма разнообразны. Однако все они обладают некоторыми общими свойствами.

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

Второе свойство формальных систем - это их формальность. Суть формального подхода состоит в соблюдении следующих принципов.

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

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

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

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

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

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

Итак, формальная система функционирует строго по правилам и различает свои объекты только по синтаксическим признакам. С этой точки зрения она однозначно задает некоторую модель. Процесс придания конкретных свойств и признаков элементам формальной системы (модели) при использовании ее в реальных задачах называется интерпретацией. Одна и та же формальная система может иметь различные интерпретации, которые зависят либо от предметной области, в которой исследуется модель, либо от целей, ради которых она используется. Например, используя одни и те же правила ходов, набор шашек и 64-клеточную доску, можно играть в две игры, противоположные по цели: обыкновенные шашки (цель – «съесть» все шашки противника) и поддавки (цель - отдать все свои шашки).

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

Уровень интерпретации лежит вне самой модели формальной системы и не может обсуждаться в рамках модели, которую она описывает. Внешний и опирающийся на формальную систему уровень называется метауровнем. На метауровне исходная формальная система становится уже не инструментом, а объектом изучения. Метауровень, в свою очередь, может быть как неформальным, так и формализованным. Например, формальная система из примера о шахматах отличает правильные шахматные ходы от неправильных, но не может отличить хорошие ходы от плохих. Вопрос о том, как оценить качество хода, решается не по ее правилам, а на метауровне: неформально - на основе индивидуального мастерства шахматиста и материала, накопленного шахматной теорией; формально - теоретиками программирования шахмат, которые создают компьютерные формальные системы, играющие в шахматы. Правила таких систем содержат и правила оценки качества хода, позволяющие выбрать ход, наилучший с точки зрения данной системы.

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

5.4. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ

ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА

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

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

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

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

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

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

Само слово «алгоритм», как утверждают историки, впервые появилось двенадцать веков назад и означало не термин, а имя. Аль-Хорезми — ученый, которому математика обязана многими открытиями,— был известен европейским математикам как Алгоризми, Так переводилось его имя на латынь. Именно с трактата Аль-Хорезми по арифметике началось знакомство Европы с алгоритмами — строгими процедурами для выполнения арифметических операций. В несколько измененном виде они действуют и до сих пор и одинаково пригодны как для упражнений первоклассника, так и для решения задач на ЭВМ. В XVI веке X. Рудольф возвел алгоритм в основной принцип арифметики.

Третий период развития концепции алгоритма начался в 30-е годы нашего столетия и продолжается поныне. Дело в том, что к началу XX в. математика выдвинула ряд задач, поиск ответов на которые, привел к осознанию понятия алгоритма как отдельного объекта изучения. А это, в конечном итоге, привело к созданию математической теории алгоритмов. Произошла трансформация эмпирического понятия алгоритма в строгое математическое оформление. Человек стал изучать собственный способ познания мира.

Настоящий период характеризуется, с одной стороны, строгой классической теорией алгоритмов, уточнившей возможности принципиальной вычислимости, с другой – стихийным развитием прикладной теории алгоритмов, возникшей из недр кибернетики и программирования. Развитие математики и техники расширило и обогатило понятие алгоритма. Его стали активно использовать в вычислительной математике, математической и технической кибернетике, проектировании ЭВМ и программировании. Каждая из этих областей вносит существенный вклад в развитие понятия алгоритма. Например, вычислительная математика требует создания параллельных, матричных и сверхточных вычислений и является одним из основных потребителей специализированных вычислительных структур. Технические устройства обработки информации — это конкретное воплощение разнообразных моделей алгоритмов, отражающих физические законы, на которых основаны такие устройства.

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

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

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

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

Понятия однозначности, результативности и элементарности, использованные в определении алгоритма, нуждаются в уточнении. Алгоритм однозначен, если при применении к одним и тем же данным он дает один и тот же результат. Но как по описанию алгоритма определить, однозначен он или нет? В каком случае шаги считаются элементарными? Что такое результативность? И так ли важно иметь точное определение алгоритма? Ответы на эти вопросы достаточно сложны и связаны с двумя аспектами: теоретическим и практическим.

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

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

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

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

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

2. Данные для своего размещения требуют памяти. В ЭВМ память состоит из одинаковых ячеек, каждая из которых может содержать один или несколько символов алфавита данных. Таким образом, единицы объема данных и памяти согласованы, и в прикладных алгоритмических моделях объем данных можно измерять числом ячеек, в которых данные размещены.

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

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

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

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

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

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

Дано: последовательность чисел.

Требуется: найти в этой последовательности максимальное число.

Метод решения:

1. В некоторой памяти М запоминаем первое число.

2. Следующее число последовательности сравниваем с числом, лежащим в М. Записываем в М большее из этих чисел (т. е. либо сохраняем в М прежнее число - если оно больше, - либо записываем вместо него следующее).

3. Повторяем шаг 2 до конца данной последовательности.

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

а) Каково представление чисел, т. е. представлены ли они целыми числами, десятичными дробями (действительными числами), простыми дробями или арифметическими выражениями типа 2 +

б) Что значит «найти максимальное число» - просто дать его значение или, кроме того, указать еще и его место в последовательности? Предлагаемый метод решения дает только значение. Если нужно указывать место числа, то числа последовательности нужно как-то нумеровать или именовать, а метод решения изменить. Кроме того, как быть, если найдено несколько одинаковых максимальных чисел - указывать все их места или, например, первое по порядку?

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

Вопросы к методу решения:

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

б) Как определить конец последовательности? Есть два стандартных способа: либо при ее вводе указать количество ее элементов (чисел), либо ввести дополнительный элемент - признак конца. Остановимся на первом варианте.

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

1. Ввести данные: исходную последовательность расположить в ячейках р(1),..., р(n).

2. k: = n (в ячейке k лежит число элементов последовательности).

3. i: = 1 (счетчик номеров устанавливаем в начальное положение).

4. М: = p(1) (в М - первое число).

5. N: = 1 (в N - его номер).

6. i: = i + 1 (счетчик увеличивается на 1).

7. Если p(i) £ М то перейти к п.10; иначе перейти к следующему шагу (п.8).

8. М: = p(i) (в М - новое число).

9. N:= i (в N - его номер).

10. Если i < k, то перейти к п.6; иначе - к следующему шагу.

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенности вычислительных, информационных и управляющих алгоритмов мы рассмотрим в специальных параграфах учебного пособия.

Дата добавления: 2013-12-13