3. Порядок выполнения работы

1. Получить вариант задания у преподавателя.

2. Разработать программу.

3. Продемонстрировать выполнение программы преподавателю.

4. Оформить и защитить отчет.

4. Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

• задание по лабораторной работе;

• листинг программы;

• выводы по проделанной работе.

5. Варианты заданий

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

2. Аналогично заданию 1, но задания, поступающие в систему имеют приоритет. В этом случае задания в очереди ожидания должны упорядочиваться в соответствии с имеющимися приоритетами заданий.

3. Имитация буфера клавиатуры. Управляющие символы могут поступают от программ (программно-формируемый поток символов).

4. Имитация буфера клавиатуры. Управляющие символы читаются из файла.

6. Контрольные вопросы.

1. Что такое очередь?

   1. Какие еще структуры данных Вам известны?

   2. Как реализовать кольцевую структуру хранения?

   3. Для чего может быть использована очередь?

Лабораторная работа №3 Аналитические преобразования полиномов от нескольких переменных

1. Цель работы

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

2. Теоретические сведения

Выбор структуры хранения полинома

При выполнении работы можно использовать следующее понимание полинома. Полином состоит из мономов. Каждый моном характеризуется коэффициентом Coef и степенями переменных A, B, C: Coef*xAyBzC. Величину степеней переменных можно ограничить значением 9. При таком предположении максимально возможное количество мономов в полиноме - 1000. Полином разрежен, если по сравнению с максимально возможным количеством мономов он имеет относительно небольшое количество отличных от нуля коэффициентов. Например, у полинома P(x,y,z)=x⁷y²z+3x²z-6y²-3z⁹ отличных от нуля коэффициентов всего 4.

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

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

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

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

Таким образом, с учетом вышеизложенного, рекомендуется следующая структура хранения полиномов. Полиномы упорядочиваются по убыванию степеней мономов. Для определения старшинства мономов вводится следующее правило. Во-первых, фиксируется старшинство переменных. Пусть x - самая старшая переменная, затем следует y, затем z. Для каждого монома следует определить его "свернутую степень" (индекс). Для монома xAyBzC. индекс равен A*102+B*101+C*100 (по условию задачи A, B и C не выше 9). Старшим считается моном с большей свернутой степенью. Например, x³y старше xy⁷z⁶, так как 310 больше 176.

Структура хранения нулевого полинома

Полином представляется кольцевым списком. Каждое звено списка соответствует моному с ненулевым коэффициентом. Звено состоит из трех полей и включает поле для хранения коэффициента, поле для хранения свернутой степени и поле для хранения указателя на звено следующего по порядку монома. Следующим после последнего звена является первое звено списка. Первым звеном списка является так называемое "головное " звено (голова списка), поле свернутой степени которого равно -1. Нулевой полином представляется только головой списка.

Структуры хранения полиномов P(x,y,z), Q(x,y,z) и их суммы показаны на рисунке.

Примеры структур хранения полиномов