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

var к: integer;

remaining, session; selection;

timetable; array[l., N\ olselection; к := 0; remaining := [1.. iV];

>.viYiiAe remaining ?t [ ] do (1-29)

begm. session := следующая выборка; remaining :- remaining - session; к := k+l; timetable] :== session

Как определяется следующая выборка ? Вначале берется любой из множества оставщихся предметов. Затем из этого множества выбираются все такие предметы, которые не конфликтуют с выбранными ранее. Назовем множество таких предметов trialset. Затем будем исследовать каждый элемент множества trialset. Включение такого элемента в session зависит от того, пусто или нет пересечение множества предметов, уже включенных в session, с множеством предметов, конфликтующих с данным. Оператор session: = := следующая выборка принимает вид var s,t: course;

trialset; selection; begin s := 1;

while -\(s in remaining) do s := s-\-l; session [s]; trialset := remaining - conflict[s]l for r := 1 to JV do (1.30)

if t in trialset then

begin if conflict[t] * session = [ ] then session :- session + [t]

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

1.10. представление массивов, записей и множеств

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

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

var store: array [address] of word (1-31)

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

1.10.1. Представление массивов

Представление массива - это отобра}кеиие (абстракт ного) массива компонент типа Т в память, которая представляет собой массив компонент типа word.

Массив следует отображать таким способом, чтобы можно было максимально просто и потому эффективно вычислять адреса его компонент. Адрес, или индекс памяти, i j-Pi компоненты массива вычисляется с помощью линейной функции отображения

/ = £о+/*5 (1.32)

где io-адрес первой компоненты, а s - число слов, которые занимает компонента. Так как по определению слово есть минимальная доступная единица памяти, то, по-видимому, желательно, чтобы s было целым числом; в простейшем случае s= sl. Если s - не целое число слов памяти (а так бывает довольно часто), то s обычно округляется до