Вариант 1.

3. Составьте программу машины Тьюринга, печатающей число 0. В результате работы программы происходит следующее преобразование машинных слов:

01^x q₁1^y 0000 1^{x + y} 0 q₀10.

3. В -ичной системе счисления используетсяцифр. Сколько в ней натуральных чисел, записываемыхзнаками?

Вариант 2.

3. Составьте программу машины Тьюринга, стирающей данный массив единиц. В результате работы программы происходит следующее преобразование машинных слов:

01^x 0^y 1^{z - 1}q₁1 0 0 1^{x - 1} q₀10^{y + z +1}.

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

Вариант 3.

3. Составьте программу машины Тьюринга, уменьшающей данное число на единицу. В результате работы программы происходит следующее преобразование машинных слов:

01^x q₁1^y 0 0 1^{x + y - 2} q₀100.

4. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях окажется, что среди вынутых карт

а) хотя бы один туз; б) ровно один туз.

Вариант 4.

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

01^x q₁1 0 ^{y + 1} 1 ^z 0 1^{x + y} q₀10 1^z 0

(x, y 0, z > 0).

4. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях окажется, что среди вынутых карт

а) не менее двух тузов; б) ровно два туза.

Вариант 5.

3. Составьте программу машины Тьюринга, сдвигающей головку влево на следующий массив единиц. В результате работы программы происходит следующее преобразование машинных слов:

01^{x + 1} 0^y 1^zq₁1^w 0 0 1^x q₀10^y1^{z + w} 0.

4. Сколько существует чисел от 0 до 10ⁿ, в которые не входят две идущие друг за другом одинаковые цифры?

Вариант 6.

3. Составьте программу машины Тьюринга, печатающей число 1. В результате работы программы происходит следующее преобразование машинных слов:

01^x q₁1^y 0000 0 1^{x +y} 0 1q₀10.

4. Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты так, чтобы среди них были карты каждой масти?

Вариант 7.

3. Составьте программу машины Тьюринга, стирающей предыдущий массив единиц. В результате работы программы происходит следующее преобразование машинных слов:

01^x 0^y 1^z-1q₁1 0 0 ^{x + y} q₀0 1^z0.

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

а) пустых урн нет;

б) во второй урне ровно шаров.

Вариант 8.

3. Составьте программу машины Тьюринга, уменьшающей данное число на два. В результате работы программы происходит следующее преобразование машинных слов:

01^x q₁1 ^y 0 0 1^{x + y - 3} q₀1000.

4. Сколькими способами можно разместить белых,черных исиних шаров поразличным урнам?

Вариант 9.

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

01^x 0 ^{y + 1} 1^{z -1}q₁1 0 0 1^{x -1} q₀10 1^{y + z}0.

4. Одновременно подбрасывают три кубика, имеющих 6, 8 и 10 граней соответственно. Сколькими различными способами они могут упасть, если известно, что, по крайней мере, два кубика упали на цифру 1?

Вариант 10.

3. Составьте программу машины Тьюринга, сдвигающей головку вправо на следующий массив единиц. В результате работы программы происходит следующее преобразование машинных слов:

01^x q₁1^y0^w 1^{z+ 1} 0 0 1^{x + y} 0^w1^z q₀10.

4. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т.е. какое-то число очков встречалось на обеих костях)?

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

1. Сафьянова Е.Н. Дискретная математика: Методическое пособие. Конспект лекций, ч.1. – Томск: ТУСУР, 1999. – 84 с.

2. Сафьянова Е.Н. Дискретная математика: Методическое пособие. Конспект лекций, ч.2. – Томск: ТУСУР,2000. –78с.

3. Кориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.

4. Волков В.А. Элементы теории множеств и развитие понятия числа: Учебное пособие. – Ленинград: Изд-во Ленингр. ун-та, 1978. – 83 с.

5. Оре О. Теория графов. – М.: Наука, 1980. – 352 с.

6. Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.

7. Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.

8. Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.

9. Шевелев Ю.П. Высшая математика 6. Дискретная математика. Ч.2: Теория конечных автоматов. Комбинаторика. Теория графов (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1999. – 120 с.