множества должен быть конечным, но и его кардинальное число - достаточно небольшим.

На всех множествах определены следующие элементар. ные операции:

* пересечение множеств + объединение множеств - разность множеств in принадлежность множеству

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

г * s + t = {r *s)-\-t r - s*t = r - {s*t) r-s + t = {r-s) + t xins + t = xin(s + t)

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

1. Имеются следующие выходные лексемы: идентификатор, число, меньше-равно, больше-равно, присвоить -и лексемы, соответствующие отдельным символам, таким, как -f, -, - и т. д.

2. Лексема идентификатор выдается по прочтении последовательности букв и цифр, начинающейся с буквы.

3. Лексема число выдается по прочтении последовательности цифр.

4. Лексемы меньше-равно, больше-равно и присвоить выдаются по прочтении соответствующих пар символов <;=i

5. Пробелы и концы строк опускаются.

В нашем распоряжении имеется простая процедура read{x), которая читает очередной символ из входной после-

овательности и присваивает его переменной х. Полученная выходная лексема присваивается глобальной переменной qtjrri. Кроме того, имеются глобальные переменные id и пит, назначение которых будет видно из программы 1.2, а также ch, содержащая текущий символ входной последовательности. jVlaccHB лексем 5 задает отображение символов в лексемы, его индексы ограничены лищь теми символами, которые не являются ни цифрами, ни буквами. Как мы видим, использование множеств символов позволяет программировать сканер независимо от их упорядоченности.

Второй пример использования множеств - программа составления школьного расписания. Предположим, что каждый из М учеников выбирает для изучения какие-либо предметы из их общего числа Л'. Теперь нужно так построить расписание, чтобы можно было некоторые предметы читать одновременно и при этом не возникало бы конфликтов [1.1].

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

Прежде всего для того чтобы решить, какие предметы можно читать в одно и то же время, нужно проанализировать индивидуальные списки выбранных предметов, составленные учениками. Эти списки представляют собой перечисления предметов, которые нельзя читать одновременно. Поэтому вначале мы программируем процесс сокращения данных. Ученикам присваиваются номера от 1 до Ж, а предметам - от 1 до Л'.

type course = 1 .. N;

student = I . .М;

selection = set of course; УЯГ s: course;

i: student;

registration: aii:&y[student] o{selection;

conflict: array[course]cf selection; (128)

[Определение множества курсов, вступающих в конфликт, по спискам курсов, выбранных отдельными учащимися] for J := 1 to do confiict[s] := [ ]; fofi := 1 to M do

for 5 := \ to N uo

if s ok registration[i] then

confiict[s\ := conflict\s] -\- registration]}]

(Заметим, что из этого алгоритма следует s in conflict[s\.\

begin := identifier; к := 0; repeat ifk < maxk then

begin к := k+i; a[k] ch end ; readich)

until -i(cA in [A.. Z , 0.. 9J) end else if ch in [0.. 9] then

begin sym number; man := 0;

repeat num 10*num+ord{cK)-ordi0y,

read(ch) until -i(cA in [0.. 9]) end else if ch in [<, >] then begin cAl := ch; read(ch); . if ch then begin

if cAl = < then sym := teg else

if cAl = then sym geq else sym := becomes;

read{cli)

else sym :~ S[chl] end else begin {другие символы] sym := S[ch]; read(ch)

end [scanner]

Программа 1.2. Сканер.

таг сА: char; sym: symbol; пит: integer; id: record

к: 0..maxk;

a: array [1.. maxk] ot char end ; procedure scanner;

var chl: char; begin {пропуск пробелов} while ch ~ do read(ch); if cA in [A..Z] then ----with id do-