Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Целочисленное деление без восстановления остатка

Алгоритм без восстановления остатка разработаем, опираясь на рассмотренный алгоритм с восстановлением остатка.

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

1. Восстановление остатка связано с выполнением операции

Ai+1:= Ai + Bi. (6.15)

 

2. Операции B:=R1(0· B) и D := R1(1· D) шага 4.5 алгоритма приводят к уменьшению значения делителя в 2 раза. То есть, на этом шаге

Bi+1:= Bi / 2 (6.16)

 

3. На следующем цикле вычисления очередной цифры частного новое значение остатка на шаге 4.1 алгоритма будет вычисляться следующим образом:

Ai+2:= Ai+1 - Bi+1. (6.17)

 

Подставим в (1.50) выражения из (1.48) и (1.49):

Ai+2:= Ai + Bi - Bi / 2. (6.18)

 

Получим:

Ai+2 = Ai + Bi / 2= Ai + Bi+1. (6.19)

 

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

Алгоритм 6.6. Целочисленноеделение без восстановления остатка со сдвигом делителя вправо.

Постановку задачи и обозначения примем как в алгоритме 6.5.

1. Подготовка переменных:

1.1. C:= 0 (- задание начального значения кода частного)

1.2. i:= 0 (- задание начального значения величины сдвига делителя)

1.3. p:= 1 (- подготовка условий для первого уменьшения делимого)

2. Начальный сдвиг кода делителя

2.1. Если bn-1 =0, топерейти к 2.2, иначеперейти к 3

2.2. Сдвиг кода делителя влево на 1 разряд с целью удаления из РС делителя незначащего нуля:

B := L1(B· 0); (- сдвиг кода делителя влево на 1 разряд)

i := i+1; (- код делителя сдвинут влево еще на один разряд)

2.3. Перейти к 2.1

3. D := nota(B)+1; (- формирование цифровой части от (-B)ДК)

4. Цикл формирования кода частного:

4.1. Если p = 0, то A:= A+B (- это увеличение остатка);

иначе A:= A+D (- это уменьшение остатка);

(При суммировании кодов в обоих случаях фиксируем значение переноса p из старшего разряда разрядной сетки)

4.2. C:= L1(C· p)

4.3. Сдвиг кодов B и D делителя вправо на 1 разряд:

B := R1(0· B); D := R1(1· D)

4.4. Если i = 0, топерейти к 5

4.5. i := i -1

4.6. Перейти к 4.1

5. Конец алгоритма (Код C задает искомый результат: A div B)


Задания на лабораторные работы

7.1. Лабораторная работа 1:
разработка имитационной модели компиляции
алгебраического выражения по алгоритму Дийкстра

Раздел курса: Формализация и алгоритмизация процессов обработки информации

Трудоемкость задачи – 8 часов.

Теоретические основы изложены в разделе 1 данного пособия, в мультимедийной обучающей системе [6] и в [1, 2].

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

Задание

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

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

Требования к организации интерфейса

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

В процессе преобразований отображать:

- исходное выражение в инфиксной форме в неизменном виде;

- исходное выражение в процессе удаления из него очередного символа переданного в стек или в выходную строку;

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

- содержимое стека.

Ограничения на сложность задачи

1. Длина исходной строки символов не превышает 80.

2. Используются 4 арифметические операции (+, -, *, /) и 4-5 функций, причем 2-3 из этих функций должны иметь ограниченную область определения.

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

4. Символ «-» используется только как символ бинарной операции вычитания.

5. Корректные выражения задаются по правилам языка Паскаль: каждая операция задается явно без использования правил умолчания.

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

Дополнительные требования

1. Исходное выражение может содержать синтаксические ошибки как в скобочной структуре, так и в порядке следования символов. Некоторые примеры возможных ошибок даны в таблице 7.1.

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

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

 

Таблица 7.1

Выражение Ошибка
…A +* d… подряд два символа операций
…A d… подряд две переменные
…A (… между переменной и скобкой отсутствует символ операции

Методика выполнения работы

1. Изучить теоретический материал, изложенный в разделе 1 данного пособия.

2. Разработать концептуальную модель проекта. На уровне концептуальной модели проектные решения должны носить общий характер. Например:

- принимать или не принимать во внимание отдельные рекомендации, изложенные в теоретическом разделе;

- позволять или не позволять пользователю вводить исходную строку с помощью клавиатуры;

- в какой форме указывать пользователю на содержимое и результат очередного шага преобразования;

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

- какие математические функции будут доступны пользователю и т.п.

3. Разработать интерфейсные средства программы, руководствуясь в качестве примера изображением экранной формы (рисунки 7.1 и 7.2). В рамках данной работы возможно использование интерфейса значительно более простого, чем показано в примере. Обязательное содержимое интерфейсных средств оговорено в сформулированном выше задании на лабораторную работу.

4. Разработать структуру проекта на уровне модулей.

5. Разработать обработчики событий и все вспомогательные подпрограммы.

Рисунок 7.1 –Главная экранная форма мультимедийного приложения

 

Примечания

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

2. Информация в стеке накапливается от его дна вверх.

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

4. Отображение каким-либо визуальным средством указателя стека в состоянии, указывающем на вершину стека, обязательно.

 

Рисунок 7.2 – Экранная форма мультимедийного
приложения для ввода исходного выражения

 

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

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

7. Спланировать вычислительные эксперименты для отладки программы и демонстрации преподавателю в процессе отчета по работе.

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

1. В чем особенности инфиксной, постфиксной и префиксной форм записи алгебраических выражений?

2. Каковы недостатки инфиксной формы записи алгебраических выражений?

3. Каковы достоинства постфиксной и префиксной форм записи алгебраических выражений?

4. Что обозначает термин «стек» ?

5. Что такое указатель стека?

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

7. Каково назначение стека в алгоритме Дийкстры?

8. Какой метод программирования положен в основу алгоритма Дийкстры?

9. Объяснить содержание указанного преподавателем шага алгоритма Дийкстры. Показать его реализацию в программе.

10. Заданное выражение представить в трех формах записи.

11. С какой целью выполняется кодирование имен функций и числовых констант?

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

13. Объяснить какие компоненты среды разработки (языка программирования) использованы для отображения интерфейсных средств.

 

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


7.2 Лабораторная работа 2:
разработка имитационной модели вычисления
значения алгебраического выражения,
представленного в постфиксной форме записи

Раздел курса: Формализация и алгоритмизация процессов обработки информации

Трудоемкость задачи – 4 часа.

Теоретические основы изложены в разделах 1 и 2 данного пособия и в мультимедийной обучающей системе [6].

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

Задание

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

Требования к организации интерфейса

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

На форме предусмотреть поля для задания числовых значений использованных переменных.

В процессе преобразований отображать:

- исходное выражение в постфиксной форме в неизменном виде;

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

- содержимое стека.

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

Ограничения на сложность задачи

1. Длина строки символов, задающей выражение, не превышает 80 символов.

2. Используются только 4 арифметические операции: +, -, *, / и 4-5 функций, причем 2-3 из этих функций должны иметь ограниченную область определения.

3. Считаем, что все возможные синтаксичес­кие ошибки в выражении выявлены на этапе получения постфиксной формы.

Дополнительные требования

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

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

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

Методика выполнения работы

1. Изучить теоретический материал, изложенный в разделе 2 данного пособия.

2. Разработать концептуальную модель проекта. На уровне концептуальной модели проектные решения должны иметь общий характер.

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

 

Рисунок 7.3 – Экранная форма мультимедийного приложения

 

4. Разработать структуру проекта на уровне модулей.

5. Разработать обработчики событий и все вспомогательные подпрограммы.

6. Учесть перечисленные ниже замечания.

 

При выполнении лабораторной работы необходимо учесть следующее.

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

2. Информация в стеке накапливается от его дна вверх.

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

- считывание данных из стека не разрушает информацию в нем: при считывании указатель стека перемещается в направлении дна стека и в ячейках выше указываемой остаются ранее записанные данные;

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

4. Учесть все замечания из предыдущей работы, относящиеся к стеку.

На все особые ситуации, не оговоренные в задании, программа может реагировать так, как пожелает автор.

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

1. В чем особенности инфиксной, постфиксной и префиксной форм записи алгебраических выражений?

2. Каковы недостатки инфиксной формы записи алгебраических выражений?

3. Каковы достоинства постфиксной и префиксной форм записи алгебраических выражений?

4. Что обозначает термин «стек»?

6. Каково назначение стека в алгоритме вычисления значения выражения?

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

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

9. Объяснить содержание указанного преподавателем шага алгоритма вычисления. Показать его реализацию в программе.

10. Какова роль скобок в постфиксной форме записи выражения?

 

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

7.3. Лабораторная работа 3:
разработка и исследование генераторов
псевдослучайных числовых последовательностей

Раздел курса: Построение моделирующих алгоритмов. Статистическое моделирование на ЭВМ

Трудоемкость задачи – 4 часа.

Теоретические основы изложены в разделах 3 и 4 данного пособия и в [5].

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

Задание

Разработать среду для исследования генератора Random псевдослучайных числовых последовательностей, встроенного в Pascal, и разработать собственный генератор, реализующий метод Лемера. Провести исследования генераторов средствами разработанной среды. Реализовать статистический метод приближенного вычисления числа p.

Методика выполнения

1. Изучить теоретический материал, изложенный в разделах 3 и 4 данного пособия.

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

3. Разработать интерфейсные средства программы (рисунок 7.4).

4. Сгенерировать заданное количество n (100 <= n <= 10000 и задается после запуска программы в виде содержимого поля ввода) псевдослучайных целых чисел диапазона [0; 99].

 

Рисунок 7.4 – Пример экранной формы

 

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

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

6.1. Для функции f(X), задающей относительные (приведенные) частоты появления конкретных значений случайной величины. Эта функция представляет собой дискретный аналог плотности вероятностей (дифференциальной функции распределения);

6.2. Для интегральной функции распределения F(X);

7. Каждая гистограмма должна состоять из 100 «ступенек», т.е. по одной ступеньки на каждое возможное значение случайной величины. Вертикальные элементы ступенек должны быть прорисованы для соединения ступенек в одно целое. Но при этом следует понимать, что эти вертикальные элементы к гистограммам, строго говоря, не относятся.

8. Должна иметься возможность представления на экране в двух системах координат (СК) (одна СК для f(X), другая - для F(X)) одновременно двух семейств гистограмм, соответствующих числовым последовательностям разной длины. Варианты (до 6 вариантов) длин числовых последовательностей задаются пользователем, например, в командной строке, в текстовом файле или в диалоговом режиме. Разные гистограммы должны рисоваться разным цветом с отображением соответствующим цветом информации о длине последовательности. Следующий вариант гистограммы формируется после нажатия какой-либо клавиши или кнопки мыши и изображения очередных гистограмм накладываются на предыдущие варианты.

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

10. Отобразить на форме значение числа p, вычисленное статистическим методом. При этом использовать количество пар координат точек либо то же, по которому строились гистограммы, либо использовать индивидуальное значение (по выбору автора программы).

11. Для простоты реализации рекомендуется отображать гистограммы с помощью компоненты TChart.

12. Спланировать вычислительные эксперименты для отладки программы и демонстрации преподавателю в процессе отчета по работе.

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

1. Объяснить понятия: непрерывная и дискретная случайные величины; кривая распределения; функция распределения; функция плотности вероятностей; математическое ожидание; дисперсия; среднеквадратичное отклонение.

2. Объяснить технический и геометрический смысл понятий математического ожидания и дисперсии.

3. Написать формулы математического ожидания и дисперсии для равномерно распределенной случайной величины.

4. Как вычисляется вероятность попадания случайной величины на заданный отрезок по функции распределения и по функции плотности вероятностей?

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

6. Как зависят статистические значения математического ожидания, дисперсии, функции распределения и функции плотности вероятности от объема выборки?

7. Доказать разумность вычисленных программой статистических характеристик и построенных гистограмм.

8. Показать в программе и объяснить по тексту программы указанный шаг решения задачи.

9. Дать объяснения по указанному фрагменту программы.

10. Объяснить общий подход к построению генераторов псевдослучайных последовательностей.

11. Что такое «цикл последовательности» и чем объясняется его существование? Каковы требования к длине цикла последовательности?

12. Объяснить метод Лемера. Показать по тексту программы его реализацию.

 

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

7.4. Лабораторная работа 4:
разработка имитационной модели простейшей СМО

Раздел курса: Построение моделирующих алгоритмов. Статистическое моделирование на ЭВМ

Трудоемкость задачи – 8 часов.

Теоретические основы изложены в разделах 3 и 5 данного пособия.

Цель работы: закрепление теоретических положений темы и получение навыков разработки и исследования имитационных моделей систем массового обслуживания.

Задание

Разработать имитационную модель простейшей разомкнутой СМО с одним прибором обслуживания и одним потоком заявок.

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

Собираемая статистика определена по вариантам в таблице 7.2.

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

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

 

Таблица 7.2

Варианты заданий по бригадам

Параметры СМО Номера учебных бригад
1. Законы распределения:  
1.1. Интервалов прибытия:
- равномерный; ´   ´   ´   ´   ´  
- экспоненциальный.   ´   ´   ´   ´   ´
1.2. Времен обслуживания заявок:  
- равномерный; ´ ´     ´ ´     ´ ´
- экспоненциальный.     ´ ´     ´ ´    
2. Дисциплины обслуживания очереди:  
2.1 FIFO – для заявок низкого приоритета и LIFO – для заявок высокого приоритета. ´     ´ ´     ´ ´  
2.2 LIFO – для заявок низкого приоритета и FIFO – для заявок высокого приоритета.   ´ ´     ´ ´     ´
3. Статистика относительно очереди:  
- текущая длина очереди; ´ ´ ´ ´ ´ ´ ´ ´ ´ ´
- максимальная длина очереди;   ´ ´ ´       ´ ´
- средняя длина очереди; ´ ´ ´ ´ ´ ´ ´ ´ ´ ´
- среднее время ожидания в очереди; ´ ´ ´ ´ ´ ´ ´ ´ ´ ´
- максимальное время ожидания в очереди. ´ ´       ´ ´ ´    
4. Статистика относительно прибора обслуживания:  
- минимальное время обслуживания заявки; ´ ´     ´ ´ ´      
- среднее время обслуживания заявки; ´ ´ ´ ´ ´ ´ ´ ´ ´ ´
- максимальное время обслуживания заявки;     ´ ´       ´ ´ ´
- время простоя прибора;   ´ ´ ´       ´ ´  
- нагрузка прибора. ´     ´ ´ ´     ´

Методика выполнения

1. Изучить теоретический материал, изложенный в разделах 3 и 5 данного пособия.

2. Разработать концептуальную модель проекта.

3. Разработать интерфейсные средства программы (рисунок 7.5).

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

 

Рисунок 7.5 – Пример экранной формы

 

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

6. Разработать структуру данных для описания отдельной заявки и контроля процесса ее продвижения по СМО.

7. Разработать структуру данных для сбора статистики.

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

9. Разработать, отладить и оттестировать программу.

10. Спланировать вычислительные эксперименты, которые будут демонстрироваться преподавателю в процессе отчета по работе.

11. Подготовиться к ответам на контрольные вопросы.

 

Замечания к содержанию рисунка 7.5.

1. Обычно очередь и прибор обслуживания изображают так, что заявки продвигаются не справа налево как на рисунке, а наоборот: слева направо.

2. Экранная форма взята в том виде как ее разработал студент. Грамматическая ошибка в слове «Колличество» в поле «Статистика» не должна быть предметом для подражания.

3. Название поля входных данных «Длина очереди» передает логический смысл этого поля не совсем точно. Имеется в виду максимально допустимая длина очереди. Названия элементов интерфейса должны быть максимально адекватными логическому содержанию этих элементов.

 

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

1. Что понимается под СМО?

2. Дать формулировки понятиям: событие, поток событий.

3. Объяснить понятия: непрерывная и дискретная случайные величины; кривая распределения; функция распределения; функция плотности вероятностей; математическое ожидание; дисперсия; среднеквадратичное отклонение.

4. Объяснить технический и геометрический смысл понятий математического ожидания и дисперсии.

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

6. Как можно получить генератор псевдослучайных величин с экспоненциальным законом распределения?

7. Как можно получить генератор псевдослучайных величин с нормальным законом распределения?

8. Как вычисляется средняя длина очереди?

9. Что такое дисциплина обслуживания очереди? Дать характеристики видов дисциплин обслуживания.

10. Привести примеры типов СМО.

11. Привести примеры моделей протоков событий.

12. Что описывает Пуассоновский закон распределения?

13. Что означает понятие «простейший поток» ?

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

 

Преподаватель может задать и другие вопросы.

7.5. Лабораторная работа 5:
разработка среды для имитационного моделирования
микропрограммы выполнения арифметической операции

Раздел курса: Математическое и компьютерное моделирование

Трудоемкость задачи – 8 часов.

Теоретические основы подробно изложены в [7, 8] и в разделе 6 данного пособия.

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

Задание

1. Разработать алгоритм и микропрограмму выполнения арифметической операции над целыми числами со знаком, представленными на разрядной сетке длиной 1 байт. В случае микропрограммы деления вычислять целую часть частного. То есть, вычислять частное вида A div B. Разработать среду для имитационного моделирования исполнения микропрограммы.

2. Тип арифметической операции и базовые признаки алгоритма ее выполнения студенты берут из варианта микропрограммы одного из членов учебной бригады, выданной в качестве исходных данных для курсовой работы по курсу «Моделирование».

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

4. Состояния кодов должны отображаться на форме по мере их изменения.

5. Должны быть предусмотрены два режима выполнения микропрограммы:

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

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

Методика выполнения

1. Изучить теоретический материал, изложенный в разделе 6 данного пособия. Более подробное изложение соответствующих вопросов можно найти в [7, 8]. При изучении теоретического материала можно ограничиться кругом вопросов, связанных с выбранным вариантом арифметической операции.

2. В результате внимательного изучения выбранного варианта микропрограммы выявить основные признаки реализованного в микропрограмме алгоритма. Например, на рисунке 7.6 в виде ГСА показана микропрограмма выполнения операции деления. Перечислим основные признаки этой микропрограммы, которые необходимо перенести в разрабатываемую микропрограмму, и отметим признаки, которые не следует переносить в новую микропрограмму.

2.1. Это микропрограмма деления, вычисляющая частное C:= A / B.

В рамках этой лабораторной работы необходимо реализовать вычисления вида: C:= A div B.

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

2.3. В микропрограмме предусмотрен ускоренный вариант получения частного в случае, когда делимое равно 0.

2.4. В микропрограмме операнды предполагаются представленными в прямых кодах.

2.5. В микропрограмме количество повторений цикла на 1 больше количества вычисляемых разрядов частного. В рамках исходных данных этой лабораторной работы вычисляется частное C в виде C:= A div B. Поэтому в микропрограмме количество повторений ее циклической части должно определяться количеством значащих разрядов частного.

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

2.7. В микропрограмме реализован алгоритм деления с восстановлением остатка. Но восстановление остатка выполняется не за счет микрооперации вида A:= A + B («Остаток»:= «Остаток» + «Делитель»), а за

 

Рисунок 7.6 – Пример микропрограммы
выполнения арифметической операции

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

2.8. В микропрограмме использован алгоритм деления со сдвигом кода остатка влево.

3. На основан

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...