Формальная грамматика. Теория алгоритмов

В любом естественном или искусственном языке можно выделить две составляющие: синтаксис и семантику. Синтаксис – это совокупность правил, по которым строятся правильные (допустимые) в данном языке конструкции. Семантика же соотносит единицы и конструкции языка с некоторым внешним миром, для описания состояний которого язык используется. Поясним эти две составляющие языка на простом примере конструктора ЛЕГО.

Всем известен детский конструктор ЛЕГО. Он состоит из набора деталей. Соединяя детали, можно собирать разнообразные конструкции. Если при этом не ломать деталей, а соединять их, следуя возможностям, представляемым создателями игры, то конструкции будут допустимыми, а сами правила соединения определят синтаксис «языка конструктора».

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

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

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

Принято задавать формальную грамматику четверкой (V, W, S, P). Здесь V - множество терминальных символов; W – множество вспомогательных символов; S – начальный вспомогательный символ из множества W; P – система подстановок.

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

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

Для пояснения понятия «алгоритм» важное значение имеет определение понятия «исполнитель алгоритма». Алгоритм формулируется в расчете на конкретного исполнителя, например человека, специально дрессированное животное, особую машину—автомат и т. д. Алгоритм является руководством к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание». Можно сказать, что алгоритм – это понятное и точное предписание (указание) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи. Отметим, что сказанное не является определением в математическом смысле, а лишь отражает интуитивное понимание алгоритма, сложившееся за долгие годы. В нематематическом смысле мы будем придерживаться именно этого определения.

В связи с вышесказанным сформулируем некоторые особенности алгоритма, понимаемого в данном смысле:

1. Алгоритм имеет некоторое число входных величин — аргументов, задаваемых до начала работы

2. Для того чтобы алгоритм был выполнен, необходимо, чтобы он был понятен исполнителю

3. Алгоритм должен иметь дискретную структуру, т.е. выполнение его должно быть пошаговым, и выполнен он должен быть за конечное число шагов

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

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

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

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

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

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

Первое направление основано на арифметизации алгоритмов. Ясно, что любые данные можно закодировать числами, и тогда всякое их преобразование станет арифметическим вычислением. Всякий алгоритм в таких моделях вычисляет значение некоторой числовой функции, а его элементарные шаги – это известные всем арифметические операции. Последовательности шагов определяется с помощью двух основных способов. Первый способ – суперпозиция, т.е. подстановка функций в функции, порождающая математические формулы, в которых порядок действий определяется расстановкой скобок. Например, формула ab+c/d получается подстановкой в функцию x+y функций ab вместо x и c/d вместо y. Другой способ менее известен – это рекурсия, т.е. определение очередного значения функции через ранее вычисленные значения этой же функции. Существуют и другие виды рекурсии, в которых понятие предыдущих точек определяется более сложно. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций и рекурсивных определений, называются рекурсивными функциями. Они являются исторически первым уточнением понятия алгоритма, т.е. первой универсальной алгоритмической моделью.

Второе направление основано на простой идее: для того, чтобы алгоритм понимался однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и ее действия, тем убедительней выглядит утверждение, что ее работа и есть выполнение некоторого алгоритма. При этом структура машины должна быть универсальной, такой, чтобы на ней можно было выполнить любой алгоритм. Эта идея привела к концепции абстрактной машины как универсальной алгоритмической модели. Она была выдвинута А.Тьюрингом и Э.Постом практически одновременно (в 1936-1937гг.). Действия абстрактной машины сводятся к тому, что она обозревает символы, записанные в памяти и в зависимости от своего состояния и того, каков обозреваемый символ, она стирает его или заменяет другим символом или какой-то последовательностью символов, после чего переходит в новое состояние и читает следующий символ. Наибольшую известность среди моделей такого типа получила модель Тьюринга, за которой закрепилось название «машина Тьюринга».

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

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

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

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

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

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

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

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

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

1. Физическое время выполнение алгоритма – это величина τt, где t – число действий (элементарных шагов, команд), τ - среднее время выполнения одного действия. Число шагов t определяется описанием алгоритма в данной алгоритмической модели и не зависит от физической реализации модели; τ - величина физическая и зависит от скорости обработки сигналов в элементах и узлах компьютера. Поэтому объективной математической характеристикой трудоемкости алгоритма в данной модели является число действий t.

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

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

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

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

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

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

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

Рассмотрим основные средства, используемые для записи алгоритмов.

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

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

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

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

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

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

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

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

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

 

Вопросы для самопроверки:

1. Что называется формальной грамматикой?

2. Поясните понятие алгоритма, применяемого в информатике.

3. Перечислите основные свойства алгоритма с точки зрения информатики.

4. Является ли определение алгоритма в информатике строгим определением с точки зрения математики? Почему?

5. На решение каких проблем была направлена теория алгоритмов?

6. Какие направления существовали для уточнения понятия алгоритма?

7. Что означают следующие понятия: «алгоритмически неразрешимая задача» и «сложность алгоритма»?

8. Перечислите основные средства записи алгоритмов. Раскройте их.

 

Языки программирования

 

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

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

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

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

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

1. неструктурный;

2. структурный;

3. логический;

4. объектно-ориентированный;

5. функциональный.

Неструктурное программирование допускает использование в явном виде команды безусловного перехода (в большинстве языков GOTO). Типичные представители неструктурных языков - ранние версии Бейсика и Фортрана. Данный стиль вызван особенностями выполнения машиной программы в кодах и унаследован от программ на языке ассемблера, поскольку там команда перехода является обязательной. Однако в языках высокого уровня наличие команды перехода влечет за собой массу серьезных недостатков: программа превращается в клубок с бесконечными переходами вверх-вниз, ее очень трудно сопровождать и модифицировать. Фактически неструктурный стиль программирования не позволяет разрабатывать большие проекты. Ранее широко практиковавшееся первоначальное обучение программированию на базе неструктурного языка (обычно Бейсика) приводило к огромным трудностям при переходе на более современные стили. Как отмечал известный голландский ученый Э. Дейкстра, «программисты, изначально ориентированные на Бейсик, умственно оболванены без надежды на исцеление».

Структурный стиль был разработан в середине 60-х - начале 70-х гг. В его основе лежат две идеи:

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

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

Принципы структурного программирования были реализованы в языке Алгол, но наибольшую популярность завоевал язык Паскаль, созданный в 1970 швейцарским ученым Н. Виртом. Паскаль получил широчайшее распространение и может считаться образцовым языком программирования, наиболее популярным и сейчас (например, в версии Delphi фирмы Imprise).

Логическое программирование представляет собой попытку возложить на программиста только постановку задачи, а поиски путей ее решения предоставить транслятору. Логические языки (Пролог, Симула) имеют специальные конструкции для описания объектов и связей между ними. Например, если дано:

БРАТЬЯ ИМЕЮТ ОДНОГО ОТЦА

ДЖОН - ОТЕЦ ДЖЕКА

МАЙК - БРАТ ДЖЕКА

Система логического программирования должна сделать вывод:

ДЖОН - ОТЕЦ МАЙКА.

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

Объектно-ориентированное (ОО) программирование, разработанное в середине 70-х гг. Керниганом и Риччи и реализованное в ОО-версиях языков Си и Паскаль, представляет собой отображение объектов реального мира, их свойств (атрибутов) и связей между ними при помощи специальных структур данных. Структурное программирование подразумевает наличие ряда встроенных структур данных: целых, вещественных и строковых переменных, массивов, записей - при помощи которых и производится отображение свойств объектов реального мира. При объектно-ориентированном подходе для объекта создается своя структура данных (класс), содержащая как свойства объекта (поля), так и процедуры для управления объектом (методы).

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

В основе функционального стиля лежит понятие функции как «черного ящика», имеющего вектор параметров (аргументов) на входе и результат r (скаляр) на выходе: f(…)=r.

Допустим случай, когда вектор параметров отсутствует. В функциональных языках программирования отсутствуют операторы: все действия, в том числе и управляющие конструкции, выполняются при помощи вызовов функций. Поскольку каждая функция возвращает значение, ее можно подставить в качестве аргумента другой функции, что позволяет записывать сложные выражения в функциональной форме. Одним из первых функциональных языков стал язык Лисп, созданный в конце 50-х гг. как язык искусственного интеллекта. К языкам искусственного интеллекта (сокращенно обозначается AI - artificial intelligence) относят такие языки, которые способны в зависимости от набора исходных данных модифицировать алгоритм работы, т.е. «на ходу» менять программу (шутка гласит, что на языках искусственного интеллекта программируют те, кому не хватает интеллекта естественного).

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

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

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

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

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

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

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

Значения элементов одномерного массива хранят в памяти также в виде последовательности, т. е. структура одномерного массива однозначно отображается на структуру памяти компьютера. Индекс элемента массива означает номер ячейки памяти, в которой хранится значение этого элемента, относительно номера той ячейки памяти, в которой хранится значение первого элемента этого массива. Например, если значение первого элемента массива хранится в ячейке с номером 101, то значение пятого элемента будет храниться в ячейке с номером 105, а значение двадцатого элемента — в ячейке с номером 120.

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

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

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

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

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

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

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

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

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

Стек можно отобразить на одномерный массив по тому же принципу, что и очередь. Для указания вершины стека можно использовать индекс i. При записи в стек указатель вершины будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение r=0 перед чтением из стека служит признаком того, что стек пуст, а значение i=n перед записью в стек – признаком того, что стек переполнен.

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