ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5051
Скачиваний: 25
96
Вариант 5
1.
Составьте программу машины Тьюринга, сдвигающей головку
влево на следующий массив единиц. В результате работы про-
граммы происходит следующее преобразование машинных
слов:
01
x + 1
0
y
1
z
q
1
1
w
0 Î 0 1
x
q
0
10
y
1
z + w
0.
2.
Сколько существует чисел от 0 до 10
n
, в которые не входят две
идущие друг за другом одинаковые цифры?
Вариант 6
1.
Составьте программу машины Тьюринга, печатающей число 1.
В результате работы программы происходит следующее преоб-
разование машинных слов:
01
x
q
1
1
y
0000 Î 0 1
x +y
0 1q
0
10.
2.
Сколькими способами можно выбрать 6 карт из колоды, содер-
жащей 52 карты так, чтобы среди них были карты каждой мас-
ти?
Вариант 7
1.
Составьте программу машины Тьюринга, стирающей предыду-
щий массив единиц. В результате работы программы происхо-
дит следующее преобразование машинных слов:
01
x
0
y
1
z-1
q
1
1 0 Î 0
x + y
q
0
0 1
z
0.
2.
Сколькими способами можно разместить
n
одинаковых шаров
по
m
различным урнам при условиях:
а) пустых урн нет;
б) во второй урне ровно
k
шаров.
Вариант 8
1.
Составьте программу машины Тьюринга, уменьшающей данное
число на два. В результате работы программы происходит сле-
дующее преобразование машинных слов:
01
x
q
1
1
y
0 Î 0 1
x + y - 3
q
0
1000.
2.
Сколькими способами можно разместить
1
n
белых,
2
n
черных
и
3
n
синих шаров по
m
различным урнам?
97
Вариант 9
1.
Составьте программу машины Тьюринга, заполняющей едини-
цами промежуток до следующего слева массива единиц (за ис-
ключением одного нуля). В результате работы программы про-
исходит следующее преобразование машинных слов:
01
x
0
y + 1
1
z -1
q
1
1 0 Î 0 1
x -1
q
0
10 1
y + z
0.
2.
Одновременно подбрасывают три кубика, имеющих 6, 8 и 10
граней соответственно. Сколькими различными способами они
могут упасть, если известно, что, по крайней мере, два кубика
упали на цифру 1?
Вариант 10
1.
Составьте программу машины Тьюринга, сдвигающей головку
вправо на следующий массив единиц. В результате работы про-
граммы происходит следующее преобразование машинных
слов:
01
x
q
1
1
y
0
w
1
z
+ 1
0 Î 0 1
x + y
0
w
1
z
q
0
10.
2.
Сколькими способами из 28 костей домино можно выбрать две
кости так, чтобы их можно было приложить друг к другу (т.е.
какое-то число очков встречалось на обеих костях)?
98
СПИСОК
ЛИТЕРАТУРЫ
1.
Виленкин Н.Я. Популярная коибинаторика. – М. Наука, 1975. –
328 с.
2.
Горбатов В.А. Основы дискретной математики. – М.: Высш.
школа, 1986. – 312 с.
3.
Кориков А.М., Сафьянова Е.Н. Основы системного анализа и
теории систем: Учебное пособие. – Томск: изд-во Том. ун-та,
1989. – 207 с.
4.
Мальцев А.И. Алгоритмы и рекурсивные функции. 2-е изд. – М.:
Наука, 1986. – 368 с.
5.
Основы кибернетики. Математические основы кибернетики /
Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.
6.
Риордан Дж. Введение в комбинаторный анализ. – М. ИЛ, 1963.
– 288 с.
7.
Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд-во
МГУ, 1985. – 312 с.
8.
Шевелев Ю.П. Высшая математика 5. Дискретная математика.
Ч.1: Теория множеств. Булева алгебра (для автоматизированной
технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т
систем управления и радиоэлектроники, 1998. – 114 с.
9.
Шевелев Ю.П. Высшая математика 6. Дискретная математика.
Ч.2: Теория конечных автоматов. Комбинаторика. Теория графов
(для автоматизированной технологии обучения): Учебное посо-
бие. – Томск: Том. гос. ун-т систем управления и радиоэлектро-
ники, 1999. – 120 с.