Список литературы

1. Айгнер М. Комбинаторная теория. – М.: Мир, 1982. – 556 с.

2. Ахо Х., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977. – 368 с.

4. Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.

6. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики: Пер. с укр. - М.: Наука. Гл. ред. физ.-мат. лит.,1977.-80 с.

7. Компьютер и задачи выбора / Автор предисл. Журавлев Ю.И.-М.: Наука, 1989.-208 с. -(теория "Кибернетика - неограниченные возможности и возможные ограничения").

8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - 2-е изд., перераб. и доп. - М.: Энергоатомиздат, 1988. -480с.

9. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975. – 240 с.

10. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич.- М.: Наука. Гл. ред. физ.-мат. лит., I990.-384 с.

11. Муромцев В.В. Методы синтеза логических схем: Учебное пособие. Белгород: Изд-во БелГТАСМ, 1994. – 78 с.

12. Прикладная теория цифровых автоматов/ К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский и др. – К.: Вища шк., 19897. – 375 с.

13. Рейнгольд Э., Нивергельт Ю., Дэо Н. Комбинаторные алгоритмы (теория и практка): Пер. с англ. - М.: мир, 1980.- 476 с.

14. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. – М.: Наука, 1980. – 400с.

15. Прнложение 1

Генерация случайных чисел

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

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

При a₀=10^-2 формула дает 9000 различных чисел. В таких случаях говорят, что период псевдослучайной последовательности t=9000.

В языке Turbo Pascal, как и во многих других языках программирования есть встроенный генератор случайных чисел. Для работы с ним имеется стандартная функция Random и процедура Randomize.

Функция Random.

Назначение. Возвращает случайное число.

Описание. Random (диапазон: word).

Тип результата. Совпадает с типом параметра.

Примечание. Если параметр "диапазон" не задан, то результатом будет вещественное число х в диапазоне 0х<1. Если задан параметр "диапазон", то он должен представлять собой выражение целого типа, а результатом будет случайное число длиной в слово в диапазоне 0х<n, где n - значение, заданное параметром "диапазон". Если параметр "диапазон" меньше или равен нулю, то возвращаемое значение будет равно нулю.

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

Процедура Randomize.

Назначение. Меняет базу генерации случайных чисел.

Примечание. Случайное значение базы генерации получается от системного таймера.

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

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

Randomize;

k:=1; Base[k]:=RandSeed;

for i:=1 to 50 do

begin

writeln(Random(100));

if i mod 10 = 0 then

begin Randomize; k:=k+1; Bese[k]:=RandSeed end

end;

k:=1; RandSeed:=Base[k];

for i:=1 to 50 do

begin

writein(Random(100));

if i mod 10 = 0 then

begin k:=k+1; RandSeed:=Beae[k] end

end;