Информатика. Лекция 5

Star InactiveStar InactiveStar InactiveStar InactiveStar Inactive
 

 

Лекция 5

§ 18. Формализованные формы и структуры данных и знаний. Представление информации в виде дискретного множества

§ 19. Понятия алфавита и языка в информатике

§ 20. Формальность и формальный подход. Формальные системы: определение, свойства, проблемы исследования

§ 21. Теоретические основы алгоритмизации. Понятие алгоритма. Свойства алгоритма

ЛЕКЦИЯ 5

§ 18. ФОРМАЛИЗОВАННЫЕ ФОРМЫ И СТРУКТУРЫ ДАННЫХ И ЗНАНИЙ. ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В ВИДЕ ДИСКРЕТНОГО МНОЖЕСТВА

Под множеством понимается набор, совокупность, собрание каких-либо объектов (которые называются элементами множества). Дискретное множество - множество, все элементы которого изолированы друг от друга. Для измерения степени изолированности элементов данного множества вводится понятие расстояния между элементами. Таким расстоянием для чисел может быть, например, модуль разности между ними; для точек на плоскости – геометрическое расстояние; для двоичных наборов (чисел, кодов) одинаковой длины – число разрядов, в которых они различаются (например, расстояние между наборами  10110 и 11101 равно 3). Отсюда следует более точное определение: дискретное множество – это множество объектов, расстояние между которыми не меньше некоторой заданной величины e. Примеры дискретных множеств: любое множество целых чисел (e = 1), любое множество дробей, имеющих общий знаменатель m (e = 1/m). Всякое дискретное множество счетно, т. е. его элементы можно пронумеровать целыми числами. Однако не всякое счетное множество дискретно, например, счетное множество {1, ½, …, 1/n, …} не дискретно, так как с ростом n расстояние между соседними элементами стремится к нулю. Если задано дискретное множество точек прямой с минимальным расстоянием e, то любой отрезок длины l может содержать не более l /e + 1 точек этого множества.

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

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

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

§ 19. ПОНЯТИЯ АЛФАВИТА И ЯЗЫКА В ИНФОРМАТИКЕ

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

Свою новую символическую алгебру (logistica speciosa) Виет противопоставлял прежней алгебре – числовой (logistica numerosa). Ученый считал, что только первая – это алгебра в собственном смысле, так как позволяет оперировать с целыми классами  вещей. Вторая же есть арифметика, оперирующая просто числами.

Виет в полном соответствии с геометрической алгеброй древних греков разделил все возможные величины на ступени. К первой ступени он отнёс «длины», или величины одного измерения, которые можно складывать и вычитать — из большей меньшую. В результате этих двух операций получится величина той же ступени. Но если перемножить две величины первой ступени, то результатом будет уже «площадь» — величина второй ступени, или величина двух измерений. Следующей ступенью, естественно, были «объемы» В отличие от греческих математиков Виет не остановился на первых трёх ступенях, а пошёл дальше — их у него бесконечно много. В этом исчислении важен принцип однородности: можно складывать и вычитать лишь величины одной ступени. При умножении величины ступени n на величину ступени m получится величина ступени n + m. Разделить же их можно, только если n > m. Результат такого действия будет принадлежать ступени n - m.

Затем Виет обозначил все величины буквами алфавита. Поскольку величины бывают известными и неизвестными, то для обозначения первых он выбрал согласные В, С, D, ..., а для вторых — гласные A, Е, I, ... (Сегодня мы обозначаем параметры задачи, как правило, первыми буквами латинского алфавита a, b, c, ..., а неизвестные — буквами из конца алфавита — x, у, z .)

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

A cubus + B plano 3 in A aequari D solido.

Здесь A cubus означает третью степень неизвестного A, B plano — «В плоское», D solido — «тело D».

Но что особенно важно, помимо уравнений теперь можно было записывать и формулы. Ведь математические формулы — это не только сокращённая запись теорем. Главное заключается в том, что над формулами можно производить операции и получать новые формулы и соотношения. Таким образом, буквенное исчисление позволяет заменить часть рассуждений механическими операциями (выкладками). Как говорил Лейбниц, оно «разгружает воображение».

Сейчас нам трудно представить математику без специального языка формул, но именно такой она была до Виета. Последний «штрих» здесь добавил уже в XVII в. Рене Декарт в своей «Геометрии» — он отказался от принципа однородности.

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

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

В информатике алфавит понимается достаточно широко как   конечное множество символов А = {а1 , а2 ,..., аn}, используемое при написании некоторого класса текстов.

Например, алфавит текстов, которые могут быть напечатаны на пишущей машинке  - это множество всех символов клавиатуры машинки: строчные и прописные буквы, цифры, знаки препинания, скобки и др.  Алфавит языка программирования - множество символов, которые могут быть использованы в текстах этого языка. В частности, символами, т. е. элементарными неделимыми единицами,  считаются ключевые слова языка программирования - begin, end, else, for и т.д.  (Здесь и далее примеры программирования реализованы на языке ПАСКАЛЬ, одним из достоинств которого является удобство в процессе обучения в силу сходства описания данного  языка с синтаксисом и лексикой естественного английского языка.) Отметим, что современные системы программирования и  языки допускают использование визуальных элементов (окон, икон и др.)  для построения программ. Такие языки обычно называют языками визуального программирования. Однако в основной, алгоритмической, части программы без символьных средств не обойтись. Традиционно программы для ЭВМ записываются в виде строк символов некоторого алфавита. Однако в основной, алгоритмической, части программы без символьных средств не обойтись.

Из символов алфавита можно составлять всевозможные цепочки различной длины, записывая символы друг за другом. Минимальная цепочка имеет длину 0, не содержит ни одного символа, называется пустой цепочкой и обозначается L (греческая лямбда). Ограничения сверху на длину цепочек нет. Любой символ алфавита может входить в цепочку произвольное число раз. Бесконечное множество всех возможных цепочек обозначается A*.

Отсюда языкэто любое подмножество L, принадлежащее бесконечному множеству A* всех возможных цепочек, составленных из алфавита A.

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

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

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

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

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

Описание  языка программирования складывается из 4 компонент:

1) описание лексики,

2) описание синтаксиса,

3) описание семантики,

4) описание прагматики.

Описание лексики в языке программирования - это задание набора символов клавиатуры, которые можно использовать при написании программ, задание ключевых (зарезервированных) слов, зарезервированных сочетаний символов (например, <=, >=, :=). С точки зрения формального языка описание лексики - это просто задание алфавита A.

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

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

При описании прагматики обычно рассматриваются практические вопросы написания программ на конкретном языке.

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

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

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

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

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

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

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

§ 20. ФОРМАЛЬНОСТЬ И ФОРМАЛЬНЫЙ ПОДХОД.

ФОРМАЛЬНЫЕ СИСТЕМЫ:

ОПРЕДЕЛЕНИЕ,  СВОЙСТВА,  ПРОБЛЕМЫ ИССЛЕДОВАНИЯ

В обычной жизни  термин «формальный» часто употребляется с отрицательным оттенком. Мы говорим, например, о «формальном отношении к делу», имея в виду, что внешние признаки дела соблюдены, а «душа не вложена». Огромное количество разнообразных ситуаций, в которых может оказаться человек, не позволяет ему запастись правилами на все случаи жизни. Часто приходится совершать действия, которые потом не объяснишь никакими правилами. Наконец, без отклонения от правил невозможно творчество. Но все же существует много сфер обычной жизни, которые организуются по принципам формальных систем. Формализм – это порядок; поэтому там, где имеется множество однотипных объектов или ситуаций, с которыми имеют дело различные люди, совершенно необходимы четкие правила и их одинаковое понимание всеми, кто ими пользуется. Творчество здесь излишне и может принести даже вред, а знания и опыт используются для того, чтобы быстрее определять, какие правила применимы, и осуществлять соответствующие действия.

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

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

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

1) «условие – действие», т.е. если построенные объекты удовлетворяют некоторым условиям, то для построений нового объекта нужно выполнить такое-то действие;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§ 21. Теоретические основы Алгоритмизации

Понятие алгоритма.  СВОЙСТВА АЛГОРИТМА

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

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

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

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

На заре возникновения человека алгоритмы природы были скрыты от него. Шло накопление фактов. Человек методом проб и ошибок, нередко трагических, постигал окружающую природу, стихийно формировал и закреплял собственные алгоритмы поведения. Так продолжалось много веков (примерно 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: = 1N - его номер).

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

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

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

9. N:= iN - его номер).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Недавно добавили

Сейчас читают